[llvm-dev] Concurrent Hashmap?

[Fangrui Song via llvm-dev]

On 2021-04-07, David Blaikie wrote:
>lld's ELF implementation at least already has some parallelism - I
>think Rui already experimented pretty broadly with various concurrent
>mapping/set to do string deduplication in parallel, so you might see
>how that's been implemented (maybe it didn't end up being done in
>parallel because it couldn't be made efficient)
>
>Probably worth prototyping your improvements with such a data
>structure - but I think it'd be worth having the data about how useful
>it is before adding it to ADT.
>
>On Wed, Apr 7, 2021 at 2:16 PM Jez via llvm-dev <llvm-dev at lists.llvm.org> wrote:
>>
>> I'm looking into parallelizing LLD, and one of the things that would
>> probably help is a concurrent hashmap. I was unable to find an
>> existing implementation under ADT/, which was somewhat surprising.
>> Should I contribute an implementation?
>>
>> Jez

One obvious place where a concurrent unordered map can help: the global symbol table
concurrently shared by object files/shared objects/archive files/bitcode files.
I estimate this as a small one-digit number percentage of the whole link time
(the whole input file scanning takes 10+% time).

mold uses Intel TBB for concurrent data structures. It uses a bunch of
concurrent vectors, two concurrent hashmaps (one for symtab, the other
for comdat group selection), two concurrent unordered maps only for ICF.
(As I mentioned in
https://lists.llvm.org/pipermail/llvm-dev/2021-March/149363.html ,
ELF/ICF.cpp is not a good reference if you want fast ICF:( )

Parallel symbol resolution is tricky. Some challenges:

1. a.so b.a and b.a a.so may have different semantics. I believe mold
   currently cannot handle this correctly.
2. How to ensure determinism when features like --trace-symbol and diagnostics reporting are plugged into
   parallel symbol resolution.
3. weak references

These are things I can think of off the top of my head.
Probably none is insurmountable but in the end the complexity may likely overweigh its advantage:)

If we have a concurrent vector in llvm-project, there may be multiple
places we can improve things...