Bug 96037

Summary: IndexedDB: Optimize key decode and comparison operations
Product: WebKit Reporter: Joshua Bell <jsbell>
Component: New BugsAssignee: Joshua Bell <jsbell>
Status: RESOLVED FIXED    
Severity: Normal CC: alecflett, dgrogan, jamesr, tony, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch
none
Patch
none
Patch
none
Patch for landing
none
Patch for landing none

Description Joshua Bell 2012-09-06 16:29:17 PDT
IndexedDB: Optimize key decode and comparison operations
Comment 1 Joshua Bell 2012-09-06 16:30:26 PDT
Created attachment 162617 [details]
Patch
Comment 2 Joshua Bell 2012-09-06 16:34:14 PDT
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.)
Comment 3 Joshua Bell 2012-09-07 12:10:40 PDT
Created attachment 162841 [details]
Patch
Comment 4 Joshua Bell 2012-09-07 12:14:03 PDT
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.
Comment 5 Joshua Bell 2012-09-07 15:16:51 PDT
Created attachment 162883 [details]
Patch
Comment 6 Joshua Bell 2012-09-10 14:18:57 PDT
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?
Comment 7 Alec Flett 2012-09-10 16:03:14 PDT
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)
Comment 8 Alec Flett 2012-09-10 16:03:33 PDT
Forgot to add "LGTM with or without the switch"
Comment 9 Joshua Bell 2012-09-10 16:18:06 PDT
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
Comment 10 Joshua Bell 2012-09-10 16:18:25 PDT
tony@ - r? cq?
Comment 11 Tony Chang 2012-09-10 16:26:44 PDT
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.
Comment 12 Joshua Bell 2012-09-11 11:20:25 PDT
Created attachment 163408 [details]
Patch for landing
Comment 13 WebKit Review Bot 2012-09-11 11:42:33 PDT
Comment on attachment 163408 [details]
Patch for landing

Clearing flags on attachment: 163408

Committed r128212: <http://trac.webkit.org/changeset/128212>
Comment 14 WebKit Review Bot 2012-09-11 11:42:37 PDT
All reviewed patches have been landed.  Closing bug.
Comment 15 James Robinson 2012-09-11 13:10:24 PDT
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
Comment 16 James Robinson 2012-09-11 13:11:05 PDT
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
Comment 17 Joshua Bell 2012-09-11 13:12:05 PDT
Bleah, wonder why it wasn't caught. Please roll out if you haven't already.
Comment 18 James Robinson 2012-09-11 13:12:56 PDT
Looks like it's just 64 bit.  I'll roll out
Comment 19 James Robinson 2012-09-11 13:14:22 PDT
Reverted r128212 for reason:

Assertion fails on linux 64

Committed r128220: <http://trac.webkit.org/changeset/128220>
Comment 20 Joshua Bell 2012-09-11 15:29:44 PDT
(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.
Comment 21 Joshua Bell 2012-09-11 15:30:00 PDT
Created attachment 163456 [details]
Patch for landing
Comment 22 WebKit Review Bot 2012-09-11 16:18:18 PDT
Comment on attachment 163456 [details]
Patch for landing

Clearing flags on attachment: 163456

Committed r128237: <http://trac.webkit.org/changeset/128237>
Comment 23 WebKit Review Bot 2012-09-11 16:18:22 PDT
All reviewed patches have been landed.  Closing bug.