[llvm-dev] Concurrent Hashmap?

[Jez via llvm-dev]

Alexandre Ganea <alexandre.ganea at ubisoft.com> 9:05 AM (2 hours ago) to
me, llvm-dev at lists.llvm.org
> When you say you'd like to parallelize LLD, which driver do you mean?

I meant the Mach-O driver; sorry for omitting context.

> There's already a specialized lock-free hashtable for the Debug Types merging the COFF driver

Oh, that's cool! Let me see if I can build upon it...

> I'd be really interested to hear what kind of design you had in mind for the concurrent hashmap?

If I were going to hand-roll one I would probably go for a simple
array of hashmaps, one lock per map, sharded by key. Lock-free is nice
but harder to write (but having a starting point helps!)

David Blaikie <dblaikie at gmail.com> Apr 7, 2021, 5:39 PM (18 hours ago)
to Fangrui, me, llvm-dev
> 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)

It looks like LLD-ELF's string table uses a simple DenseMap, so I
guess parallelization didn't end up being committed.

For starters, I wanted to parallelize section/symbol ordering (using a
hashmap to connect symbols with their corresponding entries in the
order file), which would be fairly straightforward if I had a
concurrent map. It is a relatively small part of the overall link time
though. Parallelizing the loading of inputs would be a much bigger
win, but as MaskRay pointed out, doing symbol resolution right is
hard...

I may also try parallelizing the sorting of sections. Parellel.h lacks
a stable sort implementation, but I suppose it isn't too hard to write
a parallel mergesort.

Fangrui Song <maskray at google.com> Apr 7, 2021, 11:48 PM (12 hours ago)
to me, David, llvm-dev
> (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:( )

We haven't implemented ICF yet, but we'll keep that in mind :)

Neil Henning <neil.henning at unity3d.com> 9:43 AM (2 hours ago) to
Alexandre, me, llvm-dev at lists.llvm.org
> Just because it wasn't totally clear to me - is this about having a single LLD process have better parallelism?

Yes. I believe library-fying LLD has been a contested issue, but I
have no dog in this fight, so please use another thread to hash it out
:)

Jez

On Thu, Apr 8, 2021 at 9:05 AM Alexandre Ganea
<alexandre.ganea at ubisoft.com> wrote:
>
> When you say you'd like to parallelize LLD, which driver do you mean? COFF, ELF, wasm...? They all have separate codebases.
>
> There's already a specialized lock-free hashtable for the Debug Types merging the COFF driver: https://github.com/llvm/llvm-project/blob/e7a371f9fd0076c187f4cd1a9c7546867faeb19b/lld/COFF/DebugTypes.cpp#L992
>
>
> I'd be really interested to hear what kind of design you had in mind for the concurrent hashmap?
>
> If you contribute any concurrent container into ADT, I'd like to see an application along (that is, a patch that uses the container in LLD for example). If the container is used in a tight loop, it needs to be lock-free if we want it to scale on many-core machines. And in that case we're pretty much limited to a 64-bit key/value pair if we don't want to make things complicated. We could also have a sharded container that would fit more cases, but tweaking it really depends on its usage.
>
> -----Message d'origine-----
> De : llvm-dev <llvm-dev-bounces at lists.llvm.org> De la part de Jez via llvm-dev
> Envoyé : April 7, 2021 5:16 PM
> À : llvm-dev at lists.llvm.org
> Objet : [llvm-dev] Concurrent Hashmap?
>
> 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
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev