[llvm-dev] RFC: Improving performance of HashString
Davide Italiano via llvm-dev
llvm-dev at lists.llvm.org
Tue Apr 25 14:47:37 PDT 2017
On Tue, Apr 25, 2017 at 1:19 PM, Scott Smith
<scott.smith at purestorage.com> wrote:
> On Tue, Apr 25, 2017 at 1:11 PM, Davide Italiano <davide at freebsd.org> wrote:
>> On Tue, Apr 25, 2017 at 12:55 PM, Vedant Kumar via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>> >> 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.
>> I'd lean towards this option as we already have a copy of xxHash in
>> lib/Support (llvm/Support/xxhash.h).
>> We use it for computing the --build-id in lld as fast/non-crytographic
>> hash variant and has proven to outperform other candidates (e.g.
> That's actually why I suggested it, though AFAIK xxHash has more collisions
> than other hash algorithms.
> xxHash outperforms CityHash? https://github.com/rurban/smhasher/ So many
IIRC, yes. Of course, your mileage may vary but given we have a solid
alternative in-tree already I wouldn't go for another non-crypto hash
function unless there's a good reason for it.
"There are no solved problems; there are only problems that are more
or less solved" -- Henri Poincare
More information about the llvm-dev