Page MenuHomePhabricator

ELF: New symbol table design.
ClosedPublic

Authored by pcc on Apr 29 2016, 4:48 PM.

Details

Summary

This patch implements a new design for the symbol table that stores
SymbolBodies within a memory region of the Symbol object. Symbols are mutated
by constructing SymbolBodies in place over existing SymbolBodies, rather
than by mutating pointers. As mentioned in the initial proposal [1], this
memory layout helps reduce the cache miss rate by improving memory locality.

Performance numbers:

old(s) new(s)

Without debug info:
chrome 7.178 6.432 (-11.5%)
LLVMgold.so 0.505 0.502 (-0.5%)
clang 0.954 0.827 (-15.4%)
llvm-as 0.052 0.045 (-15.5%)
With debug info:
scylla 5.695 5.613 (-1.5%)
clang 14.396 14.143 (-1.8%)

Performance counter results show that the fewer required indirections is
indeed the cause of the improved performance. For example, when linking
chrome, stalled cycles decreases from 14,556,444,002 to 12,959,238,310, and
instructions per cycle increases from 0.78 to 0.83. We are also executing
many fewer instructions (15,516,401,933 down to 15,002,434,310), probably
because we spend less time allocating SymbolBodies.

The new mechanism by which symbols are added to the symbol table is by calling
add* functions on the SymbolTable. In order to make this work for untemplated
file types such as BitcodeFile, I split SymbolTable into an untemplated base
class and a templated derived class.

In this patch, I handle local symbols by storing them inside "unparented"
SymbolBodies. This is suboptimal, but if we do want to try to avoid allocating
these SymbolBodies, we can probably do that separately.

I also removed a few members from the SymbolBody class that were only being
used to pass information from the input file to the symbol table.

This patch implements the new design for the ELF linker only. Once we're
happy with the new implementation, I intend to prepare a similar patch for
the COFF linker. I have updated the documentation under the assumption that
we will update both linkers, but we can probably land this first.

[1] http://lists.llvm.org/pipermail/llvm-dev/2016-April/098832.html

Diff Detail

Repository
rL LLVM

Event Timeline

pcc updated this revision to Diff 55688.Apr 29 2016, 4:48 PM
pcc retitled this revision from to ELF: New symbol table design..
pcc updated this object.
pcc added reviewers: ruiu, rafael, davide, grimar.
pcc added a subscriber: llvm-commits.
ruiu edited edge metadata.Apr 29 2016, 7:17 PM

This is generally looking good. First round of review comments.

