[llvm-dev] Concurrent Hashmap?

Thu Apr 8 07:26:45 PDT 2021

Neil:

I think this is a separate discussion from what Jez suggests, but I had a demo patch that allowed the LLD/COFF driver to be thread-safe when used “as-a-library”: https://reviews.llvm.org/D86353 - with this we can link several programs in parallel in the same process, it makes the lld::safeLldLink() API fully thread-safe. Only limitation though was that ThreadPools were running single-threaded only on the current thread, because there was no way (yet) to schedule tasks in common, across LLD instances.

Making all global state thread_local in D86353 was simply a cheap’n dirty solution to have visibility on what needs to be changed. I think a more flexible solution would be to move all global (LLD) state onto the stack, into a “context” structure (or a collection of “context” structures, if that makes more sense).

I’d like to do that change soon, and I’d like to hear what folks think about that? (sorry for hijacking the thread)

De : Neil Henning <neil.henning at unity3d.com>
Envoyé : April 8, 2021 9:43 AM
À : Alexandre Ganea <alexandre.ganea at ubisoft.com>
Cc : Jez <jezreel at gmail.com>; llvm-dev at lists.llvm.org
Objet : Re: [llvm-dev] Concurrent Hashmap?

Just because it wasn't totally clear to me - is this about having a single LLD process have better parallelism?

What we'd love is that we could use LLD as a library (to save on process launch cost) multithreaded, but last I checked there was still lots of globals used all over the place.

Cheers,
-Neil.

On Thu, Apr 8, 2021 at 2:05 PM Alexandre Ganea via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> 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<mailto: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<mailto: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<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--
[https://unity3d.com/profiles/unity3d/themes/unity/images/ui/other/unity-logo-dark-email.png]
Neil Henning
Senior Software Engineer Compiler
unity.com<http://unity.com>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210408/dbd85796/attachment-0001.html>