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

#21

Post by Erwin » Thu, Jan 28, 2010, 2:39 PM UTC

I ran the Python script through Shedskin, a partial Python implementation that compiles Python to machine code via an intermediate layer of C++. I did not have to declare any types for any variables, or add declarations for speed/safety; Shedskin automatically determined the types.

The finished program went down in runtime from 533.7s on my machine, to 24.42 seconds. If we adjust for machine speed (since the author's Python ran the python code in 474s), the comparative optimized result would be 21.7 seconds compared to author's hand-optimized lisp code at 30.2.

Note that this is probably an ideal case for Shedskin (which is a relatively new product: a 1-man job that's just a few years old compared to, I guess, hundreds if not thousands of man-years of research that have gone in LISP implementations).

Still, an interesting result.

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

#22

Post by stefano » Thu, Jan 28, 2010, 2:40 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…

Actually, there is a solution that takes 0.52 seconds: http://www.spoj.pl/ranks/PRIME1/lang=LISP%20sbcl

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

#23

Post by catch23 » Thu, Jan 28, 2010, 2:40 PM UTC

smanek wrote: post #6

jacquesm wrote: post #5

Earlier quoted context omitted.

Can you release the source data used for the benchmark? I'd like to compare it to C.

There is no source data. I just iterate through each latitude from -90 to 90 and each longitude from -180 to 180 in increments of 2.5 (for both the start and end). Check out the source code for any of the 5 examples (included in the post). If you'd like, post the code up somewhere and I'll be happy to run it on the same machine and post the results along with the rest.

I also wonder why your java benchmark is slow. Java seems to be around 2-3x slower than C on average, this would make your optimized CL to be around 1.5x faster than C.

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

#24

Post by smanek » Thu, Jan 28, 2010, 2:41 PM UTC

wendroid wrote: post #11

> All the benchmarks were run 5x each on the same Debian machine I refer the honourable gentlman to Zed Shaw's "Programmers Need To Learn Statistics Or I Will Kill Them All" http://www.zedshaw.com/essays/programmer_stats.html

I'm actually a mathematician by training ;-)

I ran all tests 5 times each, and averaged the results. Each of the results for each of the tests were within 2% of each other, and the machine wasn't used for anything else while the tests were running.

I know it's not perfect, but I don't see any obvious sources of error ... I did provide all the source, so you're welcome to verify my results.

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

#25

Post by [deleted] » Thu, Jan 28, 2010, 2:42 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

#26

Post by jbooth » Thu, Jan 28, 2010, 2:43 PM UTC

smanek wrote: post #20

jbooth wrote: post #17

Any guesses as to why the Java implementation is relatively slow? JNI boundary crossings for floating point arithmetic, or lack of use of the math coprocessor?

I don't know, but it's much slower than I expected. It's the latest Java installable by apt on Debian (all these tests are run in Debian running under VMWare). $ 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)

Dohhhhh don't use OpenJDK :)

Get the sun version, it's probably faster.

Although it may not be much faster, found this unfixed bug report: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5005861

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

#27

Post by smanek » Thu, Jan 28, 2010, 2:47 PM UTC

Erwin wrote: post #21

I ran the Python script through Shedskin, a partial Python implementation that compiles Python to machine code via an intermediate layer of C++. I did not have to declare any types for any variables, or add declarations for speed/safety; Shedskin automatically determined the types. The finished program went down in runtime from 533.7s on my machine, to 24.42 seconds. If we adjust for machine speed (since the author's…

Very impressive! I haven't used Shedskin before, but I hope it continues to grow and improve.

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

#28

Post by jbooth » Thu, Jan 28, 2010, 2:47 PM UTC

jbooth wrote: post #26

smanek wrote: post #20

Earlier quoted context omitted.

I don't know, but it's much slower than I expected. It's the latest Java installable by apt on Debian (all these tests are run in Debian running under VMWare). $ 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)

Dohhhhh don't use OpenJDK :) Get the sun version, it's probably faster. Although it may not be much faster, found this unfixed bug report: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5005861

In more depth : the sun JDK probably does a lot better job of JIT compilation, it's the difference between running interpreted bytecode and compiled native code.

On the Hadoop project, checksumming was a major CPU constraint, because you have to assume every file everywhere is possibly on faulty hardware, and checksum everything. They found that it was actually faster to implement CRC32 in pure Java and let the JIT compilation do it's magic than it was to make native calls to zlibc.

But that may not apply to floating point if the Java implementation is bad enough.

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

#29

Post by pierrefar » Thu, Jan 28, 2010, 2:48 PM UTC

smanek wrote: post #18

pierrefar wrote: post #15

In all seriousness, how does one start with setting up and learning how to program a CL web app?

I'm glad you asked ;-) http://blog.postabon.com/a-simple-lisp-webapp-for-beginners

Great stuff thanks!

$Weekend--;

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

#30

Post by smanek » Thu, Jan 28, 2010, 2:52 PM UTC

saurabh wrote: post #13

How about benchmarking the python code with NumPy?

My understanding is that you have to rewrite your code to take advantage of NumPy. Unfortunately, I've never used NumPy before, so I don't know how to do so.

However, if you'd like to modify my code to do so I'd be happy to rerun the test and publish the results.