Entry tags:

benchmark, c, d language, gcc, geometry, java, ldc, llvm-gcc

Jarvis March in D
Robert C. Martin in his blog has written an implementation of the Jarvis March algorithm in Clojure, and was looking for ways to speed up the code:
http://blog.objectmentor.com/articles/2009/08/11/jarvis-march-in-clojure

See also:
http://www.butunclebob.com/ArticleS.UncleBob.ConvexHullTiming

So I have translated the Java code to D (and later C), and then I have done some timing tests.

The Java results are quite good compared to the D ones.

Number of points in the hull in all tests is just 14.

Timings, n = 2_000_000:

On Windows XP, best of 6, seconds:
  D 1:    1.88 (DMD compiler)
  Java 1: 1.83
  C 2:    1.55 (GCC compiler)
  Java 2: 1.55
  Java 1: 1.47 (-server)
  Java 2: 1.47 (-server -Xms40M)
  C 2:    1.46 (LLVM-GCC compiler)
  Java 2: 1.45 (-server)
  D 2:    1.32 (DMD compiler)

On Pubuntu, best of 6, seconds:
  Java 1: 2.71
  C 2:    2.59 (GCC compiler)
  Java 1: 2.42 (-server)
  Java 2: 2.39
  Java 2: 2.37 (-server)
  D 1:    2.06 (LDC compiler)
  D 1:    2.06 (LDC compiler, LTO+I)
  D 2:    2.02 (LDC compiler, LTO+I)  
  D 2:    2.00 (LDC compiler)

Notes:
- The code of the D 1 version is similar to the Java 1 version. The code of the D 2 version is similar to the Java 2 version and C 2 version.
- On Pubuntu all timings are increased because it has a slower access to memory.
- I have used a (low quality) portable rnd generator to assure equal test cases on all compilers and operating systems. (And because while the D std library Tango has a gaussian generator, the Phobos std lib of Dv.1 doesn't have it).
- Currently the seed of the random generator can't be changed.
- All the programs give the same output, but the results aren't equal up to the last floating point digits anyway because different FP instructions produce sligtly different results. FP numbers are approximations.
- The C code is slower, I don't know why.
- The D 2 code is much faster than D 1 with DMD because DMD has limited inlining capabilities (this is why I have created the D 2 version).
- In the D code the abs function is not taken from Tango because LDC has a performance bug, and otherwise it's not able to inline it.
- For the LTO+I see below.

More info and all the code can be found here:
http://www.fantascienza.net/leonardo/js/jarvism.zip