Avoid argument copying in WTF hash-based containers

Avoid argument copying in WTF hash-based containers

The 'KeyPeekInType' used by WTF hash-based containers is declared as 'const T&' for most of the classes, the const reference however was lost in the previous implemntation of HashTable 'contains(KeyPeekInType)' and 'find(KeyPeekInType)' methods as it was deduced to 'T' in the further sub-calls (i.e. template<typename HashTranslator, typename T> ValueType* lookup(T)). This led to unneeded argument copying (2 times per each contains/find call!) and it significantly affected the performance for containers having String or AtomicString key types, such containers are widely used for example in Blink core/css code.

Below is the improvement of some randomly taken CSS performance tests results after the patch is applied (Linux desktop x64):
StyleSheetInsert.html - 3.4%
before:
avg 45.81039999999348 ms
median 45.569000000000415 ms
stdev 1.1590581657568524 ms
min 44.60299999993822 ms
max 48.70600000003833 ms

after:
avg 44.08615000000964 ms
median 44.036000000005515 ms
stdev 0.5594090185250097 ms
min 43.43600000004244 ms
max 45.64000000004853 ms

AttributeDescendantSelector.html - 7%
before:
avg 630.7230679370987 runs/s
median 631.5237186271941 runs/s
stdev 1.8378708385437512 runs/s
min 627.7266878002865 runs/s
max 632.970649942742 runs/s

after:
avg 676.0284840644981 runs/s
median 675.6238838914546 runs/s
stdev 2.1139085234317543 runs/s
min 673.3117355645138 runs/s
max 678.8715588063761 runs/s

CSSPropertyUpdateValue.html - 1.7%
before:
avg 16820.037469368264 runs/s
median 16812.805624173976 runs/s
stdev 70.629520115344 runs/s
min 16647.24488097132 runs/s
max 16989.1959332111 runs/s

after:
avg 17089.45990524665 runs/s
median 17093.550656512787 runs/s
stdev 54.79615592821426 runs/s
min 16962.157162336156 runs/s
max 17179.8873301988 runs/s

This patch also reduces content_shell binary size by 52KB.

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

[Mikhail, 2015-06-18 15:03:29]

mikhail.pozdnyakov@intel.com changed reviewers:
+ erik.corry@gmail.com, tkent@chromium.org

[Mikhail, 2015-06-18 15:04:44]

PTAL

[tkent, 2015-06-18 23:41:50]

https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashMapTest.cpp
File Source/wtf/HashMapTest.cpp (right):

https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashMapTest.cpp#...
Source/wtf/HashMapTest.cpp:317: static int counter;
counter -> s_counter

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

