USet and UMap
An implementation of a set and a map with unsigned integers as keys.
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
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 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.
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
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.
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
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.
This is an initial 0.1 version of the project, so of course there's still a lot to be done! :)
- 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.
USetimplementation insted of
Vec<boolean>. If it affects the performance too much, I might decide to create another implementation of
UBitSet?) which trades a bit of CPU power for better memory usage.
- Work on turning
UMapinto a full-fledged ECS. Again, it might mean that I will leave the actual
UMapas it is, with only small changes, and instead I'll create another entity with more robust functionality which will closely interact with