Introduce a FlatMap and FlatSet into WTF

Introduce a FlatMap and FlatSet into WTF

Cache friendly data structures which outperform std::map<> and std::set<> 
for small or static datasets. This patch delivers a ~12% improvement 
to TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues.

Measured on a z620 with the following steps taken to reduce noise:

echo performance | sudo tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
taskset 1 out_linux/Release/blink_platform_perftests --gtest_filter=TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues

Data: https://docs.google.com/spreadsheets/d/1qwsFxSay47rnd3YGs-TOVDxjjwNZKyOuIW8zOKWULVg/edit#gid=0

BUG=

[alex clarke (OOO till 29th), 2016-10-04 21:08:32]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-04 21:09:24]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-04 21:13:33]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-04 21:13:34]

Dry run: Try jobs failed on following builders:
  android_n5x_swarming_rel on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/android_n5x_...)
  linux_android_rel_ng on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/linux_androi...)
  mac_chromium_compile_dbg_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_comp...)
  mac_chromium_rel_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)

[alex clarke (OOO till 29th), 2016-10-06 14:53:06]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-06 14:53:20]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-06 14:56:05]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-06 14:56:06]

Dry run: Try jobs failed on following builders:
  mac_chromium_compile_dbg_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_comp...)

[alex clarke (OOO till 29th), 2016-10-06 15:00:05]

Description was changed from

==========
Introduce a FlatMap and FlatSet into WTF

Cache friendly datasructures which outperform std::map<> and std::set<>
for small datasets.

BUG=
==========

to

==========
Introduce a FlatMap and FlatSet into WTF

Cache friendly data structures which outperform std::map<> and std::set<> for
small datasets.  On the 

BUG=
==========

[alex clarke (OOO till 29th), 2016-10-06 15:00:10]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-06 15:00:32]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-06 15:03:35]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-06 15:03:36]

Dry run: Try jobs failed on following builders:
  cast_shell_linux on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...)
  chromeos_amd64-generic_chromium_compile_only_ng on
master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromeos_amd64-...)
  linux_chromium_chromeos_ozone_rel_ng on master.tryserver.chromium.linux
(JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
  linux_chromium_chromeos_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[alex clarke (OOO till 29th), 2016-10-06 15:18:25]

Description was changed from

==========
Introduce a FlatMap and FlatSet into WTF

Cache friendly data structures which outperform std::map<> and std::set<> for
small datasets.  On the 

BUG=
==========

to

==========
Introduce a FlatMap and FlatSet into WTF

Cache friendly data structures which outperform std::map<> and std::set<> for
small or static datasets.  This patch delivers a ~12% improvement to
TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues.

Measured on a z620 with 

echo performance | sudo tee
/sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
taskset 1 out_linux/Release/blink_platform_perftests
--gtest_filter=TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues

https://docs.google.com/spreadsheets/d/1qwsFxSay47rnd3YGs-TOVDxjjwNZKyOuIW8zO...

BUG=
==========

[alex clarke (OOO till 29th), 2016-10-06 15:22:56]

Description was changed from

==========
Introduce a FlatMap and FlatSet into WTF

Cache friendly data structures which outperform std::map<> and std::set<> for
small or static datasets.  This patch delivers a ~12% improvement to
TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues.

Measured on a z620 with 

echo performance | sudo tee
/sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
taskset 1 out_linux/Release/blink_platform_perftests
--gtest_filter=TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues

https://docs.google.com/spreadsheets/d/1qwsFxSay47rnd3YGs-TOVDxjjwNZKyOuIW8zO...

BUG=
==========

to

==========
Introduce a FlatMap and FlatSet into WTF

Cache friendly data structures which outperform std::map<> and std::set<> 
for small or static datasets. This patch delivers a ~12% improvement 
to TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues.

Measured on a z620 with the following steps taken to reduce noise:

echo performance | sudo tee
/sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
taskset 1 out_linux/Release/blink_platform_perftests
--gtest_filter=TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues

https://docs.google.com/spreadsheets/d/1qwsFxSay47rnd3YGs-TOVDxjjwNZKyOuIW8zO...

BUG=
==========

[alex clarke (OOO till 29th), 2016-10-06 15:23:10]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[alex clarke (OOO till 29th), 2016-10-06 15:23:34]

alexclarke@chromium.org changed reviewers:
+ skyostil@chromium.org

[commit-bot: I haz the power, 2016-10-06 15:23:37]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-06 15:35:43]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-06 15:35:44]

