Theraot.Collections.ThreadSafe.Mapper

Mapper<T>

This class is basically a spread array of capacity = 2^32, although the internal implementation is a "sexdecatree" (that is a n-tree where n = 16). This implementation is not optimized for retrival time, but for perallelism. To access an Mapper<T> object by multiple thread no locks are required as internally all operations are atomic, this is archived at the expense of memory space and retrival speed. The Mapper<T> is also able to recycle its breanches, making it play well with the garbage collector.

Testing showed that the Mapper<T> doesn't work well to implement queues and stacks having very bad performance, on the other hand it has virtually no penalty for multithreaded access. This makes it ideal for the implementation of hash tables and dictionaries which is how it is used in the library.

Prior research on how to implement concurrent lock-free dictionaries concluded with the development of cooperative data structures, in particular when the maximum capacity was reached multiple threads would collaborate to copy the contents to a langer copy... that implementation had the downfall of having no way for the structure to shrink*. On the other hand the sexdecatree allows for pruning the tree when a section is no longer in use and eliminated the extra delay of having to copy the contents, making it a better solution overall.

*: There was never a safe moment to shrink, and it was never certain that the shrink was going to be successful. Meaning that the only possible implementation would require to lock the whole structure and try to shrink when usage was low (but on what threshold?) and if it failed due to a collision, then it was in vain.

---

Mapper<T> doesn't behave like a ICollection<T> nor IList<T> which is why it doesn't implement those interfaces, albeit being very similar. The main gotchas are the lack of Add method and the fact tha Insert doesn't shift the indexes of the entries.

Instead, to add something it has to be inserted in the desired index (which can be any valid int, including negatives) and it will be retrieved from that same index regardless of whatever else is inserted.

If you wish to iterate over the Mapper<T>, it is better to use foreach than to access it by index. The reason is that each index access requires to traverse the tree on the other hand GetNumerator() can move up and down the tree as needed without using indexes.