[LLVMdev] On LLD performance

[Benjamin Kramer]

On Wed, Mar 18, 2015 at 9:35 PM, Sean Silva <chisophugis at gmail.com> wrote:
>
>
> On Tue, Mar 17, 2015 at 9:36 PM, Davide Italiano <davide at freebsd.org> wrote:
>>
>> On Mon, Mar 16, 2015 at 11:00 PM, David Blaikie <dblaikie at gmail.com>
>> wrote:
>> >
>> >
>> > On Mon, Mar 16, 2015 at 10:52 PM, Davide Italiano <davide at freebsd.org>
>> > wrote:
>> >>
>> >> On Mon, Mar 16, 2015 at 1:54 AM, Davide Italiano <davide at freebsd.org>
>> >> wrote:
>> >> >
>> >> > Shankar's parallel for per-se didn't introduce any performance
>> >> > benefit
>> >> > (or regression).
>> >> > If the change I propose is safe, I would like to see Shankar's change
>> >> > in (and this on top of it).
>> >> > I have other related changes coming next, but I would like to tackle
>> >> > them one at a time.
>> >> >
>> >>
>> >> Here's an update.
>> >>
>> >> After http://reviews.llvm.org/D8372 , I updated the profiling data.
>> >>
>> >> https://people.freebsd.org/~davide/llvm/lld-03162015.svg
>> >> It seems now 85% of CPU time is spent inside
>> >> FileArchive::buildTableOfContents().
>> >> In particular, 35% of the samples are spent inserting into
>> >> unordered_map, so there's maybe something we can do differently there
>> >> (e.g. , Rui's proposal of a concurrent map doesn't seem that bad).
>> >
>> >
>> > Anyone tried a DenseMap instead of an unordered_map? If you need pointer
>> > validity to the elements, a DenseMap with unique_ptrs rather than direct
>> > values could be an option. Chandler's usual argument here is that
>> > walking
>> > the map is cheap with high locality (as in a DenseMap) even if the nodes
>> > themselves involve indirection. Could be worth an experiment.
>> >
>>
>> I did now. It actually makes things slower for the aforementioned
>> workload (linking clang). It was worth trying though.
>>
>> Patch, in case somebody wants to try at home:
>> https://people.freebsd.org/~davide/llvm/densemap_membermap.diff
>
>
> FYI we have StringMap which is specialized for strings. Also I'm sort of
> amazed that StringMap is using HashString (bernstein) instead of the fairly
> sophisticated hash functionality we have in ADT/Hashing.h

I tried using the new hashing back when Hashing.h was written. The
result was that there were fewer collisions, but the hash function was
significantly slower. Result was a net regression in runtime.

- Ben
>
>>
>>
>>
>> Patched:
>> real    1m27.849s  user    2m47.373s   sys     0m16.370s
>> real    1m29.583s  user    2m47.771s   sys     0m16.816s
>> real    1m25.956s  user    2m43.397s   sys     0m15.254s
>> real    1m29.380s  user    2m47.618s   sys     0m15.386s
>> real    1m25.426s  user    2m43.388s   sys     0m16.961s
>>
>> Unpatched:
>> real    1m26.872s  user    2m46.999s sys     0m16.540s
>> real    1m28.187s  user    2m47.084s sys     0m17.149s
>> real    1m24.814s  user    2m43.311s  sys     0m16.979s
>> real    1m25.011s  user    2m43.184s  sys     0m16.975s
>> real    1m25.536s  user    2m44.577s  sys     0m16.784s
>>
>> --
>> Davide
>>
>> "There are no solved problems; there are only problems that are more
>> or less solved" -- Henri Poincare
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>