{"action":"created","issue":{"url":"https://api.github.com/repos/ProSolo/prosolo/issues/2","repository_url":"https://api.github.com/repos/ProSolo/prosolo","labels_url":"https://api.github.com/repos/ProSolo/prosolo/issues/2/labels{/name}","comments_url":"https://api.github.com/repos/ProSolo/prosolo/issues/2/comments","events_url":"https://api.github.com/repos/ProSolo/prosolo/issues/2/events","html_url":"https://github.com/ProSolo/prosolo/issues/2","id":343009586,"node_id":"MDU6SXNzdWUzNDMwMDk1ODY=","number":2,"title":"optimising prosolo performance","user":{"login":"dlaehnemann","id":1379875,"node_id":"MDQ6VXNlcjEzNzk4NzU=","avatar_url":"https://avatars1.githubusercontent.com/u/1379875?v=4","gravatar_id":"","url":"https://api.github.com/users/dlaehnemann","html_url":"https://github.com/dlaehnemann","followers_url":"https://api.github.com/users/dlaehnemann/followers","following_url":"https://api.github.com/users/dlaehnemann/following{/other_user}","gists_url":"https://api.github.com/users/dlaehnemann/gists{/gist_id}","starred_url":"https://api.github.com/users/dlaehnemann/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dlaehnemann/subscriptions","organizations_url":"https://api.github.com/users/dlaehnemann/orgs","repos_url":"https://api.github.com/users/dlaehnemann/repos","events_url":"https://api.github.com/users/dlaehnemann/events{/privacy}","received_events_url":"https://api.github.com/users/dlaehnemann/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-07-20T07:58:43Z","updated_at":"2018-07-20T08:11:42Z","closed_at":null,"author_association":"MEMBER","body":"As `ProSolo` is looking at Single Nucleotide Variants (SNVs), this means inspecting a lot more positions than `prosic` previously did. While scaling linearly with the amount of sequencing data, we needed to improve the previous runtime.\r\n\r\nThe first step was to flamegraph the running of the tool before optimisations (for methods see below). As it is not straightforward to include SVGs in GitHub issues, I'll send the respective files via eMail.\r\n\r\nSo I created an initial flamegraph with `perf + flamegraph.pl` and inspected it with @johanneskoester. The main things that stuck out were bigger chunks of time being spent in `bam_aux_get()`, an `htslib` functionality for getting auxiliairy read data, related calls to `C` string creation functions and a lot of time spent in the likelihood calculations in log space. Thus, the main ideas we came up with were:\r\n\r\n1. **Ensure that each read and each piece of auxiliary data is read only once, and as the `time` analysis below shows, the changes implemented by @johanneskoester heavily improve runtime by 1/3!**\r\n2. Ignore reads in the current read buffer that start right of a candidate SNV, in contrast to candidate indels where these might be informative. This change implemented by @johanneskoester did not cause any measurable speedup.\r\n3. Avoiding the recalculation of likelihoods for single cell sample and bulk sample allele frequencies for different `Event`s where they might be needed. This change that I implemented, did not yield any measurable speedup. My assumption is that the reduced number of likelihood calculations is offset by a slight increase in overhead caused by the caching.\r\n\r\nTo validate these findings based on timing and to see whether any further optimisations might make sense, I then also created more detailed flamegraphs with `rust` functionality. This demonstrated nicely that the first change strongly reduced the CIGAR string related time chunks, whereas the other changes did not noticeably affect relative time usage of different code parts. In addition, the resulting flamegraphs after all optimisations clearly show, that most of the time is now spent in calls to low-level rust library functions (`rust-bio` log likelihood calculations) and eventually system library log calculation functions. My conclusion for now would thus be:\r\n\r\nWe are down to pretty much the most efficient code we can get with `libprosic` and `prosolo`, and all we can do now to reduce runtime would mean reducing the amount of data we look at. I.e. we would have to introduce heuristics to downsample single cell or bulk read coverage at certain sites. To do this, we would have to track how any of those changes affect especially the recall, as throwing away data bears the danger of throwing away alternative allele evidence.\r\n\r\n# baseline timing\r\n\r\nBefore we started on optimisations, `time` for the flamegraphing run gave the following runtime:\r\n```\r\nreal    35m32.092s\r\nuser    35m30.020s\r\nsys 0m2.208s\r\n```\r\nA second run confirmed the runtime:\r\n```\r\nreal    35m4.222s\r\nuser    35m2.892s\r\nsys 0m1.172s\r\n```\r\n\r\n# unpack CIGAR Strings only once\r\n\r\nhttps://github.com/PROSIC/libprosic/pull/34\r\n\r\nRuntime after this optimisation decreased by about a third:\r\n```\r\nreal    23m16.300s\r\nuser    23m14.684s\r\nsys 0m1.028s\r\n```\r\n\r\n# ignore reads right of SNVs\r\n\r\nhttps://github.com/PROSIC/libprosic/commit/72bd0d7dc3f9da9976284bdb8f8e72caba22233e\r\n\r\nRuntime after this optimisation did improve significantly:\r\n```\r\nreal    22m58.577s\r\nuser    22m57.604s\r\nsys 0m0.868s\r\n```\r\n\r\n# caching of likelihoods\r\n\r\nhttps://github.com/PROSIC/libprosic/pull/36\r\n\r\nRuntime after this optimisation did not improve significantly:\r\n```\r\nreal    23m9.813s\r\nuser    23m8.716s\r\nsys 0m0.996s\r\n```\r\n\r\n# flamegraph procedure\r\n\r\n## system CPU sampling (perf + flamegraph.pl)\r\n\r\n### One-time setup\r\n\r\n1. Install `perf`. Under Ubuntu, apparently the wrapper packages `linux-tools-generic` and `linux-cloud-tools-generic` do not necessarily do the trick -- you will sometimes have to explicitly request the ones for your kernel version by using:\r\n```\r\nsudo apt install linux-tools-generic linux-cloud-tools-generic linux-tools-`uname -r`-generic linux-cloud-tools-`uname -r`-generic\r\n```\r\nOr you might even have to explicitly ask for an older version to meet dependencies. Trying to run perf I got an error message I cannot reconstruct any more, but from it I deduced trying to install the following version and it worked:\r\n```\r\nsudo apt install linux-tools-generic linux-cloud-tools-generic linux-tools-4.4.0-127-generic linux-cloud-tools-4.4.0-127-generic\r\n```\r\n2. Install `flamegraph` from repo:\r\n  1. Clone the repo locally: `git clone https://github.com/brendangregg/FlameGraph`\r\n  2. Add the main directory withh all the `*.pl` Perl files to the path.\r\n\r\n### flamegraph a binary\r\n\r\nTo turn on debugging information in the binary, to get actual function names in the flamegraph output, temporarily add to `Cargo.toml`:\r\n\r\n```\r\n[profile.release]\r\ndebug = true\r\n```\r\n\r\nThen compile with the `--release` flag, to get cargo to optimize the resulting binary. Otherwise, any slowness may be due to a lack of compiler optimisations:\r\n\r\n```\r\ncargo build --release\r\n```\r\n\r\nRun the cpu sampling with:\r\n\r\n```\r\nperf record -g -F 25500 ../target/release/name-of-binary <command-line-arguments>\r\n```\r\n\r\nThe resulting `report.perf` can be rather large, depending on the length of your example run and the sampling frequency selected -- e.g. 1G for a half hour run of `prosolo` with the above frequency. Based on the report, generate the flamegraph with:\r\n\r\n```\r\nperf script | stackcollapse-perf.pl | flamegraph.pl > flame.svg\r\n```\r\n\r\nInspect the `flame.svg` file by opening it in a browser and hovering over individual bars to get the respective function names displayed.\r\n\r\nOr inspect the report interactively by issuing:\r\n```\r\nperf report\r\n```\r\n\r\n## Rust internal flamegraphing: flame and flamer crates\r\n\r\nThe crates used are (basic usage is documented on GitHub):\r\n* `flame` provides flamegraphing functions for use within Rust code: https://github.com/TyOverby/flame\r\n* `flamer` makes it easy to deploy via feature annotations: https://github.com/llogiq/flamer\r\n\r\nUsing [rustup](https://rustup.rs/), install the nightly Rust build:\r\n\r\n```\r\nrustup toolchain install nightly\r\n```\r\n\r\nFollow the [documentation of `flamer`](https://github.com/llogiq/flamer) to get going. In addition, add the following to your `main.rs` (or `lib.rs` in a library crate) -- it ensures that calls to the same function at the same level of the hierarchy are collapsed into one flamegraph bar (this ensures that your browser can cope with the graph and makes it a more useful representation than with thousands to millions of little blocks of the same name):\r\n```\r\n/// Implementation as given by @ebarnard at: https://github.com/TyOverby/flame/issues/33#issuecomment-352312506\r\n#[cfg(feature=\"flame_it\")]\r\nfn write_flamegraph() {\r\n    let mut spans = flame::threads().into_iter().next().unwrap().spans;\r\n    merge_spans(&mut spans);\r\n    flame::dump_html_custom(&mut File::create(\"flame-graph.html\").unwrap(), &spans)\r\n        .unwrap();\r\n}\r\n\r\nfn merge_spans(spans: &mut Vec<flame::Span>) {\r\n    if spans.is_empty() {\r\n        return;\r\n    }\r\n\r\n    // Sort so spans to be merged are adjacent and spans with the most children are\r\n    // merged into to minimise allocations.\r\n    spans.sort_unstable_by(|s1, s2| {\r\n        let a = (&s1.name, s1.depth, usize::max_value() - s1.children.len());\r\n        let b = (&s2.name, s2.depth, usize::max_value() - s2.children.len());\r\n        a.cmp(&b)\r\n    });\r\n\r\n    // Copy children and sum delta from spans to be merged\r\n    let mut merge_targets = vec![0];\r\n    {\r\n        let mut spans_iter = spans.iter_mut().enumerate();\r\n        let (_, mut current) = spans_iter.next().unwrap();\r\n        for (i, span) in spans_iter {\r\n            if current.name == span.name && current.depth == span.depth {\r\n                current.delta += span.delta;\r\n                let mut children = mem::replace(&mut span.children, Vec::new());\r\n                current.children.extend(children.into_iter());\r\n            } else {\r\n                current = span;\r\n                merge_targets.push(i);\r\n            }\r\n        }\r\n    }\r\n\r\n    // Move merged spans to the front of the spans vector\r\n    for (target_i, &current_i) in merge_targets.iter().enumerate() {\r\n        spans.swap(target_i, current_i);\r\n    }\r\n\r\n    // Remove duplicate spans\r\n    spans.truncate(merge_targets.len());\r\n\r\n    // Merge children of the newly collapsed spans\r\n    for span in spans {\r\n        merge_spans(&mut span.children);\r\n    }\r\n}\r\n\r\n\r\n#[cfg(not(feature=\"flame_it\"))]\r\nfn write_flamegraph() {\r\n}\r\n```\r\n\r\nAnd add `write_flamegraph();` to the end of your `main()` function. Then, build with the feature `flame_it` activated and using the nightly build:\r\n\r\n```\r\nrustup run nightly cargo build --release --features flame_it\r\n```\r\n\r\nUsing the generated binary, run the program on some example data, in my case:\r\n```\r\n../../target/release/bin_flame_it/prosolo single-cell-bulk --omit-indels --candidates ../PAG5.PNG.prosolo_candidates.chr7_100000-200000.bcf ../PAG5.bps.sorted.chr7_100000-200000.bam ../PNG.bps.sorted.chr7_100000-200000.bam ~/analysis/hg19/ucsc.hg19.fasta  --sc-isize-mean 196.1 --sc-isize-sd 71.1 --output PAG5.chr7_100000-200000.prosolo.bcf\r\n```\r\n\r\nAnd inspect..."},"comment":{"url":"https://api.github.com/repos/ProSolo/prosolo/issues/comments/406523399","html_url":"https://github.com/ProSolo/prosolo/issues/2#issuecomment-406523399","issue_url":"https://api.github.com/repos/ProSolo/prosolo/issues/2","id":406523399,"node_id":"MDEyOklzc3VlQ29tbWVudDQwNjUyMzM5OQ==","user":{"login":"alicemchardy","id":2099169,"node_id":"MDQ6VXNlcjIwOTkxNjk=","avatar_url":"https://avatars2.githubusercontent.com/u/2099169?v=4","gravatar_id":"","url":"https://api.github.com/users/alicemchardy","html_url":"https://github.com/alicemchardy","followers_url":"https://api.github.com/users/alicemchardy/followers","following_url":"https://api.github.com/users/alicemchardy/following{/other_user}","gists_url":"https://api.github.com/users/alicemchardy/gists{/gist_id}","starred_url":"https://api.github.com/users/alicemchardy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alicemchardy/subscriptions","organizations_url":"https://api.github.com/users/alicemchardy/orgs","repos_url":"https://api.github.com/users/alicemchardy/repos","events_url":"https://api.github.com/users/alicemchardy/events{/privacy}","received_events_url":"https://api.github.com/users/alicemchardy/received_events","type":"User","site_admin":false},"created_at":"2018-07-20T08:11:42Z","updated_at":"2018-07-20T08:11:42Z","author_association":"NONE","body":"Thanks for the nice summary. Can you specify dataset size and system used for calculations?"}}
{"actor":{"display_login":"alicemchardy"}}