{"action":"created","issue":{"url":"https://api.github.com/repos/dib-lab/khmer/issues/1444","repository_url":"https://api.github.com/repos/dib-lab/khmer","labels_url":"https://api.github.com/repos/dib-lab/khmer/issues/1444/labels{/name}","comments_url":"https://api.github.com/repos/dib-lab/khmer/issues/1444/comments","events_url":"https://api.github.com/repos/dib-lab/khmer/issues/1444/events","html_url":"https://github.com/dib-lab/khmer/pull/1444","id":176398897,"number":1444,"title":"A type to store large hash values (>64bit)","user":{"login":"betatim","id":1448859,"avatar_url":"https://avatars.githubusercontent.com/u/1448859?v=3","gravatar_id":"","url":"https://api.github.com/users/betatim","html_url":"https://github.com/betatim","followers_url":"https://api.github.com/users/betatim/followers","following_url":"https://api.github.com/users/betatim/following{/other_user}","gists_url":"https://api.github.com/users/betatim/gists{/gist_id}","starred_url":"https://api.github.com/users/betatim/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/betatim/subscriptions","organizations_url":"https://api.github.com/users/betatim/orgs","repos_url":"https://api.github.com/users/betatim/repos","events_url":"https://api.github.com/users/betatim/events{/privacy}","received_events_url":"https://api.github.com/users/betatim/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":13,"created_at":"2016-09-12T15:01:07Z","updated_at":"2016-09-14T14:48:48Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/dib-lab/khmer/pulls/1444","html_url":"https://github.com/dib-lab/khmer/pull/1444","diff_url":"https://github.com/dib-lab/khmer/pull/1444.diff","patch_url":"https://github.com/dib-lab/khmer/pull/1444.patch"},"body":"Exploratory surgery for #1442 \r\n\r\nThis uses a byte array to store the hash value. We can template or similar to support \"arbitrarily\" large hash values.\r\n\r\nAt the moment trying to make it work and get some tests to pass. After that speeding up the code. it currently also contains various stuff that is useful for development but you might want to remove later.\r\n\r\n- [ ] benchmark `bits` vs `bytes` vs `uint64` as type of the array\r\n- [ ] clean up spurious `#include`s\r\n- [ ] asserts or other protection when users try and `|` or `&` values larger than one byte\r\n- [ ] Is it mergeable?\r\n- [ ] `make test` Did it pass the tests?\r\n- [ ] `make clean diff-cover` If it introduces new functionality in\r\n  `scripts/` is it tested?\r\n- [ ] `make format diff_pylint_report cppcheck doc pydocstyle` Is it well\r\n  formatted?\r\n- [ ] Did it change the command-line interface? Only additions are allowed\r\n  without a major version increment. Changing file formats also requires a\r\n  major version number increment.\r\n- [ ] Is it documented in the `ChangeLog`?\r\n  http://en.wikipedia.org/wiki/Changelog#Format\r\n- [ ] Was a spellchecker run on the source code and documentation after\r\n  changes were made?\r\n- [ ] Do the changes respect streaming IO? (Are they\r\n  tested for streaming IO?)\r\n- [ ] Is the Copyright year up to date?\r\n"},"comment":{"url":"https://api.github.com/repos/dib-lab/khmer/issues/comments/247038018","html_url":"https://github.com/dib-lab/khmer/pull/1444#issuecomment-247038018","issue_url":"https://api.github.com/repos/dib-lab/khmer/issues/1444","id":247038018,"user":{"login":"betatim","id":1448859,"avatar_url":"https://avatars.githubusercontent.com/u/1448859?v=3","gravatar_id":"","url":"https://api.github.com/users/betatim","html_url":"https://github.com/betatim","followers_url":"https://api.github.com/users/betatim/followers","following_url":"https://api.github.com/users/betatim/following{/other_user}","gists_url":"https://api.github.com/users/betatim/gists{/gist_id}","starred_url":"https://api.github.com/users/betatim/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/betatim/subscriptions","organizations_url":"https://api.github.com/users/betatim/orgs","repos_url":"https://api.github.com/users/betatim/repos","events_url":"https://api.github.com/users/betatim/events{/privacy}","received_events_url":"https://api.github.com/users/betatim/received_events","type":"User","site_admin":false},"created_at":"2016-09-14T14:48:48Z","updated_at":"2016-09-14T14:48:48Z","body":"[Some benchmarks](https://gist.github.com/betatim/f1351ad06fbb3029a1a5de4029463bf9):\r\n\r\n`hashing_basic` is the current implementation with a `uint64`. `bighash` uses an array of `N` integers of type `T`. The last two numbers indicate the length of the kmer (8, 16, 24, 32) and which one of two strings was used (both random sequences). My conclusions from this wall of numbers:\r\n\r\n* single `uint64` wrapped in a `BigHashType` is nearly as fast as just a `uint64`\r\n* as you increase the size of the basic type (and reduce `N`) performance improves\r\n* `hashing_bighash<uint8_t, 8>` is a bad idea?!\r\n* (not shown here but in the benchmark `bitset` is slower than `hashing_bighash<uint8_t, 8>`)\r\n* converting from a `BigHashType` to a `uint64` is pretty slow, we should avoid doing that when ever possible (-> compute the modulus directly)\r\n\r\nIf you have some experience with `google-benchmark` I'd like to chat with you. With compilers being super sneaky these days I worry that these benchmarks don't actually benchmark what I want to test.\r\n\r\n```\r\nBenchmark                                  Time           CPU Iterations\r\n------------------------------------------------------------------------\r\nhashing_basic/8/1                         20 ns         40 ns   17541837\r\nhashing_basic/8/2                         20 ns         23 ns  178492200\r\nhashing_basic/16/1                        44 ns         52 ns   86685160\r\nhashing_basic/16/2                        43 ns         49 ns   84504320\r\nhashing_basic/24/1                        63 ns         72 ns   54933840\r\nhashing_basic/24/2                        64 ns         71 ns   52610220\r\nhashing_basic/32/1                        87 ns         98 ns   41023000\r\nhashing_basic/32/2                        90 ns        177 ns    3775009\r\nhashing_bighash<uint8_t, 8>/8/1          104 ns        107 ns   10000000\r\nhashing_bighash<uint8_t, 8>/8/2          102 ns        203 ns    3449941\r\nhashing_bighash<uint8_t, 8>/16/1         213 ns        228 ns   15286310\r\nhashing_bighash<uint8_t, 8>/16/2         215 ns        430 ns    1642105\r\nhashing_bighash<uint8_t, 8>/24/1         321 ns        641 ns    1000000\r\nhashing_bighash<uint8_t, 8>/24/2         319 ns        638 ns    1113550\r\nhashing_bighash<uint8_t, 8>/32/1         450 ns        523 ns    8079410\r\nhashing_bighash<uint8_t, 8>/32/2         453 ns        499 ns    7537900\r\nhashing_bighash<uint16_t, 4>/8/1          66 ns        131 ns    5386107\r\nhashing_bighash<uint16_t, 4>/8/2          71 ns        139 ns   10000000\r\nhashing_bighash<uint16_t, 4>/16/1        141 ns        155 ns   24197510\r\nhashing_bighash<uint16_t, 4>/16/2        135 ns        150 ns   25038090\r\nhashing_bighash<uint16_t, 4>/24/1        202 ns        227 ns   16956210\r\nhashing_bighash<uint16_t, 4>/24/2        203 ns        227 ns   16856020\r\nhashing_bighash<uint16_t, 4>/32/1        272 ns        543 ns    1314850\r\nhashing_bighash<uint16_t, 4>/32/2        271 ns        313 ns   13142580\r\nhashing_bighash<uint32_t, 2>/8/1          30 ns         34 ns  116678330\r\nhashing_bighash<uint32_t, 2>/8/2          29 ns         31 ns  108268630\r\nhashing_bighash<uint32_t, 2>/16/1         61 ns        121 ns    5961404\r\nhashing_bighash<uint32_t, 2>/16/2         62 ns         71 ns   58215930\r\nhashing_bighash<uint32_t, 2>/24/1         93 ns        102 ns   36724590\r\nhashing_bighash<uint32_t, 2>/24/2         90 ns        180 ns    3883926\r\nhashing_bighash<uint32_t, 2>/32/1        122 ns        139 ns   29083780\r\nhashing_bighash<uint32_t, 2>/32/2        123 ns        140 ns   28921320\r\nhashing_bighash<uint64_t, 1>/8/1          22 ns         23 ns  100000000\r\nhashing_bighash<uint64_t, 1>/8/2          20 ns         40 ns   17014326\r\nhashing_bighash<uint64_t, 1>/16/1         42 ns         48 ns   82092180\r\nhashing_bighash<uint64_t, 1>/16/2         42 ns         49 ns   84606460\r\nhashing_bighash<uint64_t, 1>/24/1         64 ns         74 ns   55392890\r\nhashing_bighash<uint64_t, 1>/24/2         70 ns         81 ns   52367770\r\nhashing_bighash<uint64_t, 1>/32/1         88 ns         98 ns   39777700\r\nhashing_bighash<uint64_t, 1>/32/2         86 ns        170 ns    4043905\r\nhashing_bighash<uint64_t, 2>/8/1          37 ns         72 ns   10000000\r\nhashing_bighash<uint64_t, 2>/8/2          34 ns         68 ns   10315659\r\nhashing_bighash<uint64_t, 2>/16/1         69 ns         80 ns   52080230\r\nhashing_bighash<uint64_t, 2>/16/2         70 ns         80 ns   50454090\r\nhashing_bighash<uint64_t, 2>/24/1        109 ns        129 ns   34405140\r\nhashing_bighash<uint64_t, 2>/24/2        109 ns        116 ns   10000000\r\nhashing_bighash<uint64_t, 2>/32/1        148 ns        296 ns    2319986\r\nhashing_bighash<uint64_t, 2>/32/2        146 ns        163 ns   23393220\r\nhashing_bighash<uint64_t, 2>/40/1        182 ns        209 ns   19664030\r\nhashing_bighash<uint64_t, 2>/40/2        181 ns        201 ns   18983150\r\n```"}}
{"actor":{"display_login":"betatim"}}