Strategy for storing mixed value and reference types without boxing

Question

I'm looking for a way to store a large quantity of individual data values, with the following constraints.

• Assume that the types are bool, int32, double, decimal, string and blob (byte array).
• The type of each value will not be known at compile time (but the set of possible types is).
• The type of each value will be known at run time, so it doesn't need to know its own type.
• There are lots of them -- think millions at least.
• Values are collected into rows/bags of (say) 1-100 values and accessed by index (from a dictionary as it happens).
• Values are created and destroyed sometimes, read often and updated rarely.

Strategies I have so far are just these:

• Array of object, but would require value types to be boxed and that's a load on the GC that I would prefer to avoid.
• Serialise to a byte stream. String and blob would require an embedded length. Cost to read/update is high.

In C++ this could be an array of union of scalar and pointer types, but that strategy is unavailable (or at least highly unsafe) in .NET. This is a place where I really don't need a GC (object destruction is deterministic), so calling out to unmanaged code is a possibility.

The question is whether I've missed any viable strategies in the .NET world. Suggestions/comments welcome.

---

For my particular application it appears that creation/deletion happens in batches (rows/bags/sets) and individual values are not added or deleted. Think serialise/deserialise rather than random access. There are also set operations, so value-compare-equals is a common operation and boxing is bad for that.

Answer 1

I would create a strongly typed array for each value type, and use each array as a pool of potential value holders. Another option, slightly slower, is to use a set of List where each List instance contains a different value types.

This is similar to the pooling strategy commonly used for memory allocation optimization. A List, or your own array, will have to expand sometimes. In this case, a new array must be allocated, and the old contents copied over to the new one.

Whether using List or an array, in both cases you avoid boxing entirely, and use memory as efficiently as possible in the CLR. The index for an element in your pool consists of: the type (to know which list or array to access) and the array or list index. The only other optimization I can think of is to consolidate types where possible: UInt32 and Int32 can share the same container, for example.

Beware boxing when writing the methods that store or retrieve values. You will need strongly typed arguments.

Variable sized objects, such as byte arrays, are most efficiently stored in a stream. However, to use the stored object as a byte array, you must allocate a new one, and copy part of the stream to the new array. It is more efficient to reuse previously allocated arrays.