Musical graph algorithm, with an inlined lookup helper function

Question

I am working with bit strings in clojure. My question is less about performance and more about how one should go about it (in particular see the last inlined version)

The tonnetz-array represents an adjacency matrix.

(set! *warn-on-reflection* true)
(set! *unchecked-math* true)

(def ^:private ^ints tonnetz-array
  (int-array [952 1904 3808 3521 2947 1799 3598 3101 2107 119 238 476]))

get-tonnetz-connected can be thought of as a graph lookup.

(defn- get-tonnetz-connected
  "given packed binary notes representing a chord,
  returns packed notes that mark all notes that can be reached in
  the tonnetz graph. This function is used by tonnetz-connected? as
  a way of building a map / traversing a graph at a far faster
  rate than a graph search"
  [packed]
  (loop [mask (int 0)
         ^int bits packed]
    (if (= bits 0)
      mask
      (let [low-bit (Integer/lowestOneBit bits)]
        (recur
         (bit-or mask (aget ^ints tonnetz-array
                            ^int (Integer/numberOfTrailingZeros low-bit)))
         (bit-xor bits low-bit))))))

this is the main function.

(defn tonnetz-connected?
  "do the notes form a connected graph?"
  [packed]
  (let [low-bit (Integer/lowestOneBit packed)]
    (loop [mask (aget ^ints tonnetz-array
                      (Integer/numberOfTrailingZeros low-bit))
           unmatched (bit-xor packed low-bit)]
      (if (= 0 unmatched)
        true
        (let [matches (bit-and mask unmatched)
              masks (bit-or mask (get-tonnetz-connected matches))
              next-unmatched (bit-xor matches unmatched)]
          (if (= unmatched next-unmatched)
            false
            (recur masks next-unmatched)))))))

I have found that inlining has improved things a bit, and this thing is fast and it is fast enough, but I would like to understand how to properly get the most out of low level operations.

An inlined version where I have tried to make sure that ints are used all the way though.

(defn tonnetz-connected?-2
  "do the notes form a connected graph?"
  [packed]
  (let [low-bit (int (Integer/lowestOneBit (int packed)))]
    (loop [mask (int (aget ^ints tonnetz-array
                           (int (Integer/numberOfTrailingZeros low-bit))))
           unmatched (int (bit-xor (int packed) low-bit))]
      (if (= 0 unmatched)
        true
        (let [matches (int (bit-and mask unmatched))
              masks (loop [mask (int mask)
                           bits (int matches)]
                      (if (= bits (int 0))
                        mask
                        (let [low-bit (int (Integer/lowestOneBit bits))]
                          (recur
                           (int (bit-or mask (aget ^ints tonnetz-array
                                                   ^int (int (Integer/numberOfTrailingZeros low-bit)))))
                           (int (bit-xor bits low-bit))))))
              next-unmatched (int (bit-xor matches unmatched))]
          (if (= unmatched next-unmatched)
            false
            (recur (int masks) (int next-unmatched))))))))

A dirty test function

