Changeset 128237 in webkit
- Timestamp:
- Sep 11, 2012 4:18:40 PM (12 years ago)
- Location:
- trunk/Source/WebCore
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/WebCore/ChangeLog
r128235 r128237 1 2012-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 1 20 2012-09-11 Adam Klein <adamk@chromium.org> 2 21 -
trunk/Source/WebCore/Modules/indexeddb/IDBLevelDBCoding.cpp
r128220 r128237 506 506 } 507 507 508 const char* extractEncodedIDBKey(const char* start, const char* limit, Vector<char>* result) 509 { 510 ASSERT(result); 508 const char* extractEncodedIDBKey(const char* start, const char* limit, Vector<char>* result = 0) 509 { 511 510 const char* p = start; 512 511 if (p >= limit) … … 518 517 case IDBKeyNullTypeByte: 519 518 case IDBKeyMinKeyTypeByte: 520 *result = encodeByte(type); 521 return p; 519 break; 522 520 case IDBKeyArrayTypeByte: { 523 521 int64_t length; … … 527 525 if (length < 0) 528 526 return 0; 529 result->clear();530 result->append(start, p - start);531 527 while (length--) { 532 Vector<char> subkey; 533 p = extractEncodedIDBKey(p, limit, &subkey); 528 p = extractEncodedIDBKey(p, limit); 534 529 if (!p) 535 530 return 0; 536 result->append(subkey);537 531 } 538 return p;532 break; 539 533 } 540 534 case IDBKeyStringTypeByte: { … … 545 539 if (p + length * 2 > limit) 546 540 return 0; 547 result->clear(); 548 result->append(start, p - start + length * 2); 549 return p + length * 2; 541 p += length * 2; 542 break; 550 543 } 551 544 case IDBKeyDateTypeByte: … … 553 546 if (p + sizeof(double) > limit) 554 547 return 0; 548 p += sizeof(double); 549 break; 550 } 551 552 if (result) { 553 ASSERT(p); 554 ASSERT(p <= limit); 555 555 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; 561 560 } 562 561 … … 582 581 } 583 582 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++;583 int 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++; 591 590 592 591 if (int x = IDBKey::compareTypes(keyTypeByteToKeyType(typeA), keyTypeByteToKeyType(typeB))) … … 600 599 case IDBKeyArrayTypeByte: { 601 600 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) 607 606 return 0; 608 607 if (lengthA < 0 || lengthB < 0) 609 608 return 0; 610 609 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)) 612 611 return cmp; 613 612 } … … 619 618 } 620 619 case IDBKeyStringTypeByte: 621 return compareEncodedStringsWithLength(p , limitA, q, limitB);620 return compareEncodedStringsWithLength(ptrA, limitA, ptrB, limitB); 622 621 case IDBKeyDateTypeByte: 623 622 case IDBKeyNumberTypeByte: { 624 623 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); 629 628 if (d < e) 630 629 return -1; … … 644 643 ASSERT(keyB.size() >= 1); 645 644 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); 652 651 } 653 652 … … 721 720 722 721 namespace { 722 723 723 template<typename KeyType> 724 int decodeAndCompare(const LevelDBSlice& a, const LevelDBSlice& b)724 int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates = false) 725 725 { 726 726 KeyType keyA; … … 734 734 return keyA.compare(keyB); 735 735 } 736 737 template<> 738 int 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 760 template<> 761 int 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 783 template<> 784 int 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 736 833 } 737 834 … … 767 864 return 0; 768 865 if (typeByteA == DatabaseFreeListTypeByte) 769 return decodeAndCompare<DatabaseFreeListKey>(a, b);866 return compare<DatabaseFreeListKey>(a, b); 770 867 if (typeByteA == DatabaseNameTypeByte) 771 return decodeAndCompare<DatabaseNameKey>(a, b);868 return compare<DatabaseNameKey>(a, b); 772 869 } 773 870 … … 782 879 return x; 783 880 881 // FIXME: Replace this magic number. Should it account for UserIntVersion? 784 882 if (typeByteA <= 3) 785 883 return 0; 786 884 787 885 if (typeByteA == ObjectStoreMetaDataTypeByte) 788 return decodeAndCompare<ObjectStoreMetaDataKey>(a, b);886 return compare<ObjectStoreMetaDataKey>(a, b); 789 887 if (typeByteA == IndexMetaDataTypeByte) 790 return decodeAndCompare<IndexMetaDataKey>(a, b);888 return compare<IndexMetaDataKey>(a, b); 791 889 if (typeByteA == ObjectStoreFreeListTypeByte) 792 return decodeAndCompare<ObjectStoreFreeListKey>(a, b);890 return compare<ObjectStoreFreeListKey>(a, b); 793 891 if (typeByteA == IndexFreeListTypeByte) 794 return decodeAndCompare<IndexFreeListKey>(a, b);892 return compare<IndexFreeListKey>(a, b); 795 893 if (typeByteA == ObjectStoreNamesTypeByte) 796 return decodeAndCompare<ObjectStoreNamesKey>(a, b);894 return compare<ObjectStoreNamesKey>(a, b); 797 895 if (typeByteA == IndexNamesKeyTypeByte) 798 return decodeAndCompare<IndexNamesKey>(a, b);799 800 return 0;801 ASSERT_NOT_REACHED();896 return compare<IndexNamesKey>(a, b); 897 898 // FIXME: Assert not reached here? 899 return 0; 802 900 } 803 901 … … 810 908 return 1; // FIXME: This case of non-existing user keys should not have to be handled this way. 811 909 812 return decodeAndCompare<ObjectStoreDataKey>(a, b);910 return compare<ObjectStoreDataKey>(a, b); 813 911 } 814 912 if (prefixA.type() == KeyPrefix::ExistsEntry) { … … 820 918 return 1; // FIXME: This case of non-existing user keys should not have to be handled this way. 821 919 822 return decodeAndCompare<ExistsEntryKey>(a, b);920 return compare<ExistsEntryKey>(a, b); 823 921 } 824 922 if (prefixA.type() == KeyPrefix::IndexData) { … … 830 928 return 1; // FIXME: This case of non-existing user keys should not have to be handled this way. 831 929 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 840 930 bool ignoreDuplicates = indexKeys; 841 return indexDataKeyA.compare(indexDataKeyB, ignoreDuplicates);931 return compare<IndexDataKey>(a, b, ignoreDuplicates); 842 932 } 843 933
Note: See TracChangeset
for help on using the changeset viewer.