Postabon Blog

Try running the java code using the server jvm.

Thanks for the advice Ben.

Running DistancePrimitives with -server took about 113 seconds (instead of the ~115 it takes with -client). A little faster, but not really a significant difference.

interesting; i'm surprised by this. what jre are you using? i can't imagine it would make any difference, but you could "import static" the Math functions in the java code.

also, you could try running the entire java solution several times to see if it gets faster (again, just a stab in the dark).

(defconstant +earth-diameter+ 12742)

for the hotspot to kick in, I guess running 5 times might not enough try 100 times and see if there is a large discrepancy in the timing

also might I recommend using System.nanoTime();

sorry for posting so many times. just to clarify - what both i and onne are suggesting is that you need to run the routine more *within the same process*. there is a known issue that benchmarks can be misleading because something in the jit/memory management takes time to become efficient (although i have no idea what the threshold is, and what you are doing does seem like a fair chunk of work already).

andrew: Thanks for the hints. Rerunning the benchmark repeatedly in the same JVM yielded about a 10% improvement. Still not what as good as I think it should be.

$ java -version
java version "1.6.0_0"
OpenJDK Runtime Environment (build 1.6.0_0-b11)
OpenJDK 64-Bit Server VM (build 1.6.0_0-b11, mixed mode)

It's the latest java installable by apt in Debian ...

For the Python code, I would strongly suggest using a statement such as "from math import *" and using the functions sin(), cos(), sqrt(), etc. without the associated 'math.' prefix. You will find that the code runs about 25% faster (result I obtained when I tested it).

David: Thanks - good catch. I'm rerunning the benchmarks now. As soon as it finishes I'll update the code and the chart.

continuing to extend the bounds of my lack of knowledge... i had no idea what openjdk was (i just had a look at the faq - http://www.sun.com/software/opensource/java/faq.jsp - and it says what it contains, but doesn't seem to say what it doesn't contain that the proprietary jdk might).

so it might be worth downloading the "non-open" jre from java.sun.com and trying that (i develop commercially with java on linux and have always installed from java.sun.com rather than using what is provided in distros; but this openjdk looks like it is "the real thing" (at last) so again it's not clear there will be any speedup).

and while reading around i found this - http://java.sun.com/performance/reference/whitepapers/tuning.html#section3.1 - which explains better the earlier comment. see also section 4 for other suggestions on how to tune java code.

ps i am not really surprised lisp is fast - more surprised that java is not comparable.

It probably doesn't make much of a difference but you could try replacing the while constructs of the Python code with something along:

for latA in xrange(-90, 90 + increment, increment):
for lngA in xrange(-180, 180 + increment, increment):
for latB in xrange(-90, 90 + increment, increment):
for lngB in xrange(-180, 180 + increment, increment):

In my tests that was a bit faster.

If you are willing to benchmark Python further, please take a look at Psyco (http://psyco.sourceforge.net/), PyPy (http://codespeak.net/pypy/dist/pypy/doc/) and Cython (http://cython.org/). It would be somewhat interesting to see how the results gained using those would measure up against the rest.

You could also try to memoize (cache) the math func results to see if that makes any measurable difference. See http://code.activestate.com/recipes/52201/ for further information. That might be considering cheating, however. :)

Lua version:
------------------------------------------------------------------
local radius = 6371

local function distance(latA, lngA, latB, lngB)
local latAr = math.rad(latA)
local lngAr = math.rad(lngA)
local latBr = math.rad(latB)
local lngBr = math.rad(lngB)

local deltaLat = latBr - latAr
local deltaLng = lngBr - lngAr

return radius * 2 * math.asin(math.sqrt(
math.sin(deltaLat/2)^2 + math.cos(latAr)
* math.cos(latBr) * (math.sin(deltaLng/2)^2)))
end

local start = os.clock()

for latA=-90,90,2.5 do
for lngA=-90,90,2.5 do
for latB=-90,90,2.5 do
for lngB=-90,90,2.5 do
distance(latA, lngA, latB, lngB)
end
end
end
end

local stop = os.clock()
print(stop-start)
------------------------------------------------------------------

Runtime on a 3 GHz Core2 E8400:

270.55s Python 2.6.2 (for comparison)
33.49s Lua 5.1.4
0.04s LuaJIT 2.0.0-beta2

The distance() function is pure and its result is unused, so the compiler just optimizes it away. Even if you sum up the results to prevent this, it only takes 3.06 seconds with LuaJIT 2.0. No type declarations needed.

Change your time in java to use: System.currentTimeMillis();

You can test the overhead:

final long start = System.nanoTime();

//final long time = System.currentTimeMillis();
final long time = java.util.Calendar.getInstance().getTimeInMillis();

final long exec = System.nanoTime() - start;

System.out.println("exec: " + exec);

Java 1.6.0_0 was released December 2006! The current version is 1.6.0_18.

bebraw and andrew: very good points. I have to go do real work now, but I'll try to come back and rerun the java benchmark (with the official sun JRE) and the Python benchmark (with xrange). I think memoization is cheating (I'm not using it in any of the other solutions), and for the sake of simplicity I'm going to stick default Python interpreter/compiler.

Mike: Lua seems very impressive - I need to learn some more of it one of these days!

Ryan: You're right, that's probably the better way to do so. But it doesn't appear to make a measurable difference.

My mistake... I briefly glanced at this and thought the times were in milliseconds (not seconds).

>> If I'm making some terrible mistake in my Java <<

It's more that you are highlighting the danger of generalizing from a single small code snippet - maybe your code snippet does nothing more than remind us that Java sin and cos might not be using the machine hardware.

Notice the difference between

http://shootout.alioth.debian.org/gp4/program.php?test=partialsums&lang=java&id=4

and the plain vanilla program

http://shootout.alioth.debian.org/gp4/program.php?test=partialsums&lang=java&id=3

>> Rerunning the benchmark repeatedly in the same JVM <<

Here are some examples of what the differences can be, binary-trees has the noticeable improvement -

http://shootout.alioth.debian.org/help.php#java

Use -XX:+PrintCompilation -XX:-PrintGC to see what's happening with your code snippet

http://shootout.alioth.debian.org/u32q/program.php?test=binarytrees&lang=javasteady&id=2#about

Use a spell-checker! It's "dearth," not "dirth." And the ONLY valid meaning of "it's" is "it is" -- the possessive form is spelled "its" (no apostrophe). Stop contributing to the decline of the English language!

@bebraw:

your xrange isn't the same- xrange converts floats to ints for py2.6...

Brian Harring:
Oops. Good point! Coming up with a simple frange should not be too hard but that's probably beyond the point of this benchmark. :)

Few notes from boredom and an i7 @ ~2.8GHZ

1) the beazley version you've posted is bugged- needs to be sqrt( instead of math.sqrt( since you've imported sqrt into the globals() of that module
2) unladen-swallows (u-s) does a nice number on this- 144s. Still crappy admittedly, but down from 258s.
3) about 28s of u-s runtime is from continually recalculating floats + radius/radians scope lookups... calculate once (meaning down to 116s now)- that same change knocks 7s off of py2.6. Specifically making a list of the lat/longs it will inspect w/in each loop, and just iterating over that instead.
4) python function calls are stupidly expensive- via #3, down to 251s. Inlining distance (and doing the usual "localize the function" trick for the math bits you invoke) brings it down to 211s. As said... pricey ;)
5) pythons math module internally converts the items to doubles rather then floats- I'd assume that can be a hit using sqrt instead of sqrtf although I've no clue what lisp which lisp uses (I presume sqrtf going by your type modifications).

