Skip to content
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.

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

Algorithm improvements #15

Merged
merged 3 commits into from Jan 10, 2018
Merged

Algorithm improvements #15

merged 3 commits into from Jan 10, 2018

Conversation

chessman
Copy link
Contributor

I have a test that checks a space utilization:

	cf := cuckoofilter.NewCuckooFilter(cap)
	for i := uint(0); i < cap; i++ {
		ok := cf.Insert(randomBytes())
		if !ok {
			fmt.Printf("Error on %v/%v\n", i, cap)
		}
	}

With unmodified version of the cuckoofilter I have an error on 64073/1048576. It means that reinsert failed after 6% entries occupied.

With this PR I have no errors up to 96% space utilized. I believe that the problem is the similar hashing algorithms of fingerprint and i1. Your version is trying to reinsert fp to the same bucket and after maxCuckooCount it fails.

Also I removed the unnecessary lock in getFingerprint because it affected the use of multiple instances of the filter and didn't make the filter thread-safe. I think that lock should be in a filter object and lock/unlock should protect each public method.

@seiflotfy seiflotfy merged commit 9e8f22b into seiflotfy:master Jan 10, 2018
@seiflotfy
Copy link
Owner

thanks so so much

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants