Bug 96037 – IndexedDB: Optimize key decode and comparison operations

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Joshua Bell]

IndexedDB: Optimize key decode and comparison operations

[Joshua Bell]

Created attachment 162617 [details]
Patch

[Joshua Bell]

After some performance optimization work on https://bugs.webkit.org/show_bug.cgi?id=96036, the CPU bottleneck on deleting databases (and presumably other operations) are key comparisons.

We do a lot of unnecessary work when comparing keys, including:
* Slow extractions with multiple data copies
* Full decodes, even when we have optimized "compareEncodedXXX" functions

This shows up in memory allocations occurring during a LevelDB iteration as temporary objects with variable length data are allocated just for the purpose of compares.

(The attached patch is just a WIP; it eliminates some of the allocations but avoiding any allocation when doing a compare is desirable.)

[Joshua Bell]

Created attachment 162841 [details]
Patch

[Joshua Bell]

Latest patch converts "decodeAndCompare" to (effectively) compare-but-only-decode-if-necessary, and adds specializations for two of the common cases that will result in the most compares.

This seems to be a dramatic speedup of the deleteDatabase case on my box, even without the transaction work in http://webkit.org/b/96036 - not a terrible surprise, as the transaction was made slow by the expensive compares!

The current patch is missing a specialization for IndexDataKey which is going to be the next most populous type.

[Joshua Bell]

Created attachment 162883 [details]
Patch

[Joshua Bell]

I completed performance runs - details at http://crbug.com/146586 and pretty graph at:

https://docs.google.com/a/chromium.org/spreadsheet/ccc?key=0AoyP0VKkrFm8dE1VanBfR2Jpa1MwUkxCM1RsZ0RZTnc#gid=0

Seems like it'll be worth both landing this and http://webkit.org/b/96036

alecflett@ - can you take a look before I send this off for review?

[Alec Flett]

Comment on attachment 162883 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=162883&action=review

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:884
>          if (typeByteA == ObjectStoreMetaDataTypeByte)

Is there a reason this can't be a switch (I see it wasn't in the old code, mostly just curious)

[Alec Flett]

Forgot to add "LGTM with or without the switch"

[Joshua Bell]

Comment on attachment 162883 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=162883&action=review

>> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:884
>>          if (typeByteA == ObjectStoreMetaDataTypeByte)
> 
> Is there a reason this can't be a switch (I see it wasn't in the old code, mostly just curious)

No reason. Going to leave it as-is, though.

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:898
>          ASSERT_NOT_REACHED();

Nor am I going to move this above the return statement. :P

[Joshua Bell]

tony@ - r? cq?

[Tony Chang]

Comment on attachment 162883 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=162883&action=review

>> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:898
>>          ASSERT_NOT_REACHED();
> 
> Nor am I going to move this above the return statement. :P

Can you just delete the ASSERT_NOT_REACHED()?  It looks like dead code.

[Joshua Bell]

Created attachment 163408 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 163408 [details]
Patch for landing

Clearing flags on attachment: 163408

Committed r128212: <http://trac.webkit.org/changeset/128212>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[James Robinson]

Lotsa crashes from this:

STDERR: SHOULD NEVER BE REACHED
STDERR: third_party/WebKit/Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp(897) : int WebCore::IDBLevelDBCoding::compare(const WebCore::LevelDBSlice&, const WebCore::LevelDBSlice&, bool)
STDERR: [2175:6522:14854634912430:ERROR:process_util_posix.cc(143)] Received signal 11
STDERR: 	base::debug::StackTrace::StackTrace() [0x7f5f2719115a]
STDERR: 	base::(anonymous namespace)::StackDumpSignalHandler() [0x7f5f271f874d]
STDERR: 	0x7f5f20c0faf0
STDERR: 	WebCore::IDBLevelDBCoding::compare() [0x7f5f2aa5b17b]
STDERR: 	WebCore::Comparator::compare() [0x7f5f2aa6d7e0]
STDERR: 	WebCore::ComparatorAdapter::Compare() [0x7f5f2a8231db]
STDERR: 	leveldb::Version::GetOverlappingInputs() [0x7f5f2a67dc26]
STDERR: 	leveldb::VersionSet::PickCompaction() [0x7f5f2a68072e]
STDERR: 	leveldb::DBImpl::BackgroundCompaction() [0x7f5f2a666703]
STDERR: 	leveldb::DBImpl::BackgroundCall() [0x7f5f2a666328]
STDERR: 	leveldb::DBImpl::BGWork() [0x7f5f2a66629e]
STDERR: 	leveldb::(anonymous namespace)::ChromiumEnv::BGThread() [0x7f5f2a660e38]
STDERR: 	leveldb::(anonymous namespace)::ChromiumEnv::BGThreadWrapper() [0x7f5f2a6609b0]
STDERR: 	leveldb::(anonymous namespace)::Thread::ThreadMain() [0x7f5f2a660c79]
STDERR: 	base::(anonymous namespace)::ThreadFunc() [0x7f5f27231ce7]
STDERR: 	start_thread [0x7f5f20f659ca]
STDERR: 	0x7f5f20cc2cdd

[James Robinson]

Pretty much all of storage/indexeddb seems to be hitting this assertion:

storage/indexeddb (64 tests)
storage/indexeddb/mozilla (4 tests)
http/tests/inspector/indexeddb/database-data.html
http/tests/inspector/indexeddb/database-names.html

[Joshua Bell]

Bleah, wonder why it wasn't caught. Please roll out if you haven't already.

[James Robinson]

Looks like it's just 64 bit.  I'll roll out

[James Robinson]

Reverted r128212 for reason:

Assertion fails on linux 64

Committed r128220: <http://trac.webkit.org/changeset/128220>

[Joshua Bell]

(In reply to comment #11)
> (From update of attachment 162883 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=162883&action=review
> 
> >> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:898
> >>          ASSERT_NOT_REACHED();
> > 
> > Nor am I going to move this above the return statement. :P
> 
> Can you just delete the ASSERT_NOT_REACHED()?  It looks like dead code.

So... rather than removing it I actually moved it above the return - the crashes were this assertion being hit. Made it through the commit queue somehow. :(

The issue is this test:

        if (typeByteA <= 3)
             return 0;

... which is letting through 4 which is UserIntVersion. So that falls through to the "return 0;" in the current code, but would hit the relocated ASSERT_NOT_REACHED().

I've removed the ASSERT_NOT_REACHED and added FIXMEs to (1) say that the magic number should be replaced and possibly account for UserIntVersion, and (2) that there should probably be an ASSERT_NOT_REACHED() before the return 0.

[Joshua Bell]

Created attachment 163456 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 163456 [details]
Patch for landing

Clearing flags on attachment: 163456

Committed r128237: <http://trac.webkit.org/changeset/128237>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.