Try a MapSet implementation

[josevalim]

With Erlang 18 coming out, I am starting to believe that the fastest way to implement a Set would actually be by using a map behind the scenes. After all, a Set is a map where having a given key means the entry exists in the set.

So here is what I have in mind. We create a new MapSet struct, that implements the Set behaviour. MapSet will be defined as follows:

defstruct set: %{}

And all functions would work on top of this set but return a %MapSet{...} struct. Once implemented, we could benchmark and see how it fares against the current HashSet. Note Map is faster than a HashDict on all operations on Erlang 18 (here is some sample benchmarking) although we may be slower in sets due to the %MapSet{} struct indirection. We need the indirection however if we want it to work as a struct (and have protocols and what not).

[josevalim]

@lexmag interested in experimenting with this one?

[lexmag]

@josevalim sure, would love to try.

[ericmj]

We could consider cheating and have defstruct [] with values directly on the struct if there is a performance benefit.

[lexmag]

@ericmj in that case we have to deal with :__struct__ entry as with a special case.

[ericmj]

Yeah, may or may not be worth it.

[josevalim]

Yeah, i didn't figure out a way to handle :__struct__ that's why i didn't propose it. :(

[lexmag]

I've made initial implementation of MapSet lexmag@a26cd96 and run benchmarks for several functions https://gist.github.com/lexmag/32977ce8fd7cb44ddefa so far.

[josevalim]

If I read them correctly, the results are really, really good. Please do send a pull request. :)

[josevalim]

And before I forget, thank you for doing this! ❤️ 💚 💙 💛 💜

[lexmag]

My pleasure. Will send WIP PR soonish; the results are really good, but as you might see I've done the tests not for all the functions (only BIF-based), most interesting ones are left. 😄