Changeset 95682 in webkit

Timestamp:

Sep 21, 2011 4:44:20 PM (13 years ago)

Author:

commit-queue@webkit.org

Message:

IndexedDB: compare strings without decoding
​https://bugs.webkit.org/show_bug.cgi?id=68554

Patch by Joshua Bell <​jsbell@chromium.org> on 2011-09-21
Reviewed by Tony Chang.

Resolves a FIXME in IndexedDB that was also identified as a hotspot
during profiling. Yields a small performance improvement.

• Source/WebCore/storage/IDBLevelDBCoding.cpp:
• Source/WebCore/storage/IDBLevelDBCoding.h:
• Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp:

Location:

trunk

Files:

• ChangeLog (modified) (1 diff)
• Source/WebCore/storage/IDBLevelDBCoding.cpp (modified) (3 diffs)
• Source/WebCore/storage/IDBLevelDBCoding.h (modified) (1 diff)
• Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp (modified) (2 diffs)

trunk/ChangeLog

@@ -1 @@
-2011-09-21  Leandro Pereira  <leandro@profusion.mobi>
+2011-09-21  Joshua Bell  <jsbell@chromium.org>
+
+        IndexedDB: compare strings without decoding
+        https://bugs.webkit.org/show_bug.cgi?id=68554
+
+        Reviewed by Tony Chang.
+
+        Resolves a FIXME in IndexedDB that was also identified as a hotspot
+        during profiling. Yields a small performance improvement.
+
+        * Source/WebCore/storage/IDBLevelDBCoding.cpp:
+        * Source/WebCore/storage/IDBLevelDBCoding.h:
+        * Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp:
+
+011-09-21  Leandro Pereira  <leandro@profusion.mobi>
 
         Unreviewed. Remove unused ENABLE_AS_IMAGE flag after r95234 from

trunk/Source/WebCore/storage/IDBLevelDBCoding.cpp

@@ -299 +299 @@
     p += len * 2;
     return p;
+}
+
+int compareEncodedStringsWithLength(const char* p, const char* limitP, const char* q, const char* limitQ)
+{
+    ASSERT(limitP >= p);
+    ASSERT(limitQ >= q);
+    int64_t lenP, lenQ;
+    p = decodeVarInt(p, limitP, lenP);
+    q = decodeVarInt(q, limitQ, lenQ);
+    ASSERT(p && q);
+    ASSERT(lenP >= 0);
+    ASSERT(lenQ >= 0);
+    ASSERT(p + lenP * 2 <= limitP);
+    ASSERT(q + lenQ * 2 <= limitQ);
+
+    const size_t lmin = static_cast<size_t>(lenP < lenQ ? lenP : lenQ);
+    if (int x = memcmp(p, q, lmin * 2))
+        return x;
+
+    if (lenP == lenQ)
+        return 0;
+
+    return (lenP > lenQ) ? 1 : -1;
 }
 
@@ -442 +465 @@
     unsigned char typeB = *q++;
 
-    String s, t;
     double d, e;
 
@@ -455 +477 @@
     case kIDBKeyStringTypeByte:
         // String type.
-        p = decodeStringWithLength(p, limitA, s); // FIXME: Compare without actually decoding the String!
-        ASSERT(p);
-        q = decodeStringWithLength(q, limitB, t);
-        ASSERT(q);
-        return codePointCompare(s, t);
+        return compareEncodedStringsWithLength(p, limitA, q, limitB);
     case kIDBKeyDateTypeByte:
     case kIDBKeyNumberTypeByte:

trunk/Source/WebCore/storage/IDBLevelDBCoding.h

@@ -54 +54 @@
 Vector<char> encodeStringWithLength(const String&);
 const char* decodeStringWithLength(const char* p, const char* limit, String& foundString);
+int compareEncodedStringsWithLength(const char* p, const char* limitP, const char* q, const char* limitQ);
 Vector<char> encodeDouble(double);
 const char* decodeDouble(const char* p, const char* limit, double*);

trunk/Source/WebKit/chromium/tests/IDBLevelDBCodingTest.cpp

@@ -231 +231 @@
 }
 
+TEST(IDBLevelDBCodingTest, CompareEncodedStringsWithLength)
+{
+    const UChar testStringA[] = {0x1000, 0x1000, '\0'};
+    const UChar testStringB[] = {0x1000, 0x1000, 0x1000, '\0'};
+    const UChar testStringC[] = {0x1000, 0x1000, 0x1001, '\0'};
+    const UChar testStringD[] = {0x1001, 0x1000, 0x1000, '\0'};
+    const UChar testStringE[] = {0xd834, 0xdd1e, '\0'};
+    const UChar testStringF[] = {0xfffd, '\0'};
+
+    Vector<String> testCases;
+    testCases.append(String(""));
+    testCases.append(String("a"));
+    testCases.append(String("b"));
+    testCases.append(String("baaa"));
+    testCases.append(String("baab"));
+    testCases.append(String("c"));
+    testCases.append(String(testStringA));
+    testCases.append(String(testStringB));
+    testCases.append(String(testStringC));
+    testCases.append(String(testStringD));
+    testCases.append(String(testStringE));
+    testCases.append(String(testStringF));
+
+    for (size_t i = 0; i < testCases.size() - 1; ++i) {
+        String a = testCases[i];
+        String b = testCases[i + 1];
+
+        EXPECT_LT(codePointCompare(a, b), 0);
+        EXPECT_GT(codePointCompare(b, a), 0);
+        EXPECT_EQ(codePointCompare(a, a), 0);
+        EXPECT_EQ(codePointCompare(b, b), 0);
+
+        Vector<char> encodedA = encodeStringWithLength(a);
+        EXPECT_TRUE(encodedA.size());
+        Vector<char> encodedB = encodeStringWithLength(b);
+        EXPECT_TRUE(encodedA.size());
+
+        const char* p = encodedA.data();
+        const char* limitP = p + encodedA.size();
+        const char* q = encodedB.data();
+        const char* limitQ = q + encodedB.size();
+
+        EXPECT_LT(compareEncodedStringsWithLength(p, limitP, q, limitQ), 0);
+        EXPECT_GT(compareEncodedStringsWithLength(q, limitQ, p, limitP), 0);
+        EXPECT_EQ(compareEncodedStringsWithLength(p, limitP, p, limitP), 0);
+        EXPECT_EQ(compareEncodedStringsWithLength(q, limitQ, q, limitQ), 0);
+    }
+}
+
 TEST(IDBLevelDBCodingTest, EncodeDouble)
 {
@@ -303 +352 @@
     keys.append(IDBKey::createString("b"));
     keys.append(IDBKey::createString("baaa"));
+    keys.append(IDBKey::createString("baab"));
+    keys.append(IDBKey::createString("c"));
 
     for (size_t i = 0; i < keys.size() - 1; ++i) {