Dry run: Try jobs failed on following builders:
  chromeos_amd64-generic_chromium_compile_only_ng on
master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromeos_amd64-...)

[alex clarke (OOO till 29th), 2016-10-06 16:08:43]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-06 16:09:12]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-06 16:20:41]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-06 16:20:42]

Dry run: Try jobs failed on following builders:
  cast_shell_android on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/cast_shell_a...)
  linux_chromium_chromeos_ozone_rel_ng on master.tryserver.chromium.linux
(JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[alex clarke (OOO till 29th), 2016-10-06 16:26:17]

Patchset #6 (id:100001) has been deleted

[alex clarke (OOO till 29th), 2016-10-06 16:27:30]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-06 16:27:50]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[alex clarke (OOO till 29th), 2016-10-06 16:44:57]

alexclarke@chromium.org changed reviewers:
+ haraken@chromium.org

[alex clarke (OOO till 29th), 2016-10-06 16:44:58]

+haraken

[alex clarke (OOO till 29th), 2016-10-06 16:45:28]

Description was changed from

==========
Introduce a FlatMap and FlatSet into WTF

Cache friendly data structures which outperform std::map<> and std::set<> 
for small or static datasets. This patch delivers a ~12% improvement 
to TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues.

Measured on a z620 with the following steps taken to reduce noise:

echo performance | sudo tee
/sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
taskset 1 out_linux/Release/blink_platform_perftests
--gtest_filter=TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues

https://docs.google.com/spreadsheets/d/1qwsFxSay47rnd3YGs-TOVDxjjwNZKyOuIW8zO...

BUG=
==========

to

==========
Introduce a FlatMap and FlatSet into WTF

Cache friendly data structures which outperform std::map<> and std::set<> 
for small or static datasets. This patch delivers a ~12% improvement 
to TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues.

Measured on a z620 with the following steps taken to reduce noise:

echo performance | sudo tee
/sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
taskset 1 out_linux/Release/blink_platform_perftests
--gtest_filter=TaskQueueManagerPerfTest.RunTenThousandDelayedTasks_ThirtyTwoQueues

Data:
https://docs.google.com/spreadsheets/d/1qwsFxSay47rnd3YGs-TOVDxjjwNZKyOuIW8zO...

BUG=
==========

[commit-bot: I haz the power, 2016-10-06 17:18:17]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-06 17:18:18]

Dry run: Try jobs failed on following builders:
  linux_chromium_chromeos_ozone_rel_ng on master.tryserver.chromium.linux
(JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[alex clarke (OOO till 29th), 2016-10-06 17:37:58]

BTW I think I'll split this up into two patches, and I'll try and add a
comparative perf test vs std::map and WTF::HashMap.

[haraken, 2016-10-07 06:51:17]

haraken@chromium.org changed reviewers:
+ yutak@chromium.org

[haraken, 2016-10-07 06:51:18]

I want to hear an opinion of yutak@, who did a lot of investigations about
HashTable's performance.

I'm personally slightly negative about introducing FlatMap/FlatSet. I agree that
it will significantly speed up small hash tables, but in common cases we cannot
statically estimate how many values will be added to the hash tables. If people
start (mis-)using FlatMap/FlatSet for hash tables that they think would be small
but actually become large, it will end up with regressing performance.

My preference would be to optimize the implementation of the existing HashTable
so that it uses a ring buffer until the table size exceeds some threshold. That
way we can not only avoid introducing new primitive types but also prevent
people from mis-using FlatMap/FlatSet on hash tables where FlatMap/FlatSet
shouldn't be used. I think yutak@ did some experiment around the idea.

[Yuta Kitamura, 2016-10-07 07:46:59]

First just let me check one thing: is this conceptually
similar to google3's dense_hash_map? google3's has some
overhead on memory usage, but I'm not sure if yours is
the same.

I certainly have considered introducing dense_hash_map
equivalent in Blink, but I did not think about that
very deeply. There's certainly room for optimization
for small tables according to our usage pattern. I'm
especially curious about overhead/benefit balance.

[Sami, 2016-10-07 09:49:11]

Looks pretty neat. I'll leave it up to you guys to decide if this makes sense in
the grander scheme of things. It might also be worth having the discussion about
how this compares to base::SmallMap[1] and whether it is feasible to optimize
that instead?

[1]
https://cs.chromium.org/chromium/src/base/containers/small_map.h?q=base+small...

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/wtf/FlatMap.h (right):

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatMap.h:23: // a low number of Elements or it
doesn't change much.
It'd be useful to quantify what "low" means.

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/wtf/FlatSet.h (right):

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatSet.h:65: DISALLOW_COPY_AND_ASSIGN(FlatSet);
STL containers are copyable and assignable -- is there a reason to be different
here?

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/wtf/FlatTable.h (right):

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatTable.h:63: ring_buffer_.resize(4);
Should we make this a named constant?

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatTable.h:141: // O(log n + n / 2)
Maybe document the return value?

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatTable.h:163: if (empty()) {
DCHECK that value is actually unique?

Edit: I guess InsertUniqueImpl kinda does that already.

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatTable.h:253: size_t
InsertUniqueImpl(value_type value) {
Maybe the great renaming will fix this but I find it a bit jarring that we're
50% chrome/blink style here with names :)

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatTable.h:323: void ComputeModulusMask() {
modulus_mask_ = ring_buffer_.size() - 1; }
DCHECK that this is 2^n-1?

[alex clarke (OOO till 29th), 2016-10-07 11:41:13]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-07 11:41:26]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-07 11:50:56]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-07 11:50:57]

