[LLVMdev] On LLD performance

[David Blaikie]

On Thu, Mar 12, 2015 at 4:52 AM, Stephan Tolksdorf <st at quanttec.com> wrote:

>
> On 11.03.2015 23:02, Rui Ueyama wrote:
>
>> An idea to make the resolver faster would be to use a concurrent hash
>> map to insert new symbols in parallel. Assuming symbols from the same
>> file don't conflict each other (I think it's a valid assumption), this
>> can be parallelized. I wanted single-thread performance gain, though.
>> (Also, concurrent hash maps are not currently available in LLVM.)
>>
>
> 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.
>

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)


>
> 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.)
>
> - Stephan
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150312/3ed1953c/attachment.html>