13

I wrote a binary search function as part of a larger program, but it seems to be slower than it should be and profiling shows a lot of calls to methods in clojure.lang.Numbers.

My understanding is that Clojure can use primitives when it can determine that it can do so. The calls to the methods in clojure.lang.Numbers seems to indicate that it's not using primitives here.

If I coerce the loop variables to ints, it properly complains that the recur arguments are not primitive. If i coerce those too, the code works again but again it's slow. My only guess is that (quot (+ low-idx high-idx) 2) is not producing a primitive but I'm not sure where to go from here.

This is my first program in Clojure so feel free to let me know if there are more cleaner/functional/Clojure ways to do something.

(defn binary-search
  [coll coll-size target]
  (let [cnt (dec coll-size)]
    (loop [low-idx 0 high-idx cnt]
      (if (> low-idx high-idx)
        nil
        (let [mid-idx (quot (+ low-idx high-idx) 2) mid-val (coll mid-idx)]
          (cond
            (= mid-val target) mid-idx
            (< mid-val target) (recur (inc mid-idx) high-idx)
            (> mid-val target) (recur low-idx (dec mid-idx))
            ))))))

(defn binary-search-perf-test
  [test-size]
  (do
    (let [test-set (vec (range 1 (inc test-size))) test-set-size (count test-set)]
      (time (count (map #(binary-search2 test-set test-set-size %) test-set)))
    )))
Improve this question

2 Answers 2

Reset to default
13

First of all, you can use the binary search implementation provided by java.util.Collections:

(java.util.Collections/binarySearch [0 1 2 3] 2 compare)
; => 2

If you skip the compare, the search will be faster still, unless the collection includes bigints, in which case it'll break.

As for your pure Clojure implementation, you can hint coll-size with ^long in the parameter vector -- or maybe just ask for the vector's size at the beginning of the function's body (that's a very fast, constant time operation), replace the (quot ... 2) call with (bit-shift-right ... 1) and use unchecked math for the index calculations. With some additional tweaks a binary search could be written as follows:

(defn binary-search
  "Finds earliest occurrence of x in xs (a vector) using binary search."
  ([xs x]
     (loop [l 0 h (unchecked-dec (count xs))]
       (if (<= h (inc l))
         (cond
           (== x (xs l)) l
           (== x (xs h)) h
           :else nil)
         (let [m (unchecked-add l (bit-shift-right (unchecked-subtract h l) 1))]
           (if (< (xs m) x)
             (recur (unchecked-inc m) h)
             (recur l m)))))))

This is still noticeably slower than the Java variant:

(defn java-binsearch [xs x]
  (java.util.Collections/binarySearch xs x compare))

binary-search as defined above seems to take about 25% more time than this java-binsearch.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thank you. I was being a little cautious about taking the collection size as I'm not too familiar with all the Clojure types yet. I did find good information a little bit earlier at link. I'm trying to avoid calling into Java for now as I'm learning Clojure and trying to challenge myself not to call into Java (unless I get to a point where I don't think I'd be able to get the Clojure solution to where I want it). Changing quot to bit shifting did seem to help in 1.3 (and not in 1.2). Going to play around with your other suggestions and see how it goes.
Using (nth coll n) instead of (col n) seems to be slightly faster.
= operator seems to always perform boxing whereas == doesn't
In my code I have a collection of records instead of primitives which also gives a nice performance improvement because you can have a primitive field in the record (which I don't think you can easily have with a collection). I just had to coerce target to a primitive for this to be effective. Otherwise it was still autoboxing.
== is meant specifically to test numeric equality, whereas = is a general purpose function, so the boxing behaviour makes sense. I'm not sure what you mean about the collection of records...? At any rate, it'd be interesting to see the ultimate pure Clojure binary search (and to compare it against Collections), if you wouldn't mind sharing your final impl. :-)
|
3

in Clojure 1.2.x you can only coerce local variables and they can't cross functions calls. starting in Clojure 1.3.0 Clojure can use primative numbers across function calls but not through Higher Order Functions such as map.

if you are using clojure 1.3.0+ then you should be able to accomplish this using type hints

as with any clojure optimization problem the first step is to turn on (set! *warn-on-reflection* true) then add type hints until it no longer complains. 

user=> (set! *warn-on-reflection* true)                                          
true
user=> (defn binary-search
  [coll coll-size target]
  (let [cnt (dec coll-size)]
    (loop [low-idx 0 high-idx cnt]
      (if (> low-idx high-idx)
        nil
        (let [mid-idx (quot (+ low-idx high-idx) 2) mid-val (coll mid-idx)]
          (cond
            (= mid-val target) mid-idx
            (< mid-val target) (recur (inc mid-idx) high-idx)
            (> mid-val target) (recur low-idx (dec mid-idx))
            ))))))
NO_SOURCE_FILE:23 recur arg for primitive local: low_idx is not matching primitive, 
had: Object, needed: long
Auto-boxing loop arg: low-idx
#'user/binary-search
user=>

to remove this you can type hint the coll-size argument

(defn binary-search
  [coll ^long coll-size  target]
  (let [cnt (dec coll-size)]
    (loop [low-idx 0 high-idx cnt]
      (if (> low-idx high-idx)
        nil
        (let [mid-idx (quot (+ low-idx high-idx) 2) mid-val (coll mid-idx)]
          (cond
            (= mid-val target) mid-idx
            (< mid-val target) (recur (inc mid-idx) high-idx)
            (> mid-val target) (recur low-idx (dec mid-idx))
            ))))))

it is understandably difficult to connect the auto-boxing on line 10 to the coll-size parameter because it goes through cnt then high-idx then mid-ixd and so on, so I generally approach these problems by type-hinting everything until I find the one that makes the warnings go away, then remove hints so long as they stay gone

Improve this answer

5 Comments

Thanks. I actually tried in both Clojure 1.2 (because this is for a "challenge" site and they use 1.2) and Clojure 1.3. Clojure 1.2 seems to have the same check as 1.3 but it's actually an error. I was able to eliminate them but I could still see that there were a lot of calls to clojure.lang.Numbers methods which would seem to imply that something within the binary-search function is promoting an int to something else but I'm all out of ideas.
Calls to static methods of c.l.Numbers are to be expected. That's fine, really, they'll probably get inlined by the JIT given some use. (Also, the functions delegating to c.l.Numbers tend to be inlined by the Clojure compiler too.) You just need to make sure to hit the correct overload through hinting.
I'm doing some testing now, but doesn't seeing a lot of calls to clojure.lang.Numbers imply that something is getting boxed? The ones that I'm seeing have signatures involving Object/Number.
Well, c.l.Numbers has primitive overloads for the relevant methods; I'd expect to see those called with appropriate hinting.
After adding a good amount if (int x) coercion, I was able to get rid of the non-primitive calls.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.