USet and UMap

An implementation of a set and a map with unsigned integers as keys.

Premise

I believe in using the right tools for a job. There are cases where generic data structures together with traits implementations designed to work for any kind of element held inside, and any kind of usage, result in sub-optimal performance, and unclear code.

This project is an attempt to provide more suited alternatives for HashSet and HashMap when used in situations like video games or real scene simulations. I imagined a situation when the user has to handle a few hundreds or thousands (but not billions) of data structures describing objects in the scene. They can be created, modified, and deleted fairly quickly. Instead of references, they hold identifiers to data structures in other maps. The identifiers can be simple integers, so the data structure is of known size at any point in time. This allows the user to store all of them in one or many maps where unsigned integers work as keys, retrieve those keys as sets of unsigned integers, operate on them, and finally use them to access the data structures. A set of identifiers, USet, is pretty lightweight and can be cloned without much effort if moving the ownership is not possible. A map, UMap, may be hold in one place, accessible from many others, as a form of a primitive (ECS)https://en.wikipedia.org/wiki/Entity_component_system.

Implementation

Implementation is very simple: USet is built around a vector of booleans. It also has an offset, which helps with memory conservation, and redundant minimum and maximum values, which greatly speed up operations on the set. If the n-th element in the vector is true, from the API point of view it means that the set contains the value n - offset.

Accordingly, UMap<T> is built around a vector of elements of the type Option<T>. If the n-th element in the vector is Some(t), from the API point of view it means that the map contains the value t under the identifier n - offset.

All this means that USet and UMap trade memory for CPU. They are not very well suited for storing huge number of entries in the memory, but for smaller amounts the benchmarks show a 3.5-4.0x performance boost over a similar functionality.

Usage

Contrary to HashSet and HashMap, USet is not a subclass of UMap. The two closely cooperate, but their roles are a bit different. The idiomatic use of UMap is to populate it with elements and then use the query or keys methods to construct USets of identifiers fulfilling certain conditions. Then the USets can be passed around and operated on (the implemented methods are: put, remove, union, common set, difference, and xor), and then the UMap can be accessed again with the resulting USets, or individual identifiers, in order to read, modify, or delete data from it.

Planned improvements

This is an initial 0.1 version of the project, so of course there's still a lot to be done! :)

1. Minimize usage of cloning within the code. This mainly applies to UMap. For the 0.1 version I decided to appease the borrow checker with cloning the data structures where other solutions seemed not possible, but I'm learning all the time. I hope to optimize the code a bit.
2. Consider bitvec for the USet implementation insted of Vec<boolean>. If it affects the performance too much, I might decide to create another implementation of USet (UBitSet?) which trades a bit of CPU power for better memory usage.
3. Work on turning UMap into a full-fledged ECS. Again, it might mean that I will leave the actual UMap as it is, with only small changes, and instead I'll create another entity with more robust functionality which will closely interact with USet and UMap.