0

What are the fastest possible iteration techniques in C# for the following scenario ?

Since im working on a small archetype based ECS in c#, i want to make use of cache efficient iterations for maximum performance. What could i do to make the iteration faster and get the maximum cache hits ?

       var chunks = archetype.Chunks; // Property that returns a Chunk[] array
        for (var chunkIndex = 0; chunkIndex < archetype.Size; chunkIndex++) {

            ref var chunk = ref chunks[chunkIndex];
            var transforms = chunk.GetArray<Transform>();  // Returns a Transform[] array
            var rotations = chunk.GetArray<Rotation>();    // Returns a Rotation[] array

            for (var index = 0; index < chunk.Capacity; index++) {

                ref var transform = ref transforms[index];
                ref var rotation = ref rotations[index];

                transform.x++;
                rotation.w++;
            }
        }

Details...


  public struct Transform{ float x; float y; }
  public struct Rotation{ float x; float y; float z; float w; }

  T[] (chunk).GetArray<T>(){
     return fittingTightlyPackedManagedArrayForT as T[]; // Pseudocode
  }

  int (chunk).Capcity{ get; set; }  // Just a property of how big each array is in the chunk, all having the same size

I already tested a unsafe variant to reduce the bound checks, however this increased the cache misses according to my benchmark and was only slightly faster ( not noticeable, not even for high amounts ).

What elese could i do to increase the iteration speed ? Glad for any feedback, techniques and tricks ! :)

18
  • 3
    Haunting for nanoseconds? Honestly? Usually I'd suggest to think about those micro-optimizations when you have a real performance-problem in the above code. Do you? Did you profile your application to verifiy this code is causing your bottleneck? Commented Oct 19, 2022 at 10:39
  • 4
    @MakePeaceGreatAgain given that OP benchmarked and measured cache misses, why do you assume they didn't profile? Commented Oct 19, 2022 at 10:41
  • 1
    @GoodNightNerdPride fair enough, however not all benchmark-tests represent real-word scenarios. Of course I can show that I can make my function 10x faster by calling the code 1Mio times and measure. However that still does not mean it is neccessary, if the app just performs 10 calls instead of 1Mio. ones. Commented Oct 19, 2022 at 10:43
  • 1
    AFAIK in order to avoid cache misses one could place the data to iterate over into a continuous block in memory. For instance you could store all Transforms and Rotations as two huge blocks of memory and then iterate over all of them at once instead of iterating them per chunk. Commented Oct 19, 2022 at 10:46
  • 1
    Well that complicates things. I had no idea what an ECS is, so I googled and found this. Looks exactly like what you could try (but its C++). Commented Oct 19, 2022 at 11:31

1 Answer 1

1

A plain loop over an array or list is as fast as you can do iteration in c#, at least unless you have some special knowledge not available to the compiler. The compiler should recognize that you are looping over an array, and skip the bounds-check. And doing an linear iteration should allow the CPU to prefetch data before it is actually needed.

In your example I would not be certain the compiler could remove the bounds-checks, since the loop check is not against for the array length. So I would at least try changing it to two separate loops over the array instead.

I'm not sure why the unsafe version had lower cache hit rate, the cache is controlled by the CPU, not the compiler, and I would expect an unsafe version to produce very similar code to the compiler, at least with regards to memory access.

In some special cases it might be useful to manually unroll loops, but the compiler should be able to do this automatically, and this question suggest it is of little use. But compiler optimizations can be fickle, it might not always apply optimizations you expect it would, and what optimizations it applies might be different between versions, how long it is run, if you apply profile guided optimizations etc.

To get any real gains I would look at SIMD techniques, if you can process larger chunks of data you might get some very significant gains. But the gains might depend in large part on how the data is stored and accessed.

In some cases there can be major gains by using a structure of arrays (SoA) approach rather than the more common arrays of structures (AoS). In your example, if all the x and w values where stored in separate arrays you could just process the entire array in 128/256/512 bit SIMD blocks, and that would be fairly difficult to beat. This also has great cache efficiency, since you are not loading any unnecessary bytes. But using the SoA approach might have performance implications for other parts of the code.

2
  • One quick question than... C++ and rust loop iterations similar to my c# code above are faster. I replicated this... why is this ? Is the JIT not that optimized yet ?
    – genaray
    Commented Oct 19, 2022 at 16:05
  • @genaray Any offline compiler has the freedom to spend however much time it wants on optimization, a JIT however needs to be real time. For a simple iteration over an array I would expect similar times, at least without auto vectorization. But I do not think your example falls into the 'simple' category, there is to much going on that could foil the c# optimizer. But they have introduced tiered compilation in c#, so that could allow the compiler to spend more time where it is needed. Assuming it is actually the iteration that takes time, and not some reflection that is not shown.
    – JonasH
    Commented Oct 20, 2022 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.