Faster lookup if utilizing perfect hashing?

[simendsjo]

First off, thanks a lot for Sycamore! It is the key library for my little vaporware game. But because of this, I'm also having performance issues even though I see it is highly optimized; nearly all CPU and allocations happens in sycamore.

I have some thoughts on how to make things faster, but I'm not sure how feasible it is to do within sycamore or if I can use parts of sycamore to achieve my goals.

I have primarily two kinds of hash-maps, one where I have fixnum as key and use :test #'cl:= :hash-function #'identity. It stores data using the strictly increasing id's for game objects. This is the kind of map I think might benefit the most from a special implementation, but I'm not sure given that sbcl is quite good at optimizations and there are quite some type hints in your library. As it's a perfect hash function, it wouldn't need any collision detection or bucket implementation at all.

The other use is where I use keywords as keys and :test #'eq :hash-function #'sb-kernel:symbol-hash. I would have loved to just used the :test #'cl:= :hash-function sb-kernel:get-lisp-obj-address and thus reuse a perfect hash implementation, but I guess the keywords can move around in memory unless I take some special care.

I also noticed it reused the hash-set implementation by doing (cons key value) which also turned up as one of the main sources of list allocations. Not sure if avoiding this would yield much benefit, but at least it showed up as a big source of allocations.

Do you think an optimized "perfect hash" implementation is useful in sycamore, or is it way to specialized? Will creating a hardcoded version for fixnum and perfect hashing yield any benefits you think? Could parts of sycamore be reused for such an implementation?

[ndantam]

First, a couple general performance notes:

1. If you don't actually need persistence, mutable data structures generally have much better constant factors. Even when persistence offers better big-O (ropes), the constant factors favor mutable structures in typical (small-medium sizes) cases.
2. My observation of SBCL performance is that shaving off a few branches and function calls doesn't much improve running times, but reducing allocations has significant impact. So, more useful for (non-algorithmic) optimizations to focus first on allocation patterns.

For using sycamore (mostly) as-is:

• If you only ever need one version of your structures, you'll likely get the the best performance with ANSI CL hash tables (or maybe vectors).
• If you sometimes need persistence, and other times are OK to clobber other versions of structures, sycamore includes destructive HAMT updates hamt-set-n{insert,replace}. These are not directly exposed in the exported API, but that would be easy to add.

fixnum as key and use :test #'cl:= :hash-function #'identity ... "perfect hash" implementation

I believe such an implementation could be optimized to eliminate leaf nodes (saving one cons call per set insertion and two cons calls per map insertion).

keywords can move around in memory

SBCL uses a copying garbage collector on most platforms, so heap object memory addresses will tend to change (and thus no good as hash codes).

[simendsjo]

Thanks for the feedback!

If you don't actually need persistence, mutable data structures generally have much better constant factors. Even when persistence offers better big-O (ropes), the constant factors favor mutable structures in typical (small-medium sizes) cases.

I use cl-fast-ecs for things that doesn't need persistence, like updating animations and rendering. At the moment, my hash maps are very small, so I guess using arrays with copy-on-write could be another possibility.

My observation of SBCL performance is that shaving off a few branches and function calls doesn't much improve running times, but reducing allocations has significant impact. So, more useful for (non-algorithmic) optimizations to focus first on allocation patterns.

Yes, I've been chasing allocations and dynamic dispatch for great gains. The allocations are especially bad as the GC triggers stuttering in the frame rate as it pauses all threads.

If you sometimes need persistence, and other times are OK to clobber other versions of structures, sycamore includes destructive HAMT updates hamt-set-n{insert,replace}. These are not directly exposed in the exported API, but that would be easy to add.

I use the destructive versions for a couple of cases where I know I have created the maps without yet sharing them. Especially one tight loop could use the destructive version in some cases which reduced allocations a lot.

fixnum as key and use :test #'cl:= :hash-function #'identity ... "perfect hash" implementation
I believe such an implementation could be optimized to eliminate leaf nodes (saving one cons call per set insertion and two cons calls per map insertion).

Might not be worth the effort.

keywords can move around in memory
SBCL uses a copying garbage collector on most platforms, so heap object memory addresses will tend to change (and thus no good as hash codes).

Thanks, I expected as much.

---

I'll try to change my lookup algorithms to reduce the amount of lookups in the hash maps. I know several cases where I can get a lot done by reordering the queries and look up in some smaller maps first. I'll investigate creating a simple query planner.