Judy-backed storage in IO

[dpwiz]

https://hackage.haskell.org/package/judy

This looks beneficial for those components that fit into 64 bits (on 64-bit platform). Think IntMap sans the IORef redirection. All those Position Float Float would snug right in.

Actually, with some bit twiddling multiple power-of-2 values can be compressed into a single cell. Or spread over multiple cells (to be benchmarked).

[dpwiz]

A preliminary dive into this gave something like a 2x speed-up over uncached Map, at the cost of significant complexity (and unsafeCoerce'ing). And its library is LGPL (no static builds) and not on msys2 (no easy Windows packaging).

[jonascarpay]

I remember looking at judy and thinking the same thing! Thanks for looking into it. It's surprising it's only twice as fast as Map though, I wonder if most of the cost is in the marshalling

[jonascarpay]

Also, at the risk of going off topic too much, I saw your comments on the Hero reddit thread. SpareSet looks amazing, even if @Simre1 doesn't make a standalone library, I wonder if there's what would need to happen to get Cache up to parity with it. The way I see it, it should be very hard to compete with a fixed-size vector indexed by bitmasking, and yet we are a tad slower. From scanning the code the best candidates are the UNPACKing and strictness. I'm pretty sure when I initially benchmarked Cache I tried that and it didn't make a difference, but that was like 2 major GHC releases ago, so who knows.

[Simre1]

I have put the code for the sparse set online at https://github.com/Simre1/sparse-set, so you can try it out. A hackage release will take some more time; I don't really know what I need to do for that and I am not at my main workstation at the moment.

[dpwiz]

I'd rather have a sparse-set store.