[llvm-dev] Understanding LLD's SymbolTable's use of CachedHashStringRef

[Fangrui Song via llvm-dev]

On 2020-05-18, Shoaib Meenai via llvm-dev wrote:
>Got it, thanks. I didn’t realize the DenseMap would be recomputing those on a resize instead of caching them internally (although I haven’t though particularly hard about whether that internal caching would even be feasible in the general case).

I guess the design is more about saving hash computation for StringRef's
stored in the container. Only an incoming StringRef needs to be computed
for hash.

For COFF, lld::coff::SymbolTable::forEachSymbol is called just twice. It
has a comment that the iteration order is non-deterministic. The
non-determinism is fixed immediated by following sort() calls.

For ELF, symVector is iterated in many places. I experimented a bit
found

   llvm::DenseMap<llvm::CachedHashStringRef, int> symMap;
   std::vector<Symbol *> symVector;

faster than

   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> symMap;
   // which also has iteration non-determinism problems.

>From: Nikita Popov <nikita.ppv at gmail.com>
>Date: Monday, May 18, 2020 at 1:19 PM
>To: Shoaib Meenai <smeenai at fb.com>
>Cc: "llvm-dev at lists.llvm.org" <llvm-dev at lists.llvm.org>
>Subject: Re: [llvm-dev] Understanding LLD's SymbolTable's use of CachedHashStringRef
>
>On Mon, May 18, 2020 at 10:14 PM Shoaib Meenai via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
>I was looking at the SymbolTable code in LLD COFF and ELF recently, and I’m confused by the use of CachedHashStringRef.
>
>From what I understand, a CachedHashStringRef combines a StringRef with a computed hash. There’s no caching going on in the CachedHashStringRef itself; that is, if you construct CachedHashStringRef("foo"), and then construct a second CachedHashStringRef("foo") again later, you'll compute the hash for "foo" twice [1]. Instead, once you've constructed a CachedHashStringRef from a StringRef, you can pass that around instead of the StringRef to avoid needing to recompute the hash for it.
>
>LLD COFF's symbol table structure is a DenseMap<CachedHashStringRef, Symbol *> named symMap [2]. (ELF's is similar, except it maps to a vector index instead of a Symbol * directly for symbol order determinism reasons.) The only accesses to symMap are either iterating over its values or doing a lookup. In the two cases where a map lookup is done [3][4], the input to the function doing the lookup is just a StringRef, and a CachedHashStringRef is constructed to perform the lookup. What's the advantage of using a CachedHashStringRef in that case, as opposed to just having a DenseMap<StringRef, Symbol *> directly? With that, the DenseMap would be performing the hash computation for each lookup operation, but the CachedHashStringRef construction we have right now is doing the same hash computation anyway, so I don't understand the benefit of using it here.
>
>[1] https://github.com/llvm/llvm-project/blob/47a0e9f49b903aa4ef821d2c7a679a145ee983f9/llvm/include/llvm/ADT/CachedHashString.h#L35-L36
>[2] https://github.com/llvm/llvm-project/blob/3f5f8f39734e88c797b003d4a0002b2eaef1ac17/lld/COFF/SymbolTable.h#L129
>[3] https://github.com/llvm/llvm-project/blob/3f5f8f39734e88c797b003d4a0002b2eaef1ac17/lld/COFF/SymbolTable.cpp#L458
>[4] https://github.com/llvm/llvm-project/blob/3f5f8f39734e88c797b003d4a0002b2eaef1ac17/lld/COFF/SymbolTable.cpp#L727
>
>Not familiar with this code, but a possible reason might be to avoid recomputing string hashes when the DenseMap is resized.
>
>Nikita

>_______________________________________________
>LLVM Developers mailing list
>llvm-dev at lists.llvm.org
>https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev