Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(24)

Side by Side Diff: Source/wtf/HashTable.h

Issue 17583004: Improve WTF::HashTable performance by changing probing method (Closed) Base URL: https://chromium.googlesource.com/chromium/blink@master
Patch Set: rebaseline named-grid-line-get-set which depends on hashtable iteration order Created 7 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « LayoutTests/fast/css-grid-layout/named-grid-line-get-set-expected.txt ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv ed. 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv ed.
3 * Copyright (C) 2008 David Levin <levin@chromium.org> 3 * Copyright (C) 2008 David Levin <levin@chromium.org>
4 * 4 *
5 * This library is free software; you can redistribute it and/or 5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public 6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either 7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version. 8 * version 2 of the License, or (at your option) any later version.
9 * 9 *
10 * This library is distributed in the hope that it will be useful, 10 * This library is distributed in the hope that it will be useful,
(...skipping 467 matching lines...) Expand 10 before | Expand all | Expand 10 after
478 #endif 478 #endif
479 479
480 #if CHECK_HASHTABLE_ITERATORS 480 #if CHECK_HASHTABLE_ITERATORS
481 void invalidateIterators(); 481 void invalidateIterators();
482 #else 482 #else
483 static void invalidateIterators() { } 483 static void invalidateIterators() { }
484 #endif 484 #endif
485 485
486 static const int m_maxLoad = 2; 486 static const int m_maxLoad = 2;
487 static const int m_minLoad = 6; 487 static const int m_minLoad = 6;
488 static const int perturbShift = 5;
488 489
489 ValueType* m_table; 490 ValueType* m_table;
490 int m_tableSize; 491 int m_tableSize;
491 int m_tableSizeMask; 492 int m_tableSizeMask;
492 int m_keyCount; 493 int m_keyCount;
493 int m_deletedCount; 494 int m_deletedCount;
494 495
495 #if CHECK_HASHTABLE_ITERATORS 496 #if CHECK_HASHTABLE_ITERATORS
496 public: 497 public:
497 // All access to m_iterators should be guarded with m_mutex. 498 // All access to m_iterators should be guarded with m_mutex.
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after
554 #if CHECK_HASHTABLE_ITERATORS 555 #if CHECK_HASHTABLE_ITERATORS
555 , m_iterators(0) 556 , m_iterators(0)
556 , m_mutex(adoptPtr(new Mutex)) 557 , m_mutex(adoptPtr(new Mutex))
557 #endif 558 #endif
558 #if DUMP_HASHTABLE_STATS_PER_TABLE 559 #if DUMP_HASHTABLE_STATS_PER_TABLE
559 , m_stats(adoptPtr(new Stats)) 560 , m_stats(adoptPtr(new Stats))
560 #endif 561 #endif
561 { 562 {
562 } 563 }
563 564
564 inline unsigned doubleHash(unsigned key)
565 {
566 key = ~key + (key >> 23);
567 key ^= (key << 12);
568 key ^= (key >> 7);
569 key ^= (key << 2);
570 key ^= (key >> 20);
571 return key;
572 }
573
574 #if ASSERT_DISABLED 565 #if ASSERT_DISABLED
575 566
576 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits> 567 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits>
577 template<typename HashTranslator, typename T> 568 template<typename HashTranslator, typename T>
578 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait s>::checkKey(const T&) 569 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait s>::checkKey(const T&)
579 { 570 {
580 } 571 }
581 572
582 #else 573 #else
583 574
(...skipping 12 matching lines...) Expand all
596 } 587 }
597 588
598 #endif 589 #endif
599 590
600 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits> 591 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits>
601 template<typename HashTranslator, typename T> 592 template<typename HashTranslator, typename T>
602 inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTra its>::lookup(const T& key) 593 inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTra its>::lookup(const T& key)
603 { 594 {
604 checkKey<HashTranslator>(key); 595 checkKey<HashTranslator>(key);
605 596
606 int k = 0;
607 int sizeMask = m_tableSizeMask; 597 int sizeMask = m_tableSizeMask;
608 ValueType* table = m_table; 598 ValueType* table = m_table;
609 unsigned h = HashTranslator::hash(key); 599 unsigned h = HashTranslator::hash(key);
610 int i = h & sizeMask; 600 unsigned i = h;
601 unsigned perturb = h;
611 602
612 if (!table) 603 if (!table)
613 return 0; 604 return 0;
614 605
615 #if DUMP_HASHTABLE_STATS 606 #if DUMP_HASHTABLE_STATS
616 atomicIncrement(&HashTableStats::numAccesses); 607 atomicIncrement(&HashTableStats::numAccesses);
617 int probeCount = 0; 608 int probeCount = 0;
618 #endif 609 #endif
619 610
620 #if DUMP_HASHTABLE_STATS_PER_TABLE 611 #if DUMP_HASHTABLE_STATS_PER_TABLE
621 ++m_stats->numAccesses; 612 ++m_stats->numAccesses;
622 int perTableProbeCount = 0; 613 int perTableProbeCount = 0;
623 #endif 614 #endif
624 615
625 while (1) { 616 while (1) {
626 ValueType* entry = table + i; 617 ValueType* entry = table + (i & sizeMask);
627 618
628 // we count on the compiler to optimize out this branch 619 // we count on the compiler to optimize out this branch
629 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 620 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
630 if (HashTranslator::equal(Extractor::extract(*entry), key)) 621 if (HashTranslator::equal(Extractor::extract(*entry), key))
631 return entry; 622 return entry;
632 623
633 if (isEmptyBucket(*entry)) 624 if (isEmptyBucket(*entry))
634 return 0; 625 return 0;
635 } else { 626 } else {
636 if (isEmptyBucket(*entry)) 627 if (isEmptyBucket(*entry))
637 return 0; 628 return 0;
638 629
639 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor: :extract(*entry), key)) 630 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor: :extract(*entry), key))
640 return entry; 631 return entry;
641 } 632 }
642 #if DUMP_HASHTABLE_STATS 633 #if DUMP_HASHTABLE_STATS
643 ++probeCount; 634 ++probeCount;
644 HashTableStats::recordCollisionAtCount(probeCount); 635 HashTableStats::recordCollisionAtCount(probeCount);
645 #endif 636 #endif
646 637
647 #if DUMP_HASHTABLE_STATS_PER_TABLE 638 #if DUMP_HASHTABLE_STATS_PER_TABLE
648 ++perTableProbeCount; 639 ++perTableProbeCount;
649 m_stats->recordCollisionAtCount(perTableProbeCount); 640 m_stats->recordCollisionAtCount(perTableProbeCount);
650 #endif 641 #endif
651 642
652 if (k == 0) 643 perturb >>= perturbShift;
653 k = 1 | doubleHash(h); 644 i = i*5 + perturb + 1;
654 i = (i + k) & sizeMask;
655 } 645 }
656 } 646 }
657 647
658 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits> 648 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits>
659 template<typename HashTranslator, typename T> 649 template<typename HashTranslator, typename T>
660 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT raits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTr aits>::lookupForWriting(const T& key) 650 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT raits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTr aits>::lookupForWriting(const T& key)
661 { 651 {
662 ASSERT(m_table); 652 ASSERT(m_table);
663 checkKey<HashTranslator>(key); 653 checkKey<HashTranslator>(key);
664 654
665 int k = 0;
666 ValueType* table = m_table; 655 ValueType* table = m_table;
667 int sizeMask = m_tableSizeMask; 656 int sizeMask = m_tableSizeMask;
668 unsigned h = HashTranslator::hash(key); 657 unsigned h = HashTranslator::hash(key);
669 int i = h & sizeMask; 658 unsigned i = h;
659 unsigned perturb = h;
670 660
671 #if DUMP_HASHTABLE_STATS 661 #if DUMP_HASHTABLE_STATS
672 atomicIncrement(&HashTableStats::numAccesses); 662 atomicIncrement(&HashTableStats::numAccesses);
673 int probeCount = 0; 663 int probeCount = 0;
674 #endif 664 #endif
675 665
676 #if DUMP_HASHTABLE_STATS_PER_TABLE 666 #if DUMP_HASHTABLE_STATS_PER_TABLE
677 ++m_stats->numAccesses; 667 ++m_stats->numAccesses;
678 int perTableProbeCount = 0; 668 int perTableProbeCount = 0;
679 #endif 669 #endif
680 670
681 ValueType* deletedEntry = 0; 671 ValueType* deletedEntry = 0;
682 672
683 while (1) { 673 while (1) {
684 ValueType* entry = table + i; 674 ValueType* entry = table + (i & sizeMask);
685 675
686 // we count on the compiler to optimize out this branch 676 // we count on the compiler to optimize out this branch
687 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 677 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
688 if (isEmptyBucket(*entry)) 678 if (isEmptyBucket(*entry))
689 return LookupType(deletedEntry ? deletedEntry : entry, false ); 679 return LookupType(deletedEntry ? deletedEntry : entry, false );
690 680
691 if (HashTranslator::equal(Extractor::extract(*entry), key)) 681 if (HashTranslator::equal(Extractor::extract(*entry), key))
692 return LookupType(entry, true); 682 return LookupType(entry, true);
693 683
694 if (isDeletedBucket(*entry)) 684 if (isDeletedBucket(*entry))
(...skipping 10 matching lines...) Expand all
705 #if DUMP_HASHTABLE_STATS 695 #if DUMP_HASHTABLE_STATS
706 ++probeCount; 696 ++probeCount;
707 HashTableStats::recordCollisionAtCount(probeCount); 697 HashTableStats::recordCollisionAtCount(probeCount);
708 #endif 698 #endif
709 699
710 #if DUMP_HASHTABLE_STATS_PER_TABLE 700 #if DUMP_HASHTABLE_STATS_PER_TABLE
711 ++perTableProbeCount; 701 ++perTableProbeCount;
712 m_stats->recordCollisionAtCount(perTableProbeCount); 702 m_stats->recordCollisionAtCount(perTableProbeCount);
713 #endif 703 #endif
714 704
715 if (k == 0) 705 perturb >>= perturbShift;
716 k = 1 | doubleHash(h); 706 i = i*5 + perturb + 1;
717 i = (i + k) & sizeMask;
718 } 707 }
719 } 708 }
720 709
721 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits> 710 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits>
722 template<typename HashTranslator, typename T> 711 template<typename HashTranslator, typename T>
723 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT raits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, K eyTraits>::fullLookupForWriting(const T& key) 712 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT raits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, K eyTraits>::fullLookupForWriting(const T& key)
724 { 713 {
725 ASSERT(m_table); 714 ASSERT(m_table);
726 checkKey<HashTranslator>(key); 715 checkKey<HashTranslator>(key);
727 716
728 int k = 0;
729 ValueType* table = m_table; 717 ValueType* table = m_table;
730 int sizeMask = m_tableSizeMask; 718 int sizeMask = m_tableSizeMask;
731 unsigned h = HashTranslator::hash(key); 719 unsigned h = HashTranslator::hash(key);
732 int i = h & sizeMask; 720 unsigned i = h;
721 unsigned perturb = h;
733 722
734 #if DUMP_HASHTABLE_STATS 723 #if DUMP_HASHTABLE_STATS
735 atomicIncrement(&HashTableStats::numAccesses); 724 atomicIncrement(&HashTableStats::numAccesses);
736 int probeCount = 0; 725 int probeCount = 0;
737 #endif 726 #endif
738 727
739 #if DUMP_HASHTABLE_STATS_PER_TABLE 728 #if DUMP_HASHTABLE_STATS_PER_TABLE
740 ++m_stats->numAccesses; 729 ++m_stats->numAccesses;
741 int perTableProbeCount = 0; 730 int perTableProbeCount = 0;
742 #endif 731 #endif
743 732
744 ValueType* deletedEntry = 0; 733 ValueType* deletedEntry = 0;
745 734
746 while (1) { 735 while (1) {
747 ValueType* entry = table + i; 736 ValueType* entry = table + (i & sizeMask);
748 737
749 // we count on the compiler to optimize out this branch 738 // we count on the compiler to optimize out this branch
750 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 739 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
751 if (isEmptyBucket(*entry)) 740 if (isEmptyBucket(*entry))
752 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h); 741 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
753 742
754 if (HashTranslator::equal(Extractor::extract(*entry), key)) 743 if (HashTranslator::equal(Extractor::extract(*entry), key))
755 return makeLookupResult(entry, true, h); 744 return makeLookupResult(entry, true, h);
756 745
757 if (isDeletedBucket(*entry)) 746 if (isDeletedBucket(*entry))
(...skipping 10 matching lines...) Expand all
768 #if DUMP_HASHTABLE_STATS 757 #if DUMP_HASHTABLE_STATS
769 ++probeCount; 758 ++probeCount;
770 HashTableStats::recordCollisionAtCount(probeCount); 759 HashTableStats::recordCollisionAtCount(probeCount);
771 #endif 760 #endif
772 761
773 #if DUMP_HASHTABLE_STATS_PER_TABLE 762 #if DUMP_HASHTABLE_STATS_PER_TABLE
774 ++perTableProbeCount; 763 ++perTableProbeCount;
775 m_stats->recordCollisionAtCount(perTableProbeCount); 764 m_stats->recordCollisionAtCount(perTableProbeCount);
776 #endif 765 #endif
777 766
778 if (k == 0) 767 perturb >>= perturbShift;
779 k = 1 | doubleHash(h); 768 i = i*5 + perturb + 1;
780 i = (i + k) & sizeMask;
781 } 769 }
782 } 770 }
783 771
784 template<bool emptyValueIsZero> struct HashTableBucketInitializer; 772 template<bool emptyValueIsZero> struct HashTableBucketInitializer;
785 773
786 template<> struct HashTableBucketInitializer<false> { 774 template<> struct HashTableBucketInitializer<false> {
787 template<typename Traits, typename Value> static void initialize(Value& bucket) 775 template<typename Traits, typename Value> static void initialize(Value& bucket)
788 { 776 {
789 new (NotNull, &bucket) Value(Traits::emptyValue()); 777 new (NotNull, &bucket) Value(Traits::emptyValue());
790 } 778 }
(...skipping 23 matching lines...) Expand all
814 802
815 invalidateIterators(); 803 invalidateIterators();
816 804
817 if (!m_table) 805 if (!m_table)
818 expand(); 806 expand();
819 807
820 internalCheckTableConsistency(); 808 internalCheckTableConsistency();
821 809
822 ASSERT(m_table); 810 ASSERT(m_table);
823 811
824 int k = 0;
825 ValueType* table = m_table; 812 ValueType* table = m_table;
826 int sizeMask = m_tableSizeMask; 813 int sizeMask = m_tableSizeMask;
827 unsigned h = HashTranslator::hash(key); 814 unsigned h = HashTranslator::hash(key);
828 int i = h & sizeMask; 815 unsigned i = h;
816 unsigned perturb = h;
829 817
830 #if DUMP_HASHTABLE_STATS 818 #if DUMP_HASHTABLE_STATS
831 atomicIncrement(&HashTableStats::numAccesses); 819 atomicIncrement(&HashTableStats::numAccesses);
832 int probeCount = 0; 820 int probeCount = 0;
833 #endif 821 #endif
834 822
835 #if DUMP_HASHTABLE_STATS_PER_TABLE 823 #if DUMP_HASHTABLE_STATS_PER_TABLE
836 ++m_stats->numAccesses; 824 ++m_stats->numAccesses;
837 int perTableProbeCount = 0; 825 int perTableProbeCount = 0;
838 #endif 826 #endif
839 827
840 ValueType* deletedEntry = 0; 828 ValueType* deletedEntry = 0;
841 ValueType* entry; 829 ValueType* entry;
842 while (1) { 830 while (1) {
843 entry = table + i; 831 entry = table + (i & sizeMask);
844 832
845 // we count on the compiler to optimize out this branch 833 // we count on the compiler to optimize out this branch
846 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 834 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
847 if (isEmptyBucket(*entry)) 835 if (isEmptyBucket(*entry))
848 break; 836 break;
849 837
850 if (HashTranslator::equal(Extractor::extract(*entry), key)) 838 if (HashTranslator::equal(Extractor::extract(*entry), key))
851 return AddResult(makeKnownGoodIterator(entry), false); 839 return AddResult(makeKnownGoodIterator(entry), false);
852 840
853 if (isDeletedBucket(*entry)) 841 if (isDeletedBucket(*entry))
(...skipping 10 matching lines...) Expand all
864 #if DUMP_HASHTABLE_STATS 852 #if DUMP_HASHTABLE_STATS
865 ++probeCount; 853 ++probeCount;
866 HashTableStats::recordCollisionAtCount(probeCount); 854 HashTableStats::recordCollisionAtCount(probeCount);
867 #endif 855 #endif
868 856
869 #if DUMP_HASHTABLE_STATS_PER_TABLE 857 #if DUMP_HASHTABLE_STATS_PER_TABLE
870 ++perTableProbeCount; 858 ++perTableProbeCount;
871 m_stats->recordCollisionAtCount(perTableProbeCount); 859 m_stats->recordCollisionAtCount(perTableProbeCount);
872 #endif 860 #endif
873 861
874 if (k == 0) 862 perturb >>= perturbShift;
875 k = 1 | doubleHash(h); 863 i = i*5 + perturb + 1;
876 i = (i + k) & sizeMask;
877 } 864 }
878 865
879 if (deletedEntry) { 866 if (deletedEntry) {
880 initializeBucket(*deletedEntry); 867 initializeBucket(*deletedEntry);
881 entry = deletedEntry; 868 entry = deletedEntry;
882 --m_deletedCount; 869 --m_deletedCount;
883 } 870 }
884 871
885 HashTranslator::translate(*entry, key, extra); 872 HashTranslator::translate(*entry, key, extra);
886 873
(...skipping 524 matching lines...) Expand 10 before | Expand all | Expand 10 after
1411 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa bleConstIteratorAdapter<T, U>& b) 1398 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa bleConstIteratorAdapter<T, U>& b)
1412 { 1399 {
1413 return a.m_impl != b.m_impl; 1400 return a.m_impl != b.m_impl;
1414 } 1401 }
1415 1402
1416 } // namespace WTF 1403 } // namespace WTF
1417 1404
1418 #include <wtf/HashIterators.h> 1405 #include <wtf/HashIterators.h>
1419 1406
1420 #endif // WTF_HashTable_h 1407 #endif // WTF_HashTable_h
OLDNEW
« no previous file with comments | « LayoutTests/fast/css-grid-layout/named-grid-line-get-set-expected.txt ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698