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

[WIP] Add FNV1a hash function #1760

Open
wants to merge 2 commits into
base: master
Choose a base branch
from
Open

[WIP] Add FNV1a hash function #1760

wants to merge 2 commits into from

Conversation

betatim
Copy link
Member

@betatim betatim commented Aug 22, 2017

Fixes #1757

Test driving the FNV hash. Benchmarks to do:

  • computation time
  • "quality" of the hashing (returning a constant would be a fast hash, but low quality) not sure yet how to measure this.
  • Is it mergeable?
  • make test Did it pass the tests?
  • make clean diff-cover If it introduces new functionality in
    scripts/ is it tested?
  • make format diff_pylint_report cppcheck doc pydocstyle Is it well
    formatted?
  • Did it change the command-line interface? Only backwards-compatible
    additions are allowed without a major version increment. Changing file
    formats also requires a major version number increment.
  • For substantial changes or changes to the command-line interface, is it
    documented in CHANGELOG.md? See keepachangelog
    for more details.
  • Was a spellchecker run on the source code and documentation after
    changes were made?
  • Do the changes respect streaming IO? (Are they
    tested for streaming IO?)

@betatim
Copy link
Member Author

betatim commented Aug 22, 2017

Surprising how few tests fail with this!

@ctb
Copy link
Member

ctb commented Aug 22, 2017

nice :).

@betatim betatim mentioned this pull request Aug 23, 2017
Open
@betatim
Copy link
Member Author

betatim commented Aug 25, 2017

Results from running this script as a benchmark.

$ python fp.py bf # FNV
kind, load, query, t_load, t_queryNP, t_queryP
bf, 9000000, 1000000, 10.381915807723999, 1.5168020725250244, 1.2786040306091309
bf, 9000000, 1000000, 10.489625930786133, 1.3121399879455566, 1.2331571578979492
bf, 9000000, 1000000, 9.589091062545776, 1.1095459461212158, 1.0996849536895752
bf, 9000000, 1000000, 10.481687068939209, 1.2617030143737793, 1.159147024154663

$ python fp.py bf # murmur
kind, load, query, t_load, t_queryNP, t_queryP
bf, 9000000, 1000000, 10.766052007675171, 1.184602975845337, 1.1206409931182861
bf, 9000000, 1000000, 9.716826915740967, 1.169848918914795, 1.0594408512115479
bf, 9000000, 1000000, 10.398908853530884, 1.231614112854004, 1.2056090831756592
bf, 9000000, 1000000, 11.516963958740234, 1.6280360221862793, 1.1633579730987549
bf, 9000000, 1000000, 10.743386030197144, 1.2828280925750732, 1.1859049797058105

The thing to look at are the last three columns which measure how long how it takes to load kmers, lookup a kmer that isn't present and kmers which are present.

Observations: the benchmark isn't very useful because it is pretty noisy and I'd conclude that FNV1a is no faster than murmurhash. I find that at least somewhat surprising.

@ctb
Copy link
Member

ctb commented Aug 26, 2017 via email

@codecov-io
Copy link

Codecov Report

Merging #1760 into master will increase coverage by <.01%.
The diff coverage is 0%.

Impacted file tree graph

@@            Coverage Diff            @@
##           master   #1760      +/-   ##
=========================================
+ Coverage    0.05%   0.06%   +<.01%     
=========================================
  Files          87      78       -9     
  Lines       11441    9807    -1634     
  Branches     3072    2459     -613     
=========================================
  Hits            6       6              
+ Misses      11435    9801    -1634
Impacted Files Coverage Δ
include/oxli/hashtable.hh 0% <ø> (ø) ⬆️
include/oxli/kmer_hash.hh 0% <ø> (ø) ⬆️
src/oxli/kmer_hash.cc 0% <0%> (ø) ⬆️
src/oxli/hllcounter.cc 0% <0%> (ø) ⬆️
scripts/abundance-dist.py 0% <0%> (ø) ⬆️
scripts/trim-low-abund.py 0% <0%> (ø) ⬆️
scripts/make-initial-stoptags.py 0% <0%> (ø) ⬆️
src/oxli/labelhash.cc 0% <0%> (ø) ⬆️
include/oxli/hashgraph.hh 0% <0%> (ø) ⬆️
src/khmer/_cpy_khmer.cc 0% <0%> (ø) ⬆️
... and 14 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update acdacef...43aaf93. Read the comment docs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@betatim @ctb @codecov-io