Hi Hiltjo,
On Thu, Jul 06, 2023 at 07:08:57PM +0200, Hiltjo Posthuma wrote:
> What hash algorithm is this exactly, it looks interesting? I've found it at:
>
> https://github.com/skeeto/hash-prospector
>
> Is that the one?
The "xor-shift multiply" construct itself is fairly popular and can be
found on many hash algorithms (e.g murmur, fnv etc). I *think* it
originates from LGCs, but not sure about that:
https://en.wikipedia.org/wiki/Linear_congruential_generator
The specific multiplier and shift constants are indeed taken from
hash-prospector README, I've updated v2 commit message to include it.
> What's the measured performance improvement and wouldn't it increase collisions
> vs a simple linear search?
In case the cache gets filled up, the false-negative rate of either a
linear search or the hash-table will be unpredictable since both of them
use a "dumb" eviction policy.
The old method overwrites whatever came in first and the new one
overwrites whatever was in `h1`. Something like an LRU *might* help in
those cases, but I think it's not worth the trouble.
As for collisions, the new 2x size made collisions rarer. Testing with a
list of ~1.6k emojies I saw only 5 collisions. (The result will
obviously vary depending on your installed fonts).
But this made me realize that it was dumb to throw away the high bits of
the hash. It can be used to probe another slot. With that, I now only
get 1 collision. I've updated the v2 patch with the new logic.
> I'm not sure we should change the assumption for ints to POSIX in dmenu in all
> cases and assume 32-bit int (although a lot of software in practise does). But
> this is very pedantic :)
>
> Bit off-topic: recently I tested some software on MS-DOS with the OpenWatcom
> compiler. It had 16-bit int and caught a bug in my code (lower-level parser
> stuff).
Since dmenu already requires POSIX, I didn't think it'd be a problem.
`uint_least32_t` or `uint32_t` can probably be used, but suckless code
base typically seems to avoid <stdint.h>.
---
Avoiding wastage and thus being able to 2x the cache size is the *main*
improvement here, IMO.
The hash-table is measurably faster than linear search but it won't be
noticeable by the user (~30ns vs ~130ns, in theory it also avoids
polluting the cache but I doubt that'll matter much either) so I don't
mind dropping the hash-table if there's concerns about it.
But I think avoiding waste and 2x cache size is worthwhile since it
means we can avoid even more unnecessary and expensive XftFontMatch()
calls.
- NRK
Received on Fri Jul 07 2023 - 13:00:42 CEST