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
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 > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
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
Hi, For parallelizing LLD, another approach could be something similar to clojure collection instead of a concurrent hashmap. It might change the processing design pattern for LLD a bit, but it might be very fast. Kind Regards James On Wed, 7 Apr 2021 at 22:17, 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 > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev