* Andi Kleen via Gcc: > Joern Wolfgang Rennecke <g...@amylaar.uk> writes: > >> This has come up several time over the years: >> https://gcc.gnu.org/legacy-ml/gcc/2006-07/msg00158.html >> https://gcc.gnu.org/legacy-ml/gcc/2006-07/msg00155.html >> https://gcc.gnu.org/pipermail/gcc/2010-March/190234.html >> >> , but maybe now (or maybe a while ago) is the right time to do this, >> considering the changes in relative costs of basic operations? >> Multiply and barrel shift are cheap on many modern microarchitectures. > > There are much more powerfull primitives for hashes on modern CPUs, like > CRC or AES rounds. I don't know if anybody has tried to do a > perfect hash on top of those though, but perhaps it wouldn't need > to be.
Also carry-less multiply persumably. It's challenging to use those instructions for compiling switch statements because they would then be used all over the place. But maybe Fibonacci hashing is good enough. >> Control flow and non-linear memory access is expensive. > > Before going to hashes I would rather exploit SIMD first, e.g. to do > multiple comparisons in a single instruction. Modern hash > table implementations like Swiss tables are already doing that > for good results. What are you proposing? Broadcast the scrutinee to a vector register, perform a vector compare against possible switch values, and then extract the index of the non-zero component, and then use that for a table lookup? Thanks, Florian