Aside from that random optimization run... yeah, python is getting it's ass handed to it here- I do truly wonder what the sqrt/sqrtf hit is though.

Obligatory Haskell version: http://domor.pastebin.com/f11063fdd
Runs in 13s on my laptop (-02, on Windows so no -fvia-c), but over half the time is spent in GC so it could probably be improved a lot.

It does have some nice type safety between radians and degrees :)

Java's transcendental math functions have a well-known problem in that their API contract means that they don't use the hardware sin/cos instructions. Something to do with the fact that java produces good results no matter what the input while the intel hardware instructions will do some strange stuff outside of the [-PI/2, PI/2] range. Can't find the link right now.
So yeah, in this case, you're going to get better results with a language-runtime-JIT that has enough information to safely compile down to the machine instructions.

You are doing optimizations in your querying, but there are better ways of handling 'nearest neighbor' scenario. You can go from seconds to milliseconds. One data structure that comes to mind if the kd-tree, which is often used for when you want to find nearby locations to a coordinates.

http://en.wikipedia.org/wiki/Kd-tree

@jtarchie: We're using a modified R*-tree with some really cool bulk loading stuff for spatial/nearest-neigbhor queries. This is an order of magnitude faster than a kd-tree - and I may write a post at some point explaining it. The distance function is used in our recommendation engine - where we have to have a precise numerical distance as an argument in the 'weighting' function.

In this current configuration, hotspot is not working.
In order for Hotspot to trigger its magic, you need to extract your code into another method.
Warm-up hotspot by executing a few times this method.
Then you should experience the real speed of java.

and someone has tried it with the standard jdk - http://news.ycombinator.com/item?id=1084139 - which makes the times comparable (lisp is still slightly faster).

Python with psyco clocked at 150 seconds. Without: 398.

I love it how everyone's jumping in to defend the other languages.

All I have to say is... Go Lisp!

@framiere - not true, hotspot server can do on-stack replacement. With such long running test, difference is not huge.

Noel gave a real hint - sin/cos etc are very slow in java due to different expectations for quality of results. What you are testing here is speed of those functions and here java loses, no question about it. In fact, most of Math.* functions are way slower than expected - I remember getting 5x speedup in some microbenchmark when using (int)f instead of Math.floor(f) after noticing that f > 0 in particular place.

Hi, I so often saw the code like (the float (... (the float ...))), so decided to write small library that would add the type declarations recursively. It's very basic and just provides the only macro THE*, so if you write

(THE* SIGNLE-FLOAT (SIN (/ 1 4))

, it expands it into

(THE SINGLE-FLOAT (SIN (THE SINGLE-FLOAT (/ (THE SINGLE-FLOAT 1.0) (THE SINGLE-FLOAT 4.0)))))

But I have never used in in practice and can not tell how it is usable yet. So, I'd be glad if you could try it, and tell me if it is usable or not for a real project.

It is asdf-installable the name of the package is THE. Page on cliki: http://www.cliki.net/the

For the Java benchmark, please see the "Performance Options" part of the HotSpot VM options: http://java.sun.com/javase/technologies/hotspot/vmoptions.jsp#PerformanceTuning

For your test it may be more appropriate to apply aggressive optimization, like AggressiveOpts, or setting the CompileThreshold to a very low value (like to 1 :).

Best regards:
--
Norbert Sándor
http://jvminside.blogspot.com/

The frivolous denial of the Java crowd is classic.

> The frivolous denial of the Java crowd is classic.

That's not true :)
I'm just curious, if the test is run with more proper "real-life"-like configuration, how the HotSpot performs.

I am surprised at how poorly Python did in this case. I know from previous experience that in terms of string handling / parsing large log files etc it outperforms Java by a wide margin. I wonder what the bottleneck here is.