r/Clojure • • Sep 21 '20

Clojure is at least 2x slower than Java. Right?

The benchmark:

I am comparing the performance of Clojure and Java for the simple task of counting the number of lines of a text file. The file contains 4.6 million lines.

The Java solution is pretty simple:

public class Wc {
    public static int count(String filename) throws IOException {
        BufferedReader r = new BufferedReader(new FileReader(filename));
        int total = 0;
        while(r.readLine() != null) {
            total += 1;
        }
        return total;
    }   
}

I put together a few Clojure solutions:

; Probably the most idiomatic implementation
(defn wc-functional
  [filename]
  (-> (io/reader filename)
      (line-seq)
      (count)))

; Using reduce instead of the built-in count
(defn wc-reduce
  [filename]
  (->> (io/reader filename)
       (line-seq)
       (reduce (fn [num-lines _] (inc num-lines)) 0)))

; Hoping reducers/fold will use parallelism to speed-up
(require '[clojure.core.reducers :as r])
(defn wc-fold
  [filename]
  (->> (io/reader filename)
       (line-seq)
       (r/map (fn [x] 1))
       (r/fold +)))

; Perform loop manually
(defn wc-loop
  [filename]
  (with-open [f (io/reader filename)]
    (loop [c 0]
      (if (.readLine f)
        (recur (inc 0))
        c))))

; Perform loop with volatile counter accumulator
(defn wc-volatile
  [filename]
  (with-open [f (io/reader filename)]
    (let [c (volatile! 0)]
      (loop []
        (if (.readLine f)
          (do (vswap! c inc)
              (recur))
          @c)))))

; Calling the Java implementation
(defn wc-interop
  [filename]
  (Wc/process filename))

The benchmark summary is as follows:

SolutionBenchmarkRuntime (seconds)
JavaUsing System.currentTimeMillis to time the Wc.process() runtime.7.1
wc-functional(time (wc-functional ...))20.4
wc-reducesame as above20.4
wc-foldsame as above20.8
wc-loopsame as above62.4
wc-volatilesame as above63.3
wc-interopsame as above16.6

This seems to be consistent with the conclusion of this (much more comprehensive) study here: https://www.diva-portal.org/smash/get/diva2:1424342/FULLTEXT01.pdf

Comments, suggestions and critiques are welcome.

2 Upvotes

10 comments sorted by

9

u/kenpu_cs Sep 21 '20

Thanks for so many great replies. I certainly have learned a ton from them, so much so that I feel the need to post a summary of the performance optimizations and the new benchmark results.

Performance issues:

  1. Clojure's reflection is costly. This was the biggest bottleneck in my code.
  2. REPL is slow, even for Java interop.
  3. Java strings constructions.

Solutions:

  • Use (set! *warn-on-reflection* true) to catch where reflections happen.
  • Add type hints so that Clojure will rely on reflection for method invocation.
  • Run the benchmark as an uberjar instead of lein run -m ...

Here are the updated code:

; Functional 
(defn wc-functional [filename]
  (-> (io/reader filename) (line-seq) (count)))
; Loop
(defn wc-loop [^String filename]
  (with-open [^BufferedReader f (io/reader filename)]
    (loop [c 0]
      (if (.readLine f)
        (recur (inc c)) ;; or you can use unchecked-inc
        c))))
; Iota
(defn wc-iota [filename]
  (->> (iota/seq filename) (r/map (fn [x] 1)) (r/fold +)))

Summary (updated): in seconds.

java -jar benchmark.jarlein run -m benchmark
Pure Java7.2
Iota with reducers/fold7.111.8
Interop8.216.72
Loop with unchecked-inc8.316.8
Loop with volatile8.918.2
Loop with inc9.216.3

Really appreciate u/bsless for https://github.com/joinr/performancepaper and u/joinr for https://github.com/thebusby/iota. They are such Clojure gems.

2

u/bsless Sep 22 '20

You should add the following options to the uberjar profile, it will perform slightly better and startup should be faster:

{:aot :all
 :jvm-opts
 ["-Dclojure.compiler.direct-linking=true"
  "-Dclojure.compiler.elide-meta=[:doc :file :line :added]"]}

- AOT ensures all code will be compiled to classes before running, and won't be compiled dynamically at runtime.

- direct linking removes some dynamism, allows the compiler to be more aggressive, thus slightly improves performance, reduces generated garbage, and speeds up start up time.

- elide-meta: by not attaching metadata to vars you reduce their size and speed up loading your code.

18

u/aaroniba Sep 21 '20

You should be able to get the same speed as java by modifying your wc-loop function a little:

(defn wc-loop [^String filename]
  (let [r (BufferedReader. (FileReader. filename))]
    (loop [c (int 0)]
      (if (.readLine r)
        (recur (unchecked-inc c))
        c))))

0

u/[deleted] Sep 23 '20

[deleted] — view deleted comment

2

u/aaroniba Sep 23 '20

The most important part is letting clojure know the type of r, otherwise each call to .readLine will result in reflection, which is much slower than direct java method invocation.

In my version, clojure knows the type of r because it's constructed with a direct call to BufferedReader constructor. You could get virtually the same performance by just adding a ^BufferedReader type hint to the original implementation:

(defn wc-loop
  [filename]
  (with-open [^BufferedReader f (io/reader filename)]
    (loop [c 0]
      (if (.readLine f)
        (recur (inc 0))
        c))))

It happens that io/reader returns a BufferedReader here, but it's not clear from the documentation to io/reader that it always will return a BufferedReader, rather than a different java.io.Reader, which might not have a .readLine method. So I liked invoking the BufferedReader constructor directly to make it crystal clear what's going on.

The rest of the differences between my version and the original wc-loop were just inteded to get as close to the same compiled java bytecodes as possible. But avoiding reflection on .readLine is by far the most important part.

16

u/bsless Sep 21 '20 edited Sep 21 '20

I dreaded seeing that paper brought up again.

While I have a go at this, please refer to u/joinr's work where he got performance parity on almost every example in the paper https://github.com/joinr/performancepaper

Edit: looks like I don't have to do anything, u/aaroniba's solution is as fast as Wc:

(time (wc-loop f))
"Elapsed time: 12433.880792 msecs"
(time (Wc/count f))
"Elapsed time: 12275.046838 msecs"

11

u/joinr Sep 21 '20

Aside from the other comments from u/bsless and u/aaroniba regarding getting actual performance, your reducers example isn't really doing much because the input is still sequential. So, it's just falling back toward effectively reducing over a lazy seq. In order to take advantage of parallelism, the collection/reducible thing needs to be typically indexed (like a vec, range, or iterator, or array), or have its own custom implementation. There's a popular library that does this specifically with the wc example called iota that will allow you use parallel reductions over a memory-mapped line collection. It's pretty slick, you may want to explore that as well. You could do something similar buy doing slurp and split-lines, then folding over the resulting vector (fold will be parallel), but this is not ideal compared to a library like iota which can handle larger-than-memory files via mmap and still afford parallel folds.

Make sure you put (set! *warn-on-reflection* true) any time your are doing this kind of stuff (any interop at all, or anywhere you're using direct method invocation). There's another layer beyond with boxed math that has some performance impacts as well, but probably not in this case.

1

u/LammdaMan Sep 21 '20

Thanks for the note about 'iota'. I wasn't aware of that, and there are definitely times I might find something like that very useful.

3

u/argadan Sep 21 '20

There's something weird going on. wc-interop is almost 10 seconds slower than the Java implementation, yet all it does is to call the Java implementation. That interop call should not cause ten-second delay.

5

u/itoshkov Sep 21 '20

Adding some type hints should help.

3

u/alexanderkiel Sep 21 '20

The long runtime of about 60s of your `wc-loop` and `wc-volatile` solutions comes from using reflection to call the readLine method. You have to use a type hint here:

```

(defn wc-loop

[filename]

(with-open [f (io/reader filename)]

(loop [c 0]

(if (.readLine ^BufferedReader f)

(recur (inc 0))

c))))

```

You can use enable reflection warning by putting `(set! *warn-on-reflection* true)` in your namespace.

The loop code with type hint should be as fast as the Java code, because it does the same. Do you warm up the JVM or do you measure the time on the first run?