4

I'm writing a B+-tree implementation in C#, and the tree implementation I chose for my application has a very specific structure which is cache-conscious. To achieve these properties, it has strict layout policies on tree nodes.

What I want is simply expressed using C#'s fixed keyword for fixed-sized 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-sized buffers can only be used with primitive value types, like int and float. Just using plain arrays would add pointer indirections which destroy the cache-friendly properties of this tree type.

I also can't generate 128 fields and use pointer arithmetic to extract the field I want because there are no conversions between pointer types and managed objects.

About the only thing left is generating 128 fields with an indexer that selects the right one based on a switch (which can't be fast), or writing it as a C library and using P/Invoke, which would also destroy the performance.

Any suggestions?

Improve this question
5
  • Why would C library destroy performance? Commented Oct 7, 2011 at 21:08
  • 2
    @Dani: It's not the C library, but p/invoke that is the concern, IIUC. Commented Oct 7, 2011 at 21:11
  • 1
    You will always have a pointer indirection unless you make Tree a struct. This does not imply that an array of objects is not cache-friendly. The friendly garbage collector ensures it is, it compacts the heap and puts every nicely together. Avoid premature optimization. The nodes member should almost certainly be a List<>. Commented Oct 7, 2011 at 21:18
  • Thanks for the correction Henk, post updated. Unfortunately there's other data in this tree structure that I excluded for the sake of brevity, but that was good idea. Hans, an array is cache-friendly, but a class pointing to an array is less so. I need the array embedded in the class, or a struct pointing to an array would also work. Commented Oct 7, 2011 at 21:34
  • @naasking: The 129th "element" Hans was talking about was right. You probably didn't want to reduce the size of the array, unless you want computations modulo 127 instead of bit-shifting. Commented Oct 7, 2011 at 22:13

1 Answer 1

Reset to default
3

Use C++/CLI. That gives you total control over layout, just like C, but the cost of managed/unmanaged transitions is much reduced from p/invoke (probably no extra cost at all).

Unfortunately managed code is not very good for "cache-conscious" work: inside the managed heap you are powerless to avoid false-sharing. C++/CLI lets you use the unmanaged allocator, so you can not only keep the data contiguous, but aligned to cache lines.

Also note: Using the class keyword creates a "reference type" which already adds that level of indirection you wanted to avoid. With some reorganization, you might be able to use a struct and an array and not have any more indirection that the code you proposed.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

I already tried just using structs with a managed array. Unfortunately, because there are more than 1 tree node type, the array must be polymorphic and thus a pointer type of some sort. I don't know much about C++/CLI, so I'll take a look. If it would allow me to specify a reference type with an inline array without marshalling overhead of P/Invoke, then I'm sold.
@naasking: C++/CLI isn't going to change the rules for managed types (well, you can try: see How do I specify a fixed-size buffer in C++/CLI? ) Mainly, it's going to get you to "C library with p/invoke" without needing the p/invoke part. "C++ interop" (codename "It Just Works") is both faster than p/invoke and understands C header files so you don't have to write p/invoke declarations.
Ultimately, you want to use unmanaged structures with explicit alignment if you care about cache behavior. In this case, that'll be a native C++ struct containing an array of pointers.
I was hopeful for a minute there, but that inline_array template has roughly the same restrictions as 'fixed', ie. T can only be a value type. Darn.
@naasking: You can make an array of pointers though, and use the gcroot template to store handles back to managed objects.
|

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.