Dry run: Try jobs failed on following builders:
  linux_chromium_chromeos_ozone_rel_ng on master.tryserver.chromium.linux
(JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[alex clarke (OOO till 29th), 2016-10-07 11:59:57]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-07 12:00:06]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[alex clarke (OOO till 29th), 2016-10-07 12:02:32]

On 2016/10/07 06:51:18, haraken wrote:
> I want to hear an opinion of yutak@, who did a lot of investigations about
> HashTable's performance.
> 
> I'm personally slightly negative about introducing FlatMap/FlatSet. I agree
that
> it will significantly speed up small hash tables, but in common cases we
cannot
> statically estimate how many values will be added to the hash tables. If
people
> start (mis-)using FlatMap/FlatSet for hash tables that they think would be
small
> but actually become large, it will end up with regressing performance.
> 
> My preference would be to optimize the implementation of the existing
HashTable
> so that it uses a ring buffer until the table size exceeds some threshold.
That
> way we can not only avoid introducing new primitive types but also prevent
> people from mis-using FlatMap/FlatSet on hash tables where FlatMap/FlatSet
> shouldn't be used. I think yutak@ did some experiment around the idea.

That might be interesting to do as well, but for the scheduler use cases HashSet
doesn't help because it's unordered.

FlatMap/FlatSet are associative containers (i.e. they're sorted) so finding and
extracting the lowest value is O(1).

[haraken, 2016-10-07 12:07:36]

On 2016/10/07 12:02:32, alex clarke wrote:
> On 2016/10/07 06:51:18, haraken wrote:
> > I want to hear an opinion of yutak@, who did a lot of investigations about
> > HashTable's performance.
> > 
> > I'm personally slightly negative about introducing FlatMap/FlatSet. I agree
> that
> > it will significantly speed up small hash tables, but in common cases we
> cannot
> > statically estimate how many values will be added to the hash tables. If
> people
> > start (mis-)using FlatMap/FlatSet for hash tables that they think would be
> small
> > but actually become large, it will end up with regressing performance.
> > 
> > My preference would be to optimize the implementation of the existing
> HashTable
> > so that it uses a ring buffer until the table size exceeds some threshold.
> That
> > way we can not only avoid introducing new primitive types but also prevent
> > people from mis-using FlatMap/FlatSet on hash tables where FlatMap/FlatSet
> > shouldn't be used. I think yutak@ did some experiment around the idea.
> 
> That might be interesting to do as well, but for the scheduler use cases
HashSet
> doesn't help because it's unordered.
> 
> FlatMap/FlatSet are associative containers (i.e. they're sorted) so finding
and
> extracting the lowest value is O(1).

Yeah, makes sense. Maybe it's better to discuss this in
platform-architecture-dev@ including wtf/ and base/ experts.

[alex clarke (OOO till 29th), 2016-10-07 12:10:39]

On 2016/10/07 12:07:36, haraken wrote:
> On 2016/10/07 12:02:32, alex clarke wrote:
> > On 2016/10/07 06:51:18, haraken wrote:
> > > I want to hear an opinion of yutak@, who did a lot of investigations about
> > > HashTable's performance.
> > > 
> > > I'm personally slightly negative about introducing FlatMap/FlatSet. I
agree
> > that
> > > it will significantly speed up small hash tables, but in common cases we
> > cannot
> > > statically estimate how many values will be added to the hash tables. If
> > people
> > > start (mis-)using FlatMap/FlatSet for hash tables that they think would be
> > small
> > > but actually become large, it will end up with regressing performance.
> > > 
> > > My preference would be to optimize the implementation of the existing
> > HashTable
> > > so that it uses a ring buffer until the table size exceeds some threshold.
> > That
> > > way we can not only avoid introducing new primitive types but also prevent
> > > people from mis-using FlatMap/FlatSet on hash tables where FlatMap/FlatSet
> > > shouldn't be used. I think yutak@ did some experiment around the idea.
> > 
> > That might be interesting to do as well, but for the scheduler use cases
> HashSet
> > doesn't help because it's unordered.
> > 
> > FlatMap/FlatSet are associative containers (i.e. they're sorted) so finding
> and
> > extracting the lowest value is O(1).
> 
> Yeah, makes sense. Maybe it's better to discuss this in
> platform-architecture-dev@ including wtf/ and base/ experts.

Sure. I'll write some more perf tests so we can understand where std::map<> and
wtf::HashMap beat it
and then loop them in.

[commit-bot: I haz the power, 2016-10-07 12:11:56]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-07 12:11:57]

Dry run: Try jobs failed on following builders:
  chromeos_x86-generic_chromium_compile_only_ng on
master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromeos_x86-ge...)

[alex clarke (OOO till 29th), 2016-10-07 12:14:59]

On 2016/10/07 07:46:59, Yuta Kitamura wrote:
> First just let me check one thing: is this conceptually
> similar to google3's dense_hash_map? google3's has some
> overhead on memory usage, but I'm not sure if yours is
> the same.

Not seen dense_hash_map before, that's quite interesting.  This is different
it's just a sorted ring buffer.

> 
> I certainly have considered introducing dense_hash_map
> equivalent in Blink, but I did not think about that
> very deeply. There's certainly room for optimization
> for small tables according to our usage pattern. I'm
> especially curious about overhead/benefit balance.

It should be possible to run some microbenchamarks.

[alex clarke (OOO till 29th), 2016-10-07 12:16:54]

Patchset #8 (id:160001) has been deleted

[alex clarke (OOO till 29th), 2016-10-07 12:17:02]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-07 12:17:08]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-07 12:24:39]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-07 12:24:40]

