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.

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

Jump to bottom

Reconsider hashing strategy #22

Closed
crepererum opened this issue Jun 17, 2018 · 4 comments
Closed

Reconsider hashing strategy #22

crepererum opened this issue Jun 17, 2018 · 4 comments
Assignees
@crepererum
Labels
global Repo-wide/generic enhancements

Comments

@crepererum
Copy link
Member

Right now, we use integer modulo hashing, which may have some serious consequences for hashing quality and performance. Evaluate if Fibonacci hashing would be an option.
@crepererum
Copy link
Member Author

Blocked on #9

@crepererum
Copy link
Member Author

See

https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/

https://en.m.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use

Fibonacci Hashing: The Optimization That the World Forgot - https://news.ycombinator.com/item?id=17328756

@crepererum crepererum added the global Repo-wide/generic enhancements label Aug 16, 2018
@crepererum
Copy link
Member Author

Also see 5.2. in https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf

@crepererum crepererum self-assigned this Aug 25, 2018
@crepererum crepererum mentioned this issue Aug 25, 2018
Merged
bors bot added a commit that referenced this issue Aug 25, 2018
@bors @crepererum
Merge #32
b74c233 
32: Improve hashing r=crepererum a=crepererum

Result:
![screenshot from 2018-08-25 18-57-43](https://user-images.githubusercontent.com/1529400/44620666-d2353d80-a898-11e8-97b2-a373c00130a5.png)

See #22.

Co-authored-by: Marco Neumann <[email protected]>
@crepererum
Copy link
Member Author

Fibonacci hashing won't work because the domain is of hash function we genera is not always a power of 2. But #32 improved the situation quite a bit, so I think this mission is complete for now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@crepererum crepererum

Labels
global Repo-wide/generic enhancements
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@crepererum