HomePhabricator

Optimize resolver by using std::unordered_multimap.
Audit RequiredrL231432

Description

Optimize resolver by using std::unordered_multimap.

_reverseRef is a multimap from atoms to atoms. The map contains
reverse edges of "layout-before" and "group" edges for dead-stripping.

The type of the variable was DenseMap<Atom *, DenseSet<Atom *>>.
This patch changes that to std::unordered_multimap<Atom *, Atom *>.

A DenseMap with a value type of DenseSet was not fast. Inserting 900k
items to the map took about 1.6 seconds on my workstation.
unordered_multimap on the other hand took only 0.6 seconds.
Use of the map also got faster -- originally markLive took 1.3 seconds
in the same test case, and it now took 1.0 seconds. In total we shove
off 1.3 seconds out of 27 seconds in that test case.

Details

Auditors
Bigcheese
Committed
ruiuMar 5 2015, 4:22 PM
Parents
rL231431: Add a download link to the web page (PR22764)
Branches
Unknown
Tags
Unknown