Skip to content

Do not ceil k hash functions. #105

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 1 commit into
base: master
Choose a base branch
from
Open

Do not ceil k hash functions. #105

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Do not ceil k hash functions. 
Flooring `k` instead of ceiling has meaningful effect on performance since: (1) `k` is smaller by 1 which translate for fewer calls. (2) the fillrate of the filter is lower so non existing elements will get a negative bit faster.

For a filter with 1% false-positive-probability we can expect a 10-15% performance gain.
  • Loading branch information
@ashtul
ashtul authored Nov 7, 2024
commit 334b9d52b89df19357ef1a78f0077ff34bb3d256
2 changes: 1 addition & 1 deletion bloom.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -132,7 +132,7 @@ func (f *BloomFilter) location(h [4]uint64, i uint) uint {
// used with permission.
func EstimateParameters(n uint, p float64) (m uint, k uint) {
m = uint(math.Ceil(-1 * float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))
k = uint(math.Ceil(math.Log(2) * float64(m) / float64(n)))
k = uint(math.Log(2) * float64(m) / float64(n))
return
}

Expand Down