search

skeeto / hash-prospector

Automated integer hash function discovery
The Unlicense
672 stars 27 forks source link

Provide a vectorized output bit count loop #1

Closed TheIronBorn closed 5 years ago

TheIronBorn commented 5 years ago

This loop: https://github.com/skeeto/hash-prospector/blob/79a6074062a84907df6e45b756134b74e2956760/prospector.c#L567-L568

vectorizes really well even with SSE2 and x86-64 is already required.

Note: if the density of 1's is low enough, branching algorithms similar to this https://lemire.me/blog/2019/05/03/really-fast-bitset-decoding-for-average-densities might be better, but they have worse worst-case performance

TheIronBorn commented 5 years ago

I just checked the generated assembly and gcc auto-vectorizes it. My bad

TheIronBorn commented 5 years ago

Only with AVX2 variable shifts though