[webkit-reviews] review granted: [Bug 207183] [WTF] Try using 75% load factor for HashTable : [Attachment 389898] Patch

[bugzilla-daemon at webkit.org]

Mark Lam <mark.lam at apple.com> has granted Yusuke Suzuki <ysuzuki at apple.com>'s
request for review:
Bug 207183: [WTF] Try using 75% load factor for HashTable
https://bugs.webkit.org/show_bug.cgi?id=207183

Attachment 389898: Patch

https://bugs.webkit.org/attachment.cgi?id=389898&action=review




--- Comment #12 from Mark Lam <mark.lam at apple.com> ---
Comment on attachment 389898
  --> https://bugs.webkit.org/attachment.cgi?id=389898
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=389898&action=review

r=me

> Source/WTF/wtf/HashTable.h:492
> +	       return keyAndDeleteCount * maxLoadDenominator >= tableSize *
maxLoadNumerator;

As we discussed offline, let's use 64-bit math here to ensure that there's no
overflow issue.

> Source/WTF/wtf/HashTable.h:568
> +	   constexpr unsigned maxLoadNumerator = 3;
> +	   constexpr unsigned maxLoadDenominator = 4;

Can you put the HashTable's constexprs in a HashTableBase class, make them
public, and just use those here?

Alternatively, instead of making those fields public, make this
capacityForSize() function a private utility method in
HashTableCapacityForSize, and make template<unsigned> struct
HashTableCapacityForSize, a friend of HashTableBase (since capacityForSize() is
only used by HashTableCapacityForSize).

> Source/WTF/wtf/HashTable.h:569
> +	   if (size == 0)

WebKit style: use !size instead of size == 0 (though I personally prefer size
== 0).

> Source/WTF/wtf/HashTable.h:571
> +	   unsigned candidate = roundUpToPowerOfTwo(size);

Let's call this capacity instead of candidate.

> Source/WTF/wtf/HashTable.h:572
> +	   if (size * maxLoadDenominator >= candidate * maxLoadNumerator)

Alternatively, can you put the constexpr shouldExpand in HashTableBase and just
use HashTableBase::shouldExpand(size, capacity) here.

> Source/WTF/wtf/HashTable.h:1231
> +	   // If we are getting halfway between 11/24 and 3/4 (we pick 15/24 ==
5/8), we double the size to avoid being too close to

I suggest rephrasing "(we pick 15/24 == 5/8)" as "(i.e. past 14.5/24, which
we'll round up to 15/24 i.e. 5/8)"

> Source/WTF/wtf/HashTable.h:1232
> +	   // loadMax and bring the ratio close to 11/24. This give us a load
in the bounds [9/24, 15/24).

I haven't figured out how you arrived at the 9/24 number, but the reasoning for
choosing 5/8 is sound to me.

> Source/WTF/wtf/HashTable.h:1233
> +	   bool aboveThreeQuarterLoad = keyCount * 8 >= bestTableSize * 5;

The name aboveThreeQuarterLoad sounds wrong given the math.  Can you use a
better name?

> Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp:58
>      // Adding items up to less than half the capacity should not change the
capacity.

This comment is stale.	Please update.