llvm dev - Apr 2021 - Concurrent Hashmap?

On 08/04/2021 20:44, Reid Kleckner via llvm-dev wrote:
> I recommend splitting up symbol resolution into a fully data parallel 
> phase and a "shuffle" phase that does the concurrent hash table 
> insertion. This makes rehashing very simple: if the table gets too full, 
> simply abort the concurrent insertions, sync up the worker threads, and 
> retry with a bigger table.
Could you do a dynamic hash instead? In other words grow the hash 
instead of starting over - what's going to be the cost of retrying as 
opposed to growing?

Cheers,
Wol

On Fri, Apr 9, 2021 at 12:01 PM antlists via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Could you do a dynamic hash instead? In other words grow the hash
> instead of starting over - what's going to be the cost of retrying as
> opposed to growing?
>
At a really high level, I believe starting the insertion over has the same
algorithmic complexity as rehashing with the partially filled table, it's
all O(n). Eventually you build a table of size n, and along the way you
have to build a table of size n/2, n/4, n/8..., and if you sum up all the
work to build those tables, you get 2n, or O(n).

At a lower level, for common inputs, rehashing could be faster by a
constant factor. Suppose there are n input symbols and m unique output
symbols, and m is significantly smaller than n. Rehashing only takes O(m)
time, but reinserting takes O(n) time. The overall work is still O(n).
However, rehashing requires a much fancier concurrent data structure,
probably with higher constant factor overhead. You may gain as much as you
lose. And you open yourself up to concurrency bugs. Even if you take a
tested concurrent data structure off the shelf, they can be tricky to use
correctly.

So, at least for PDB global type hashing, I felt it was better to implement
a less general data structure that only does bulk inserts followed by
lookups. I also knew how many insertions I was going to do, so I could also
conservatively overallocate a big hash table and sidestep rehashing. We
can't quite do the same for symbols because symbol resolution can discover
new inputs.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210412/836c73cc/attachment.html>