Repository: chrovis/cljam
Pull request #201 (2020-06-10 03:55:24)

Refactor cljam.io.util.bin
#### Summary
Refactored `cljam.io.util.bin`

#### Changes
- Rearrange functions
- Add docstrings
- Add tests

#### Tests

- `lein check` ✅ 
- `lein test :all` ✅ 
- `lein cloverage` ✅
- `lein eastwood` ✅
- `lein cljfmt check` ✅ 


codecov[bot]: # [Codecov](https://codecov.io/gh/chrovis/cljam/pull/201?src=pr&el=h1) Report
> Merging [#201](https://codecov.io/gh/chrovis/cljam/pull/201?src=pr&el=desc) into [master](https://codecov.io/gh/chrovis/cljam/commit/84a535d3138a829b90dee0540aff910fa873c9df&el=desc) will **increase** coverage by `0.02%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/chrovis/cljam/pull/201/graphs/tree.svg?width=650&height=150&src=pr&token=hrCuiz6NWa)](https://codecov.io/gh/chrovis/cljam/pull/201?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master     #201      +/-   ##
==========================================
+ Coverage   86.91%   86.94%   +0.02%     
==========================================
  Files          77       77              
  Lines        6267     6266       -1     
  Branches      520      518       -2     
==========================================
+ Hits         5447     5448       +1     
  Misses        300      300              
+ Partials      520      518       -2     
```


| [Impacted Files](https://codecov.io/gh/chrovis/cljam/pull/201?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/cljam/io/util/bin.clj](https://codecov.io/gh/chrovis/cljam/pull/201/diff?src=pr&el=tree#diff-c3JjL2NsamFtL2lvL3V0aWwvYmluLmNsag==) | `98.07% <100.00%> (+3.73%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/chrovis/cljam/pull/201?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/chrovis/cljam/pull/201?src=pr&el=footer). Last update [84a535d...e2f153b](https://codecov.io/gh/chrovis/cljam/pull/201?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

alumi: > Just to confirm, memoization for reg->bins was dropped, but is it intended?
> If so (probably so), could you elaborate a little more on the reason just for future reference? It messed up the performance improvement by unboxed function calls? You were concerned about its memory consumption? Or for any other reason?

Ah, sorry I forgot to mention that 🙇 
The changes to `reg->bins` are intentional.
- I fixed it to use `transduce` to speed it up by 1.5x-2x.
- I decided to remove the `memoize` because it's not repeatedly called and it likely to have a high cache miss rate (not well tested). `reg->bins*` was fast (~10 μs) enough by itself compared to actual file I/O ops. As you said, this will benefit reducing CPU overhead and memory leak.
- I made it public to balance with `reg->bin`.

Patch:
diff --git a/src/cljam/io/util/bin.clj b/src/cljam/io/util/bin.clj
index fceb279..228d5dc 100644
--- a/src/cljam/io/util/bin.clj
+++ b/src/cljam/io/util/bin.clj
@@ -1,79 +1,75 @@
 (ns cljam.io.util.bin
   (:require [cljam.io.util.chunk :as util-chunk]))
 
-(defn max-pos ^long [^long min-shift ^long depth]
+(defn max-pos
+  "Returns a maximum position of a binning index. The value is identical to the
+  width of bin 0."
+  ^long [^long min-shift ^long depth]
   (bit-shift-left 1 (+ min-shift (* 3 depth))))
 
-(defn- reg->bins*
-  "Returns candidate bins for the specified region as a vector."
-  [^long beg ^long end ^long min-shift ^long depth]
-  (let [max-pos (max-pos min-shift depth)
-        beg (if (<= beg 0) 0 (min (dec beg) max-pos))
-        end (if (<= end 0) max-pos (min end max-pos))]
-    (into [0]
-          (mapcat
-           (fn [^long d]
-             (let [t
-                   (apply + (map (fn [^long x] (bit-shift-left 1 (* x 3)))
-                                 (range (inc d))))
-                   s (+ min-shift (* 3 (- depth d 1)))]
-               (range (+ t (bit-shift-right beg s))
-                      (+ t 1 (bit-shift-right (dec end) s))))))
-          (range depth))))
-
-(def ^:private reg->bins (memoize reg->bins*))
-
-(defn first-bin-of-level ^long [^long level]
+(defn first-bin-of-level
+  "Returns a left-most bin number of the given `level`."
+  ^long [^long level]
   (quot (bit-shift-left 1 (* 3 level)) 7))
 
-(defn bin-width-of-level ^long [^long level ^long min-shift ^long depth]
+(defn bin-width-of-level
+  "Returns a width shared by bins of the same given `level`."
+  ^long [^long level ^long min-shift ^long depth]
   (bit-shift-left 1 (+ min-shift (* 3 (- depth level)))))
 
-(defn bin-level ^long [^long bin]
+(defn bin-level
+  "Returns a level that the given `bin` belongs to."
+  ^long [^long bin]
   (let [x (inc (quot (- 64 (Long/numberOfLeadingZeros bin)) 3))]
     (cond-> x (< bin (first-bin-of-level x)) dec)))
 
-(defn bin-beg ^long [^long bin ^long min-shift ^long depth]
+(defn bin-beg
+  "Returns a beginning position of the given `bin`. 1-based."
+  ^long [^long bin ^long min-shift ^long depth]
   (let [level (bin-level bin)]
     (inc (* (- bin (first-bin-of-level level))
             (bin-width-of-level level min-shift depth)))))
 
-(defn max-bin ^long [^long depth]
+(defn max-bin
+  "Returns a maximum bin number of a binning index with the given `depth`."
+  ^long [^long depth]
   (dec (first-bin-of-level (inc depth))))
 
-(defprotocol IBinningIndex
-  (get-chunks [this ref-idx bins])
-  (get-min-offset [this ref-idx beg])
-  (get-min-shift [this])
-  (get-depth [this])
-  (get-chr-names  [this]))
+(defn leading-bins-at-level
+  "Returns the distance between the bin corresponding to `pos` and the first one
+  at the same level."
+  ^long [^long pos ^long level ^long min-shift ^long depth]
+  (unsigned-bit-shift-right pos (+ min-shift (* (- depth level) 3))))
 
 (defn pos->lidx-offset
+  "Returns an offset of a linear index that the given `pos` belongs to."
   [^long pos ^long linear-index-shift]
   (bit-shift-right (if (<= pos 0) 0 (dec pos)) linear-index-shift))
 
-(defn get-spans
-  "Calculates span information for random access from index data such as tabix."
-  [index-data ^long ref-idx ^long beg ^long end]
-  (let [bins
-        (reg->bins beg end (get-min-shift index-data) (get-depth index-data))
-        chunks (get-chunks index-data ref-idx bins)
-        min-offset (get-min-offset index-data ref-idx beg)]
-    (->> (util-chunk/optimize-chunks chunks min-offset)
-         (map vals))))
-
-(defn leading-bins-at-level
-  "Returns the distance between the binning corresponding to pos and
-   the first one at the passed depth"
-  ^long [^long pos ^long level ^long min-shift ^long depth]
-  (unsigned-bit-shift-right pos (+ min-shift (* (- depth level) 3))))
+(defn reg->bins
+  "Returns all overlapping bins for the specified region [`beg`, `end`] as a
+  vector."
+  [^long beg ^long end ^long min-shift ^long depth]
+  (let [max-pos (max-pos min-shift depth)
+        beg (dec (Math/min max-pos (Math/max 1 beg)))
+        end (dec (Math/min max-pos (Math/max 1 end)))]
+    (into [0]
+          (mapcat
+           (fn [^long d]
+             (let [t (long (transduce
+                            (map (fn [^long x] (bit-shift-left 1 (* x 3))))
+                            + 0 (range (inc d))))
+                   s (+ min-shift (* 3 (- depth d 1)))]
+               (range (+ t (bit-shift-right beg s))
+                      (+ t 1 (bit-shift-right end s))))))
+          (range depth))))
 
 (defn reg->bin
-  "Calculates bin given an alignment covering [beg, end]"
+  "Calculates the smallest bin containing the given region [`beg`, `end`]."
   ^long [^long beg ^long end ^long min-shift ^long depth]
   (let [max-pos (max-pos min-shift depth)
-        beg (dec (Math/min max-pos (Math/max 1  beg)))
-        end (dec (Math/min max-pos (Math/max 1  end)))]
+        beg (dec (Math/min max-pos (Math/max 1 beg)))
+        end (dec (Math/min max-pos (Math/max 1 end)))]
     (loop [level depth]
       (if-not (neg? level)
         (let [beg-bins (leading-bins-at-level beg level min-shift depth)]
@@ -81,3 +77,20 @@
             (+ (first-bin-of-level level) beg-bins)
             (recur (dec level))))
         0))))
+
+(defprotocol IBinningIndex
+  (get-chunks [this ref-idx bins])
+  (get-min-offset [this ref-idx beg])
+  (get-min-shift [this])
+  (get-depth [this])
+  (get-chr-names [this]))
+
+(defn get-spans
+  "Calculates span information for random access from index data such as tabix."
+  [index-data ^long ref-idx ^long beg ^long end]
+  (let [bins (reg->bins
+              beg end (get-min-shift index-data) (get-depth index-data))
+        chunks (get-chunks index-data ref-idx bins)
+        min-offset (get-min-offset index-data ref-idx beg)]
+    (->> (util-chunk/optimize-chunks chunks min-offset)
+         (map vals))))


Test patch:
diff --git a/test/cljam/io/util/bin_test.clj b/test/cljam/io/util/bin_test.clj
index 077c989..b751e15 100644
--- a/test/cljam/io/util/bin_test.clj
+++ b/test/cljam/io/util/bin_test.clj
@@ -8,41 +8,67 @@
             [cljam.io.csi :as csi]
             [cljam.io.util.bin :as util-bin]))
 
-(deftest get-spans-returns-a-sequence-including-regions
-  (let [tabix* (tabix/read-index test-tabix-file)]
-    (is (= [[0 50872]] (util-bin/get-spans tabix* 0 1 100)))
-    (is (every? #(and (= 2 (count %))
-                      (number? (first %))
-                      (number? (second %)))
-                (util-bin/get-spans tabix* 0 1 100))))
-  (let [csi* (csi/read-index test-csi-file)]
-    (is (= [[3904 3973]] (util-bin/get-spans csi* 0 1 100000)))
-    (is (every? #(and (= 2 (count %))
-                      (number? (first %))
-                      (number? (second %)))
-                (util-bin/get-spans csi* 0 1 100000)))))
+(deftest max-pos-test
+  (are [?min-shift ?depth ?max-pos]
+       (= ?max-pos (util-bin/max-pos ?min-shift ?depth))
+    14 5 536870912
+    15 5 1073741824
+    0 0 1
+    0 1 8
+    0 2 64
+    1 1 16
+    1 2 128))
 
-(deftest reg->bins-test
-  (are [x] (= [0 1 9 73 585 4681]
-              (#'util-bin/reg->bins 1 (bit-shift-left 1 x) x 5))
-    13 14 15 16)
-  (are [x] (= [0 1 9 73 585 4681 4682]
-              (#'util-bin/reg->bins 1 (inc (bit-shift-left 1 x)) x 5))
-    13 14 15 16)
-  (is (= [0 2 17]
-         (#'util-bin/reg->bins 9 9 0 2)))
-  (is (= [0 1 9 73 585]
-         (#'util-bin/reg->bins 1 1 14 4)))
-  (is (= [0 1 9 73 585 4681]
-         (#'util-bin/reg->bins 1 1 14 5)))
-  (is (= [0 1 9 73 585 4681 37449]
-         (#'util-bin/reg->bins 1 1 14 6)))
-  (is (= [0 1 9 73 585 4681 37449 299593]
-         (#'util-bin/reg->bins 1 1 14 7)))
-  (is (= [0 1 9 73 585 4681 37449 37450]
-         (#'util-bin/reg->bins 1 32769 15 6))))
+(deftest first-bin-of-level-test
+  (are [?level ?first-bin]
+       (= ?first-bin (util-bin/first-bin-of-level ?level))
+    0 0
+    1 1
+    2 (+ 1 8)
+    3 (+ 1 8 64)
+    4 (+ 1 8 64 512)
+    5 (+ 1 8 64 512 4096)
+    6 (+ 1 8 64 512 4096 32768)))
+
+(deftest bin-width-of-level-test
+  (are [?level ?min-shift ?depth ?bin-width]
+       (= ?bin-width (util-bin/bin-width-of-level ?level ?min-shift ?depth))
+    0 14 5 536870912
+    1 14 5 67108864
+    2 14 5 8388608
+    3 14 5 1048576
+    4 14 5 131072
+    5 14 5 16384
+    0 15 5 1073741824
+    0 0 0 1
+    0 0 1 8
+    1 0 1 1
+    1 0 2 8))
+
+(deftest bin-level-test
+  (are [?bin ?level]
+       (= ?level (util-bin/bin-level ?bin))
+    0 0
+    1 1
+    2 1
+    8 1
+    9 2
+    72 2
+    73 3
+    584 3
+    585 4
+    4680 4
+    4681 5
+    37448 5
+    37449 6))
 
 (deftest bin-beg-test
+  (are [?bin ?min-shift ?depth ?bin-beg]
+       (= ?bin-beg (util-bin/bin-beg ?bin ?min-shift ?depth))
+    4680 14 5 536739841
+    4681 14 5 1
+    4682 14 5 16385
+    4683 14 5 32769)
   (doseq [index-shift [12 14 16]]
     (let [min-size (bit-shift-left 1 index-shift)]
       (is (= 1 (util-bin/bin-beg 4681 index-shift 5)))
@@ -54,16 +80,56 @@
       (is (= (+ 1 (* min-size 24)) (util-bin/bin-beg 588 index-shift 5))))))
 
 (deftest max-bin-test
-  (are [depth ans] (= (util-bin/max-bin depth) ans)
+  (are [?depth ?ans] (= (util-bin/max-bin ?depth) ?ans)
     1 8
     2 72
     3 584
     5 37448))
 
+(deftest leading-bins-at-level-test
+  (are [?pos ?level ?min-shift ?depth ?bins]
+       (= ?bins (util-bin/leading-bins-at-level ?pos ?level ?min-shift ?depth))
+    1 0 14 5 0
+    1 5 14 5 0
+    16385 5 14 5 1
+    536870912 5 14 5 32768))
+
+(deftest pos->lidx-offset-test
+  (are [?pos ?linear-index-shift ?offset]
+       (= ?offset (util-bin/pos->lidx-offset ?pos ?linear-index-shift))
+    0 14 0
+    1 14 0
+    16384 14 0
+    16385 14 1
+    32768 14 1
+    32769 14 2))
+
+(deftest reg->bins-test
+  (are [x] (= [0 1 9 73 585 4681]
+              (util-bin/reg->bins 1 (bit-shift-left 1 x) x 5))
+    13 14 15 16)
+  (are [x] (= [0 1 9 73 585 4681 4682]
+              (util-bin/reg->bins 1 (inc (bit-shift-left 1 x)) x 5))
+    13 14 15 16)
+  (is (= [0 2 17]
+         (util-bin/reg->bins 9 9 0 2)))
+  (is (= [0 1 9 73 585]
+         (util-bin/reg->bins 1 1 14 4)))
+  (is (= [0 1 9 73 585 4681]
+         (util-bin/reg->bins 1 1 14 5)))
+  (is (= [0 1 9 73 585 4681 37449]
+         (util-bin/reg->bins 1 1 14 6)))
+  (is (= [0 1 9 73 585 4681 37449 299593]
+         (util-bin/reg->bins 1 1 14 7)))
+  (is (= [0 1 9 73 585 4681 37449 37450]
+         (util-bin/reg->bins 1 32769 15 6))))
+
 (deftest reg->bin-test
   (testing "BAI-compatible"
     (are [?start ?end ?bin]
-         (= ?bin (util-bin/reg->bin ?start ?end 14 5))
+         (= ?bin
+            (util-bin/reg->bin ?start ?end 14 5)
+            ((set (util-bin/reg->bins ?start ?end 14 5)) ?bin))
       0 0 4681
       0 1 4681
       1 1 4681
@@ -79,7 +145,9 @@
       536870912 536870913 37448))
   (testing "1-by-1"
     (are [?start ?end ?bin]
-         (= ?bin (util-bin/reg->bin ?start ?end 0 2))
+         (= ?bin
+            (util-bin/reg->bin ?start ?end 0 2)
+            ((set (util-bin/reg->bins ?start ?end 0 2)) ?bin))
       0 1 9
       1 1 9
       2 2 10
@@ -96,3 +164,17 @@
     (is (= (util-bin/reg->bin 1 1 14 7) 299593))
     (is (= (util-bin/reg->bin 1 32769 15 6) 4681))
     (is (= (util-bin/reg->bin 240877561 240877568 14 6) 52150))))
+
+(deftest get-spans-returns-a-sequence-including-regions
+  (let [tabix* (tabix/read-index test-tabix-file)]
+    (is (= [[0 50872]] (util-bin/get-spans tabix* 0 1 100)))
+    (is (every? #(and (= 2 (count %))
+                      (number? (first %))
+                      (number? (second %)))
+                (util-bin/get-spans tabix* 0 1 100))))
+  (let [csi* (csi/read-index test-csi-file)]
+    (is (= [[3904 3973]] (util-bin/get-spans csi* 0 1 100000)))
+    (is (every? #(and (= 2 (count %))
+                      (number? (first %))
+                      (number? (second %)))
+                (util-bin/get-spans csi* 0 1 100000)))))