Bug 118455 – Investigate HashTable::HashTable(const HashTable&) and HashTable::operator=(const HashTable&) performance for hash-based static analyses

• Component: Web Template Framework
• Status: RESOLVED FIXED

[Filip Pizlo]

Currently HashTable::HashTable(const HashTable&) does a dumb copy, and HashTable::operator=(const HashTable&) deletes the existing backing store and uses the machinery of the copy-constructor.

It's likely that this can be improved, for static analyses that use HashSets. Taking a HashSet that has 10ish elements and replacing its contents with that of another HashSet that also has 10ish elements will probably work better if we (a) don't free and then allocate the backing store and (b) just memcpy the elements if possible.  There are a bunch of optimizations we can do here, and it's not clear yet if we need them, but it's definitely worth investigating.

This is related to https://bugs.webkit.org/show_bug.cgi?id=118338, since the SSA work will lead to more static analyses using hashes, and it will copy the hashes a lot, in a fixpoint.

[Sam Weinig]

Finally. I have been meaning to improve this for a long time. (We should also make sure we have a good move constructor).

[Darin Adler]

Sam's point about a move constructor is a good one. That's trivial to write and we should do it ASAP.

Obvious starting point for the copy constructor is to reuse the layout of the hash table. Allocate one of the same size and just move over the slots. Hard to see a reason that would be a bad thing. And that solves most of the badness.

Then there's Phil’s comment that we should use memcpy when we can. Might take a bit of traits work to enable that optimization.

Assignment operator should not need to change. It should be plenty efficient to implement it in terms of copy and swap.

Move assignment operator should also be easy to build out of a move constructor and swap.

[Benjamin Poulain]

Created attachment 257982 [details]
Patch

[WebKit Commit Bot]

Attachment 257982 [details] did not pass style-queue:


ERROR: Source/WTF/wtf/HashTable.h:810:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Total errors found: 1 in 6 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Removing "fourthTier" prefix since we used that for code that landed on the old FTL branch.

[Benjamin Poulain]

Committed r187733: <http://trac.webkit.org/changeset/187733>

[Csaba Osztrogonác]

(In reply to comment #6)
> Committed r187733: <http://trac.webkit.org/changeset/187733>

It broke the Apple Windows build:

..\PageLoadTestClient.cpp(237): error C2039: 'wtf_pow' : is not a member of 'std' [C:\cygwin\home\buildbot\slave\win-release\build\Tools\WinLauncher\WinLauncher.vcxproj\WinLauncherLib.vcxproj]

[Alex Christensen]

http://trac.webkit.org/changeset/187738