<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Mar 12, 2015 at 9:40 AM, David Blaikie <span dir="ltr"><<a href="mailto:dblaikie@gmail.com" target="_blank">dblaikie@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="">On Thu, Mar 12, 2015 at 4:52 AM, Stephan Tolksdorf <span dir="ltr"><<a href="mailto:st@quanttec.com" target="_blank">st@quanttec.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span><br>
On 11.03.2015 23:02, Rui Ueyama wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
An idea to make the resolver faster would be to use a concurrent hash<br>
map to insert new symbols in parallel. Assuming symbols from the same<br>
file don't conflict each other (I think it's a valid assumption), this<br>
can be parallelized. I wanted single-thread performance gain, though.<br>
(Also, concurrent hash maps are not currently available in LLVM.)<br>
</blockquote>
<br></span>
Instead of using a concurrent hash map you could fill multiple hash maps in parallel and then merge them afterwards. If the implementation caches the hash values (which it should for string keys), merging maps doesn't require recomputing the hash values and can be a relatively fast operation when there is only a small overlap between the maps.<br></blockquote></span><div><br>Yeah - I'd wonder more about the process here - each file has non-overlapping items? Are the possibly-overlapping items between files know-able? (only certain kinds of symbols) maybe you can use that to your advantage in some way? (yeah, I know - super vague)</div></div></div></div></blockquote><div><br></div><div>Each file has non-overlapping symbols. We may be able to know possibly-overlapping symbols between files, but I don't know if we can exploit that because it's similar to what the linker actually does.</div><div><br></div><div>We can model an object file using two sets, U and D, containing names of undefined symbols and defined symbols, respectively. For each file, U and D are non-overlapping. Linker has two sets, U' and D', containing name of undefined symbols need to be resolved, and defined symbols it collected so far. It reads files until U' is empty. For each file, new undefined symbols are added or removed by U' = union(U' - D, U - D'). Defined symbols are added by D' = union(D', D). D' grows as we read more files and U' shrinks.</div><div><br></div><div>And there are library files, which gives a linker a choice whether it reads a member file or not. Linker only reads member files who resolves undefined symbols.</div><div><br></div><div>There are also odd stuffs such as COMDAT groups or merge-not-by-name-but-by-content sections, that may complicate the model. (I don't think about that yet.)</div><div><br></div><div>It feels to me what linker does is straightforward and it's hard to improve, but I can't prove. There might be room to improve.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class="">
<br>
More generally, if hash map operations make up a large share of the run time, it might be worth looking for situations where hash values are unnecessarily recomputed, e.g. when an item is conditionally inserted or when a hash map is grown or copied. (This is just a general observation, I don't know anything about LLD's implementation.)<br>
<br>
- Stephan<br></span>
______________________________<u></u>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/<u></u>mailman/listinfo/llvmdev</a><br>
</blockquote></div><br></div></div>
</blockquote></div><br></div></div>