What to do with HashSet and HashMap?

[krauthaufen]

The system uses lots of datastructures like HashMap, HashSet, etc.

Since they need to be part of the public API we cannot make them internal.

My current approach is to leave HashMap, HashSet in the Incremental namespace and expose 'internal' things like CountingHashSet or History in the FSharp.Control.Traceable namespace.

That way users can explicity open and work with it, while still leaving the standard-API relatively clean.

Any suggestions?

[krauthaufen]

I think we should keep it that way for the moment being. Maybe some of the DataStructures like HashSet/HashMap could make their way into FSharp.Core or a new library (e.g. FSharp.Collections).

[dsyme]

We could split out HashMap and HashSet to FSharp.Collections.HashCollections. But no rush with that, can be done later.

[krauthaufen]

sadly no such thing as sealed interfaces in OOP 😁

[krauthaufen]

we could also implement AdaptiveSet/AdaptiveMap (without hashing) based on Set/Map respectively. Sadly Set and Map do not provide the needed functions currently (computDelta/applyDelta/choose2/alter). Is there any way to implement these things using the internals of Map/Set without moving them to FSharp.Core or copying the code?

[dsyme]

Is there any way to implement these things using the internals of Map/Set without moving them to FSharp.Core or copying the code?

I believe we should just move all this into FSharp.Core. The use cases are important and real.

Separately I think having F# implementations of HashSet and HashMap is excellent.

[krauthaufen]

Hey, would definetly be cool to have better Map/HashMap/etc. support...

[dsyme]

Hey, would definetly be cool to have better Map/HashMap/etc. support...

Have you read https://michael.steindorfer.name/publications/phd-thesis-efficient-immutable-collections.pdf? I'd be interested to know how these compare. We could discuss that sort of thing in a separate repo. My thought is that if we move HashSet/HashMap to a separate repo we can get the F# community focusing on them, including performance testing, and make really good improvements to them bit by bit.

Note that achieving performance with the techniques in this thesis tend to rely on some bit-counting intrinsics which I believe are now available in .NET Core (I haven't checked though)

[krauthaufen]

hey, never heard of this one (we always kept reading https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf) but I'll take a look when I have the time...

Yep, we could separate them from Adaptive, nonetheless keep them here until it's done and once it makes its way to FSharp.Core drop our adaptive-implementation...

[krauthaufen]

I started reading the dissertation but couldn't get my head around it yet... Our current IntMap implementation is clearly suboptimal since it's just not written with F# in mind. Most likely it allocates lambdas, etc. and should be rewritten from scratch. Nonetheless we should do some performance tests with it and see where we are. I'm currently focused on rewriting our DomainTypeCompiler that can turn immutable model-types into adaptive ones because the current implementation is pretty complicated and has several known bugs, but once I get this up and running I can start a repo for HashCollections.

[dsyme]

Asked twitter for state of the art here https://twitter.com/dsyme/status/1179891536546484224?s=19

[krauthaufen]

Hey, I will create a repo with the current HashMap implementation and add some perf tests, etc. as soon as I have the time. I finally had the time to understand (at least I think so) the dissertation. I think we should definetly test that but another thing worth investigating would be 'treelets' representing a portion of the tree in a tight structure...

[krauthaufen]

Hey, I just created a repo with a new HashMap implementation (inspired by Okasaki's paper) with minimal performance testing. https://github.com/krauthaufen/ImmutableHashCollections

I'm planning to add other implementations to the Benchmark (especially ImmutableDictionary) and I would be happy to see PRs with other implementations too 😀

[krauthaufen]

A little update: I added several benchmarks to the repo and started using the new System.Runtime.Intrinsics which seems to boost performance drastically. I'm currently running the benchmarks again, but on my machine lookup of an existing element took about 15ns (without intriniscs 20ns). I will update the readme once the benchmarks are done (takes quite a while)

[krauthaufen]

Oh and btw. @dsyme the Fsharpx.Collections implementation uses the techniques described in the paper you mentioned, but the encoding with object-arrays is not really optimal in F# since struct values need to get boxed/unboxed all the time (didn't matter in java of course). Nonetheless I think there might be some valuable bits in it, but I think the current HashMapOkasaki in the repo is quite good.

One thing to note: the virtual-member implementation improved performance drastically (~1.5x) and the same thing could be done with F#'s Map implementation. Of course it reduces readability but I think the improvement justifies the "ugly" implementation. What do you think?

[krauthaufen]

Hey @dsyme did your twitter call dig up any HashMap implementations yet? I tried to get the best out of the okasaki-implementation and it looks quite promising to me, but some comparisons with additional techniques would be cool. The FSharpX implementation is clearly suboptimal but maybe the concept might nonetheless be better. Maybe someone out there has an efficient implementation I didn't find yet...

[dsyme]

Hey @dsyme did your twitter call dig up any HashMap implementations yet? I tried to get the best out of the okasaki-implementation and it looks quite promising to me, but some comparisons with additional techniques would be cool.

Nope.

The FSharpX implementation is clearly suboptimal but maybe the concept might nonetheless be better.

Is it using the popcount intrinsic for bit counting? I had the impression that was really important.

[krauthaufen]

Hey, no it stores all bitcounts in an array which is possible since only values in (0 - 65k) are popcnted.

I was thinking about reimplementing it without all the object arrays and other weirdnesses (each node captures a ref to the creating Thread, etc.) but couldn't yet figure out how to encode that properly in .NET.

The main problem is, that in the JVM everything is boxed, so storing ValueTypes in an object-array doesn't impose additional cost.

However the object-arrays will not improve a .NET implementation but the n-ary encoding used could still improve performance. Maybe a hybrid-solution would also be possible.

I will try to re-implement the datastructure when I have the time but I was hoping to find other implementations somewhere... Cheers

[krauthaufen]

@dsyme I just found a heavily tuned implementation at HAMT.NET which is implemented in C#.
I tried to run it in netcore3 but something doesn't seem to work. (using a lot of native copies, etc) However it uses System.Runtime.Intrinsics.Experimental and I honestly don't know if these translate to actual CPU instructions or just use something like this.

I'm currently running new benchmarks using random keys, etc. but my first results show, that it seems to be a significantly slower than the Okasaki implementation for all operations.

[krauthaufen]

added new benchmarks to ImmutableCollections

• HAMT.NET
• ImTools

ImTools performs really good, but the modification times are a little larger than the ones for the Okasaki HashMap. It internally uses a binary search tree on hashcodes essentially. The lookup times are the best in my benchmark currently.
The HAMT.NET implementation makes heavy use of Intrinsics and native copies, etc. but seems to be slower than the other ones in my benchmarks