1

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.

  • With regards to the Array, I didn't think that value types were necessarily boxed. See here. – J Trana Sep 19 '14 at 3:53
  • Question about usage: can the operations you need be done in batches or are they required to happen one-by-one? If batches are not a good option, then crossing the managed-unmanaged boundary may prove too heavy. – J Trana Sep 19 '14 at 3:55
  • @JTrana: Arrays of value types are not boxed, but arrays of objects that hold value types are. – david.pfx Sep 20 '14 at 23:57
  • @JTrana: Creation is batched, but most retrievals are not. Good point. – david.pfx Sep 20 '14 at 23:58
  • The more I read through this question, the more I'm thinking: "This is not .NET's sweet spot." Sounds like C++ is not in the works for this project though? The only other thing I can think of to even ask is if - and this is a big if - Mono is on the table as an option, would Mono.SIMD be applicable for the processing side of this application? If so, that might guide some of your data choices to align with calls there, etc. and also data access patterns. – J Trana Sep 21 '14 at 1:49
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.

  • That's a good answer, and the one I came up with (the day after asking the question). I plan to use object arrays first to get some working code, and then switch based on benchmarking. But see also edit. – david.pfx Sep 20 '14 at 23:57
  • 1
    I am a former C/C++ programmer, so I am familiar with the trade-offs. In this case, the main differences with C/C++: you cannot put value types and pointers (called references in C#) into the same vector (called List<T> in C#); you need a separate List<T> instance allocation for each value type stored (references could share the same List<object>). These should not have a huge impact on performance. It is possible to create unions of value types in C#, using structures and field offsets, but I see no advantage in this case. – Frank Hileman Sep 22 '14 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.