C # - fixed / inline arrays

Question

I am writing a B + -tree implementation in C #, and the tree implementation that I selected for my application has a very specific structure, which is cache-conscious. To achieve these properties, it has strict rules for placement on tree nodes.

I want to simply express using C # a fixed keyword for fixed-size buffers:

public abstract class Tree<K, T> { } sealed class Node<K, T> : Tree<K, T> { Node<K, T> right; fixed Tree<K, T> nodes[127]; // inline array of 128 nodes } 

Unfortunately, fixed-size buffers can only be used with primitive value types, such as int and float. Just using simple arrays, add pointers that destroy the properties associated with the cache of this tree type.

I also cannot generate 128 fields and use pointer arithmetic to retrieve the field that I want, because there are no conversions between pointer types and managed objects .

The only thing left is to generate 128 fields with an index that selects the correct one based on the switch (which cannot be fast), or write it as a C library and use P / Invoke, which also destroys performance.

Any suggestions?

Answer 1

Use C ++ / CLI. This gives you full control over the layout, just like C, but the cost of managed / unmanaged transitions is significantly reduced by p / invoke (probably no extra cost whatsoever).

Unfortunately, managed code is not very good for working with a cache: inside a managed heap, you are powerless to avoid a false exchange. C ++ / CLI allows you to use an unmanaged allocator, so you can not only keep data contiguous, but also align with cache lines.

---

Also note: using the class keyword creates a "reference type" that already adds the level of indirection that you wanted to avoid. With some reorganization, you can use a struct and an array and no longer have the indirectness of the code that you suggested.