[llvm-dev] RFC: Improving performance of HashString

[Vedant Kumar via llvm-dev]

> On Apr 24, 2017, at 5:37 PM, Scott Smith via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> I've been working on improving the startup performance of lldb, and ran into an issue with llvm::HashString.  It works a character at a time, which creates a long dependency chain in the processor.  On the other hand, the function is very short, which probably works well for short identifiers.
> 
> I don't know how the mix of identifier length seen by lldb compares with that seen by llvm/clang; I imagine they're pretty similar.
> 
> I have to different proposals, and wanted to gauge which would be preferred:


> 1. Use xxhash instead.

Seems OK to me. I suppose we'd have to fall back to the original hash function if xxhash isn't supported. 

vedant

> 
> 2. Use the Intel native crc32q instruction to process 8 bytes at a time, then fall back to byte at a time.  Non sse 4.2 capable processors (either early or non Intel/AMD x86) would use the existing algorithm, or possibly #1 above.
> 
> For my test, both result in approximately the same # of cycles (within 0.5%).
> 
> #1 uses 3+% more instructions.
> #2 requires (realistically) runtime detection of cpu capabilities, because distributions would want generic x86/x86_64 compatible binaries, not separate binaries per cpu feature.
> 
> I'm leaning toward #1 despite the instruction increase.  My only worry is the effect on compile times for code with lots of short identifiers.  I haven't tested that though (and I don't have a suitable benchmark suite for that) so for all I know I'm worrying about nothing.
> 
> FYI the improvement is approximately 11.5% reduction in cycles for my lldb test (b main, run, quit), so IMO it's pretty significant.
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev