This is an archive of the discontinued LLVM Phabricator instance.

[DWARF] - Speedup handling of relocations in DWARFContextInMemory.
ClosedPublic

Authored by grimar on Mar 20 2017, 9:46 AM.

Details

Summary

I am working on a LLD bug "Bug 32228 - -gdb-index is too slow".

One of place I want to start from is a proccessing of relocations. It is usually
a hot place. I noticed that relocations that are proccessed in DWARFContextInMemory often uses
the same symbol in a row.

I took debug LLC binary objects configured with -ggnu-pubnames and linked it using LLD.

  1. Link time without --gdb-index is about 4,45s.
  2. Link time with --gdb-index: a) Without patch: 19,16s b) With patch: 15,52s

That means time spent on --gdb-index in this configuration is
19,16s - 4,45s = 14,71s vs 15,52s - 4,45s = 11,07s.

Total time change spent on building index then is 11,07s/14,71 = 0,7525

Diff Detail

Event Timeline

grimar created this revision.Mar 20 2017, 9:46 AM
dblaikie edited edge metadata.Mar 20 2017, 9:54 AM

Could you dump the relevant relocations in some object files you're testing?

I'd be curious to understand/see why so many relocations to the same symbol appear in a row - and wonder if it'd be good to consider caching all the results, not only the previous/most recent one.

aprantl added inline comments.Mar 20 2017, 9:56 AM
DebugInfo/DWARF/DWARFContext.cpp
627 ↗(On Diff #92339)

Please add comments describing the purpose of the new static helper functions.

641 ↗(On Diff #92339)

We typically spell this as ~1ULL. But, is there a better way of passing the error? Should we use optional<uint64_t> here?

641 ↗(On Diff #92339)

~0(!)ULL of course.

Could you dump the relevant relocations in some object files you're testing?

I'd be curious to understand/see why so many relocations to the same symbol appear in a row - and wonder if it'd be good to consider caching all the results, not only the previous/most recent one.

Uploaded "readelf -a" dump of llc.cpp.o,
notice ".rela.debug_info" sections contains tons of relocations against ".debug_str" section symbol in a row.
Also relocations against other symbols are often grouped as well.

I cached only the last relocation in this patch because I knew dynamic linkers do that.
I can try to experiment with caching more results tomorrow to see what will happen.

rui314 edited subscribers, added: ruiu; removed: rui314.Mar 20 2017, 10:11 AM
grimar updated this revision to Diff 92503.Mar 21 2017, 9:45 AM
  • Addressed review comments.
  • Performed cleanup of error reporting for new getSymbolAddress() method.
DebugInfo/DWARF/DWARFContext.cpp
627 ↗(On Diff #92339)

Done.

641 ↗(On Diff #92339)

I used Expected<>, it was used for SymbolRef::getAddress(), so is it looks consistent to use it here too.

grimar added a comment.Apr 4 2017, 5:46 AM

Ping. (not sure we will use this change in LLD, since D31424 looks better, but it still looks like a good cleanup and speedup for other users. If no I'll abandon this).

grimar updated this revision to Diff 97658.EditedMay 3 2017, 9:09 AM
grimar edited the summary of this revision. (Show Details)
  • Reimplemented to use std::map instead of "is last symbol the same" optimization.

Ping.

FWIW, found one more place where it useful in LLD. It creates DWARFContextInMemory for error reporting for each object (when there are any errors of course).
Since this speedups relocation handling, it should speedup thing a bit. It is not very important probably, because we have default linit for errors amount (20)
and it is not a regular linker path. But anyways all users that creates context for something can have benefit from speedup this patch do.

dblaikie accepted this revision.May 12 2017, 10:33 AM

Still curious to hear back from Adrian - but can revisit this post-commit if he's got any particular perspective to add :)

lib/DebugInfo/DWARF/DWARFContext.cpp
1052

Probably an llvm::DenseMap here?

This revision is now accepted and ready to land.May 12 2017, 10:33 AM
grimar added inline comments.May 12 2017, 10:36 AM
lib/DebugInfo/DWARF/DWARFContext.cpp
1052

I'll do benchmarks at monday for this change then and commit fastest solution then.
Sounds fine ?

dblaikie added inline comments.May 12 2017, 10:42 AM
lib/DebugInfo/DWARF/DWARFContext.cpp
1052

Sure

I don't have an informed opinion at the moment, besides "let's benchmark it", so please go ahead for now. Once we switch over LLDB to use the LLVM DWARF parser I will likely revisit this in more depth.

grimar added inline comments.May 15 2017, 4:48 AM
lib/DebugInfo/DWARF/DWARFContext.cpp
1052

Ah, I just faced it again and now I remember. I already tried to use DenseMap initially, but it would require DenseMapInfo<SymbolRef> specialization, when std::map just wants only operator< which SymbolRef already has.
I would probably don't add this specialization to reduce amount of code for start. I don't expect significant perfomance difference here, so less code is better probably. So I am going to commit std::map version then..

This revision was automatically updated to reflect the committed changes.