An alternative/extension to the std collections

[makingthematrix]

Specifically, this issue

I need an easy way to perform operations on sets of integers. Ideally with the operators +, -, and *, and with the "move" semantics. It's important because I would like to expose this to game programmers, so they would be able to write GAI functions with it. If not, then maybe I can find a crate that would help me write this by myself.

Unfortunately crates.io just died, so no links right now.

[makingthematrix]

The im crate is interesting (https://crates.io/crates/im), but it's purpose is to bring a bit of Scala and Haskell to Rust. So I'm drawn to it because of how convenient to use it seems for me, but on the hand it seems too slow. Or maybe I'm just using it wrong. But they way I use it seems very natural, so if I need to make something very different to achieve better performance, I will rather stick with a more low-level approach.

In https://github.com/makingthematrix/rust-experiments I tested the performance of three Set implementations:

• std::collections::HashSet<usize>
• im::HashSet<usize>
• my own implementation, which I call USet I wrote an algorithm which generate trees of given size and breadth and return them as a vector where indices are the ids of the nodes and the values are the ids of the parent nodes. The vector may later be used to in another algorithm, solving the tree. In the algorithm the sets are used to hold the indices of nodes: one set for all indices, one for the aleady used ones, and one for not yet used. I create them from vectors of usize, then use substraction and element removal.
  I used Criterion to check the performance. For a tree of size 1000 the results are something like this:
  • std::collections::HashSet<usize> - 24ms
• im::HashSet<usize> - 1000ms
• USet - 0.7ms

So... yeah.

The USet implementation is not generic as the other two. It works only on usize and it uses a lot of memory. The assumption is that there will never be more than a couple thousands / tens of thousands ids to manipulate. So, USet focuses on small sets of integers with operations on them performed very often, but is not able to hold other types of data and will run in trouble if we try to use it to store ids in very large quantities.

Nevertheless, I think the assumption is ok, and I'm willing to use this implementation in my project. After all it's one of the most crucial elements in GAI.