Dry run: Try jobs failed on following builders:
  cast_shell_android on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/cast_shell_a...)

[Yuta Kitamura, 2016-10-07 12:32:22]

OK let me take a look next week. (Monday is a national holiday
in Japan, so I'll work on this on next Tuesday.)

Currently, I feel it makes sense to have a container like
this in WTF. Will think about this next week.

[alex clarke (OOO till 29th), 2016-10-07 13:24:17]

Patchset #8 (id:180001) has been deleted

[alex clarke (OOO till 29th), 2016-10-07 13:24:40]

Patchset #7 (id:140001) has been deleted

[alex clarke (OOO till 29th), 2016-10-07 14:15:08]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-07 14:15:22]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-07 14:56:57]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-07 14:56:58]

Dry run: Try jobs failed on following builders:
  cast_shell_linux on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...)

[alex clarke (OOO till 29th), 2016-10-07 17:37:59]

Patchset #8 (id:220001) has been deleted

[alex clarke (OOO till 29th), 2016-10-07 17:38:05]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-07 17:38:29]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-07 17:49:16]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-07 17:49:19]

Dry run: Try jobs failed on following builders:
  chromium_presubmit on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)

[alex clarke (OOO till 29th), 2016-10-10 09:16:58]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-10 09:17:10]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-10 09:26:19]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-10 09:26:20]

Dry run: Try jobs failed on following builders:
  chromium_presubmit on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)

