Changeset 128212 in webkit


Ignore:
Timestamp:
Sep 11, 2012 11:42:55 AM (12 years ago)
Author:
jsbell@chromium.org
Message:

IndexedDB: Optimize key decode and comparison operations
​https://bugs.webkit.org/show_bug.cgi?id=96037

Reviewed by Tony Chang.

Eliminate memory allocations in code identified as CPU bottlenecks in IDB profiling.

No new tests - just performance work.

  • Modules/indexeddb/IDBLevelDBCoding.cpp:

(WebCore::IDBLevelDBCoding::extractEncodedIDBKey): Avoid incremental allocations.
(WebCore::IDBLevelDBCoding::compareEncodedIDBKeys): Rename confusing variables p and q.
(IDBLevelDBCoding):
(WebCore::IDBLevelDBCoding::compare): Rename from decodeAndCompare, and add specializations
for frequently encountered types (e.g. object/index data) that can be compared without a
full decode.

Location:
trunk/Source/WebCore
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r128210 r128212  
     12012-09-11  Joshua Bell  <jsbell@chromium.org>
     2
     3        IndexedDB: Optimize key decode and comparison operations
     4        https://bugs.webkit.org/show_bug.cgi?id=96037
     5
     6        Reviewed by Tony Chang.
     7
     8        Eliminate memory allocations in code identified as CPU bottlenecks in IDB profiling.
     9
     10        No new tests - just performance work.
     11
     12        * Modules/indexeddb/IDBLevelDBCoding.cpp:
     13        (WebCore::IDBLevelDBCoding::extractEncodedIDBKey): Avoid incremental allocations.
     14        (WebCore::IDBLevelDBCoding::compareEncodedIDBKeys): Rename confusing variables p and q.
     15        (IDBLevelDBCoding):
     16        (WebCore::IDBLevelDBCoding::compare): Rename from decodeAndCompare, and add specializations
     17        for frequently encountered types (e.g. object/index data) that can be compared without a
     18        full decode.
     19
    1202012-09-11  Marcelo Lira  <marcelo.lira@openbossa.org>
    221

  • trunk/Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp

    r124865 r128212  
    506506}
    507507
    508 const char* extractEncodedIDBKey(const char* start, const char* limit, Vector<char>* result)
    509 {
    510     ASSERT(result);
     508const char* extractEncodedIDBKey(const char* start, const char* limit, Vector<char>* result = 0)
     509{
    511510    const char* p = start;
    512511    if (p >= limit)
    … …  
    518517    case IDBKeyNullTypeByte:
    519518    case IDBKeyMinKeyTypeByte:
    520         *result = encodeByte(type);
    521         return p;
     519        break;
    522520    case IDBKeyArrayTypeByte: {
    523521        int64_t length;
    … …  
    527525        if (length < 0)
    528526            return 0;
    529         result->clear();
    530         result->append(start, p - start);
    531527        while (length--) {
    532             Vector<char> subkey;
    533             p = extractEncodedIDBKey(p, limit, &subkey);
     528            p = extractEncodedIDBKey(p, limit);
    534529            if (!p)
    535530                return 0;
    536             result->append(subkey);
    537531        }
    538         return p;
     532        break;
    539533    }
    540534    case IDBKeyStringTypeByte: {
    … …  
    545539        if (p + length * 2 > limit)
    546540            return 0;
    547         result->clear();
    548         result->append(start, p - start + length * 2);
    549         return p + length * 2;
     541        p += length * 2;
     542        break;
    550543    }
    551544    case IDBKeyDateTypeByte:
    … …  
    553546        if (p + sizeof(double) > limit)
    554547            return 0;
     548        p += sizeof(double);
     549        break;
     550    }
     551
     552    if (result) {
     553        ASSERT(p);
     554        ASSERT(p <= limit);
    555555        result->clear();
    556         result->append(start, 1 + sizeof(double));
    557         return p + sizeof(double);
    558     }
    559     ASSERT_NOT_REACHED();
    560     return 0;
     556        result->append(start, p - start);
     557    }
     558
     559    return p;
    561560}
    562561
    … …  
    582581}
    583582
    584 int compareEncodedIDBKeys(const char*& p, const char* limitA, const char*& q, const char* limitB)
    585 {
    586     ASSERT(&p != &q);
    587     ASSERT(p < limitA);
    588     ASSERT(q < limitB);
    589     unsigned char typeA = *p++;
    590     unsigned char typeB = *q++;
     583int compareEncodedIDBKeys(const char*& ptrA, const char* limitA, const char*& ptrB, const char* limitB)
     584{
     585    ASSERT(&ptrA != &ptrB);
     586    ASSERT(ptrA < limitA);
     587    ASSERT(ptrB < limitB);
     588    unsigned char typeA = *ptrA++;
     589    unsigned char typeB = *ptrB++;
    591590
    592591    if (int x = IDBKey::compareTypes(keyTypeByteToKeyType(typeA), keyTypeByteToKeyType(typeB)))
    … …  
    600599    case IDBKeyArrayTypeByte: {
    601600        int64_t lengthA, lengthB;
    602         p = decodeVarInt(p, limitA, lengthA);
    603         if (!p)
    604             return 0;
    605         q = decodeVarInt(q, limitB, lengthB);
    606         if (!q)
     601        ptrA = decodeVarInt(ptrA, limitA, lengthA);
     602        if (!ptrA)
     603            return 0;
     604        ptrB = decodeVarInt(ptrB, limitB, lengthB);
     605        if (!ptrB)
    607606            return 0;
    608607        if (lengthA < 0 || lengthB < 0)
    609608            return 0;
    610609        for (int64_t i = 0; i < lengthA && i < lengthB; ++i) {
    611             if (int cmp = compareEncodedIDBKeys(p, limitA, q, limitB))
     610            if (int cmp = compareEncodedIDBKeys(ptrA, limitA, ptrB, limitB))
    612611                return cmp;
    613612        }
    … …  
    619618    }
    620619    case IDBKeyStringTypeByte:
    621         return compareEncodedStringsWithLength(p, limitA, q, limitB);
     620        return compareEncodedStringsWithLength(ptrA, limitA, ptrB, limitB);
    622621    case IDBKeyDateTypeByte:
    623622    case IDBKeyNumberTypeByte: {
    624623        double d, e;
    625         p = decodeDouble(p, limitA, &d);
    626         ASSERT(p);
    627         q = decodeDouble(q, limitB, &e);
    628         ASSERT(q);
     624        ptrA = decodeDouble(ptrA, limitA, &d);
     625        ASSERT(ptrA);
     626        ptrB = decodeDouble(ptrB, limitB, &e);
     627        ASSERT(ptrB);
    629628        if (d < e)
    630629            return -1;
    … …  
    644643    ASSERT(keyB.size() >= 1);
    645644
    646     const char* p = keyA.data();
    647     const char* limitA = p + keyA.size();
    648     const char* q = keyB.data();
    649     const char* limitB = q + keyB.size();
    650 
    651     return compareEncodedIDBKeys(p, limitA, q, limitB);
     645    const char* ptrA = keyA.data();
     646    const char* limitA = ptrA + keyA.size();
     647    const char* ptrB = keyB.data();
     648    const char* limitB = ptrB + keyB.size();
     649
     650    return compareEncodedIDBKeys(ptrA, limitA, ptrB, limitB);
    652651}
    653652
    … …  
    721720
    722721namespace {
     722
    723723template<typename KeyType>
    724 int decodeAndCompare(const LevelDBSlice& a, const LevelDBSlice& b)
     724int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates = false)
    725725{
    726726    KeyType keyA;
    … …  
    734734    return keyA.compare(keyB);
    735735}
     736
     737template<>
     738int compare<ExistsEntryKey>(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates)
     739{
     740    KeyPrefix prefixA;
     741    KeyPrefix prefixB;
     742    const char* ptrA = KeyPrefix::decode(a.begin(), a.end(), &prefixA);
     743    const char* ptrB = KeyPrefix::decode(b.begin(), b.end(), &prefixB);
     744    ASSERT(ptrA);
     745    ASSERT(ptrB);
     746    ASSERT(prefixA.m_databaseId);
     747    ASSERT(prefixA.m_objectStoreId);
     748    ASSERT(prefixA.m_indexId == ExistsEntryKey::SpecialIndexNumber);
     749    ASSERT(prefixB.m_databaseId);
     750    ASSERT(prefixB.m_objectStoreId);
     751    ASSERT(prefixB.m_indexId == ExistsEntryKey::SpecialIndexNumber);
     752    ASSERT(ptrA != a.end());
     753    ASSERT(ptrB != b.end());
     754    // Prefixes are not compared - it is assumed this was already done.
     755    ASSERT(!prefixA.compare(prefixB));
     756
     757    return compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end());
     758}
     759
     760template<>
     761int compare<ObjectStoreDataKey>(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates)
     762{
     763    KeyPrefix prefixA;
     764    KeyPrefix prefixB;
     765    const char* ptrA = KeyPrefix::decode(a.begin(), a.end(), &prefixA);
     766    const char* ptrB = KeyPrefix::decode(b.begin(), b.end(), &prefixB);
     767    ASSERT(ptrA);
     768    ASSERT(ptrB);
     769    ASSERT(prefixA.m_databaseId);
     770    ASSERT(prefixA.m_objectStoreId);
     771    ASSERT(prefixA.m_indexId == ObjectStoreDataKey::SpecialIndexNumber);
     772    ASSERT(prefixB.m_databaseId);
     773    ASSERT(prefixB.m_objectStoreId);
     774    ASSERT(prefixB.m_indexId == ObjectStoreDataKey::SpecialIndexNumber);
     775    ASSERT(ptrA != a.end());
     776    ASSERT(ptrB != b.end());
     777    // Prefixes are not compared - it is assumed this was already done.
     778    ASSERT(!prefixA.compare(prefixB));
     779
     780    return compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end());
     781}
     782
     783template<>
     784int compare<IndexDataKey>(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates)
     785{
     786    KeyPrefix prefixA;
     787    KeyPrefix prefixB;
     788    const char* ptrA = KeyPrefix::decode(a.begin(), a.end(), &prefixA);
     789    const char* ptrB = KeyPrefix::decode(b.begin(), b.end(), &prefixB);
     790    ASSERT(ptrA);
     791    ASSERT(ptrB);
     792    ASSERT(prefixA.m_databaseId);
     793    ASSERT(prefixA.m_objectStoreId);
     794    ASSERT(prefixA.m_indexId >= MinimumIndexId);
     795    ASSERT(prefixB.m_databaseId);
     796    ASSERT(prefixB.m_objectStoreId);
     797    ASSERT(prefixB.m_indexId >= MinimumIndexId);
     798    ASSERT(ptrA != a.end());
     799    ASSERT(ptrB != b.end());
     800    // Prefixes are not compared - it is assumed this was already done.
     801    ASSERT(!prefixA.compare(prefixB));
     802
     803    // index key
     804    if (int x = compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end()))
     805        return x;
     806    if (ignoreDuplicates)
     807        return 0;
     808
     809    // sequence number [optional]
     810    int64_t sequenceNumberA = -1;
     811    int64_t sequenceNumberB = -1;
     812    if (ptrA != a.end())
     813        ptrA = decodeVarInt(ptrA, a.end(), sequenceNumberA);
     814    if (ptrB != b.end())
     815        ptrB = decodeVarInt(ptrB, b.end(), sequenceNumberB);
     816
     817    // primar key [optional]
     818    if (!ptrA || !ptrB)
     819        return 0;
     820    if (ptrA == a.end() && ptrB == b.end())
     821        return 0;
     822    if (ptrA == a.end())
     823        return -1;
     824    if (ptrB == b.end())
     825        return 1;
     826
     827    if (int x = compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end()))
     828        return x;
     829
     830    return compareInts(sequenceNumberA, sequenceNumberB);
     831}
     832
    736833}
    737834
    … …  
    767864            return 0;
    768865        if (typeByteA == DatabaseFreeListTypeByte)
    769             return decodeAndCompare<DatabaseFreeListKey>(a, b);
     866            return compare<DatabaseFreeListKey>(a, b);
    770867        if (typeByteA == DatabaseNameTypeByte)
    771             return decodeAndCompare<DatabaseNameKey>(a, b);
     868            return compare<DatabaseNameKey>(a, b);
    772869    }
    773870
    … …  
    786883
    787884        if (typeByteA == ObjectStoreMetaDataTypeByte)
    788             return decodeAndCompare<ObjectStoreMetaDataKey>(a, b);
     885            return compare<ObjectStoreMetaDataKey>(a, b);
    789886        if (typeByteA == IndexMetaDataTypeByte)
    790             return decodeAndCompare<IndexMetaDataKey>(a, b);
     887            return compare<IndexMetaDataKey>(a, b);
    791888        if (typeByteA == ObjectStoreFreeListTypeByte)
    792             return decodeAndCompare<ObjectStoreFreeListKey>(a, b);
     889            return compare<ObjectStoreFreeListKey>(a, b);
    793890        if (typeByteA == IndexFreeListTypeByte)
    794             return decodeAndCompare<IndexFreeListKey>(a, b);
     891            return compare<IndexFreeListKey>(a, b);
    795892        if (typeByteA == ObjectStoreNamesTypeByte)
    796             return decodeAndCompare<ObjectStoreNamesKey>(a, b);
     893            return compare<ObjectStoreNamesKey>(a, b);
    797894        if (typeByteA == IndexNamesKeyTypeByte)
    798             return decodeAndCompare<IndexNamesKey>(a, b);
    799 
    800         return 0;
     895            return compare<IndexNamesKey>(a, b);
     896
    801897        ASSERT_NOT_REACHED();
     898        return 0;
    802899    }
    803900
    … …  
    810907            return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
    811908
    812         return decodeAndCompare<ObjectStoreDataKey>(a, b);
     909        return compare<ObjectStoreDataKey>(a, b);
    813910    }
    814911    if (prefixA.type() == KeyPrefix::ExistsEntry) {
    … …  
    820917            return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
    821918
    822         return decodeAndCompare<ExistsEntryKey>(a, b);
     919        return compare<ExistsEntryKey>(a, b);
    823920    }
    824921    if (prefixA.type() == KeyPrefix::IndexData) {
    … …  
    830927            return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
    831928
    832         IndexDataKey indexDataKeyA;
    833         IndexDataKey indexDataKeyB;
    834 
    835         ptrA = IndexDataKey::decode(a.begin(), endA, &indexDataKeyA);
    836         ptrB = IndexDataKey::decode(b.begin(), endB, &indexDataKeyB);
    837         ASSERT(ptrA);
    838         ASSERT(ptrB);
    839 
    840929        bool ignoreDuplicates = indexKeys;
    841         return indexDataKeyA.compare(indexDataKeyB, ignoreDuplicates);
     930        return compare<IndexDataKey>(a, b, ignoreDuplicates);
    842931    }
    843932
Note: See TracChangeset for help on using the changeset viewer.