This is an archive of the discontinued LLVM Phabricator instance.

[ELF] - Speedup -r and --emit-relocs
ClosedPublic

Authored by grimar on Sep 21 2017, 4:30 AM.

Details

Summary

This is "Bug 34688 - lld much slower than bfd when linking the linux kernel"

Inside copyRelocations() we have O(N*M) algorithm, where N - amount of
relocations and M - amount of symbols in symbol table. It isincredibly slow for linking linux kernel.

Patch creates local search tables to speedup.
With this fix link time goes for me from 12.95s to 0.55s what is almost 23x faster. (used release LLD).

Diff Detail

Event Timeline

grimar created this revision.Sep 21 2017, 4:30 AM
ruiu edited edge metadata.Sep 21 2017, 10:47 AM

Honestly this doesn't look good. I cannot point out how you can improve it at the moment, but your new helper functions handle too low-level things. Such details shouldn't be leaked here.

grimar updated this revision to Diff 116346.Sep 22 2017, 7:19 AM
  • Reimplemented.
In D38129#877829, @ruiu wrote:

Honestly this doesn't look good. I cannot point out how you can improve it at the moment, but your new helper functions handle too low-level things. Such details shouldn't be leaked here.

What do you think about new version ? It incapsulates all low level logic inside SymbolTableSection class.

grimar updated this revision to Diff 116348.Sep 22 2017, 7:47 AM
  • Removed stale comment.
ruiu added inline comments.Sep 22 2017, 10:54 AM
ELF/SyntheticSections.cpp
1363

Flip the condition and swap then and else.

1366–1371

You should use lookup instead of find.

grimar updated this revision to Diff 116505.Sep 25 2017, 3:03 AM
  • Addressed review comments.
ruiu added inline comments.Sep 25 2017, 10:57 AM
ELF/SyntheticSections.cpp
1356–1358

is -> are
allow to -> allow us to

Probably a better comment is just: Initializes a symbol lookup table lazily. This is used only for -r or -emit-relocs.

1362–1365

I think the following comment suffices.

// Section symbols are mapped based on their output sections to maintain their semantics.
ELF/SyntheticSections.h
422–424 ↗(On Diff #116505)

Rename OnceFlag, SymbolIndexMap and SectionIndexMap.

grimar updated this revision to Diff 116650.Sep 26 2017, 1:33 AM
  • Addressed review comments.
ELF/SyntheticSections.cpp
1356–1358

Used "Initializes a symbol lookup tables lazily. This is used only for -r or -emit-relocs.".

ruiu accepted this revision.Sep 26 2017, 5:39 PM

LGTM

ELF/SyntheticSections.cpp
1356–1357

Remove "a".

This revision is now accepted and ready to land.Sep 26 2017, 5:39 PM
This revision was automatically updated to reflect the committed changes.