(defn testit [n f]
  (let [xs (repeatedly n #(+ 1 (rand-int 4094)))]
    (time (do (doall (map f xs)) nil))))

generally I am averaging (ran each about 10 times):

clj-music.core> (testit 100000 tonnetz-connected?)
"Elapsed time: 77.175712 msecs"

and for the inlined version

clj-music.core> (testit 100000 tonnetz-connected?-2)
"Elapsed time: 61.413721 msecs"

So the performance has improved, but now I just have (int ...) everywhere. This was mainly to silence warnings like:

core.clj:165 recur arg for primitive local: mask is not matching primitive, had: Object, needed: long
Auto-boxing loop arg: mask

Is this the correct way?

Answer 1

... I would like to understand how to properly get the most out of low level operations. ... Is this the correct way? ...

Up to a point.

• There's little or nothing wrong with your get-tonnetz-connected and tonnetz-connected? functions. I've tidied up the latter a bit.
• Your tuned tonnetz-connected?-2 is a bit faster, but not much.
• Pre-calculating the tonnetz-connected? values into a data structure roughly doubles its speed.
• Finally, we take a look at a way to derive the tonnetz graph from first principles.

Functionality

Given a chord (set of notes/pitch-classes):

• the get-tonnetz-connected function returns the fattest chord you can reach from it in the tonnetz graph;
• the tonnetz-connected? function tells you whether all its notes are connected in the tonnetz graph.

Here's my revised tonnetz-connected?, which is essentially the same as yours:

(defn tonnetz-connected?
  "is the subgraph of the chord in the tonnetz graph connected?"
  [^long chord]
  (let [chord (int chord)]
    (loop [found (Integer/lowestOneBit chord)
           unmatched chord]
      (or (zero? unmatched)
          (let [newly-found (bit-and found unmatched)]
            (and (not (zero? newly-found))
              (recur (bit-or found (get-tonnetz-connected newly-found))
                     (bit-and-not unmatched newly-found))))))))

What is it doing?

• It conducts a breadth-first search of the chord's subgraph of the tonnetz graph, starting at an arbitrary note (in fact, the lowest one) of the chord.
• It keeps track of the found notes and of the unmatched ones: those yet to be found.
• It terminates
  • when there are no unmatched notes , returning true; otherwise
  • when there are no newly-found notes, returning false.

I've improved the algorithm a little, by

• simplifying the setup of the loop;
• abbreviating the logic by using the and and or macros, which you can often bring into play when if forms return true or false values; and
• returning false as soon as there are no newly-found notes, saving a breadth-first-search step.

I've also changed a bit-xor to a bit-and-not. This makes no difference for this bit-field representation of the graph, but would be a lot faster if the equivalent adjacency-list representation were in play.

But the main thing is that the working of the algorithm is clearer (to me, at least), because the names tell me what's going on.

The only functional advantage this version possesses over yours is that it can handle the empty chord (denoted by 0), whereas yours blows up.

Performance

I used Criterium to measure performance:

(bench (tonnetz-connected? (rand-int 4096)))
Evaluation count : 684489240 in 60 samples of 11408154 calls.
             Execution time mean : 89.362030 ns
    Execution time std-deviation : 5.205238 ns

And for the tuned version;

(bench (tonnetz-connected?-2 (inc (rand-int 4095))))
Evaluation count : 666279660 in 60 samples of 11104661 calls.
             Execution time mean : 88.302147 ns
    Execution time std-deviation : 1.055889 ns

The untuned version is now just as fast as the tuned one. The tuned one's previous advantage of about 15% could probably be restored by changing its algorithm in the same way. I haven't troubled to do this, since there's a better way to speed things up:

Pre-calculating the tonnetz-connected? function.

We can pre-load the values of tonnetz-connected? into an array of booleans:

(def tonnetz-connected?-array
  (let [ans (->> 4096
                 range
                 (map tonnetz-connected?)
                 boolean-array)]
    (fn [^long chord] (aget ans chord))))

Measuring its performance ...

(bench (tonnetz-connected?-array (rand-int 4096)))
Evaluation count : 1202760240 in 60 samples of 20046004 calls.
             Execution time mean : 48.140865 ns
    Execution time std-deviation : 0.349284 ns

It's 45% faster than the tuned version.

---

Appendix: Deriving the Tonnetz graph

(This is not something you asked about, but I think it's worth doing.)

The Tonnetz graph just drops out of the sky as a series of magic numbers:

(def ^:private ^ints tonnetz-array
  (int-array [952 1904 3808 3521 2947 1799 3598 3101 2107 119 238 476]))

I've reverse-engineered the construction of this graph.

We start from the relative intervals that make up the tonnetz relation, which are the same for every note/pitch-class:

[3 4 5 7 8 9]

To turn these into a bit-mask, we use

(defn bits [bitlist]
  (reduce
    (fn [a i] (bit-or a (bit-shift-left 1 i)))
    0
    bitlist))

And, indeed

(bits [3 4 5 7 8 9])
=> 952

the mask for note 0.

For every semitone increment, we have to rotate the twelve-bit mask one bit to the left. A function that yields a function to rotate an n bit bit-field one to the left is

(defn rotate-bits-left-fn [n]
  (fn [bit-field]
    (if (bit-test bit-field (dec n))
      (-> bit-field (bit-shift-left 1) (bit-clear n) (bit-or 1))
      (-> bit-field (bit-shift-left 1)))))

If we apply this twelve times to 952 we get

(->> 952
     (iterate (rotate-bits-left-fn 12))
     (take 12))
=> (952 1904 3808 3521 2947 1799 3598 3101 2107 119 238 476)

... the tonnetz mapping we've seen already.

Putting it all together, we can derive your tonnetz-array thus:

(def ^:private ^ints tonnetz-array
  (->> [3 4 5 7 8 9]
       bits
       (iterate (rotate-bits-left-fn 12))
       (take 12)
       int-array))

Answer 2

(defn- get-tonnetz-connected
  "given packed binary notes representing a chord,
  returns packed notes that mark all notes that can be reached in
  the tonnetz graph. This function is used by tonnetz-connected? as
  a way of building a map / traversing a graph at a far faster
  rate than a graph search"

I find the name and the comment misleading. The tonnetz graph has a single connected component, so the entire graph "can be reached" from any note. If I'm understanding the code correctly then I propose (using British spelling, but other dialects of English are available)

(defn- get-tonnetz-neighbourhood
  "given packed binary notes representing a chord,
  returns packed notes that mark all notes that are adjacent in the
  tonnetz graph to at least one note in the chord. ...

---

      (let [low-bit (Integer/lowestOneBit bits)]
        (recur
         (bit-or mask (aget ^ints tonnetz-array
                            ^int (Integer/numberOfTrailingZeros low-bit)))
         (bit-xor bits low-bit))))))

The number of trailing zeros doesn't change when you mask away the ones above the lowest one, so I don't see that this is any clearer or simpler than

      (recur
       (bit-or mask (aget ^ints tonnetz-array
                          ^int (Integer/numberOfTrailingZeros bits)))
       (bit-xor bits (Integer/lowestOneBit bits))))))

