{"action":"created","issue":{"url":"https://api.github.com/repos/rust-bio/rust-bio/issues/76","repository_url":"https://api.github.com/repos/rust-bio/rust-bio","labels_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/76/labels{/name}","comments_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/76/comments","events_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/76/events","html_url":"https://github.com/rust-bio/rust-bio/pull/76","id":167419154,"number":76,"title":"Occ::get performance, redux","user":{"login":"dikaiosune","id":6812281,"avatar_url":"https://avatars.githubusercontent.com/u/6812281?v=3","gravatar_id":"","url":"https://api.github.com/users/dikaiosune","html_url":"https://github.com/dikaiosune","followers_url":"https://api.github.com/users/dikaiosune/followers","following_url":"https://api.github.com/users/dikaiosune/following{/other_user}","gists_url":"https://api.github.com/users/dikaiosune/gists{/gist_id}","starred_url":"https://api.github.com/users/dikaiosune/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dikaiosune/subscriptions","organizations_url":"https://api.github.com/users/dikaiosune/orgs","repos_url":"https://api.github.com/users/dikaiosune/repos","events_url":"https://api.github.com/users/dikaiosune/events{/privacy}","received_events_url":"https://api.github.com/users/dikaiosune/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":16,"created_at":"2016-07-25T17:19:14Z","updated_at":"2016-08-15T07:28:46Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/rust-bio/rust-bio/pulls/76","html_url":"https://github.com/rust-bio/rust-bio/pull/76","diff_url":"https://github.com/rust-bio/rust-bio/pull/76.diff","patch_url":"https://github.com/rust-bio/rust-bio/pull/76.patch"},"body":"I ended up writing a blog post about the tools I used for profiling the change I proposed to Occ::get. Fun story, @aatch [pointed out on Reddit](https://www.reddit.com/r/rust/comments/4udxmr/rust_performance_a_story_featuring_perf_and/d5plly1) that the slowdown in some other versions I had tried was probably due to the overhead of dealing with alignment in a vectorized version of the function, and noted that 3 may be an odd sample rate to test with the FMIndex. As an example, bowtie2's FM index appears to default to a sampling rate of 32, and I've seen a few cases of using higher rates as well.\r\n\r\nThe version of Occ::get proposed by Aatch is at approximate parity with the filter/count version for performance at a sampling rate of 32 (just a tiny bit slower), but it quickly gets much, much faster as the sampling rate increases. For example, with a sampling rate of 128 (in use in one of my applications):\r\n\r\nfilter/count, k = 128\r\n```\r\ntest search_index_seeds ... bench:     179,442 ns/iter (+/- 1,947)\r\n```\r\n\r\nvectorized, k = 128\r\n```\r\ntest search_index_seeds ... bench:     152,368 ns/iter (+/- 433)\r\n```\r\n\r\nfilter/count, k = 64\r\n```\r\ntest search_index_seeds ... bench:     105,141 ns/iter (+/- 1,665)\r\n```\r\n\r\nvectorized, k = 64\r\n```\r\ntest search_index_seeds ... bench:      99,044 ns/iter (+/- 252)\r\n```\r\n\r\nfilter/count, k = 32\r\n```\r\ntest search_index_seeds ... bench:      74,427 ns/iter (+/- 5,166)\r\n```\r\n\r\nvectorized, k = 32\r\n```\r\ntest search_index_seeds ... bench:      75,333 ns/iter (+/- 303)\r\n```\r\n\r\nSeems like an overall win to me. At a `k` of 32, the averages are just slightly higher than the filter/count version, but well within the error margin reported by libtest.\r\n\r\nThe one downside here is that at smaller sampling rates, a non-vectorized version wins out:\r\n\r\nfilter/count, k = 8\r\n```\r\ntest search_index_seeds ... bench:      40,598 ns/iter (+/- 1,170)\r\n```\r\n\r\nvectorized, k = 8\r\n```\r\ntest search_index_seeds ... bench:      53,842 ns/iter (+/- 224)\r\n```\r\n\r\nThoughts here? Without integer generics (at all) and specialization (in stable), I'm not sure it's possible to cleanly maximize performance of small sampling rates and large ones. I'm biased here because I'm working with very large indices that need high sampling rates, but I'm not sure what other values of `k` are \"in the wild.\""},"comment":{"url":"https://api.github.com/repos/rust-bio/rust-bio/issues/comments/239744101","html_url":"https://github.com/rust-bio/rust-bio/pull/76#issuecomment-239744101","issue_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/76","id":239744101,"user":{"login":"johanneskoester","id":1858646,"avatar_url":"https://avatars.githubusercontent.com/u/1858646?v=3","gravatar_id":"","url":"https://api.github.com/users/johanneskoester","html_url":"https://github.com/johanneskoester","followers_url":"https://api.github.com/users/johanneskoester/followers","following_url":"https://api.github.com/users/johanneskoester/following{/other_user}","gists_url":"https://api.github.com/users/johanneskoester/gists{/gist_id}","starred_url":"https://api.github.com/users/johanneskoester/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/johanneskoester/subscriptions","organizations_url":"https://api.github.com/users/johanneskoester/orgs","repos_url":"https://api.github.com/users/johanneskoester/repos","events_url":"https://api.github.com/users/johanneskoester/events{/privacy}","received_events_url":"https://api.github.com/users/johanneskoester/received_events","type":"User","site_admin":false},"created_at":"2016-08-15T07:28:46Z","updated_at":"2016-08-15T07:28:46Z","body":"Maybe you can add some comments to the code that explain why no iterators are used in the refined implementation. This way, we ensure that your insights on this snippet are not lost or even reverted at later times."}}
{"actor":{"display_login":"johanneskoester"}}