[PATCH] remove loop in lookuptable_delete
Reported by Jeremy Roach | March 9th, 2008 @ 04:00 PM | in 1.0 preview
bins = 2^n, bins >= 16 [LOOKUPTABLE_MIN_SIZE]
entries < (30% of bins) [LOOKUPTABLE_MIN_DENSITY]
(30% of bins) = (60% of (bins / 2))
((entries / (bins / 2)) * 100)% < 60% < 75% [LOOKUPTABLE_MAX_DENSITY]
Comments and changes to this ticket
-
Charles Comstock March 11th, 2008 @ 03:07 PM
- → State changed from “new” to “open”
Please format as a real patch. This is merely the diff output. Commit the change to your local branch, and then generate a patch for submission using git-format-patch.
-
-
Brian Ford March 12th, 2008 @ 05:42 PM
- → State changed from “open” to “resolved”
Well, I had to read this a bunch of times, but I think I got it. :) If not, please correct me. I would say it like this:
If the hash density (percentage of entries to bins) is less than 30%, then double that will be less than 60%. So, halving the number of bins will result in hash density still being below 75%, which is max hash density. So, just divide the existing number of bins by 2, preserving the invariant that bins be a power of 2.
Committed in 8a34b7c95. Thanks!
Please Login or create a free account to add a new comment.
You can update this ticket by sending an email to from your email client. (help)
Create your profile
Help contribute to this project by taking a few moments to create your personal profile. Create your profile »
