Closed Bug 1828560 Opened 2 years ago Closed 2 years ago

BitBloomFilter does not use top 3 bits

Categories

(Core :: JavaScript Engine: JIT, enhancement, P3)

enhancement

Tracking

()

RESOLVED FIXED
114 Branch
Tracking Status
firefox114 --- fixed

People

(Reporter: arai, Assigned: arai)

References

Details

(Whiteboard: [sp3])

Attachments

(2 files)

https://searchfox.org/mozilla-central/rev/31f5847a4494b3646edabbdd7ea39cb88509afe2/mfbt/BloomFilter.h#138-140,142,154-158,167

static const size_t kArraySize = (1 << (KeySize - 3));
static const uint32_t kKeyMask = (1 << (KeySize - 3)) - 1;
static const uint32_t kKeyShift = 16;
...
static uint32_t hash1(uint32_t aHash) { return aHash & kKeyMask; }
...
void setSlot(uint32_t aHash) {
  uint32_t index = aHash / 8;
  uint8_t shift = aHash % 8;
  uint8_t bit = 1 << shift;
  mCounters[index] |= bit;
...
uint8_t mCounters[kArraySize];

KeySize - 3 in kArraySize is because single entry is uint8_t,

kKeyMask shouldn't use KeySize - 3 but just KeySize, because the result is used to point single bit, and the - 3 part is already performed by aHash / 8 and aHash % 8 in setSlot.

The point of a bloom filter is not to be correct, as false positive are acceptable.
Thus is technically not invalid to ignore some of the bits.

Is there any other reasoning behind the "part 1" ?

Severity: -- → N/A
Type: defect → enhancement
Priority: -- → P3

(In reply to Nicolas B. Pierron [:nbp] from comment #3)

The point of a bloom filter is not to be correct, as false positive are acceptable.
Thus is technically not invalid to ignore some of the bits.

Is there any other reasoning behind the "part 1" ?

the code was using 2 ** (KeySize - 3) bits, instead of 2 ** KeySize bits, which means the only 1/8 of the array was used.

Whiteboard: [sp3]
Pushed by arai_a@mac.com: https://hg.mozilla.org/integration/autoland/rev/932f5df42bd2 Part 1: Use correct kKeyMask in BitBloomFilter. r=dpalmeiro https://hg.mozilla.org/integration/autoland/rev/fd4414470dad Part 2: Rename BitBloomFilter::mCounters to mBits. r=dpalmeiro
Status: ASSIGNED → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → 114 Branch
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: