Page MenuHomePhabricator

Avoid hash table lookup when sorting local symbols.
AcceptedPublic

Authored by ruiu on Apr 11 2018, 5:52 PM.

Details

Reviewers
espindola
grimar
Summary

Looking up a hash table for each symbol should be avoided for
performance reasons. In this patch, I assign a unique ID to each
file and use that number to sort symbols.

The other way of doing this would be to use object addresses of files,
but that algorithm fails to make output reproducible. So I had to
add FileId member to InputFile class.

Event Timeline

ruiu created this revision.Apr 11 2018, 5:52 PM
grimar requested changes to this revision.Apr 12 2018, 1:53 AM

Will not help I believe. Please see my answer in the D45519 thread.

This revision now requires changes to proceed.Apr 12 2018, 1:53 AM

Numbers I got after re-profiling this place today:

lld-speed-test\mozilla\response-O0.txt
(Configuration: RelWithDebInfo, used MSVS2015 built-in profiler)

Benchmarked execution time of
lld::elf::SymbolTableBaseSection::postThunkContents

  • LLD vanilla r329846: Total CPU (%): 3.42 Total CPU (ms): 246
  • Changed predicate to return L.Sym->File < R.Sym->File; Total CPU (%): 2.3 Total CPU (ms): 161
  • My patch (D45519) applied: Total CPU (%): 0.72 Total CPU (ms): 49
  • This (D45548) patch applied: Total CPU (%): 2.08 Total CPU (ms): 148

Results were pretty stable.
Versions with sorting ((2) and (4)) seem to show almost equal time, and I believe it is expected.
The approach used in my patch (3) is about 3 times faster than them. And does not require additional members.
So IMO it is better.

My idea was actually to combine both patches.

With this patch the map

MapVector<InputFile *, std::vector<SymbolTableEntry>> Arr;

in D45519 can become a simple array, no?

I will benchmark each independently and the combined patch.

espindola added inline comments.Apr 12 2018, 2:13 PM
lld/ELF/SyntheticSections.cpp
1570

Given regular symbol A and an internal symbol B (file is null), this comparison will return false for A < B and B < A.

I think this has to be

if (!L.Sym->File || !R.Sym->File)

return L.Sym->File; // or R.Sym->File.

The results I got

master: 2.819319468 seconds time elapsed
This patch: 2.735310955 seconds time elapsed
D45519: 2.624760166 seconds time elapsed
combined: 2.604495001 seconds time elapsed

So I think we want both.

The results I got

master: 2.819319468 seconds time elapsed
This patch: 2.735310955 seconds time elapsed
D45519: 2.624760166 seconds time elapsed
combined: 2.604495001 seconds time elapsed

So I think we want both.

Thanks for the numbers. For me having combined version is fine. Rui, what do you think? (I'll rebase mine when/if this be landed).

With this patch the map

MapVector<InputFile *, std::vector<SymbolTableEntry>> Arr;

in D45519 can become a simple array, no?

There is one minor issue I am thinking about. We will need the array of size [number of files].
We could use the NextFileId to find array size, but since LLD can be used as a library, we
will have to reset NextFileId to zero value in elf::link, otherwise, we will have a hidden issue here,
which will lead to creating arrays larger than needed.

(this is one line change fix, posted just for the record to not forget. Probably it worth to include that change
to this patch).

grimar accepted this revision.Apr 13 2018, 1:39 AM

LGTM with Rafael's comment addressed.

This revision is now accepted and ready to land.Apr 13 2018, 1:39 AM
espindola accepted this revision.Apr 16 2018, 9:45 AM

LGTM with the sort predicate fixed.

Can it be committed? D45519 depends on this.

grimar added a comment.May 4 2018, 1:44 AM

Rui, can you commit this please? Or do you have any concerns?