Fast F#: Writing a Dictionary Part 9 - Robing Hood Hashing

Let's try using Robing Hood Hashing to improve data locality and, therefore, the lookup performance of our Dictionary? Will it help? Will it make it worse? Let's find out!
Robin Hood Hashing: en.wikipedia.org/wiki/Hash_ta...
=== Contact ===
Email: [e-mail]
Mastadon: mastodon.sdf.org/@fastfsharp
Twitter: / fastfsharp
=== Donate ===
Ko-Fi: ko-fi.com/fastfsharp
=== Tags ===
Tags: #fsharp, #dotnet

[@FastFSharp]

What other non-trivial data structures would you like me to look at writing a fast version of?

[@greggy_b]

I would love to see an exploration of the ideas behind Clojure's persistent data structures. These have been ported in the FSharpx.Collections, but I am unsure how optimized they are there. A series similar to this with persistent vectors or maps would be incredible.

[@FastFSharp]

Good idea! I’ve been wanting to optimize some tree data structure and this would likely be a good fit.

[@talwald1680]

I have a pet project in f# for finding the count of unique solutions of the 8-queens problem for a board of size n.
It would be really cool to try out some of the things that you have been showing in this series on that project and see how it improves it.
For clarity- the 8-queens problem is trying to put 8 queens on a chessboard so that 2 queens do not occupy the same column row or diagonal. By unique I mean that 2 solutions that are related by some symmetry (mirror, roatation etc) are counted as 1.
If you want me to share the different stages of the code that I went through I'd love to chat about it 😀

[@FastFSharp]

@@talwald1680 I'd be happy to chat. Shoot me an email and we can set something up. Email in the description.

[@javiera1546]

muchas gracias rey

[@chudchadanstud]

Instead of a linked list what happens if you use an ArrayList or vector that grows only 50% instead of doubling. Can we also use strategies like reserving space and for it and only creating the bucket when it's actually used?

[@talwald1680]

Great video !
In the previous solution, on lookup you had to check every entry from the correct bucket until the empty bucket to find whether or not the lookup key exists in the dictionary. What if we stored in each location the index of the next occurrence of this bucket? Then we could jump like a linked list but all the data is in the same array (hopefully in cache) and its not pointers so the branch mispredictions should be a lot smaller.
Also storing the index of the next occurrence during insert isn't complicated or expensive.
Your thoughts?

[@FastFSharp]

Have you been reading ahead? 😉You'll see something like this in the Byte List solutions which are coming up soon.

[@talwald1680]

How come the branch mispredictions between the 2 benchmark runs have 10X less mispredictions?

[@FastFSharp]

The hardware counter columns aren't always printed in the same order so what you are seeing is the Branch Instructions vs Branch Instruction Mispredictions.