Overall, I very much like the C# language, the .NET Framework, and the benefits of having my programs run in a virtual machine. But sometimes, all that gets in the way. I recently ran into an excellent example that illustrates how the execution environment can make things very difficult.
A skip list is a data structure that stores a sorted list of items, using a hierarchy of linked lists. The average search performance of a skip list is roughly the same as a balanced binary tree, but inserting and deleting items is significantly faster because the skip list doesn’t have to spend any time re-balancing the tree. The skip list has theoretical worst-case performance that is truly horrendous, but in practice it’s difficult to construct a severely non-optimal structure, and almost impossible to generate a worst-case arrangement of items. The original paper describing the skip list was written in 1990 by William Pugh. See Skip Lists: A Probabilistic Alternative to Balanced Trees.
Another use for a skip list is a priority queue. The research I’ve seen shows that a skip list based priority queue is significantly faster than a heap-based priority queue. Several of my programs make very heavy use of priority queues, and they could benefit from a more efficient implementation. More importantly, a concurrent skip list priority queue is much more efficient than a concurrent heap-based priority queue. See Skiplist-Based Concurrent Priority Queues.
In ease of implementation, a skiplist is approximately equal to a heap. Both are very simple data structures that require only about 150 lines of C# for everything. The skiplist is slightly more complex because it requires that each item contain an array of link pointers to nodes further in the list. By contrast, I can implement a heap in an array and not require any node pointers.
It’s the implementation of the node structure that causes a problem in C# (.NET in general, I would think). Let me explain why.
If you read the skip list paper, you’ll understand that it implies a node structure similar to this:
class SkiplistNode
{
T Value;
SkiplistNode[] Forward;
}
That is, the node contains a reference to the value and also an array of references to following nodes. The array is of variable size, depending on the node’s level in the hierarchy. (It really is helpful if you read the skip list paper.)
In a perfectly balanced skip list, one half of the nodes will be at level 1, and will need only one Forward pointer. Of the other half, one half of them will be at level 2 and will need only two Forward pointers. In a skip list of a million items, there will be one node at level 20, two nodes at level 19, four nodes at level 18, etc. This is all probabilistic, of course, so the actual number of nodes at each level will vary by a small amount, but it generally follows the power of 2 structure of a binary tree.
So what’s the problem? After all, it’s trivial to allocate an array with whatever number of elements you want. Here’s a simple constructor for the SkiplistNode class:
public SkiplistNode(T val, int level)
{
this.Value = val;
Forward = new SkiplistNode[level];
}
But how much memory does that node occupy? The Value will typically be a reference, which is 8 bytes in the 64 bit runtime. The Forward references require 8 bytes each, so the minimum size of the node will be 16 bytes. Okay so far.
In a skip list with N nodes, there will be approximately 2N forward references. So a skip list with a million nodes would require about 16 megabytes for forward references and another 8 megabytes for the Value references, making up a total of about 24 megabytes. (Not counting the per-node allocation overhead, which I can eliminate by making these things value types.)
But that’s not the whole story. It turns out that allocating an array involves 56 bytes of overhead. All of a sudden, the average per-node size isn’t 24 bytes, but rather 80 bytes. My million-node list grows from 24 megabytes to 80 megabytes. I had hoped to build a skip list with 100 million nodes, but I don’t have 8 gigabytes for it.
If I were writing this in C or C++, I could create a variable sized structure, like this:
typedef struct tag_Node
{
void * Value;
tag_Node* Forward[1];
} SkiplistNode;
And, to allocate it, I’d write:
SkiplistNode* newNode = malloc(sizeof(SkiplistNode) + (level-1)*sizeof(SkiplistNode*));
That would allocate exactly the amount of space I need, with no array overhead at all. You can’t do that in C#. Or if you can, I certainly don’t know how it’s done.
The difference between the two is quite striking. Imagine that you’re allocating a node at level 3. The C code allocates memory as though the structure were laid out like this:
typedef struct tag_node
{
void * Value;
tag_node* Forward1;
tag_node* Forward2;
tag_node* Forward3;
} SkiplistNode;
That structure occupies 32 bytes: 8 bytes for the Value reference, and 8 bytes for each of the Forward references.
But in C#, an array is an object in its own right. There’s no way to allocate an array of references in-line. The C# code allocates memory as if the structure is defined like this (in C):
typedef struct tag_node
{
void * Value;
tag_node** Forward;
} SkiplistNode;
And the code that allocates it looks like this:
SkiplistNode* Node = malloc(sizeof SkiplistNode); Node.Forward = malloc((level-1) * sizeof(SkiplistNode*));
The Forward array is allocated separately on the heap. It’s the overhead of that allocation that costs 56 bytes in .NET. The C# structure occupies 8 bytes for the Value reference, 8 bytes for each of the three members of the Forward array, and 56 bytes of array allocation overhead (which includes the 8 bytes for the Forward reference itself).
I don’t know of a good solution here. I thought I could do it with fixed-sized buffers and some fancy inheritance, but there are several problems with that solution. First, fixed-sized buffers can only store primitive types (not references), and fixed-sized buffers may only be members of structs, not classes. I could try to simulate a fixed-sized buffer (using a base class that has one Forward reference, and derived classes that implement additional Forward references), but doing so would lead to some very ugly and difficult code.
Other solutions are possible, including explicit linked lists, managing my own heap of Forward reference arrays, and doing everything indirectly, with an array of references and a custom linked list that contains indexes into that array rather than the references themselves. But all of those solutions complicate the data structure and add additional overhead to the skip list algorithm, making it perform slower–perhaps slower than the heap that I want to replace. It’s frustrating.
Again, in the vast majority of cases I’m very happy working with C# in the managed .NET environment. But for some things, this skip list being an excellent example, I chafe at the handcuffs the runtime places on me. In this case, I’ll have to come up with an innovative way of getting around that per-node cost or just skip the skip list altogether.