# Data structure that is fast to read and modify

I'm working on an apllication that needs to process a lot of objects in realtime. I've separated the logic from the UI so that it isn't as much of a mess. The basic idea is that every tick I'm trying to populate a list of objects to process and once they are processed I update the UI accordingly.

I've written this collection class for use in the main processing loop. Here is the reasoning behind some of my decisions:

• The objects are processed sequentially in a loop. I only care for fast sequential reading so I've decided to use arrays at the base of it all hoping to get some kind of cache hit benefit.

• The maximum amount of objects is known at compile time so I've tried to avoid rapid heap allocations by pooling my data objects. I allocate a maximum amount but only use the amount that is active.

• I needed a way to correlate the logical objects with the presentation layer, so I've decided to use identifiers. These identifiers allow me to know what actual UI object the data belongs to.

Through basic stopwatch benchmarking I've arrived to the following solution:

class FixedCapCollectionIntGuids<T> where T : struct
{
public T[] m_array;
Dictionary<int, int> m_guidToIDs;
int[] m_idToGuids;
int m_capacity;

public int Size { get; private set; }

public FixedCapCollectionIntGuids(int capacity)
{
Size = 0;
m_capacity = capacity;
m_array = new T[capacity];
m_guidToIDs = new Dictionary<int, int>(capacity);
m_idToGuids = new int[capacity];
}

public T this[int key]
{
get
{
return m_array[key];
}
}

public void Add(T value, int guid)
{
Debug.Assert(!m_guidToIDs.ContainsKey(guid), "Double insertion");
m_array[Size] = value;
m_guidToIDs[guid] = Size;
m_idToGuids[Size] = guid;
++Size;
}

public void Remove(int guid)
{
int i = m_guidToIDs[guid];
int lasti = Size - 1;
int lastGuid = m_idToGuids[lasti];
m_array[i] = m_array[lasti];
m_guidToIDs.Remove(guid);
m_guidToIDs[lastGuid] = i;
m_idToGuids[i] = lastGuid;
--Size;
}
}


Please try to ignore the dumb naming, this is WIP so I didn't put much thought into what the best names for variables and classes are at this point.

My benchmarks show that this approach appears to be faster than just having a dictionary for reading(presumably because an array is cache friendlier), but slower for adding\removing(presumably because I'm maintaining 3 separate collections instead of one). I'm somewhat fine with this because addition and removal is going to be less frequent than iteration, but I'm still wondering whether I've solved the problem in a stupid way or not. Can it be done better?

• What do you need the dictionary and the other array for? You're not using them anywhere. All you are doing is assingn values to them but you never read them. Mar 15 '19 at 12:24
• Not quite. Look closer at the code of the Remove function. I get the index of the data array from the specified guid using the dictionary. Without the dictionary I can't identify where the object is in the array. The other array is the reverse of the dictionary - it lets me quickly identify which guid the object at index has. Otherwise I would need to iterate the values of the dictionary which I believe is slower. Mar 15 '19 at 12:37
• "My benchmarks show that this approach appears to be faster than just having a dictionary for reading" That would probably depend on what kind of data you're storing as well. How did you benchmark, or can you share a representative example of your input?
– Mast
Mar 19 '19 at 12:18

This looks like a good (i.e. not stupid) implementation if your main requirements is efficient sequential access to the data. Addition and removal will necessarily be slower than for a Dictionary because you are wrapping a dictionary, but the time complexity is of the other work is constant, so it isn't something I would worry about too much if your goal is fast read/modification.

## Encapsulation

Generally the encapsulation is fine, but there is one exception: m_array should not be publically settable. It should be readonly or a getter-only {get; } property. Being a reference type, I can't think of any downside to making it a property. Being publically settable means that anyone can change it to null or an array of the wrong size and break the data-structure, which is obviously bad. The other array and dictionary should also be readonly.

I do wonder why you provide an indexer as well as the array, but do not provide a setter for the indexer. The indexer will also create confusion by copying structs you want to mutate. You should probably look at whether you can hide m_array altogether, and do all the work via the indexer: this would produce a much tighter API if you can 'get away' with it. You may be interested to look into ArraySegment as a possible means of facilitating a somewhat tighter API if that indexer is deficient.

## Exception Handling

I don't know you use-case, but I'd reconsier using Debug.Assert for input sanitisation. It would seem much better would be to exploit the TryGetValue method of Dictionary'2 in Remove and TryAdd in Add to efficiency perform the check and throw under any runtime conditions.

Your exception messages could also be clearer. "NotFound": what is not found? If you throw an exception instead of asserting, you can throw an ArgumentException and make it completely clear what was not found and where the caller went wrong. "IllegalRead" means nothing at all. "Double Insertion" is pretty cryptic.

You could also do with checking that Size is less than Capacity when adding, as this should also throw an exception, rather than relying on the order of operations to throw with an IndexOutOfRange exception before doing any damanger (if m_guidToIDs[guid] was set first, this would linger despite the operation failing, so the code is extremely brittle).

A check in the constructor that capacity is non-negative would also be nice, just to cover as much of the API surface as possible with clear and useful exceptions (it will still fail if it tries to allocate a negative length array, but an ArgumentOutOfRangeException would be so much nicer.

## Typical C♯

The code is mostly nice-to-read C#, though there are some bits that could be nicer:

• The m_ member prefix is typical in C++, but much less so in C#. m_array should have a name consistent with being a public member: it should be in ProperCamelCase.

• Generally it is advised that the accessibility of any member of type is made explicit e.g. public class FixedCapCollectionIntGuids<T>, private int m_capactiy). This avoids any confusion (particularly when people are used to using different languagse with different defaults), and makes it completely clear that this is the intention and you didn't just forget to qualify the accessibility.

• The BCL uses Count rather than Size for everything: it's what people using C# will expect. I'd also argue it is clearer, because Size has can relate to size in memory. Conformity with the BCL also be sensible if you wanted to implement IReadOnlyList<T> (for which you would need to provide in addition an enumerator but nothing more), which could be useful.

• It's also typical to have key, value in the BCL add methods, so you might want to consider having the same in Add.

• Usually we use 4 spaces for indentation.

• While I think I see why you would except this to only be used with structs, I don't see why you need limit this general purpose data structor to only structs. If you don't have a reason, I would remove the generic constraint (it has no semantic/performance impact for when structs are used). The only change this would warrant would be clearing removed values (so that you don't hold references to objects that are not in the structure). This is just a suggestion, and 'that would increase the API surface and costs of maintance/testing' would be a good reason to not do this.
• public T this[int key] should have parameter guid for consistency.
• FixedCapCollectionIntGuids is an odd name; I will only say that shorting Cap to Capacity is not a good idea: it only obfuscates the meaning.
• For a 'tricky' API like this one (where it's very easy to mis-use m_array), you need to provide inline documentation (///) for all public parts of the API. This should detail the usage and assumptions, and explain things like "this is not thread safe at all", and that m_array may be larger than Size and you should not access anything beyond index Size - 1. I find that the act of writing documentation makes me aware of the edge cases I need to handle, makes it possible to maintain code without having to guess at the exact intention of a method/class, and gives consumers the information and confidence they need to use your APIs as intended.
• Remove is a bit untidy looking: I would try to break it up a bit with empty lines, to separate the bit where you remove the old values, move the 'last' value into the inner position, and finally resize the structure. There is also a bug in Remove: it will go wrong if you try to remove the last element: writing the code to detect this should automatically force you to organise it so that my previous comment is addressed.