[LLVMdev] On LLD performance

[Sean Silva]

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

-- Sean Silva


>
>
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150318/d085dbbc/attachment.html>