New issue
Advanced search Search tips

Issue 681980 link

Starred by 1 user
Status: Verified
Owner:
jsb...@chromium.org
Closed: Jan 2017
Cc:
jakearchibald@chromium.org
dmu...@chromium.org
pwnall@chromium.org
Components:
EstimatedDays: ----
NextAction: ----
OS: ----
Pri: 2
Type: Bug



Sign in to add a comment

Index key computation scales poorly

Project Member Reported by jsb...@chromium.org, Jan 17 2017 
Putting a value with lots of index keys scales very poorly - bad algorithm?

  const store = db.createObjectStore('words', {autoIncrement: true});
  const index = store.createIndex('words', '', {multiEntry: true});

  const count = 100000;
  const words = [];
  for (let i = 0; i < count; ++i)
    words.push(String(Math.random()));

  const tx = db.transaction('words', 'readwrite');
  const store = tx.objectStore('words');
  const r = store.put(words);

On my system, the put() times are:

count = 1e3 --> 14ms
count = 1e4 --> 649ms
count = 1e5 --> 48324ms

Comment 1 by jsb...@chromium.org, Jan 17 2017 

In the multiEntry case, the code in generateIndexKeysForValue() does a push_back() for each entry. Possibly just thrashing if we don't reserve space ahead of time.

(Also, need to make sure the array() call is cheap. That's been bad before...)

Comment 2 by jsb...@chromium.org, Jan 18 2017

Status: Started (was: Available)
IDBKey::createMultiEntryArray is O(n^2). Derp.
Project Member

Comment 3 by bugdroid1@chromium.org, Jan 18 2017 

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/d84c00297b927bf972fa30578cf8217f84f34a8a

commit d84c00297b927bf972fa30578cf8217f84f34a8a
Author: jsbell <jsbell@chromium.org>
Date: Wed Jan 18 21:30:55 2017

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}

[modify] https://crrev.com/d84c00297b927bf972fa30578cf8217f84f34a8a/third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp
[modify] https://crrev.com/d84c00297b927bf972fa30578cf8217f84f34a8a/third_party/WebKit/Source/modules/indexeddb/IDBKey.h
[modify] https://crrev.com/d84c00297b927bf972fa30578cf8217f84f34a8a/third_party/WebKit/Source/modules/indexeddb/IDBObjectStore.cpp

Comment 4 by pwnall@chromium.org, Jan 18 2017 

I'm in the process of using the code above to verify the fix.

Under Chrome 55 on OSX 10.12, the attached code produces the following times:

1000 values: 6.794999999999959ms
10000 values: 533.735ms
100000 values: 54765.62ms
b681980.html
1.5 KB View Download

Comment 5 by jsb...@chromium.org, Jan 18 2017

Status: Fixed (was: Started)

Comment 6 by pwnall@chromium.org, Jan 19 2017

Status: Verified (was: Fixed)
Closing the loop, as my Chromium build just finished.

After the change, the same code above produces the following times.

1000 values: 16.024999999999977ms
10000 values: 132.55999999999995ms
100000 values: 1377.9250000000004ms

This looks close enough to O(N * logN) for me.
►

Sign in to add a comment