<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<font size="-1"><span class="pl-c"><a class="moz-txt-link-freetext" href="https://github.com/facebook/folly/blob/master/folly/AtomicHashMap.h">https://github.com/facebook/folly/blob/master/folly/AtomicHashMap.h</a></span></font>
<p><font size="-1"><span class="pl-c"> * AtomicHashMap --<br>
*<br>
* A high-performance concurrent hash map with int32_t or
int64_t keys. Supports<br>
* insert, find(key), findAt(index), erase(key), size, and
more. Memory cannot<br>
* be freed or reclaimed by erase. Can grow to a maximum of
about 18 times the<br>
* initial capacity, but performance degrades linearly with
growth. Can also be<br>
* used as an object store with unique 32-bit references
directly into the<br>
* internal storage (retrieved with iterator::getIndex()).<br>
*<br>
* Advantages:<br>
* - High-performance (~2-4x tbb::concurrent_hash_map in
heavily<br>
* multi-threaded environments).<br>
* - Efficient memory usage if initial capacity is not over
estimated<br>
* (especially for small keys and values).<br>
* - Good fragmentation properties (only allocates in large
slabs which can<br>
* be reused with clear() and never move).<br>
* - Can generate unique, long-lived 32-bit references for
efficient lookup<br>
* (see findAt()).<br>
*<br>
* Disadvantages:<br>
* - Keys must be native int32_t or int64_t, or explicitly
converted.<br>
* - Must be able to specify unique empty, locked, and
erased keys<br>
* - Performance degrades linearly as size grows beyond
initialization<br>
* capacity.<br>
* - Max size limit of ~18x initial size (dependent on max
load factor).<br>
* - Memory is not freed or reclaimed by erase.<br>
<br>
* Copyright (c) Facebook, Inc. and its affiliates.<br>
*<br>
* Licensed under the Apache License, Version 2.0 (the
"License");<br>
* you may not use this file except in compliance with the
License.<br>
* You may obtain a copy of the License at<br>
</span></font></p>
<p><span class="pl-c"><font size="-1">Neil Nelson </font><br>
</span></p>
<div class="moz-cite-prefix">On 4/8/21 9:06 AM, Neil Henning via
llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CALRoqd37KeGG7rziGhU0Jy8Mbbx7TbDxNfN-3OPoNLKGAXKcxw@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div>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.</div>
<div><br>
</div>
<div>(sorry for hijacking too!)<br>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Thu, Apr 8, 2021 at 3:26 PM
Alexandre Ganea <<a
href="mailto:alexandre.ganea@ubisoft.com" target="_blank"
moz-do-not-send="true">alexandre.ganea@ubisoft.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div lang="EN-CA">
<div>
<p class="MsoNormal"><span>Neil:</span></p>
<p class="MsoNormal"><span> </span></p>
<p class="MsoNormal"><span>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”:
<a href="https://reviews.llvm.org/D86353"
target="_blank" moz-do-not-send="true">https://reviews.llvm.org/D86353</a>
- 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.</span></p>
<p class="MsoNormal"><span> </span></p>
<p class="MsoNormal"><span>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).</span></p>
<p class="MsoNormal"><span> </span></p>
<p class="MsoNormal"><span>I’d like to do that change
soon, and I’d like to hear what folks think about
that? (sorry for hijacking the thread)</span></p>
<p class="MsoNormal"><span> </span></p>
<p class="MsoNormal"><span> </span></p>
<div style="border-color:rgb(225,225,225) currentcolor
currentcolor;border-style:solid none
none;border-width:1pt medium medium;padding:3pt 0cm 0cm">
<p class="MsoNormal"><b>De :</b> Neil Henning <<a
href="mailto:neil.henning@unity3d.com"
target="_blank" moz-do-not-send="true">neil.henning@unity3d.com</a>>
<br>
<b>Envoyé :</b> April 8, 2021 9:43 AM<br>
<b>À :</b> Alexandre Ganea <<a
href="mailto:alexandre.ganea@ubisoft.com"
target="_blank" moz-do-not-send="true">alexandre.ganea@ubisoft.com</a>><br>
<b>Cc :</b> Jez <<a href="mailto:jezreel@gmail.com"
target="_blank" moz-do-not-send="true">jezreel@gmail.com</a>>;
<a href="mailto:llvm-dev@lists.llvm.org"
target="_blank" moz-do-not-send="true">llvm-dev@lists.llvm.org</a><br>
<b>Objet :</b> Re: [llvm-dev] Concurrent Hashmap?</p>
</div>
<p class="MsoNormal"> </p>
<div>
<div>
<p class="MsoNormal">Just because it wasn't totally
clear to me - is this about having a single LLD
process have better parallelism?</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">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.</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">Cheers,</p>
</div>
<div>
<p class="MsoNormal">-Neil.</p>
</div>
</div>
<p class="MsoNormal"> </p>
<div>
<div>
<p class="MsoNormal">On Thu, Apr 8, 2021 at 2:05 PM
Alexandre Ganea via llvm-dev <<a
href="mailto:llvm-dev@lists.llvm.org"
target="_blank" moz-do-not-send="true">llvm-dev@lists.llvm.org</a>>
wrote:</p>
</div>
<blockquote style="border-color:currentcolor
currentcolor currentcolor
rgb(204,204,204);border-style:none none none
solid;border-width:medium medium medium
1pt;padding:0cm 0cm 0cm 6pt;margin:5pt 0cm 5pt 4.8pt">
<p class="MsoNormal">When you say you'd like to
parallelize LLD, which driver do you mean? COFF,
ELF, wasm...? They all have separate codebases.<br>
<br>
There's already a specialized lock-free hashtable
for the Debug Types merging the COFF driver:
<a
href="https://github.com/llvm/llvm-project/blob/e7a371f9fd0076c187f4cd1a9c7546867faeb19b/lld/COFF/DebugTypes.cpp#L992"
target="_blank" moz-do-not-send="true">
https://github.com/llvm/llvm-project/blob/e7a371f9fd0076c187f4cd1a9c7546867faeb19b/lld/COFF/DebugTypes.cpp#L992</a><br>
<br>
<br>
I'd be really interested to hear what kind of design
you had in mind for the concurrent hashmap?<br>
<br>
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.<br>
<br>
<span lang="FR-CA">-----Message d'origine-----<br>
De : llvm-dev <</span><a
href="mailto:llvm-dev-bounces@lists.llvm.org"
target="_blank" moz-do-not-send="true"><span
lang="FR-CA">llvm-dev-bounces@lists.llvm.org</span></a><span
lang="FR-CA">> De la part de Jez via llvm-dev<br>
Envoyé : April 7, 2021 5:16 PM<br>
À : </span><a
href="mailto:llvm-dev@lists.llvm.org"
target="_blank" moz-do-not-send="true"><span
lang="FR-CA">llvm-dev@lists.llvm.org</span></a><span
lang="FR-CA"><br>
Objet : [llvm-dev] Concurrent Hashmap?<br>
<br>
</span>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.<br>
Should I contribute an implementation?<br>
<br>
Jez<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org"
target="_blank" moz-do-not-send="true">llvm-dev@lists.llvm.org</a><br>
<a
href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
target="_blank" moz-do-not-send="true">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org"
target="_blank" moz-do-not-send="true">llvm-dev@lists.llvm.org</a><br>
<a
href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
target="_blank" moz-do-not-send="true">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></p>
</blockquote>
</div>
<p class="MsoNormal"><br clear="all">
<br>
-- </p>
<div>
<div>
<table
style="width:100%;border-collapse:collapse;border-spacing:0px"
width="100%" cellspacing="0" cellpadding="0"
border="0">
<tbody>
<tr>
<td style="padding:0cm 0cm 15pt" valign="top">
<table
style="border-collapse:collapse;border-spacing:0px"
cellspacing="0" cellpadding="0" border="0"
align="left">
<tbody>
<tr>
<td style="width:48pt;padding:0cm"
width="64" valign="top">
<p class="MsoNormal"
style="line-height:18pt"><span
style="font-size:12.5pt"
lang="FR-CA"><img style="width:
0.6666in; height: 0.25in;"
id="gmail-m_-6544610267668817757gmail-m_4397030810613675928_x0000_i1025"
src="https://unity3d.com/profiles/unity3d/themes/unity/images/ui/other/unity-logo-dark-email.png"
moz-do-not-send="true"
width="64" height="24"
border="0"></span><span
style="font-size:12.5pt"
lang="FR-CA"></span></p>
</td>
</tr>
</tbody>
</table>
</td>
</tr>
<tr>
<td style="padding:0cm" valign="top">
<div>
<p class="MsoNormal"
style="line-height:11.25pt"><b><span
style="font-size:10.5pt;font-family:Roboto;color:black"
lang="FR-CA">Neil Henning</span></b></p>
</div>
</td>
</tr>
<tr>
<td style="padding:0cm" valign="top">
<div>
<p class="MsoNormal"
style="line-height:11.25pt"><span
style="font-size:10.5pt;font-family:Roboto;color:black"
lang="FR-CA">Senior Software Engineer
Compiler</span></p>
</div>
</td>
</tr>
<tr>
<td style="padding:0cm" valign="top">
<div>
<p class="MsoNormal"
style="line-height:11.25pt"><span
lang="FR-CA"><a href="http://unity.com"
target="_blank" moz-do-not-send="true"><span
style="font-size:9pt;font-family:Roboto">unity.com</span></a></span><span
style="font-size:9pt;font-family:Roboto;color:black" lang="FR-CA"></span></p>
</div>
</td>
</tr>
</tbody>
</table>
<p class="MsoNormal"> </p>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br clear="all">
<br>
-- <br>
<div dir="ltr">
<div dir="ltr">
<table
style="border-collapse:collapse;border-spacing:0px;color:rgb(90,90,91);font-size:13px;margin:0px
0px 20px;padding:0px" width="100%" cellspacing="0"
cellpadding="0" border="0">
<tbody style="margin:0px;padding:0px">
<tr style="margin:0px;padding:0px">
<td
style="border-collapse:collapse;font-size:0px;line-height:1.5em;padding:0px
0px 20px;vertical-align:top" align="left">
<table
style="border-collapse:collapse;border-spacing:0px;margin:0px;padding:0px"
cellspacing="0" cellpadding="0" border="0"
align="left">
<tbody style="margin:0px;padding:0px">
<tr style="margin:0px;padding:0px">
<td
style="border-collapse:collapse;font-size:1.12em;line-height:1.5em;padding:0px;vertical-align:top;width:64px"><img
style="border: medium none; border-radius:
0px; display: block; font-size: 13px;
height: auto; line-height: 100%; margin:
0px; max-width: 100%; outline-style: none;
outline-width: medium; padding: 20px 0px
0px; width: 100%;" alt=""
src="https://unity3d.com/profiles/unity3d/themes/unity/images/ui/other/unity-logo-dark-email.png"
moz-do-not-send="true" width="64"
height="auto"></td>
</tr>
</tbody>
</table>
</td>
</tr>
<tr style="margin:0px;padding:0px">
<td
style="border-collapse:collapse;font-size:0px;line-height:1.5em;padding:0px;vertical-align:top"
align="left">
<div
style="color:rgb(0,0,0);font-family:Roboto,Arial;font-size:14px;font-weight:600;line-height:15px;margin:0px;padding:0px">Neil
Henning</div>
</td>
</tr>
<tr style="margin:0px;padding:0px">
<td
style="border-collapse:collapse;font-size:0px;line-height:1.5em;padding:0px;vertical-align:top"
align="left">
<div
style="color:rgb(0,0,0);font-family:Roboto,Arial;font-size:14px;line-height:15px;margin:0px;padding:0px
0px 10px">Senior Software Engineer Compiler</div>
</td>
</tr>
<tr style="margin:0px;padding:0px">
<td
style="border-collapse:collapse;font-size:0px;line-height:1.5em;padding:0px;vertical-align:top"
align="left">
<div
style="color:rgb(0,0,0);font-family:Roboto,Arial;font-size:12px;line-height:15px;margin:0px;padding:0px"><a
href="http://unity.com" target="_blank"
moz-do-not-send="true">unity.com</a></div>
</td>
</tr>
</tbody>
</table>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</body>
</html>