I'm working on a graphics application and am trying to put together an implementation of a quadtree in C#. This is a very performance-sensitive data structure and I'm trying to bench and optimize it as best I can, but so far the results aren't very satisfying. I also have the special requirement that I need to be able to quickly deep-copy the data structure (to save snapshots).
I know that if I were working in C/C++ this would be easy — the structure would consist of a big pre-allocated buffer of structs and I would pass pointers around to read/write elements in the buffer. To clone the data structure I could just memcpy the buffer and be done. Having everything in one solid chunk would be good for the cache and minimize cache misses since generally if I want to access one node, I want to access a bunch of them.
C# doesn't seem to make this very easy. My biggest hurdle is that if I use a struct buffer in the same way as C/C++, I can't easily pass around and store pointers to the elements. I can use ref parameters, but not for local variables. Some of my functions deal with many nodes at a time and I don't want a bunch of functions with 6+ ref parameters. Without refs I have to copy the struct to the stack, edit it on the stack, and store it back to the array on the heap, which seems unnecessary.
If, on the other hand, I use an array of classes, I compromise performance in three ways. First, I have a lot of allocation and garbage collection whenever I add or remove elements (as opposed to a struct buffer I can just pre-allocate and forget about). Second, if I want to iterate or search I have to hunt down these classes scattered all over the heap and run into a lot of unnecessary cache misses. Third, this throws my quick deep-copy memcpy out of the window and makes deep cloning very slow.
Is there a better way I can handle something like this in C#? Is there a C# way to do this that's cache-friendly? I know there are pointers in unsafe contexts, but I also know there are a lot of limitations and things to worry about. If I do need to look into unsafe/fixed for this, is there anything I should read as a primer?
by Recatek via /r/csharp