ELF/InputFiles.h
126–127 ↗(On Diff #55688)

I think it's better to make Symtab globally accessible just like Config object. It is a singleton, and it is accessed everywhere (Writer is using it, symbol resolution of course uses it, and now file parsing is starting to use it.)

190 ↗(On Diff #55688)

Can we merge SymbolTableBase with SymbolTable<ELFT> if you template this, ArchiveFile::parse and BitcodeFile::parse functions?

ELF/LTO.cpp
112 ↗(On Diff #55688)

undefine -> Undefine

ELF/SymbolTable.cpp
136 ↗(On Diff #55688)

This comment seems obsolete.

266 ↗(On Diff #55688)

Can you define two variables for P's members and use std::tie?

293 ↗(On Diff #55688)

Please separate the pair members so that we can give explicit name for each member.

330 ↗(On Diff #55688)

auto -> int

rafael edited edge metadata.Apr 30 2016, 12:44 PM

I really like where this is going. I can also reproduce the speed improvements:

chromium

master 5.024864816
patch  4.623026768 0.92003007788

chromium fast

master 1.79596235
patch  1.674374543 0.932299356387

the gold plugin

master 0.380117134
patch  0.35906784 0.9446241905

clang

master 0.661575233
patch  0.623685952 0.942728688878

llvm-as

master 0.036052227
patch  0.034932404 0.968938867494

the gold plugin fsds

master 0.407010562
patch  0.384177885 0.943901512315

clang fsds

master 0.74843173
patch  0.704943104 0.941893663434

llvm-as fsds

master 0.032178185
patch  0.031151157 0.968083097291

scylla

master 4.159922688
patch  4.089454365 0.983060184459
ELF/InputFiles.h
212 ↗(On Diff #55688)

I am really happy to see these temporary vectors go. We now only have object local vector of symbols when something refers to them by index (relocations) :-)

ELF/Symbols.h
427 ↗(On Diff #55688)

Using ELF64LE is here is problematic as the SharedSymbol has a pointer to Elf_Sym. As silly as it sounds I think you need to include the various ELFTs in the "union".

And can this be just a plain union?

  • void parse(); -
  • llvm::MutableArrayRef<LazyObject> getLazySymbols() { return LazySymbols; } + void parse(SymbolTableBase *Symtab);

    ---------------- Can we merge SymbolTableBase with SymbolTable<ELFT> if you template this, ArchiveFile::parse and BitcodeFile::parse functions?

I assume these vectors make it hard:

std::vector<std::unique_ptr<ObjectFile<ELFT>>> ObjectFiles;

std::vector<std::unique_ptr<SharedFile<ELFT>>> SharedFiles;

Cheers,
Rafael

emaste added a subscriber: emaste.Apr 30 2016, 1:44 PM
pcc updated this revision to Diff 55732.Apr 30 2016, 6:37 PM
pcc marked 7 inline comments as done.
pcc edited edge metadata.
  • Merge SymbolTableBase and SymbolTable, and add Symtab global
  • Fix merge error
  • Remove some unused members of SymbolBody
  • undefine -> Undefine
  • Remove obsolete comment
  • auto Cmp -> int Cmp
  • Use std::tie
ELF/InputFiles.h
190 ↗(On Diff #55688)

I can, done. I'm not sure if it's a good idea to add more template bloat like this, but we can probably think about that separately.

ELF/Symbols.h
427 ↗(On Diff #55688)

All I need is an appropriately sized and aligned char array. That's what AlignedCharArrayUnion provides. I never actually access this field as a SharedSymbol<ELF64LE> for example (unless of course I'm in a templated function with ELFT=ELF64LE). I'm making an assumption here that ELF32* data structures are not larger or more aligned than ELF64* data structures (and the same for LE and BE), but if they somehow are not, that's what the static_asserts below are for.

I think this could be a union, but we'd need default constructors in every derived class of SymbolBody, and I think we'd need to use the unrestricted unions feature of C++, which MSVC doesn't support until 2015.

Just some cursory code review because I was curious to see the implementation (the aligned storage usage, etc) - nothing vital, feel free to take-or-leave as you see fit.

ELF/MarkLive.cpp
141–142 ↗(On Diff #55688)

(unrelated cleanup: this could/should just be dyn_cast_or_null)

ELF/SymbolTable.cpp
282–283 ↗(On Diff #55688)

Should this just be an else-if?

334–335 ↗(On Diff #55688)

else-after-return

369–373 ↗(On Diff #55688)

Seems to be a bit of inconsistency about whether single line blocks have {} or not here (& elsewhere in this change)

451 ↗(On Diff #55688)

Could invert this & use an early return to reduce indentation, perhaps.

489–490 ↗(On Diff #55688)

Could roll these together with dyn_cast_or_null

ELF/Symbols.h
63–65 ↗(On Diff #55688)

I think, technically, from a UB perspective, you want to implement the non-const version in terms of the const version rather than the other way around.

If this object were really const then you'd have UB const_casting it and calling a member function. But if you do it the other way - you just call a const operation, knowing you have a non-const object, and cast away the constness of the result because you know it's not really const.

431 ↗(On Diff #55688)

Same here (wrt const/non-const overload implementation)

And can this be just a plain union?

All I need is an appropriately sized and aligned char array. That's what AlignedCharArrayUnion provides. I never actually access this field as a SharedSymbol<ELF64LE> for example (unless of course I'm in a templated function with ELFT=ELF64LE). I'm making an assumption here that ELF32* data structures are not larger or more aligned than ELF64* data structures (and the same for LE and BE), but if they somehow are not, that's what the static_asserts below are for.

Got it. Please add a comment :-)

I liked the non templated base, but yes, we can discuss that in another patch.

Cheers,
Rafael

In any case. I am happy with this patch if others are happy.

We can discuss templating less code in another patch.

pcc updated this revision to Diff 55733.Apr 30 2016, 8:16 PM
pcc marked 6 inline comments as done.
  • A few simplifications from David
  • Improve comment for Symbol::Body
pcc added a comment.Apr 30 2016, 8:16 PM

Got it. Please add a comment :-)

Done

ELF/Symbols.h
63–65 ↗(On Diff #55732)

I see. I think all the Symbol objects we ever create are in fact non-const, so this is somewhat of a moot point. Writing these the other way around would I think be a little more verbose, so I'll keep this the way it is. Thanks for pointing that out though.

davide accepted this revision.Apr 30 2016, 8:31 PM
davide edited edge metadata.

Thank for doing this, I found your code to be up to 15% faster while linking some FreeBSD system binaries.
As a general comment, I find the new logic slightly easier to understand, so my hope is that you convert the COFF linker once you get a chance. I don't find any obvious problems with the patch, and others commented at length on the style, so I have very little to add. lgtm.

This revision is now accepted and ready to land.Apr 30 2016, 8:31 PM
This revision was automatically updated to reflect the committed changes.