<div dir="ltr"><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, May 18, 2020 at 10:14 PM Shoaib Meenai via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I was looking at the SymbolTable code in LLD COFF and ELF recently, and I’m confused by the use of CachedHashStringRef.<br>
<br>
>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.<br>
<br>
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.<br>
<br>
[1] <a href="https://github.com/llvm/llvm-project/blob/47a0e9f49b903aa4ef821d2c7a679a145ee983f9/llvm/include/llvm/ADT/CachedHashString.h#L35-L36" rel="noreferrer" target="_blank">https://github.com/llvm/llvm-project/blob/47a0e9f49b903aa4ef821d2c7a679a145ee983f9/llvm/include/llvm/ADT/CachedHashString.h#L35-L36</a><br>
[2] <a href="https://github.com/llvm/llvm-project/blob/3f5f8f39734e88c797b003d4a0002b2eaef1ac17/lld/COFF/SymbolTable.h#L129" rel="noreferrer" target="_blank">https://github.com/llvm/llvm-project/blob/3f5f8f39734e88c797b003d4a0002b2eaef1ac17/lld/COFF/SymbolTable.h#L129</a><br>
[3] <a href="https://github.com/llvm/llvm-project/blob/3f5f8f39734e88c797b003d4a0002b2eaef1ac17/lld/COFF/SymbolTable.cpp#L458" rel="noreferrer" target="_blank">https://github.com/llvm/llvm-project/blob/3f5f8f39734e88c797b003d4a0002b2eaef1ac17/lld/COFF/SymbolTable.cpp#L458</a><br>
[4] <a href="https://github.com/llvm/llvm-project/blob/3f5f8f39734e88c797b003d4a0002b2eaef1ac17/lld/COFF/SymbolTable.cpp#L727" rel="noreferrer" target="_blank">https://github.com/llvm/llvm-project/blob/3f5f8f39734e88c797b003d4a0002b2eaef1ac17/lld/COFF/SymbolTable.cpp#L727</a><br>
</blockquote><div><br></div><div>Not familiar with this code, but a possible reason might be to avoid recomputing string hashes when the DenseMap is resized.</div><div><br></div><div>Nikita<br></div></div></div>