---

(defn tonnetz-connected?
  "do the notes form a connected graph?"

To be precise, "do the notes induce a connected subgraph of the tonnetz graph?"

  [packed]
  (let [low-bit (Integer/lowestOneBit packed)]
    (loop [mask (aget ^ints tonnetz-array
                      (Integer/numberOfTrailingZeros low-bit))
           unmatched (bit-xor packed low-bit)]

Same comment as before - although it's because there's duplicated code, so arguably mask should be initialised as (get-tonnetz-neighbourhood low-bit) for DRYness.

In addition,

1. What does (aget tonnetz-array 32) do? Do you need a special case to handle (= 0 packed)?

2. It's not obvious here why unmatched should not have mask masked out. I think I can more-or-less figure it out by reading the whole method, but IMO a comment wouldn't hurt.

Renaming might help too. mask is rather unhelpful: essentially every variable here is a mask.

      (if (= 0 unmatched)
        true
        (let [matches (bit-and mask unmatched)
              masks (bit-or mask (get-tonnetz-connected matches))
              next-unmatched (bit-xor matches unmatched)]
          (if (= unmatched next-unmatched)

Equivalently (if (= 0 matches), which might be more obviously correct. It also allows inlining masks and next-unmatched.

---

Despite what I said above about inlining low-bit, there is an argument for ditching Integer/numberOfTrailingZeros instead. This is because (aget tonnetz-graph (Integer/numberOfTrailingZeros low-bit)) when low-bit is a single bit can be expressed as (assuming I've got the notation correct) (bit-and 4095 (/ (* low-bit 3900344) 4096). Note that if you do go down this route you have to use longs, because the intermediate value can reach 7987904512.