[llvm-dev] Concurrent Hashmap?
Neil Nelson via llvm-dev
llvm-dev at lists.llvm.org
Fri Apr 9 11:18:24 PDT 2021
https://github.com/facebook/folly/blob/master/folly/AtomicHashMap.h
* AtomicHashMap --
*
* A high-performance concurrent hash map with int32_t or int64_t keys.
Supports
* insert, find(key), findAt(index), erase(key), size, and more.
Memory cannot
* be freed or reclaimed by erase. Can grow to a maximum of about 18
times the
* initial capacity, but performance degrades linearly with growth. Can
also be
* used as an object store with unique 32-bit references directly into the
* internal storage (retrieved with iterator::getIndex()).
*
* Advantages:
* - High-performance (~2-4x tbb::concurrent_hash_map in heavily
* multi-threaded environments).
* - Efficient memory usage if initial capacity is not over estimated
* (especially for small keys and values).
* - Good fragmentation properties (only allocates in large slabs
which can
* be reused with clear() and never move).
* - Can generate unique, long-lived 32-bit references for efficient
lookup
* (see findAt()).
*
* Disadvantages:
* - Keys must be native int32_t or int64_t, or explicitly converted.
* - Must be able to specify unique empty, locked, and erased keys
* - Performance degrades linearly as size grows beyond initialization
* capacity.
* - Max size limit of ~18x initial size (dependent on max load factor).
* - Memory is not freed or reclaimed by erase.
* Copyright (c) Facebook, Inc. and its affiliates.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
Neil Nelson
On 4/8/21 9:06 AM, Neil Henning via llvm-dev wrote:
> We'd definitely use this functionality if available, so it's a +1 from
> myself. Ideally we'd have it possible to work on the three main
> desktop platforms (so the ELF/MACHO code would be able to be run as a
> thread-safe library on multiple threads too), but COFF alone would be
> a huge win for starters for us.
>
> (sorry for hijacking too!)
>
> On Thu, Apr 8, 2021 at 3:26 PM Alexandre Ganea
> <alexandre.ganea at ubisoft.com <mailto:alexandre.ganea at ubisoft.com>> wrote:
>
> 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 <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
> <mailto:neil.henning at unity3d.com>>
> *Envoyé :* April 8, 2021 9:43 AM
> *À :* Alexandre Ganea <alexandre.ganea at ubisoft.com
> <mailto:alexandre.ganea at ubisoft.com>>
> *Cc :* Jez <jezreel at gmail.com <mailto:jezreel at gmail.com>>;
> llvm-dev at lists.llvm.org <mailto: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
> <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
> <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://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>
>
>
> --
>
> *Neil Henning*
>
> Senior Software Engineer Compiler
>
> unity.com <http://unity.com>
>
>
>
> --
>
> Neil Henning
> Senior Software Engineer Compiler
> unity.com <http://unity.com>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210409/a71fdf67/attachment.html>
More information about the llvm-dev
mailing list