bigdatagenomics/adam — pull request #380 by nfergu (2014-09-14 14:11:45+00:00)
Title: Rewrite of MarkDuplicates which seems to improve performance

This is a rewrite of MarkDuplicates, which gives around a 3x performance increase over the original in my tests. It reduces the total time spent marking duplicates in a job from an average of 860 seconds to an average of 259 seconds when running against NA12878_chr20 on an Amazon r3.xlarge machine (t=23.9, df=8, a<0.0005).

Note that the above refers the time spent actually executing the duplicate marking code. There will be a much less significant impact on the entire job. For example, running a job to mark duplicates in NA12878_chr20 (already sorted, in ADAM format) took an average of 46 minutes 36 seconds with the old code and 43 minutes 57 seconds with the new code (t=6.6, df=8, a<0.0005). This is an improvement of around 5%.

The new implementation takes a similar approach to the old one -- however it is a re-write, so many variables have been renamed, functions moved around etc. This makes the diff a bit difficult to read unfortunately -- apologies for that.

I've checked the new implementation carefully to ensure that it's equivalent to the old one, but it's possible I've missed something -- let me know if I have. I've also tried hard to ensure that it's at least as readable as the old version, but let me know if anything is unclear.