Bug 91813 - IndexedDB: Size the Vector in encodeInt/encodeVarInt/encodeString
Summary: IndexedDB: Size the Vector in encodeInt/encodeVarInt/encodeString
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: WebKit Misc. (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Xingnan Wang
URL:
Keywords:
Depends on: 92730 93364
Blocks:
  Show dependency treegraph
 
Reported: 2012-07-19 21:24 PDT by Xingnan Wang
Modified: 2012-08-07 07:02 PDT (History)
9 users (show)

See Also:


Attachments
Patch (2.42 KB, patch)
2012-07-19 21:34 PDT, Xingnan Wang
no flags Details | Formatted Diff | Diff
Patch (6.92 KB, patch)
2012-07-22 23:49 PDT, Xingnan Wang
no flags Details | Formatted Diff | Diff
Patch (7.28 KB, patch)
2012-07-23 21:28 PDT, Xingnan Wang
no flags Details | Formatted Diff | Diff
Patch (7.81 KB, patch)
2012-07-25 00:26 PDT, Xingnan Wang
no flags Details | Formatted Diff | Diff
Patch (7.54 KB, patch)
2012-07-25 19:21 PDT, Xingnan Wang
no flags Details | Formatted Diff | Diff
Patch (7.59 KB, patch)
2012-08-06 19:28 PDT, Xingnan Wang
no flags Details | Formatted Diff | Diff
Patch (7.59 KB, patch)
2012-08-06 22:07 PDT, Xingnan Wang
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from gce-cr-linux-05 (564.79 KB, application/zip)
2012-08-06 23:05 PDT, WebKit Review Bot
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description Xingnan Wang 2012-07-19 21:24:38 PDT
To avoid memory re-allocation in Vector, set the capability of the Vector in encodeInt and encodeVatInt and set the initial size of Vector in encodeString.
Comment 1 Xingnan Wang 2012-07-19 21:34:22 PDT
Created attachment 153401 [details]
Patch
Comment 2 Joshua Bell 2012-07-20 09:41:01 PDT
Comment on attachment 153401 [details]
Patch

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

LGTM with test nits.

I see three other places where a zero-length Vector<char> is allocated and appended to; would it be worth speculatively giving these a small inline buffer (e.g. 16 bytes) since most IDBKeys will be short?

Also, there is one case (encodeBool) where a vector is sized via a constructor param rather than template param. Can you change it to use the template param style, for consistency? (I was unaware of that style when I wrote it.)


Thanks for going after these FIXMEs!

> Source/WebCore/ChangeLog:11
> +        No new tests - Low level functions covered by existing tests.

You could also mention this is covered by Chromium webkit_unit_tests IDBLevelDBCodingTest.* - this validates the sizes of buffers returned by encodeVarInt.

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:245
> +    Vector<char, 9> ret;

I don't see a test case in Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp for a value that returns a 9-byte buffer. Can you add one?

The test in TEST(IDBLevelDBCodingTest, EncodeVarInt) that encodes -100 should generate this, but it mistakenly calls encodeInt rather than encodeVarInt - can you fix it as part of this patch?
Comment 3 Joshua Bell 2012-07-20 09:44:40 PDT
Comment on attachment 153401 [details]
Patch

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

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:202
> +    Vector<char, 4> ret;

Can you add a const instead of the magic number, e.g.:

size_t maxEncodedIntBytes = 4;
Vector<char, maxEncodedIntBytes> ret;

>> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:245
>> +    Vector<char, 9> ret;
> 
> I don't see a test case in Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp for a value that returns a 9-byte buffer. Can you add one?
> 
> The test in TEST(IDBLevelDBCodingTest, EncodeVarInt) that encodes -100 should generate this, but it mistakenly calls encodeInt rather than encodeVarInt - can you fix it as part of this patch?

Use a const size_t here too (more important, as 9 is not obvious).
Comment 4 Xingnan Wang 2012-07-22 23:49:48 PDT
Created attachment 153740 [details]
Patch
Comment 5 Xingnan Wang 2012-07-22 23:52:31 PDT
Comment on attachment 153401 [details]
Patch

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

>> Source/WebCore/ChangeLog:11
>> +        No new tests - Low level functions covered by existing tests.
> 
> You could also mention this is covered by Chromium webkit_unit_tests IDBLevelDBCodingTest.* - this validates the sizes of buffers returned by encodeVarInt.

Done.

>> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:202
>> +    Vector<char, 4> ret;
> 
> Can you add a const instead of the magic number, e.g.:
> 
> size_t maxEncodedIntBytes = 4;
> Vector<char, maxEncodedIntBytes> ret;

Done.

>>> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:245
>>> +    Vector<char, 9> ret;
>> 
>> I don't see a test case in Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp for a value that returns a 9-byte buffer. Can you add one?
>> 
>> The test in TEST(IDBLevelDBCodingTest, EncodeVarInt) that encodes -100 should generate this, but it mistakenly calls encodeInt rather than encodeVarInt - can you fix it as part of this patch?
> 
> Use a const size_t here too (more important, as 9 is not obvious).

Done.
Comment 6 Xingnan Wang 2012-07-22 23:57:28 PDT
(In reply to comment #2)
> (From update of attachment 153401 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=153401&action=review
> 
> LGTM with test nits.
> 
> I see three other places where a zero-length Vector<char> is allocated and appended to; would it be worth speculatively giving these a small inline buffer (e.g. 16 bytes) since most IDBKeys will be short?

I agree, use 16 in the updated patch, but I am not sure it`s the best value.

> 
> Also, there is one case (encodeBool) where a vector is sized via a constructor param rather than template param. Can you change it to use the template param style, for consistency? (I was unaware of that style when I wrote it.)
> 
> 
> Thanks for going after these FIXMEs!

Recently I am learning the implementation of indexedDB in chromium, I`m very glad that I can do the contribution to this part. Also thanks your review very much.

> 
> > Source/WebCore/ChangeLog:11
> > +        No new tests - Low level functions covered by existing tests.
> 
> You could also mention this is covered by Chromium webkit_unit_tests IDBLevelDBCodingTest.* - this validates the sizes of buffers returned by encodeVarInt.
> 
> > Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:245
> > +    Vector<char, 9> ret;
> 
> I don't see a test case in Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp for a value that returns a 9-byte buffer. Can you add one?
> 
> The test in TEST(IDBLevelDBCodingTest, EncodeVarInt) that encodes -100 should generate this, but it mistakenly calls encodeInt rather than encodeVarInt - can you fix it as part of this patch?
Comment 7 Joshua Bell 2012-07-23 09:12:54 PDT
Comment on attachment 153740 [details]
Patch

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

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:168
> +static const size_t maxEncodedBoolBytes = 1;

I believe the convention is that non-local static consts should start with upper-case, i.e. MaxEncodedBoolBytes.

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:171
> +static const size_t maxEncodedVarIntBytes = 10;

Nice catch that it's 10, not 9!

Can we follow the patter for encodeByte (line 175) and encodeDouble() (line 372) as well?

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.h:48
> +#ifndef DEFAULT_INLINE_BUFFER_SIZE

Is this defined elsewhere? If not, it should probably be a static const size_t for safety.

And instead of 16 (which I suggested!) maybe it should be expressed as the sum of e.g. 1 byte for type prefix + MaxEncodedDoubleBytes (which would handle Number and Date keys)?

> Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp:-190
> -#ifdef NDEBUG

The #ifdef NDEBUG is in there because of http://trac.webkit.org/changeset/121082/trunk/Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp - see https://bugs.webkit.org/show_bug.cgi?id=89625 for discussion. Without the ifdef guard the last case should fail ASSERT(nParam >= 0) in debug builds (but it's the Chromium webkit_unit_tests target which you're probably not building)
Comment 8 Xingnan Wang 2012-07-23 21:28:18 PDT
Created attachment 153951 [details]
Patch
Comment 9 Xingnan Wang 2012-07-23 21:30:01 PDT
Comment on attachment 153740 [details]
Patch

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

Updated the patch.

>> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:168
>> +static const size_t maxEncodedBoolBytes = 1;
> 
> I believe the convention is that non-local static consts should start with upper-case, i.e. MaxEncodedBoolBytes.

Done.

>> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp:171
>> +static const size_t maxEncodedVarIntBytes = 10;
> 
> Nice catch that it's 10, not 9!
> 
> Can we follow the patter for encodeByte (line 175) and encodeDouble() (line 372) as well?

Done.

>> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.h:48
>> +#ifndef DEFAULT_INLINE_BUFFER_SIZE
> 
> Is this defined elsewhere? If not, it should probably be a static const size_t for safety.
> 
> And instead of 16 (which I suggested!) maybe it should be expressed as the sum of e.g. 1 byte for type prefix + MaxEncodedDoubleBytes (which would handle Number and Date keys)?

Done.

>> Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp:-190
>> -#ifdef NDEBUG
> 
> The #ifdef NDEBUG is in there because of http://trac.webkit.org/changeset/121082/trunk/Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp - see https://bugs.webkit.org/show_bug.cgi?id=89625 for discussion. Without the ifdef guard the last case should fail ASSERT(nParam >= 0) in debug builds (but it's the Chromium webkit_unit_tests target which you're probably not building)

Done.
Comment 10 Joshua Bell 2012-07-24 09:26:23 PDT
Comment on attachment 153951 [details]
Patch

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

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.h:49
> +static const size_t MaxEncodedDoubleBytes = 4;

Sorry, one more thing: I think this should be 8.

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.h:50
> +static const size_t MaxEncodedIntBytes = 4;

And this should be 8 too.

You could add ASSERT(ret.size() == MaxEncodedDoubleBytes) and ASSERT(ret.size() <= MaxEncodedVarIntBytes) (etc) to the encodeXXX functions before the return ret; line.

Otherwise, LGTM. You should ask tony@ or haraken@ to review.
Comment 11 Xingnan Wang 2012-07-25 00:26:55 PDT
Created attachment 154283 [details]
Patch
Comment 12 Kentaro Hara 2012-07-25 00:48:09 PDT
Comment on attachment 154283 [details]
Patch

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

Actually I'm not sure if this is really worth doing.

> Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.h:51
> +static const size_t MaxEncodedBoolBytes = 1;
> +static const size_t MaxEncodedByteBytes = 1;
> +static const size_t MaxEncodedDoubleBytes = 8;
> +static const size_t MaxEncodedIntBytes = 8;
> +static const size_t MaxEncodedKeyPrefixBytes = 21;
> +static const size_t MaxEncodedVarIntBytes = 10;

All these values are quite small. Given that Vectors are stack-allocated, I do not think there is any perf & memory difference between your fully-optimized bytes and "let's always use 32 byte".

Please confirm that your fully-optimized bytes win the case where you always use 32 bytes. If you cannot observe any perf or memory win, I would recommend you to use 32 bytes for the following reasons:

- We do not want to mess up the code for what is not worth doing.
- Magic values are buggy. What if 11 were the correct value for MaxEncodedVarIntBytes? Then Vector has to be expanded, which will cause a perf regression. Always using 32 bytes would be more robust.
Comment 13 Xingnan Wang 2012-07-25 01:35:49 PDT
(In reply to comment #12)
> (From update of attachment 154283 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=154283&action=review
> 
> Actually I'm not sure if this is really worth doing.
> 
> > Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.h:51
> > +static const size_t MaxEncodedBoolBytes = 1;
> > +static const size_t MaxEncodedByteBytes = 1;
> > +static const size_t MaxEncodedDoubleBytes = 8;
> > +static const size_t MaxEncodedIntBytes = 8;
> > +static const size_t MaxEncodedKeyPrefixBytes = 21;
> > +static const size_t MaxEncodedVarIntBytes = 10;
> 
> All these values are quite small. Given that Vectors are stack-allocated, I do not think there is any perf & memory difference between your fully-optimized bytes and "let's always use 32 byte".
> 
> Please confirm that your fully-optimized bytes win the case where you always use 32 bytes. If you cannot observe any perf or memory win, I would recommend you to use 32 bytes for the following reasons:
> 
> - We do not want to mess up the code for what is not worth doing.
> - Magic values are buggy. What if 11 were the correct value for MaxEncodedVarIntBytes? Then Vector has to be expanded, which will cause a perf regression. Always using 32 bytes would be more robust.

Hi Kentaro,

I understand your concern, these values are small but they are the maximum values for the Vectors used in each function, which means they will never be expanded or we will never use more memory that these values. For example, MaxEncodedVarIntBytes won`t be larger than 10, because 10 bytes is enough to encode a varint. If we do not use these magic values, the Vectors in those functions will be expanded many times (by append() method) during encoding, which will cause memory re-allocation each time. So in this way we just allocate the memory of Vectors only once.

But "DefaultInlineBufferSize" is different. Through the value we set covers the most cases, it still might be expanded.
Comment 14 Kentaro Hara 2012-07-25 01:39:48 PDT
(In reply to comment #13)
> I understand your concern, these values are small but they are the maximum values for the Vectors used in each function, which means they will never be expanded or we will never use more memory that these values. For example, MaxEncodedVarIntBytes won`t be larger than 10, because 10 bytes is enough to encode a varint. If we do not use these magic values, the Vectors in those functions will be expanded many times (by append() method) during encoding, which will cause memory re-allocation each time. So in this way we just allocate the memory of Vectors only once.

So my suggestion is how about using 32 byte always for those small values? If there is no perf & memory win between 32 byte and your fully-optimized values, I would prefer 32 byte.
Comment 15 Xingnan Wang 2012-07-25 19:21:59 PDT
Created attachment 154526 [details]
Patch
Comment 16 Xingnan Wang 2012-07-25 19:23:06 PDT
(In reply to comment #15)
> Created an attachment (id=154526) [details]
> Patch

Updated the patch as Kentaro`s comment.
Comment 17 Kentaro Hara 2012-07-25 19:27:34 PDT
Comment on attachment 154526 [details]
Patch

Looks OK.
Comment 18 WebKit Review Bot 2012-07-31 00:12:38 PDT
Comment on attachment 154526 [details]
Patch

Clearing flags on attachment: 154526

Committed r124179: <http://trac.webkit.org/changeset/124179>
Comment 19 WebKit Review Bot 2012-07-31 00:12:43 PDT
All reviewed patches have been landed.  Closing bug.
Comment 20 WebKit Review Bot 2012-07-31 02:35:39 PDT
Re-opened since this is blocked by 92730
Comment 21 Joshua Bell 2012-08-06 12:16:48 PDT
(In reply to comment #20)
> Re-opened since this is blocked by 92730

xingnan.wang@intel.com - can you fix and resubmit?

This change to the patch should fix the issue seen in the Chromium build:

- EXPECT_EQ(static_cast<size_t>(9), encodeVarInt(0x7fffffffffffffff).size());
+ EXPECT_EQ(static_cast<size_t>(9), encodeVarInt(0x7fffffffffffffffLL).size());
Comment 22 Xingnan Wang 2012-08-06 19:28:34 PDT
Created attachment 156835 [details]
Patch
Comment 23 Kentaro Hara 2012-08-06 20:14:11 PDT
Comment on attachment 156835 [details]
Patch

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

> Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp:209
> +    EXPECT_EQ(static_cast<size_t>(9), encodeVarInt(0x7fffffffffffffffll).size());

Nit: LL is better than ll. (l is confusing with 1.)
Comment 24 Xingnan Wang 2012-08-06 22:07:35 PDT
Created attachment 156860 [details]
Patch
Comment 25 Xingnan Wang 2012-08-06 22:08:19 PDT
(In reply to comment #23)
> (From update of attachment 156835 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=156835&action=review
> 
> > Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp:209
> > +    EXPECT_EQ(static_cast<size_t>(9), encodeVarInt(0x7fffffffffffffffll).size());
> 
> Nit: LL is better than ll. (l is confusing with 1.)

Done.
Comment 26 Kentaro Hara 2012-08-06 22:11:23 PDT
Comment on attachment 156860 [details]
Patch

Looks OK
Comment 27 WebKit Review Bot 2012-08-06 23:05:11 PDT
Comment on attachment 156860 [details]
Patch

Attachment 156860 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/13449367

New failing tests:
http/tests/misc/bad-charset-alias.html
Comment 28 WebKit Review Bot 2012-08-06 23:05:15 PDT
Created attachment 156872 [details]
Archive of layout-test-results from gce-cr-linux-05

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: gce-cr-linux-05  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.39-gcg-201203291735-x86_64-with-Ubuntu-10.04-lucid
Comment 29 Xingnan Wang 2012-08-06 23:42:08 PDT
(In reply to comment #27)
> (From update of attachment 156860 [details])
> Attachment 156860 [details] did not pass chromium-ews (chromium-xvfb):
> Output: http://queues.webkit.org/results/13449367
> 
> New failing tests:
> http/tests/misc/bad-charset-alias.html

It confused me that the patch caused http test failed.
Comment 30 Kentaro Hara 2012-08-06 23:43:23 PDT
Comment on attachment 156860 [details]
Patch

The build bot looks confused. Try to cq+ again.
Comment 31 WebKit Review Bot 2012-08-07 01:16:56 PDT
Comment on attachment 156860 [details]
Patch

Clearing flags on attachment: 156860

Committed r124865: <http://trac.webkit.org/changeset/124865>
Comment 32 WebKit Review Bot 2012-08-07 01:17:02 PDT
All reviewed patches have been landed.  Closing bug.
Comment 33 Csaba Osztrogonác 2012-08-07 07:02:17 PDT
(In reply to comment #31)
> (From update of attachment 156860 [details])
> Clearing flags on attachment: 156860
> 
> Committed r124865: <http://trac.webkit.org/changeset/124865>

It broke ARM Chromium build - https://bugs.webkit.org/show_bug.cgi?id=93364
Could you check and fix it, please?