Bug 91813 – IndexedDB: Size the Vector in encodeInt/encodeVarInt/encodeString

• Status: RESOLVED
• Resolution: FIXED
• Component: WebKit Misc.

[Xingnan Wang]

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.

[Xingnan Wang]

Created attachment 153401 [details]
Patch

[Joshua Bell]

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?

[Joshua Bell]

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).

[Xingnan Wang]

Created attachment 153740 [details]
Patch

[Xingnan Wang]

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.

[Xingnan Wang]

(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?

[Joshua Bell]

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)

[Xingnan Wang]

Created attachment 153951 [details]
Patch

[Xingnan Wang]

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.

[Joshua Bell]

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.

[Xingnan Wang]

Created attachment 154283 [details]
Patch

[Kentaro Hara]

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.

[Xingnan Wang]

(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.

[Kentaro Hara]

(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.

[Xingnan Wang]

Created attachment 154526 [details]
Patch

[Xingnan Wang]

(In reply to comment #15)
> Created an attachment (id=154526) [details]
> Patch

Updated the patch as Kentaro`s comment.

[Kentaro Hara]

Comment on attachment 154526 [details]
Patch

Looks OK.

[WebKit Review Bot]

Comment on attachment 154526 [details]
Patch

Clearing flags on attachment: 154526

Committed r124179: <http://trac.webkit.org/changeset/124179>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[WebKit Review Bot]

Re-opened since this is blocked by 92730

[Joshua Bell]

(In reply to comment #20)
> Re-opened since this is blocked by 92730

[e-mail] - 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());

[Xingnan Wang]

Created attachment 156835 [details]
Patch

[Kentaro Hara]

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.)

[Xingnan Wang]

Created attachment 156860 [details]
Patch

[Xingnan Wang]

(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.

[Kentaro Hara]

Comment on attachment 156860 [details]
Patch

Looks OK

[WebKit Review Bot]

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

[WebKit Review Bot]

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

[Xingnan Wang]

(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.

[Kentaro Hara]

Comment on attachment 156860 [details]
Patch

The build bot looks confused. Try to cq+ again.

[WebKit Review Bot]

Comment on attachment 156860 [details]
Patch

Clearing flags on attachment: 156860

Committed r124865: <http://trac.webkit.org/changeset/124865>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Csaba Osztrogonác]

(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?