This is an archive of the discontinued LLVM Phabricator instance.

Switch the new COFF linker's symbol table to use a DenseMap of StringRefs. This uses the LLVM hashing rather than the standard library and a closed addressed hash table rather than chaining.
ClosedPublic

Authored by chandlerc on Jun 24 2015, 3:19 AM.

Details

Summary

This improves the Windows self-link of LLD by 4.4% (averaged over 10
runs, with well under 1% of variance on each).

There is still some room to improve here. Two things I clearly see in
the profile:

  1. This is one of the biggest stress tests for the LLVM hashing code. It actually consumes something like 3-4% of the link time after the change.
  2. The way that StringRef keys are handled in the DenseMap interface is pretty suboptimal. We pay the price of checking for empty and tombstone keys when we could only possibly be looking for a normal key. But fixing this requires invasive API changes.

So there is still some headroom here.

Diff Detail

Event Timeline

chandlerc updated this revision to Diff 28326.Jun 24 2015, 3:19 AM
chandlerc retitled this revision from to Switch the new COFF linker's symbol table to use a DenseMap of StringRefs. This uses the LLVM hashing rather than the standard library and a closed addressed hash table rather than chaining..
chandlerc updated this object.
chandlerc edited the test plan for this revision. (Show Details)
chandlerc added a reviewer: ruiu.
chandlerc added a subscriber: Unknown Object (MLST).
ruiu accepted this revision.Jun 24 2015, 9:18 AM
ruiu edited edge metadata.

LGTM. Nice.

One thing I want to mention is that the hash table used for the symbol table is append-only. We never remove any item from the hash table. All newly inserted keys are unique, so once a key-value pair is inserted, they will never change. Not sure if it helps you optimize it more (probably not), but that's an interesting property of the symbol table compared to other generic hash table uses.

This revision is now accepted and ready to land.Jun 24 2015, 9:18 AM
This revision was automatically updated to reflect the committed changes.