Inline HashTable::find() methods for performance

Inline HashTable::find() methods for performance

Inline HashTable::find() methods for performance and remove unnecessary
null checks for m_table as this check is already done inside
HashTable::lookup(). Also move the m_table null-check to the beginning of
HashTable::lookup() to avoid unnecessary initialization and hashing when
m_table is null.

This change improves Bindings/get-element-by-id's score by 8-10% (tested on
Linux desktop). This patch is a follow-up to r164029 which replaced a call
to HashMap::get() by one to HashMap::find() in DocumentOrderedMap::get(),
causing a performance regression in Bindings/get-element-by-id micro benchmark.
pprof confirmed that HashTable::find() calls were really hot (26% of the time
spent in them).

Despite the inlining, the size of the release binary is actually ~54Kb smaller
with gcc 4.7, likely because the compiler is able to optimize further (e.g. by
removing redundant code).

BUG=330778
R=eseidel, cevans

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=164387

[abarth-chromium, 2013-12-30 17:27:06]

Neat!  LGTM

[Chris Evans, 2013-12-30 20:50:54]

Cool. Thanks for not using the blunt hammer of ALWAYS_INLINE :-)

LGTM with one nit and one thing to think about (does not need to be tackled with
this CL unless you're inspired):

The existing inline hint for HashTable<Key, Value, Extractor, HashFunctions,
Traits, KeyTraits>::lookup(const T& key) is a bit clunky. The function is large
so the compiler might well ignore the hint. Or if it universally obeys the hint,
we have a lot of code bloat!

Furthermore, this CL seems to be observing that we desire fast lookup on a
completely empty HashMap / HashSet etc.

Putting the two together, perhaps we could have a lookupFastPath which is
declared with an inline hint, and simply does the m_table==NULL check before
calling lookupSlowPath (which could still be declared inline to keep it the same
as existing code). This way, we've given the compiler more room to inline just
the fast path that handles a completely empty table.

https://codereview.chromium.org/117123003/diff/1/Source/wtf/HashTable.h
File Source/wtf/HashTable.h (right):

https://codereview.chromium.org/117123003/diff/1/Source/wtf/HashTable.h#newco...
Source/wtf/HashTable.h:823: return false;
You can remove this one too right?

[Inactive, 2013-12-30 21:14:04]

On 2013/12/30 20:50:54, Chris Evans wrote:
> Cool. Thanks for not using the blunt hammer of ALWAYS_INLINE :-)
> 
> LGTM with one nit and one thing to think about (does not need to be tackled
with
> this CL unless you're inspired):
> 
> The existing inline hint for HashTable<Key, Value, Extractor, HashFunctions,
> Traits, KeyTraits>::lookup(const T& key) is a bit clunky. The function is
large
> so the compiler might well ignore the hint. Or if it universally obeys the
hint,
> we have a lot of code bloat!
> 
> Furthermore, this CL seems to be observing that we desire fast lookup on a
> completely empty HashMap / HashSet etc.
> 
> Putting the two together, perhaps we could have a lookupFastPath which is
> declared with an inline hint, and simply does the m_table==NULL check before
> calling lookupSlowPath (which could still be declared inline to keep it the
same
> as existing code). This way, we've given the compiler more room to inline just
> the fast path that handles a completely empty table.

In the micro-benchmark I was working on (Bindings/get-element-by-id), the
HashTable is actually not empty. I moved the m_table null check to the beginning
of lookup() because the null check was previously done *before* calling lookup()
and I removed that null check in my patch. I wanted to limit the chances of my
patch introducing a regression in the null case because we would now be doing
the string hashing uselessly in that case.

[Inactive, 2013-12-30 21:14:14]

https://codereview.chromium.org/117123003/diff/1/Source/wtf/HashTable.h
File Source/wtf/HashTable.h (right):

https://codereview.chromium.org/117123003/diff/1/Source/wtf/HashTable.h#newco...
Source/wtf/HashTable.h:823: return false;
On 2013/12/30 20:50:55, Chris Evans wrote:
> You can remove this one too right?

Right, good catch. Done.

[commit-bot: I haz the power, 2013-12-30 21:14:45]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/ch.dumez@samsung.com/117123003/80001

[commit-bot: I haz the power, 2013-12-30 22:14:21]

Change committed as 164387