This assumes that
a) finding the bucket containing the value is LIKELY
b) finding an empty bucket is LIKELY
c) growing the table is UNLIKELY
I also switched the a) and b) cases for SmallPtrSet as we seem to use
the set mostly more for insertion than for checking existence.
In a simple benchmark consisting of 2^21 insertions of 2^20 unique
pointers into a DenseMap or SmallPtrSet a few percent speedup on average,
but nothing statistically significant.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@230232
91177308-0d34-0410-b5e6-
96231b3b80d8
// causing infinite loops in lookup.
unsigned NewNumEntries = getNumEntries() + 1;
unsigned NumBuckets = getNumBuckets();
- if (NewNumEntries*4 >= NumBuckets*3) {
+ if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
this->grow(NumBuckets * 2);
LookupBucketFor(Key, TheBucket);
NumBuckets = getNumBuckets();
- } else if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) {
+ } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
+ NumBuckets/8)) {
this->grow(NumBuckets);
LookupBucketFor(Key, TheBucket);
}
while (1) {
const BucketT *ThisBucket = BucketsPtr + BucketNo;
// Found Val's bucket? If so, return it.
- if (KeyInfoT::isEqual(Val, ThisBucket->getFirst())) {
+ if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
FoundBucket = ThisBucket;
return true;
}
// If we found an empty bucket, the key doesn't exist in the set.
// Insert it and return the default value.
- if (KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey)) {
+ if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
// If we've already seen a tombstone while probing, fill it in instead
// of the empty bucket we eventually probed to.
FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
}
// Otherwise, hit the big set case, which will call grow.
}
-
- if (NumElements*4 >= CurArraySize*3) {
+
+ if (LLVM_UNLIKELY(NumElements * 4 >= CurArraySize * 3)) {
// If more than 3/4 of the array is full, grow.
Grow(CurArraySize < 64 ? 128 : CurArraySize*2);
- } else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) {
+ } else if (LLVM_UNLIKELY(CurArraySize - (NumElements + NumTombstones) <
+ CurArraySize / 8)) {
// If fewer of 1/8 of the array is empty (meaning that many are filled with
// tombstones), rehash.
Grow(CurArraySize);
const void *const *Array = CurArray;
const void *const *Tombstone = nullptr;
while (1) {
- // Found Ptr's bucket?
- if (Array[Bucket] == Ptr)
- return Array+Bucket;
-
// If we found an empty bucket, the pointer doesn't exist in the set.
// Return a tombstone if we've seen one so far, or the empty bucket if
// not.
- if (Array[Bucket] == getEmptyMarker())
+ if (LLVM_LIKELY(Array[Bucket] == getEmptyMarker()))
return Tombstone ? Tombstone : Array+Bucket;
-
+
+ // Found Ptr's bucket?
+ if (LLVM_LIKELY(Array[Bucket] == Ptr))
+ return Array+Bucket;
+
// If this is a tombstone, remember it. If Ptr ends up not in the set, we
// prefer to return it than something that would require more probing.
if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
// If the hash table is now more than 3/4 full, or if fewer than 1/8 of
// the buckets are empty (meaning that many are filled with tombstones),
// grow/rehash the table.
- if (NumItems*4 > NumBuckets*3) {
+ if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
NewSize = NumBuckets*2;
- } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) {
+ } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=
+ NumBuckets / 8)) {
NewSize = NumBuckets;
} else {
return BucketNo;