Musical graph algorithm, with an inlined lookup helper function 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&gt; (testit 100000 tonnetz-connected?)
"Elapsed time: 77.175712 msecs"


and for the inlined version

clj-music.core&gt; (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?
... 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 (-&gt;&gt; 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])
=&gt; 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))
      (-&gt; bit-field (bit-shift-left 1) (bit-clear n) (bit-or 1))
      (-&gt; bit-field (bit-shift-left 1)))))


If we apply this twelve times to 952 we get

(-&gt;&gt; 952
     (iterate (rotate-bits-left-fn 12))
     (take 12))
=&gt; (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
  (-&gt;&gt; [3 4 5 7 8 9]
       bits
       (iterate (rotate-bits-left-fn 12))
       (take 12)
       int-array))