{"action":"created","issue":{"url":"https://api.github.com/repos/rust-bio/rust-bio/issues/68","repository_url":"https://api.github.com/repos/rust-bio/rust-bio","labels_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/68/labels{/name}","comments_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/68/comments","events_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/68/events","html_url":"https://github.com/rust-bio/rust-bio/pull/68","id":164957123,"number":68,"title":"FM Index + Suffix Array Sampling, removing reference counts","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":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":10,"created_at":"2016-07-11T22:48:59Z","updated_at":"2016-07-12T17:16:41Z","closed_at":"2016-07-12T17:16:41Z","pull_request":{"url":"https://api.github.com/repos/rust-bio/rust-bio/pulls/68","html_url":"https://github.com/rust-bio/rust-bio/pull/68","diff_url":"https://github.com/rust-bio/rust-bio/pull/68.diff","patch_url":"https://github.com/rust-bio/rust-bio/pull/68.patch"},"body":"**TDLR: I made sampled suffix arrays work with FMIndex, but it's sort of been polluted by a refactoring of FMIndex I was also working on. Thanks for taking a look!**\r\n\r\nApologies in advance for a PR with two concerns and the wall of text. I was working on a fork of FMIndex that would allow me to avoid reference counting (it hurt me a little in some of my benchmarks), and also decided to try to make the sampled suffix array approach work. In short, I have a PR which does both: moving FMIndex to a generics-based version with no reference counting (but which also allows both raw and sampled SAs), and also fixes the sampled suffix array lookup to allow for reduced memory usage.\r\n\r\nThe sampled suffix array technique I used is based on the example Python code here:\r\n\r\nhttp://nbviewer.jupyter.org/github/BenLangmead/comp-genomics-class/blob/master/notebooks/CG_FmIndex.ipynb\r\n\r\nslides here:\r\n\r\nhttps://www.cs.jhu.edu/~langmea/resources/lecture_notes/bwt_and_fm_index.pdf\r\n\r\nand recorded lecture here:\r\n\r\nhttps://www.youtube.com/watch?v=kvVGj5V65io\r\n\r\nI am sure this is not a perfect implementation and that the API design may need some work to account for other use cases, so I'm mostly submitting this PR to provide some context for discussion. There are a couple of known issues with this approach, and some questions that I consider open.\r\n\r\n## Advantages\r\n\r\n1. Uses generics without reference counting to allow both raw and sampled suffix arrays in FMIndex/FMDIndex.\r\n2. Sampled suffix array potentially reduces memory usage at a minimal performance tradeoff (depending on sampling rate -- see benchmarks).\r\n\r\n## Potential disadvantages\r\n\r\n1. When multiple sentinel characters are present in a text, the sampled suffix array is not able to match a raw suffix array's output. I'm honestly not sure whether this is something which should be supported, and at the very least the Python code from Ben Langmead (above) has nearly identical behavior with multiple sentinels.\r\n2. HashMap performance with the default SIPHasher is not ideal for small keys. This could be improved by moving to an FNV hasher, but it would be an additional dependency to track, and would also break serialization/deserialization (PR incoming for that too, BTW).\r\n3. This would be a breaking change to several APIs (but so was the recent move to `Deref` IIRC). Since rust-bio is pre-1.0, I don't think any major version bump would be needed.\r\n4. One advantage of the `Deref`-based API is that the suffix array could be kept separate from the FMIndex. While the changes I propose eliminate that specific pattern, it's still possible to make a `Rc<FMIndex<FMIndexCore>>` and call `FMIndexable::sa()` on it to get a reference to the suffix array.\r\n\r\n## Open Questions\r\n\r\n* Should multiple sentinel characters in database sequences stay in the test cases? If so, is it OK for the sampled suffix array to not include them?\r\n* Should the HashMap implementation be swapped out for something else entirely (either a Vec or a BTreeMap)? A BTreeMap shows *slightly* better performance for smaller tests, but I imagine it's going to scale poorly compared to a HashMap at larger sizes (for example, I'm currently running tests with 250GB suffix arrays, and I don't imagine BTreeMap would hold up well there). We could add another layer of generics, but I feel that would be clunky.\r\n* Is the performance gain from removing reference counting worth the complications to the API? It is for my use case (which is why I started the work in the first place), and I think that allowing the FM Index to provide access to the underlying suffix array is good enough.\r\n* Should the FMIndex be given a method which consumes self and returns the underlying FMIndexCore? This would allow a user to \"get back\" their suffix array, BWT, etc. when done with the FMIndex. I don't have a specific need for this, but I recognize that the suffix array was left separately for a reason when first designed.\r\n\r\n## Benchmarks\r\n\r\nOn my machine, with a 1.6Ghz Xeon:\r\n\r\n```\r\n$ rustup run nightly cargo bench fmindex\r\n   Compiling bio v0.7.0 (file:///home/adam/rust-projects/rust-bio)\r\n     Running target/release/bio-e7ffa72605bd6174\r\n...\r\nrunning 4 tests\r\ntest bench_fmindex_creation_raw_sa        ... bench:   4,141,403 ns/iter (+/- 156,132)\r\ntest bench_fmindex_creation_sampled_sa_32 ... bench:   4,279,735 ns/iter (+/- 114,902)\r\ntest bench_fmindex_raw_sa                 ... bench:       1,052 ns/iter (+/- 20)\r\ntest bench_fmindex_sampled_sa_32          ... bench:       4,045 ns/iter (+/- 82)\r\n\r\ntest result: ok. 0 passed; 0 failed; 0 ignored; 4 measured\r\n```\r\n\r\nSeems like not a bad performance tradeoff to make available. Could probably be optimized further, but I think this is a good start.\r\n\r\n---\r\n\r\nI believe this would close #45 if merged, so I'm pinging @cramertj.\r\n"},"comment":{"url":"https://api.github.com/repos/rust-bio/rust-bio/issues/comments/232114767","html_url":"https://github.com/rust-bio/rust-bio/pull/68#issuecomment-232114767","issue_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/68","id":232114767,"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},"created_at":"2016-07-12T17:16:40Z","updated_at":"2016-07-12T17:16:40Z","body":"So, a couple of things are obvious to me after a good night's sleep: there are too many interleaved issues here, and the only code from this diff likely to be mergeable is the SampledSuffixArray (and only after figuring out the multiple sentinels stuff. I am still not sure what a good answer to the composition question is, but it may be a moot point if we can't find a way to make sure the SampledSuffixArray fits with the needs of the project. I opened this issue to explore that, and am closing this since it's going to need a bunch of work before merged anyway.\r\n\r\nSee #70.\r\n\r\n"}}
{"actor":{"display_login":"dikaiosune"}}