ARMv7 vs. x86-64: Pathfinding benchmark of C++, D, Go, Nim, Ocaml, and more

    (defun get-longest-path (nodes node-id visited)
      (declare (optimize (speed 3) (space 0) (debug 0) (safety 0)
                         (compilation-speed 0)
                         #+lispworks (fixnum-safety 0))
               (type fixnum node-id)
               (type (vector node) nodes)
               (type (vector atom) visited))
      (setf (aref visited node-id) t)
      (Let ((max (loop for neighbour of-type route across (node-neighbours (aref nodes node-id))
                       unless (aref visited (route-dest neighbour))
                       maximize (the fixnum
                                     (+ (the fixnum (route-cost neighbour))
                                        (the fixnum (get-longest-path nodes (route-dest neighbour) visited)))))))
        (declare (fixnum max))
        (setf (aref visited node-id) nil)
        max))

Above Common Lisp version improves the runtime from 8.5 to 3.6 seconds in SBCL and from 30 seconds to 2 seconds in LispWorks 64bit. Computer: i7 Mac mini.

I'd really like to see a "pull out all the stops" benchmark using highly-optimised Asm for the two architectures, as then it's just a matter of how much you can squeeze out of the CPU itself and not something limited by the thick layers of language abstractions on top of that. That would be a nice theoretical maximum to compare against.

Edit: I tested the C++ version on my 5-year-old i7, with an even older compiler (just had to modify the code to not use C++11 features), and with the max optimisation level, it produces a result of 1465ms - which is pretty damn amazing, considering that this is a 16-year-old compiler generating 32-bit code and the most recent CPU it had knowledge of was the Pentium Pro (P6)! I'm convinced that an Asm version could be <1s though, so there's still plenty of room for improvement.

So if it's a "Galaxy S3 with 2GB of ram and a quad-core 1.3ghz processor" then this should be the version with the Exynos SOC. That means that these are cores inside are A9s. The Intel cores are from the Westmere generation.

I wonder how much of the difference we're seeing between various languages is the quality of the code their compilers generate for various backends and how much is due to the different languages benefiting more from architectural differences between the two chips.

I imagine that languages that generate code with more indirection are going to excersize the prefetcher and branch predictor of the core they're running on much more than languages that generate code with simpler control flows. Both the A9 and the Nehalem cores are out of order but the Nehalem has a much, much more sophisticated set of facilities for that. I predict that if you were to re-run the benchmarks on an iPhone 5S you'd see much less of a difference between the various ARM times. And if you were to run it on a cheap Android phone with A7 or A53 cores you'd see a much larger difference.

Based on profiling the C++, this seems to be more a benchmark of function call cost in various languages than anything else - this code makes 42975348 calls to

  int getLongestPath<16>(std::vector<node, std::allocator<node> > const&, int, std::bitset<16>)

Which is fine, but seems a slightly limited platform / language comparison!

Which version of OCaml? The ARMv7 backend was rewritten about 2 years ago, and merged in 4.00.

http://caml.inria.fr/mantis/view.php?id=5433

The new backend is supposed to be considerably faster on floating point code. This code looks integer only, and I don't have relative performance of old/new backend for integer code.

As a wider question: Who cares much about ARMv7? ARMv8 is a completely different beast, requiring a different backend, with much better raw performance (on the same terms as x86-64). That's where languages should be concentrating their current efforts.

> Functional code in Haskell/OCaml can be faster than imperative code using iorefs.

IORefs involve locking. They are bad performance-wise. An algorithm like this should be done either fully functionaly without any mutation at all or in ST.

This is a comparison of specific implementations of the two processor architectures. The benchmarking is still an interesting work, but it isn't a straight comparison of language performance across architectures. It might be a more enlightening result to know the number of opcodes each run executed.

No love for nim on this thread? nim is as fast as c++ with clang. http://www.reddit.com/r/programming/comments/2pvf68/armv7_vs...

I'm really impressed you implemented this in so many languages!

I was curious how fast Javascript would run this, so I ported the lua example over, it ran in 2200msec on my mac laptop. I'm not sure it's a great comparison benchmark however, because there are some obvious optimizations you can make. I added a simple cache to avoid recalculating travel costs for leaves and it now runs in 150msec.

var fs = require('fs');

  var nodes = [], visited = [];
  var visitCache = {};

  function readPlaces() {
    var lines = fs.readFileSync('agraph','utf8').split('\n');
    var numnodes = lines[0]|0;
    for(var i=0;i<numnodes;i++) {
      nodes[i] = [];
      visited[i] = false;
    }
    for(i=1;i<lines.length;i++) {
      var line = lines[i].split(' ');
      nodes[line[0]|0].push({dst: line[1]|0, cost: line[2]|0});
    }
  }

  function getLongestPath(nodes, nodeid, visited) {
    visited[nodeid] = true;
    var neighbours = nodes[nodeid];
    var max = 0
    for(var i=0;i<neighbours.length;i++) {
      if (!visited[neighbours[i].dst]) {
        var dist = neighbours[i].cost + getLongestPath(nodes, neighbours[i].dst, visited);
        if (dist > max) {
          max = dist
        }
      }
    }
    visited[nodeid] = false;
    return max;
  }

  function getLongestPathCached(nodes, nodeid, visited, depth) {
    var idx;
    visited |= 1 << nodeid;
    if (depth == nodes.length - 7) {
      idx = (visited * 32) + nodeid;
      if (visitCache[idx]) {
        return visitCache[idx];
      }
    }
    var neighbours = nodes[nodeid];
    var max = 0
    for(var i=0;i<neighbours.length;i++) {
      if (!(visited & (1 << neighbours[i].dst))) {
        var dist = neighbours[i].cost + getLongestPathCached(nodes, neighbours[i].dst, visited, depth+1);
        if (dist > max) {
          max = dist
        }
      }
    }
    if (idx) {
      visitCache[idx] = max;
    }
    if (typeof visited != 'number') {
      visited[nodeid] = false;
    }
    return max;
  }

  readPlaces();
  var start = Date.now();
  var length;
  if (nodes.length < 32) {
    length = getLongestPathCached(nodes, 0, 0, 0);
  } else {
    length = getLongestPath(nodes, 0, visited);
  }
  console.log(length+' LANGUAGE Javascript: '+(Date.now() - start));

Seeing as how they're likely the most widely distributed Java runtimes on ARM, I would have liked to see Dalvik and ART benchmarks for the Java code

Key takeaway for me is that statically typed languages that are compiled to native code are still 2-3x faster than the fastest JITs. On both platforms.

The Racket and Lisp comments are a bit odd. To the best of my knowledge Typed Racket does support gradual typing, and as well, comparing it's compatibility to Scheme is a category error: Racket is not Scheme anymore, that's why it's called Racket now and not PLT Scheme.

I'm not really sure what this data means because amd64 and ARMv7 are ISAs. For instance, you could make a very deep and superscalar ARMv7 chip that blows a typical amd64 out of the water if you sacrifice size and power. Is the intent simply to show that some language backends are not optimized? Otherwise, without something like "These two chips and clock-for-clock or watt-for-watt it looks like this" it seems meaningless.

The LuaJIT results don't surprise me. I've always been impressed with LuaJIT. The OpenJDK results also don't surprise me. If you work in a Java shop, you learn very quickly to throw out OpenJDK in favor of Sun/Oracle Java. OpenJDK is indeed a "steaming pile of crap".

However, I would have liked to see Julia and Javascript benchmarks in those results. I've heard great things about Julia, and knowing just how incredibly far we've brought the Javascript VMs over the past decade, it wouldn't surprise me to see Javascript fairly high on the list.

This is some quality work. The Java results are particularly striking! It would be interesting to see some more languages that have more than one implementation compared.

What is the difference between FSharp and F#?

Something not measure that is just as important as speed (if not more so) was how long it took to create a working program in each language.

> [Rust] 0.12 is so much prettier; vec[i] instead of vec.get(i), for instance

That was just a momentary bit of weirdness, vec[i] has since returned.

EDIT: Further down, the author acknowledges that this has been fixed. That's what I get for commenting before scrolling the whole way down!

It seems kinda unfair to compare 32bit ARMv7 against 64bit x86-64. Wouldn't it be much fairer to compare ARMv7 against the register-starved x86, or to compare AArch64 against x86-64?

Obligatory question: what compiler options did you use for c++? Good first try is -o3 -march=native. It really makes huge difference in case of C/C++

I updated rust versions and submitted PR https://github.com/logicchains/LPATHBench/pull/33

In the Go code, if you want to ignore an err you can write _ in its place.

Another things that I'm not sure you can even do anymore is disable bounds checking by adding "-gcflags -B" to the compile.

That is some horrible Common Lisp code. I have to try this out....

"The F# was however nowhere near as fast as the OCaml"

I find this a bit odd. Microsoft should be able to build a better compiler. I thought F# was getting a lot of traction.

C++ wins again. There's really no competition.

That's some alien Java code indeed.

Wow Dart is impressive above Lisp and close to F#

Not that the article does this, but since my current bandwagon is that assessing performance by comparing the source of two programs without consideration of the compiler and target processor is silly, I decided to try out the C++ version with several compilers and options. Renaming the file to 'lpath.cpp' and compiling with 'cc lpath.cpp -std=gnu++11 -Wall -Oxxx -march=native -o lpath-cc-Oxxx' here's what I found an an i7 Haswell running at 3.4 GHz:

  lpath-clang3.5-O2 8981 LANGUAGE C++ 763
  lpath-gcc4.7-O2 8981 LANGUAGE C++ 769
  lpath-gcc4.8-O2 8981 LANGUAGE C++ 746
  lpath-icpc14-O2 8981 LANGUAGE C++ 750
  lpath-icpc15-O2 8981 LANGUAGE C++ 735
  lpath-clang3.5-O3 8981 LANGUAGE C++ 734
  lpath-gcc4.7-O3 8981 LANGUAGE C++ 943
  lpath-gcc4.8-O3 8981 LANGUAGE C++ 946
  lpath-icpc14-O3 8981 LANGUAGE C++ 664
  lpath-icpc15-O3 8981 LANGUAGE C++ 655

The last column is the time reported by the program in milliseconds. What this shows is that the same source compiled with Intel's icpc 14 or 15 -O3 is about 50% faster than the same source compiled with g++ 4.7 or 4.8 and -O3, and about 20% faster against g++ -O2. The point isn't that Intel's compiler is so much better, but that this degree of variation is normal for a benchmark like this. There are times when Clang or GCC will come out ahead by the same margin. The lesson is that you aren't benchmarking source code, you are benchmarking a particular compiler with particular options running on a particular processor.

The article is wonderfully specific about what was used, but one should be very careful extrapolating to different combinations. In addition to the compiler differences, note for example that although I did my tests on a processor running less than 1.5x faster, I got runtimes that were almost 2-3x faster. Most likely, this is because the Haswell processor I tested on is more efficient than the several generation old Westmere that the author used. There's nothing right or wrong about either choice, but the degree of difference is why it's always important to specify.

I glanced briefly at the code with 'perf record -F10000', and my quick conclusion was the the Intel version was running faster because it was making better use of the branchless cmov's than the other compilers, and thus has 10,000,000 fewer branch prediction errors. At 20 cycles per miss, this accounts for over half the difference between icpc and the others. The use of the new fast variable shift instructions (shlx) and the once-again fast bit test (bt) instruction is probably the rest of the difference.

The difference between g++ -O2 and -O3 seems to be that the -O3 version is doing almost everything off the stack rather than in registers. It's bad enough that this is probably a performance bug rather than intended behavior.