<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Roboto;
panose-1:2 0 0 0 0 0 0 0 0 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-CA" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Neil:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">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">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">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).<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">I’d like to do that change soon, and I’d like to hear what folks think about that? (sorry for hijacking the thread)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b>De :</b> Neil Henning <neil.henning@unity3d.com> <br>
<b>Envoyé :</b> April 8, 2021 9:43 AM<br>
<b>À :</b> Alexandre Ganea <alexandre.ganea@ubisoft.com><br>
<b>Cc :</b> Jez <jezreel@gmail.com>; llvm-dev@lists.llvm.org<br>
<b>Objet :</b> Re: [llvm-dev] Concurrent Hashmap?<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></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?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Cheers,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">-Neil.<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></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">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<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">
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"><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"><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">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">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">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal"><br clear="all">
<br>
-- <o:p></o:p></p>
<div>
<div>
<table class="MsoNormalTable" border="0" cellspacing="0" cellpadding="0" width="100%" style="width:100.0%;border-collapse:collapse;border-spacing:0px">
<tbody>
<tr>
<td valign="top" style="padding:0cm 0cm 15.0pt 0cm">
<table class="MsoNormalTable" border="0" cellspacing="0" cellpadding="0" align="left" style="border-collapse:collapse;border-spacing:0px">
<tbody>
<tr>
<td width="64" valign="top" style="width:48.0pt;padding:0cm 0cm 0cm 0cm">
<p class="MsoNormal" style="line-height:18.0pt"><span lang="FR-CA" style="font-size:12.5pt;mso-fareast-language:EN-US"><img border="0" width="64" height="24" style="width:.6666in;height:.25in" id="_x0000_i1025" src="https://unity3d.com/profiles/unity3d/themes/unity/images/ui/other/unity-logo-dark-email.png"></span><span lang="FR-CA" style="font-size:12.5pt;mso-fareast-language:EN-US"><o:p></o:p></span></p>
</td>
</tr>
</tbody>
</table>
</td>
</tr>
<tr>
<td valign="top" style="padding:0cm 0cm 0cm 0cm">
<div>
<p class="MsoNormal" style="line-height:11.25pt"><b><span lang="FR-CA" style="font-size:10.5pt;font-family:Roboto;color:black;mso-fareast-language:EN-US">Neil Henning<o:p></o:p></span></b></p>
</div>
</td>
</tr>
<tr>
<td valign="top" style="padding:0cm 0cm 0cm 0cm">
<div>
<p class="MsoNormal" style="line-height:11.25pt"><span lang="FR-CA" style="font-size:10.5pt;font-family:Roboto;color:black;mso-fareast-language:EN-US">Senior Software Engineer Compiler<o:p></o:p></span></p>
</div>
</td>
</tr>
<tr>
<td valign="top" style="padding:0cm 0cm 0cm 0cm">
<div>
<p class="MsoNormal" style="line-height:11.25pt"><span lang="FR-CA" style="mso-fareast-language:EN-US"><a href="http://unity.com" target="_blank"><span style="font-size:9.0pt;font-family:Roboto">unity.com</span></a></span><span lang="FR-CA" style="font-size:9.0pt;font-family:Roboto;color:black;mso-fareast-language:EN-US"><o:p></o:p></span></p>
</div>
</td>
</tr>
</tbody>
</table>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</body>
</html>