IndexedDB: Replace O(n^2) algorithm computing multientry index keys

IndexedDB: Replace O(n^2) algorithm computing multientry index keys

Replace a stupid O(n^2) algorithm for ensuring that multientry keys are
unique with an O(n log n) (sort then remove duplicates)

BUG=681980
Review-Url: https://codereview.chromium.org/2635403002
Cr-Commit-Position: refs/heads/master@{#444489}
Committed: https://chromium.googlesource.com/chromium/src/+/d84c00297b927bf972fa30578cf8217f84f34a8a

[jsbell, 2017-01-18 00:59:35]

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

[commit-bot: I haz the power, 2017-01-18 01:00:18]

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

[jsbell, 2017-01-18 01:00:22]

jsbell@chromium.org changed reviewers:
+ pwnall@chromium.org

[jsbell, 2017-01-18 01:00:22]

pwnall@ - please take a look?

[pwnall, 2017-01-18 02:35:19]

LGTM with a couple of small comments.

Nice perf find!

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp (right):

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp:109: KeyArray result;
Would it make sense to add a comment stating that we're not using HeapHashSet
because getting rid of the log factor isn't worth the code size/complexity of
having to implement DefaultHash<IDBKey>?

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/modules/indexeddb/IDBObjectStore.cpp (right):

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/modules/indexeddb/IDBObjectStore.cpp:333:
indexKeys->appendVector(indexKey->array());
Would it make sense to have IDBKey::createMultiEntryArray return a KeyArray, and
pass the return type directly to appendVector()?

codesearch says that IDBKey::createMultiEntryArray isn't called elsewhere, and
removing the packing/unpacking could let you get rid of some code.
Performance-wise, I'd expect/hope that RVO would make it free to return the
vector directly (no unnecessary copies).

[commit-bot: I haz the power, 2017-01-18 02:40:30]

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

[commit-bot: I haz the power, 2017-01-18 02:40:31]

Dry run: This issue passed the CQ dry run.

[jsbell, 2017-01-18 18:18:56]

Thanks, can you take another look pwnall?

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp (right):

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp:109: KeyArray result;
On 2017/01/18 02:35:19, pwnall wrote:
> Would it make sense to add a comment stating that we're not using HeapHashSet
> because getting rid of the log factor isn't worth the code size/complexity of
> having to implement DefaultHash<IDBKey>?

I'm not sure why that is worth calling out. A hash lookup is O(log n) but we do
n inserts so that's O(n log n) to build the set, same as the sort.

What am I missing?

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/modules/indexeddb/IDBObjectStore.cpp (right):

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/modules/indexeddb/IDBObjectStore.cpp:333:
indexKeys->appendVector(indexKey->array());
On 2017/01/18 02:35:19, pwnall wrote:
> Would it make sense to have IDBKey::createMultiEntryArray return a KeyArray,
and
> pass the return type directly to appendVector()?
> 
> codesearch says that IDBKey::createMultiEntryArray isn't called elsewhere, and
> removing the packing/unpacking could let you get rid of some code.
> Performance-wise, I'd expect/hope that RVO would make it free to return the
> vector directly (no unnecessary copies).

Done; also made it non-static to simplify further.

[pwnall, 2017-01-18 19:04:15]

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp (right):

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp:109: KeyArray result;
On 2017/01/18 18:18:56, jsbell wrote:
> On 2017/01/18 02:35:19, pwnall wrote:
> > Would it make sense to add a comment stating that we're not using
HeapHashSet
> > because getting rid of the log factor isn't worth the code size/complexity
of
> > having to implement DefaultHash<IDBKey>?
> 
> I'm not sure why that is worth calling out. A hash lookup is O(log n) but we
do
> n inserts so that's O(n log n) to build the set, same as the sort.
> 
> What am I missing?

If I'm reading HashTable.h correctly, we're using an open-addressing hash table
implementation in WTF, which should give us lookups and insertions in O(1)
amortized.

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/modules/indexeddb/IDBObjectStore.cpp (right):

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/modules/indexeddb/IDBObjectStore.cpp:333:
indexKeys->appendVector(indexKey->array());
On 2017/01/18 18:18:56, jsbell wrote:
> On 2017/01/18 02:35:19, pwnall wrote:
> > Would it make sense to have IDBKey::createMultiEntryArray return a KeyArray,
> and
> > pass the return type directly to appendVector()?
> > 
> > codesearch says that IDBKey::createMultiEntryArray isn't called elsewhere,
and
> > removing the packing/unpacking could let you get rid of some code.
> > Performance-wise, I'd expect/hope that RVO would make it free to return the
> > vector directly (no unnecessary copies).
> 
> Done; also made it non-static to simplify further.

Cool, nice find!

[jsbell, 2017-01-18 19:39:56]

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp (right):

https://codereview.chromium.org/2635403002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp:109: KeyArray result;
On 2017/01/18 19:04:15, pwnall wrote:
> If I'm reading HashTable.h correctly, we're using an open-addressing hash
table
> implementation in WTF, which should give us lookups and insertions in O(1)
> amortized.

Ah, right. Sleepy josh is sleepy. I'll add a note.

[jsbell, 2017-01-18 19:44:36]

The CQ bit was checked by jsbell@chromium.org

[jsbell, 2017-01-18 19:44:37]

The patchset sent to the CQ was uploaded after l-g-t-m from pwnall@chromium.org
Link to the patchset: https://codereview.chromium.org/2635403002/#ps100001
(title: "add comment about hashtable")

[commit-bot: I haz the power, 2017-01-18 19:45:24]

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, 2017-01-18 21:31:00]

CQ is committing da patch.

Bot data: {"patchset_id": 100001, "attempt_start_ts": 1484768676950760,
"parent_rev": "9a437d715c1a675df47945d02fa351c38fd7be17", "commit_rev":
"d84c00297b927bf972fa30578cf8217f84f34a8a"}

[commit-bot: I haz the power, 2017-01-18 21:31:30]

Description was changed from

==========
IndexedDB: Replace O(n^2) algorithm computing multientry index keys

Replace a stupid O(n^2) algorithm for ensuring that multientry keys are
unique with an O(n log n) (sort then remove duplicates)

BUG=681980
==========

to

==========
IndexedDB: Replace O(n^2) algorithm computing multientry index keys

Replace a stupid O(n^2) algorithm for ensuring that multientry keys are
unique with an O(n log n) (sort then remove duplicates)

BUG=681980

Review-Url: https://codereview.chromium.org/2635403002
Cr-Commit-Position: refs/heads/master@{#444489}
Committed:
https://chromium.googlesource.com/chromium/src/+/d84c00297b927bf972fa30578cf8...
==========

[commit-bot: I haz the power, 2017-01-18 21:31:32]

Committed patchset #6 (id:100001) as
https://chromium.googlesource.com/chromium/src/+/d84c00297b927bf972fa30578cf8...