https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashTable.h#newc...
Source/wtf/HashTable.h:902: inline auto HashTable<Key, Value, Extractor,
HashFunctions, Traits, KeyTraits, Allocator>::find(KeyPeekInType key) ->
iterator {
I don't think we allow trailing return type though it is not blacklisted.  So,
please avoid it, or propose to allow it in chromium-dev.

https://chromium-cpp.appspot.com/

[Mikhail, 2015-06-29 11:03:27]

mikhail.pozdnyakov@intel.com changed reviewers:
+ thakis@chromium.org

[Mikhail, 2015-06-29 11:05:24]

On 2015/06/18 23:41:50, unavailable_until_Jul3 wrote:
> https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashMapTest.cpp
> File Source/wtf/HashMapTest.cpp (right):
> 
>
https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashMapTest.cpp#...
> Source/wtf/HashMapTest.cpp:317: static int counter;
> counter -> s_counter
Done.

> 
> https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashTable.h
> File Source/wtf/HashTable.h (right):
> 
>
https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashTable.h#newc...
> Source/wtf/HashTable.h:902: inline auto HashTable<Key, Value, Extractor,
> HashFunctions, Traits, KeyTraits, Allocator>::find(KeyPeekInType key) ->
> iterator {
> I don't think we allow trailing return type though it is not blacklisted.  So,
> please avoid it, or propose to allow it in chromium-dev.

I think it was allowed as a part of lambda semantics, @Nico should trailing
return type be discussed separately in ML?
> 
> https://chromium-cpp.appspot.com/
Thanks!

[Nico, 2015-06-29 16:12:44]

On Mon, Jun 29, 2015 at 4:05 AM, <mikhail.pozdnyakov@intel.com> wrote:

> On 2015/06/18 23:41:50, unavailable_until_Jul3 wrote:
>
>>
>> https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashMapTest.cpp
>> File Source/wtf/HashMapTest.cpp (right):
>>
>
>
>
>
https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashMapTest.cpp#...
>
>> Source/wtf/HashMapTest.cpp:317: static int counter;
>> counter -> s_counter
>>
> Done.
>
>
>  https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashTable.h
>> File Source/wtf/HashTable.h (right):
>>
>
>
>
>
https://codereview.chromium.org/1176303008/diff/1/Source/wtf/HashTable.h#newc...
>
>> Source/wtf/HashTable.h:902: inline auto HashTable<Key, Value, Extractor,
>> HashFunctions, Traits, KeyTraits, Allocator>::find(KeyPeekInType key) ->
>> iterator {
>> I don't think we allow trailing return type though it is not
>> blacklisted.  So,
>> please avoid it, or propose to allow it in chromium-dev.
>>
>
> I think it was allowed as a part of lambda semantics, @Nico should trailing
> return type be discussed separately in ML?
>

I think they're "generally allowed" only for lambdas. For regular
functions, trailing return types only make sense out of line. This is an
out-of-line function where the return type would have to be spelled
HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits,
Allocator>::iterator so I think this is the only case where having this
makes sense – so I think this is fine.

To unsubscribe from this group and stop receiving emails from it, send an email
to blink-reviews+unsubscribe@chromium.org.

[Mikhail, 2015-06-30 10:17:36]

On 2015/06/29 16:12:44, Nico wrote:
> On Mon, Jun 29, 2015 at 4:05 AM, <mailto:mikhail.pozdnyakov@intel.com> wrote:
> > I think it was allowed as a part of lambda semantics, @Nico should trailing
> > return type be discussed separately in ML?
> >
> 
> I think they're "generally allowed" only for lambdas. For regular
> functions, trailing return types only make sense out of line. This is an
> out-of-line function where the return type would have to be spelled
> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits,
> Allocator>::iterator so I think this is the only case where having this
> makes sense – so I think this is fine.
> 
thanks for clarification! saying that, do you think
https://codereview.chromium.org/1129373003/ would make sense?

[Nico, 2015-06-30 18:31:32]

On 2015/06/30 10:17:36, Mikhail wrote:
> On 2015/06/29 16:12:44, Nico wrote:
> > On Mon, Jun 29, 2015 at 4:05 AM, <mailto:mikhail.pozdnyakov@intel.com>
wrote:
> > > I think it was allowed as a part of lambda semantics, @Nico should
trailing
> > > return type be discussed separately in ML?
> > >
> > 
> > I think they're "generally allowed" only for lambdas. For regular
> > functions, trailing return types only make sense out of line. This is an
> > out-of-line function where the return type would have to be spelled
> > HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits,
> > Allocator>::iterator so I think this is the only case where having this
> > makes sense – so I think this is fine.
> > 
> thanks for clarification! saying that, do you think
> https://codereview.chromium.org/1129373003/ would make sense?

I'm more +0 than -0 on that change I guess :-P

[tkent, 2015-07-03 00:10:53]

lgtm

[Mikhail, 2015-07-03 12:23:31]

Win bot fails: the newly added test cannot pass on Windows:

hashmaptest.cpp(353): error: Value of: CopyCounter::s_counter
  Actual: 2
Expected: 0

(I'd like to note though that there is still an improvement as s_counter == 4
without the hash table changes is applied) 

Right now I do not have Win Environment to find a fix for that so I'm merely
changing the expected results for MSVC,
@tkent, @Nico is it OK for you?

[tkent, 2015-07-06 00:34:28]

On 2015/07/03 12:23:31, Mikhail (OOO until Jul 13) wrote:
> Right now I do not have Win Environment to find a fix for that so I'm merely
> changing the expected results for MSVC,
> @tkent, @Nico is it OK for you?

No.  We don't need to be hurry to land this CL.  Please investigate the MSVC
issue.

[Mikhail, 2015-07-22 10:11:18]

On 2015/07/06 00:34:28, tkent wrote:
> On 2015/07/03 12:23:31, Mikhail (OOO until Jul 13) wrote:
> > Right now I do not have Win Environment to find a fix for that so I'm merely
> > changing the expected results for MSVC,
> > @tkent, @Nico is it OK for you?
> 
> No.  We don't need to be hurry to land this CL.  Please investigate the MSVC
> issue.

I cannot reproduce it on Win 8.1 VS2013. What is the build environment in the
bots? I see that bots have Win 7
(http://build.chromium.org/p/tryserver.blink/buildslaves/vm791-m4) but how do I
know the compiler version used there?

[tkent, 2015-07-24 02:19:24]

On 2015/07/22 10:11:18, Mikhail wrote:
> On 2015/07/06 00:34:28, tkent wrote:
> > On 2015/07/03 12:23:31, Mikhail (OOO until Jul 13) wrote:
> > > Right now I do not have Win Environment to find a fix for that so I'm
merely
> > > changing the expected results for MSVC,
> > > @tkent, @Nico is it OK for you?
> > 
> > No.  We don't need to be hurry to land this CL.  Please investigate the MSVC
> > issue.
> 
> I cannot reproduce it on Win 8.1 VS2013. What is the build environment in the
> bots? I see that bots have Win 7
> (http://build.chromium.org/p/tryserver.blink/buildslaves/vm791-m4) but how do
I
> know the compiler version used there?

I think the bots use VS2013.
I reproduced the issue, that is to say the final s_counter was 2, with Windows 7
+ VS2013 (cl.exe v18.00.31101 for x86).

[Mikhail, 2015-07-27 14:49:36]

On 2015/07/24 02:19:24, tkent wrote:
> On 2015/07/22 10:11:18, Mikhail wrote:
> > On 2015/07/06 00:34:28, tkent wrote:
> > > On 2015/07/03 12:23:31, Mikhail (OOO until Jul 13) wrote:
> > > > Right now I do not have Win Environment to find a fix for that so I'm
> merely
> > > > changing the expected results for MSVC,
> > > > @tkent, @Nico is it OK for you?
> > > 
> > > No.  We don't need to be hurry to land this CL.  Please investigate the
MSVC
> > > issue.
> > 
> > I cannot reproduce it on Win 8.1 VS2013. What is the build environment in
the
> > bots? I see that bots have Win 7
> > (http://build.chromium.org/p/tryserver.blink/buildslaves/vm791-m4) but how
do
> I
> > know the compiler version used there?
> 
> I think the bots use VS2013.
> I reproduced the issue, that is to say the final s_counter was 2, with Windows
7
> + VS2013 (cl.exe v18.00.31101 for x86).

I'm having Windows 8.1 + VS2013 (cl.exe 18.0.31101.0) and I can reproduce it in
Debug mode only.

[tkent, 2015-07-27 23:11:47]

On 2015/07/27 14:49:36, Mikhail wrote:
> > I think the bots use VS2013.
> > I reproduced the issue, that is to say the final s_counter was 2, with
Windows
> 7
> > + VS2013 (cl.exe v18.00.31101 for x86).
> 
> I'm having Windows 8.1 + VS2013 (cl.exe 18.0.31101.0) and I can reproduce it
in
> Debug mode only.

I checked with Debug build.  Try bots use Release + Assert setting.  So,
assertions affects the result.

[Mikhail, 2015-07-28 14:40:19]

On 2015/07/27 23:11:47, tkent wrote:
> On 2015/07/27 14:49:36, Mikhail wrote:
> > > I think the bots use VS2013.
> > > I reproduced the issue, that is to say the final s_counter was 2, with
> Windows
> > 7
> > > + VS2013 (cl.exe v18.00.31101 for x86).
> > 
> > I'm having Windows 8.1 + VS2013 (cl.exe 18.0.31101.0) and I can reproduce it
> in
> > Debug mode only.
> 
> I checked with Debug build.  Try bots use Release + Assert setting.  So,
> assertions affects the result.

Right, when the assertions are enabled (even on release build) the arg. copies
turn up, now I've disabled the test on Win if assertions are enabled.

[tkent, 2015-07-28 22:26:44]

On 2015/07/28 14:40:19, Mikhail wrote:
> Right, when the assertions are enabled (even on release build) the arg. copies
> turn up, now I've disabled the test on Win if assertions are enabled.

Why asserts make copies?  Disabling the new test without understanding the root
cause is not acceptable.

[Mikhail, 2015-07-30 09:18:57]

On 2015/07/28 22:26:44, tkent wrote:
> On 2015/07/28 14:40:19, Mikhail wrote:
> > Right, when the assertions are enabled (even on release build) the arg.
copies
> > turn up, now I've disabled the test on Win if assertions are enabled.
> 
> Why asserts make copies?  Disabling the new test without understanding the
root
> cause is not acceptable.

Enabling assertions causes calling of
'ASSERT((HashTableKeyChecker<...>::checkKey(key)));' from HashTable::lookup().
Further we have there !HashTranslator::equal(KeyTraits::emptyValue(), key); and
'KeyTraits::emptyValue()' is leading to an unneeded copy!
Looks like this is a generic issue with WTF containers in Blink on Win.

static T emptyValue() { return T(); } // No RVO with VS2013

In the latest patch I have a workaround for the test in order to keep it
enabled:

   static CopyCounter emptyValue()
    {
        CopyCounter empty;
        return empty;  // now NRVO works
    }


MSDN says that there are few cases when optimization won't actually kick in
https://msdn.microsoft.com/en-us/library/ms364057%28vs.80%29.aspx#nrvo_cpp05_...
but I'm yet not sure why RVO does not work in this particular case.

[tkent, 2015-07-30 23:55:54]

lgtm.  Thank you for the analysis!

https://codereview.chromium.org/1176303008/diff/100001/Source/wtf/HashMapTest...
File Source/wtf/HashMapTest.cpp (right):

https://codereview.chromium.org/1176303008/diff/100001/Source/wtf/HashMapTest...
Source/wtf/HashMapTest.cpp:340: static CopyCounter emptyValue()
Please add a comment why this is necessary.

[Mikhail, 2015-07-31 09:48:51]

The CQ bit was checked by mikhail.pozdnyakov@intel.com

[Mikhail, 2015-07-31 09:48:51]

The patchset sent to the CQ was uploaded after l-g-t-m from tkent@chromium.org
Link to the patchset: https://codereview.chromium.org/1176303008/#ps120001
(title: "Added explanation comment")

[commit-bot: I haz the power, 2015-07-31 09:49:16]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1176303008/120001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1176303008/120001

[commit-bot: I haz the power, 2015-07-31 12:45:43]

Committed patchset #7 (id:120001) as
https://src.chromium.org/viewvc/blink?view=rev&revision=199826

[johnme, 2015-07-31 15:21:05]

A revert of this CL (patchset #7 id:120001) has been created in
https://codereview.chromium.org/1261953005/ by johnme@chromium.org.

The reason for reverting is: This broke HashMapTest.LookupNoKeyCopies on WebKit
Win7 (dbg) and WebKit Win Oilpan (dbg):

http://test-results.appspot.com/dashboards/flakiness_dashboard.html#tests=Has....

[Mikhail, 2015-08-03 10:10:43]

Patchset #8 (id:140001) has been deleted