[alex clarke (OOO till 29th), 2016-10-10 17:27:00]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-10 17:27:19]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-10 17:34:42]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-10 17:34:43]

Dry run: Try jobs failed on following builders:
  chromium_presubmit on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)

[alex clarke (OOO till 29th), 2016-10-10 18:27:09]

On 2016/10/07 12:32:22, Yuta Kitamura wrote:
> OK let me take a look next week. (Monday is a national holiday
> in Japan, so I'll work on this on next Tuesday.)
> 
> Currently, I feel it makes sense to have a container like
> this in WTF. Will think about this next week.

Some initial benchmarks:
https://docs.google.com/spreadsheets/d/1kQTss_EzfUpNm8hwHAJFPX3l4ej9HCrbOL8xj...

For the use case I'm interested in for the scheduler, the FlatSet is
significantly faster than std::set for realistic set sizes.

Generally WTF::HashSet is the fastest although for very small sets (<10) FlatSet
beats it sometimes.

Note the graphs are all log scale which understates the differences a little.

I wanted to try boost::flat_set but we don't seem to have that readily
available, it seems to be quite a complex algorithm so it's anyone's guess how
that actually performs in reality.

A couple of criticisms of these benchmarks:

1. The set sizes being a power of 2 is likely bad for FlatSet since the array
has only just grown
2. The cache is not flushed which skews things.

[haraken, 2016-10-11 00:06:13]

On 2016/10/10 18:27:09, alex clarke wrote:
> On 2016/10/07 12:32:22, Yuta Kitamura wrote:
> > OK let me take a look next week. (Monday is a national holiday
> > in Japan, so I'll work on this on next Tuesday.)
> > 
> > Currently, I feel it makes sense to have a container like
> > this in WTF. Will think about this next week.
> 
> Some initial benchmarks:
>
https://docs.google.com/spreadsheets/d/1kQTss_EzfUpNm8hwHAJFPX3l4ej9HCrbOL8xj...
> 
> For the use case I'm interested in for the scheduler, the FlatSet is
> significantly faster than std::set for realistic set sizes.
> 
> Generally WTF::HashSet is the fastest although for very small sets (<10)
FlatSet
> beats it sometimes.
> 
> Note the graphs are all log scale which understates the differences a little.
> 
> I wanted to try boost::flat_set but we don't seem to have that readily
> available, it seems to be quite a complex algorithm so it's anyone's guess how
> that actually performs in reality.
> 
> A couple of criticisms of these benchmarks:
> 
> 1. The set sizes being a power of 2 is likely bad for FlatSet since the array
> has only just grown
> 2. The cache is not flushed which skews things.

Thanks for the performance results! 

I'd suggest moving further discussions to platform-architecture-dev@.

[alex clarke (OOO till 29th), 2016-10-11 10:41:39]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-11 10:41:48]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-11 11:49:29]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-11 11:49:30]

Dry run: Try jobs failed on following builders:
  android_arm64_dbg_recipe on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/android_arm6...)

[alex clarke (OOO till 29th), 2016-10-13 14:16:32]

Lets close this for now

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/wtf/FlatSet.h (right):

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatSet.h:65: DISALLOW_COPY_AND_ASSIGN(FlatSet);
On 2016/10/07 09:49:11, Sami wrote:
> STL containers are copyable and assignable -- is there a reason to be
different
> here?

Done.

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/wtf/FlatTable.h (right):

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatTable.h:141: // O(log n + n / 2)
On 2016/10/07 09:49:11, Sami wrote:
> Maybe document the return value?

Done.

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatTable.h:163: if (empty()) {
On 2016/10/07 09:49:11, Sami wrote:
> DCHECK that value is actually unique?
> 
> Edit: I guess InsertUniqueImpl kinda does that already.

Right, that should be enough?

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatTable.h:253: size_t
InsertUniqueImpl(value_type value) {
On 2016/10/07 09:49:11, Sami wrote:
> Maybe the great renaming will fix this but I find it a bit jarring that we're
> 50% chrome/blink style here with names :)

Done.

https://codereview.chromium.org/2396533004/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/wtf/FlatTable.h:323: void ComputeModulusMask() {
modulus_mask_ = ring_buffer_.size() - 1; }
On 2016/10/07 09:49:11, Sami wrote:
> DCHECK that this is 2^n-1?

Done something similar.