Investigate HashTable::HashTable(const HashTable&) and HashTable::operator=(const...
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 3 Aug 2015 04:33:15 +0000 (04:33 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 3 Aug 2015 04:33:15 +0000 (04:33 +0000)
commit401664e4ce9dfc523b0f45836d194b2d2ed460ac
treebff297a714a08959c17a4414b94c5a272b45254b
parent8e021cc3a10e60fad01b3133597f30cbe4e559d2
Investigate HashTable::HashTable(const HashTable&) and HashTable::operator=(const HashTable&) performance for hash-based static analyses
https://bugs.webkit.org/show_bug.cgi?id=118455

Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-08-02
Reviewed by Filip Pizlo.

Source/JavaScriptCore:

LivenessAnalysisPhase lights up like a christmas tree in profiles.

This patch cuts its cost by 4.
About half of the gains come from removing many rehash() when copying
the HashSet.
The last quarter is achieved by having a special add() function for initializing
a HashSet.

This makes benchmarks progress by 1-2% here and there. Nothing massive.

* dfg/DFGLivenessAnalysisPhase.cpp:
(JSC::DFG::LivenessAnalysisPhase::process):
The m_live HashSet is only useful per block. When we are done with it,
we can transfer it to liveAtHead to avoid a copy.

Source/WTF:

Previously, when copying a HashTable, we would start from scratch
with an empty table and insert elements one by one, growing-rehashing
the table as needed.

With this patch, we have 2 improvements to remove most of the cost.

First, we compute a good size from the start. This removes all the
reallocations and rehashs.
This is where the biggest gain comes from.

The second part is a simpler version of add() when we know that
we cannot find a bucket with the same key and there cannot
be any deleted bucket.
This removes most branches from the hot loop, cutting another 25%
of the time.

* wtf/HashTable.h:
(WTF::KeyTraits>::addUniqueForInitialization):
(WTF::KeyTraits>::HashTable):

Tools:

* TestWebKitAPI/Tests/WTF/HashSet.cpp:
(TestWebKitAPI::TEST):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@187733 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/HashTable.h
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp