Make Lisp 15x faster than Python or 4x faster than Java • Hacker News Board

Re: Make Lisp 15x faster than Python or 4x faster than Java

#51

Post by csbrooks » Thu, Jan 28, 2010, 3:42 PM UTC

brlewis wrote: post #7

Are people still calling Lisp slow in 2010? That was somewhat true when most programming was done in C. Plenty of languages slower than Lisp have risen to popularity since then.

What does it mean to call a language "slow", though? It's all relative, and it depends on the problem set.

I'm wary of analogies, because they can be tortured into "proving" anything you like. But what's faster, a car or a bike? In a big city during rush hour, a bike could very well be faster than driving. Clearly on the freeway, the car wins out.

Re: Make Lisp 15x faster than Python or 4x faster than Java

#52

Post by pvg » Thu, Jan 28, 2010, 3:52 PM UTC

Isn't it a much better idea to pick a distance comparison algorithm that's not so staggeringly slow to begin with? Why not convert (i.e. pre-compute) the lat/lons to 3-vectors (origin center of the earth) and then compare distances by pythagoras, no fuss, muss or trig and you can even skip the square root. If you need to display an actual accurate distance you can do the (significantly smaller amount of) trig to get something presentable.

Re: Make Lisp 15x faster than Python or 4x faster than Java

#53

Post by lliiffee » Thu, Jan 28, 2010, 4:05 PM UTC

ez77 wrote: post #37

lliiffee wrote: post #36

Earlier quoted context omitted.

4x is low: http://shootout.alioth.debian.org/u32q/benchmark.php?test=al... Roughly speaking, anything time-critical needs to be done in c.

Thanks! You guys rock! Also, would you therefore guess most of Google's search engine is written in C?

I really don't know, but I would guess Google's search engine is almost all C/C++. When you are operating at that scale, it makes sense to invest huge programmer time for very small speed increases.

As to "normal" people, I do a lot of numerical computing using python+C. I end up with probably 90% of the code in python, and 10% inner loops in C. That's typically enough that the C code is taking, say, 50% of the time, at which it isn't worth it (for me) to move more python into C, since I could never buy myself more than a factor of 2 speedup.

Re: Make Lisp 15x faster than Python or 4x faster than Java

#54

Post by pvg » Thu, Jan 28, 2010, 4:08 PM UTC

It's better to use the actual JDK (i.e. the one everyone uses) rather than the implementation you get from debian apt-get due to debian's licensing hangups.

SBCL:

  * (test)

  Evaluation took:
    45.268 seconds of real time

Sun JDK

  Runtime was: 51086 Milliseconds

That's less than 15%, a far, far cry from '4 times'

Re: Make Lisp 15x faster than Python or 4x faster than Java

#55

Post by [deleted] » Thu, Jan 28, 2010, 4:21 PM UTC

maweaver wrote: post #10

One interesting source of data is www.spoj.pl, since they keep records of the runtime of submissions to their site. For example, take a look at the solutions to PRIME 1; the task is to generate a list of prime numbers: http://www.spoj.pl/ranks/PRIME1/ The top 20 C solutions all take less than 0.05 seconds. The top 20 Java solutions all take less than 0.5 second. Python has several solutions that took 0.55 seconds. Bu…

[deleted]

Re: Make Lisp 15x faster than Python or 4x faster than Java

#56

Post by pierrefar » Thu, Jan 28, 2010, 4:39 PM UTC

mahmud wrote: post #45

pierrefar wrote: post #29

Earlier quoted context omitted.

Great stuff thanks! $Weekend--;

What platform are you on? Let me know if you're on Win32 and I will package for you my setup, with a double-clickable installer, and your choice of Emacs or Win32 friendly IDE :-)

Thanks for the offer, but I'm afraid I have to decline so that I learn how start from scratch.

I'm on an EC2 Ubuntu instance.

Re: Make Lisp 15x faster than Python or 4x faster than Java

#57

Post by astine » Thu, Jan 28, 2010, 4:45 PM UTC

maweaver wrote: post #10

One interesting source of data is www.spoj.pl, since they keep records of the runtime of submissions to their site. For example, take a look at the solutions to PRIME 1; the task is to generate a list of prime numbers: http://www.spoj.pl/ranks/PRIME1/ The top 20 C solutions all take less than 0.05 seconds. The top 20 Java solutions all take less than 0.5 second. Python has several solutions that took 0.55 seconds. Bu…

There are two Lisp implementations on www.spoj.pl. One is Clisp which is bytecode compiled and rather slow and the other is SBCL which compiles to machine code and is the implementation used by the OP.

It looks as if you only looked at the former as the later has an entry at 0.52 (as mentioned by another commenter.)

A note about Common Lisp implementations is that there are many of them, all with different performance specs ideal use cases. Some are considered very fast, such as SBCL and CCL, others, not so much. Most of the data I've seen benchmarking Lisp against other languages uses one of the open source implementations. I'd like to see how a commercial Lisp, such as Allegro or Lispworks, performed, especially since those are the ones that have actually been worked on since the 80s/

Re: Make Lisp 15x faster than Python or 4x faster than Java

#58

Post by Semiapies » Thu, Jan 28, 2010, 4:53 PM UTC

drats wrote: post #35

brlewis wrote: post #7

Are people still calling Lisp slow in 2010? That was somewhat true when most programming was done in C. Plenty of languages slower than Lisp have risen to popularity since then.

Indeed, I thought it was always much faster: http://shootout.alioth.debian.org/u32/benchmark.php?test=all... One of the guys behind R is also looking at moving to a LISP base after considering python: http://www.springerlink.com/content/v38u176xp7j562m3/ That said, I will stick with python as I am not a programmer by profession and can't deal with a plethora of languages when I have a good swiss army knife as it is.

There are worse ones to pick.

Re: Make Lisp 15x faster than Python or 4x faster than Java

#59

Post by jedbrown » Thu, Jan 28, 2010, 5:16 PM UTC

1. Looping with a floating point increment is silly here because you can't be sure how many iterations it takes.

2. C translation takes 11 seconds (compare to 25.6 for SBCL)

http://gist.github.com/288936#file_silly distance loop

Re: Make Lisp 15x faster than Python or 4x faster than Java

#60

Post by jedbrown » Thu, Jan 28, 2010, 5:37 PM UTC

Retric wrote: post #48

smanek wrote: post #42

Earlier quoted context omitted.

I don't count the startup time for any of the languages (Java included). And the runtime for Java was over 2 minutes.

Wow, that is slow. Well java's pow function uses floats on the exponent so it would be a lot faster if you used a temporary variable, and then multiplied it by its self. Other than that I don't know, most of these math functions should translate to a single ASM function so I don't know why it's that slow. PS: I would probably inline the C function, but that's not a huge deal. My point was each language has its own op…

1. There is no C function.

2. Inlining in an actual C implementation doesn't matter because there is no register pressure and each trig function generates a real function call. Function calls to known addresses are really fast (~2 cycles), even indirect calls are fast compared to transcendental functions (~ 6 cycles). For comparison, the C implementation takes ~260 cycles each distance computation. This can't be improved much without vectorizing the trig functions.