CODEWITHSUNDEEP
javaperformanceclojure
user1002430
user1002430

Reputation:

Clojure numerical performance: What am I missing in my code?

I'm trying to figure out why there is a performance difference between this Clojure code and its Java equivalent. The Clojure code:

(ns trigperf.core (:gen-class))

(deftype city [^String name ^double latr ^double lonr
               ^double sinlat ^double coslat ^double sinlon ^double coslon])

(defn dist [^city city1 ^city city2]
  (let [st1 (double (.sinlat city1)) st2 (double (.sinlat city2))
        ct1 (double (.coslat city1)) ct2 (double (.coslat city2))
        ln1 (double (.lonr city1))   ln2 (double (.lonr city2))]
    (Math/acos (+ (* st1 st2) (* ct1 ct2 (Math/cos (Math/abs (- ln1 ln2))))))))

(defn cost [route]
  (reduce + (map dist route (drop 1 route))))

(defn test-data []
  (take 100 (repeatedly
             #(let [latr (/ (* (- (rand 180) 90) Math/PI) 180)
                    lonr (/ (* (- (rand 360) 180) Math/PI) 180)]
                (city. "" latr lonr
                       (Math/sin latr) (Math/cos latr)
                       (Math/sin lonr) (Math/cos lonr))))))

(defn run-test []
  (let [data (test-data)] (time (dotimes [i 99999] (cost data)))))

(defn -main [& args] (run-test))

And the Java equivalent:

public class City {
    public String name;
    public double latr;
    public double lonr;
    public double sinlat;
    public double coslat;
    public double sinlon;
    public double coslon;

    public City(String n, double a, double b, double c, double d, double e, double f) {
        name = n; latr = a; lonr = b;
        sinlat = c; coslat = d; sinlon = e; coslon = f;
    }
}

public class Trigperf {

    public static City[] test_data() {
        City[] arr = new City[100];
        for (int c=0; c < 100; ++c) {
            double latr = (((Math.random() * 180) - 90) * Math.PI) / 180;
            double lonr = (((Math.random() * 180) - 90) * Math.PI) / 180;
            arr[c] = new City("", latr, lonr, Math.sin(latr), Math.cos(latr),
                              Math.sin(lonr), Math.cos(lonr));
        }

        return arr;
    }

    public static double dist(City city1, City city2) {
        return Math.acos((city1.sinlat * city2.sinlat) +
                         (city1.coslat * city2.coslat *
                          (Math.cos (Math.abs (city1.lonr - city2.lonr)))));
    }

    public static double cost(City[] route) {
        double acc = 0;
        for (int c=0; c < route.length - 1; ++c) {
            acc += dist(route[c], route[c + 1]);
        }
        return acc;
    }

    public static void run_test() {
        City[] data = test_data();
        long start = System.currentTimeMillis();
        for (int c=0; c < 99999; ++c) { cost(data); }
        long stop = System.currentTimeMillis();
        System.out.format( "Elapsed: %dms\n", stop - start);
    }

    public static void main(String[] args) {
        run_test();
    }

}

It takes roughly 4 seconds to run the Clojure code and 2 seconds to run the Java version. So Clojure takes twice as long. But I've already type-hinted everywhere I can think of, and made sure that there are no reflection warnings. How can I improve the speed of the Clojure code to approach that of the Java code?

Upvotes: 2

Views: 197

Answers (2)

Diego Basch
Diego Basch

Reputation: 13059

There are a number of reasons. In general, dealing with Clojure sequences is not as efficient as using Java arrays. For some noticeable speed gains, try this:

(defn test-data []
  (into-array city (take 100 (repeatedly ...)

and then compute your cost in a loop:

(defn cost [route]
  (let [n (dec (alength ^objects route))]
    (loop [i 0
           acc 0]
      (if (< i n)
        (recur (inc i)
               (+ acc (dist (aget ^objects route i) (aget ^objects route (inc i)))))
         acc))))

This still won't be as fast as Java but it will bring it closer. In general, getting Clojure to perform as well as Java is a bit of an art. See this question:

Clojure Performance For Expensive Algorithms

Upvotes: 1

Arthur Ulfeldt
Arthur Ulfeldt

Reputation: 91534

The clojure code is using slightly different math, because every operation is checking for overflow and will throw an exception if so:

user> (* Long/MAX_VALUE 2)
ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1501)

user> (unchecked-add Long/MAX_VALUE 2)
-9223372036854775807

So you may be able to squeeze a little more by turning the safeties off. And on a historical note old (ancient now) versions of clojure would also promote to larger types by default which was later decided to not be worth the time. Also watch out for use of the / function because it computes ratios when it can which involved calculating the GCD so it can sneak some cost in there:

user> (/ (int 2) (int 6))
1/3
user> (quot (int 2) (int 6))
0
user> (/ (float 2) (float 6))
0.3333333333333333

though this does not look like the case here because you are multiplying by PI which will make it be a double.

Upvotes: 2

Related Questions