The battle of the languages part II

Posted by Giovanni Intini | Filed under Java, Javascript, Lua, PHP, Programming, Ruby

My previous post about a programming contest I had with my friends was wildly popular. Much much more than I even thought possible.

I started with a simple comparison of PHP, C, Ruby, Erlang and Javascript and ended up with lots of comments where people posted interesting implementations in more and more languages, even obscure ones (to me) like Haskell and Ocaml.

I owe everyone a fairer benchmark so I will do the test again, this time testing the following languages:

  • C
  • Common Lisp
  • Erlang
  • Haskell
  • Javascript
  • Java
  • Ocaml
  • Perl
  • PHP
  • Python
  • Ruby

I need submissions for most of these languages, and I actually am quite open to submissions for the languages I speak :)

The rules are simple, the program has to store the results in an array (not just count them) and has to run without any strange libraries or compilers or compiler switches. To avoid interpreter starting time problems, please submit programs that autotime themselves.

As usual we’ll find the pythagorean triplets up to 5000. The reference implementation is the following, in Ruby:

t = Time.now
result = []
2.upto(5000) do |c| 
  1.upto(c-1) do |b|
    a = Math.sqrt(c*c - b*b)
    result << [a.to_i, b, c] if a.to_i == a 
  end
end
puts Time.now - t

This code takes 15.70s to run on my macbook pro.

Now it’s your turn!

Update: Lua version by Sindisil

local tt = os.clock()
local result = {}
local c
  for c = 2, 5000 do
    local b
    for b = 1, c-1 do
      local a = math.sqrt(c*c - b*b)
      if a == math.floor(a) then
      result[#result+1] = { a, b, c }
    end
  end
end
print(os.clock() - tt)

It takes 5.48s to run on my box.

Update: new Ruby version.

include Math
 
a, b, c = 0
result = []
2.upto(5000) do |c| 
  d = c * c
  1.upto(c-1) do |b|
    a = sqrt(d - b*b)
    result << [a.floor, b, c] if a.floor == a 
  end
end
puts Process.times[0]

Following Gabriele Renzi’s suggestions we now have a faster ruby version: 12.30s

Update: faster Lua version from Chris Swetenham, it runs in 3.44s

local tt = os.clock()
local result = {}
local c
local n = 1
local math = math
local sqrt = math.sqrt
local floor = math.floor
 
for c = 2, 5000 do
  local b
  for b = 1, c-1 do
    local a = sqrt(c*c - b*b)
    if a == floor(a) then
      result[n] = { a, b, c }
      n = n + 1
    end
  end
end
 
print(os.clock() - tt)

Update: PHP version by Fullo

<?php
$start = microtime(true);
$a = $b = $c = 0;
$result = array();
 
for ($c = 2; $c <= 5000; $c++) {
  for ($b = 1; $b < $c; $b++) {
    $a = sqrt($c*$c - $b*$b);
	if (intval($a) == $a) 
       $result[] = array($a,$b,$c);              
  }
}
echo (microtime(true) - $start);
?>

It runs in 9.73s.

Update: Python version from ludo, it runs in 11.2s

from time import clock
 
start = clock()
 
from math import sqrt
 
results = []
 
for c in xrange(2, 5001):
  d = c * c
  for b in xrange(1, c):
    a = sqrt(d - b * b)
    if a % 1 == 0.0:
      results.append((a, b, c))
 
print clock() - start

The results for now:

  1. Lua 3.44
  2. PHP 9.73
  3. Python 11.20
  4. Ruby 12.30

Permalink | Comments (31) | May 23, 2007

31 Responses to “The battle of the languages part II”

  1. Erlang, Ruby and PHP battle it out! -- A Tempest of Thoughts Says:
    May 23rd, 2007 at 5:48 pm

    [...] Update: here’s the followup! [...]

  2. Sindisil Says:
    May 23rd, 2007 at 10:59 pm

    Not that you asked, but in lua that would be:

    local c
    for c = 2, 5000 do
    local b
    for b = 1, c-1 do
    local a = math.sqrt(c*c – b*b)
    if a == math.floor(a) then
    result[#result+1] = { a, b, c }
    end
    end
    end
    print(os.clock() – tt)

    On my 2GHz Core Duo Windows XP laptop, that takes 5.69 seconds in Lua 5.1.2 (best of three, rounded to match your result). Using LuaJit 1.1.2 (based on Lua 5.1.1) it takes 3.88 seconds (again, best of three, rounded to two places to match your posted time).

  3. Giovanni Intini Says:
    May 24th, 2007 at 12:00 am

    I’m trying to launch your code, but I get this error:

    lua: pythag.lua:7: attempt to get length of global 'result' (a nil value)
stack traceback:
        pythag.lua:7: in main chunk
        [C]: ?
  4. Sindisil Says:
    May 24th, 2007 at 12:10 am

    Sorry, cut-n-paste error. Add the following two lines at the beginning, before “local c”:

    local tt = os.clock()
    local result = {}

    Sorry ‘bout that. I should have proofed it before submitting. Too bad your blog ate my indentation.

  5. Giovanni Intini Says:
    May 24th, 2007 at 10:19 am

    It takes 5.48 on my MB Pro with Lua 5.1.2. I’ll update the post.

  6. Erlang, Ruby and PHP battle it out! | the pix zone Says:
    May 24th, 2007 at 10:44 am

    [...] Update: the battle continues here. [...]

  7. riffraff Says:
    May 24th, 2007 at 11:31 am

    I believe that in the ruby versione you should be using
    utime,stime=Process.times
    in place of Time.now – Time.before, so that you can filter the real time spent from the script from the system time.

    Oh and as I alrteady told you, predeclaring the variables out of the loops and include’ing Math will give you a small improvement (5% on my box).

    Stay tuned for a parrot+perl6 test :)

  8. Chris Swetenham Says:
    May 24th, 2007 at 12:24 pm

    My improved version of the Lua code – I see a 25% speedup compared to Sindisil’s version.

    local tt = os.clock()
    local result = {}
    local c
    local n = 1
    local math = math
    local sqrt = math.sqrt
    local floor = math.floor
    for c = 2, 5000 do
    local b
    for b = 1, c-1 do
    local a = sqrt(c*c – b*b)
    if a == floor(a) then
    result[n] = { a, b, c }
    n = n + 1
    end
    end
    end
    print(os.clock() – tt)

  9. fullo Says:
    May 24th, 2007 at 1:18 pm

    I prefer this code.. I’ve speedup the other by 2ms ;)

    $start = microtime(true);
    (float) $a = $b = $c = 0;
    $result = array();

    for ($c = 2; $c

  10. fullo Says:
    May 24th, 2007 at 1:26 pm

    ops.. the code is gone away…
    $start = microtime(true);
    (float) $a = $b = $c = 0;
    $result = array();

    for ($c = 2; $c

  11. ludo Says:
    May 24th, 2007 at 1:50 pm

    Python:

    #!/usr/bin/python2.5 -O

    from time import clock

    start = clock()

    from math import sqrt

    results = []

    for c in xrange(2, 5001):
    d = c * c
    for b in xrange(1, c):
    a = sqrt(d – b * b)
    if a % 1 == 0.0:
    results.append((a, b, c))

    print clock() – start

  12. Mike Says:
    May 25th, 2007 at 7:50 pm

    About the Lua program: the “local b” and “local c” is unnecessary (loop variables are always locals). Caching the math table is pointless since it’s only used twice.

    This gives:

    local tt = os.clock()
    local sqrt, floor = math.sqrt, math.floor
    local result, n = {}, 1
    for c = 2, 5000 do
    for b = 1, c-1 do
    local a = sqrt(c*c – b*b)
    if a == floor(a) then
    result[n] = { a, b, c }
    n = n + 1
    end
    end
    end
    print(os.clock() – tt)

    On my box I get:

    2.97s Lua 5.1.2 (lua pythag.lua)
    0.47s LuaJIT 1.1.3 (luajit -O pythag.lua)

    (If you don’t get a 6x speedup with LuaJIT then you forgot to activate the optimizer with -O.)

    The LuaJIT result implies that 5000 may be a bit too low for a meaningful comparison. Remember to turn off speedstep/cool’n’quiet before benchmarking for such a short period of time.

  13. Giovanni Intini Says:
    May 26th, 2007 at 1:35 am

    Your version on my box is slower than the other one.

  14. ludo Says:
    May 26th, 2007 at 11:05 am

    Strange, the Python version on my box is faster than the PHP one. Maybe because I’m using python2.5?

  15. Giovanni Intini Says:
    May 26th, 2007 at 5:49 pm

    I’m using python2.5 too, what version of PHP are you using?

  16. ludo Says:
    May 26th, 2007 at 6:14 pm

    PHP 5.2.1 (cli)

  17. Giovanni Intini Says:
    May 27th, 2007 at 10:34 am

    I’m using 5.2.2 but I don’t think there should be any speed differences between them.

  18. Giovanni Intini Says:
    May 27th, 2007 at 10:36 am

    I tried again running both, just to be sure, and PHP is faster, at least on my box (MB Pro).

  19. Valentino Says:
    June 2nd, 2007 at 1:48 pm

    This python version should be faster, or at least it is on my macbook pro.

    from time import clock

    start = clock()

    results = []
    add = results.append

    for c in xrange(2, 5001):
    d = c ** 2
    for b in xrange(1, c):
    a = (d – b * b) ** 0.5
    if a % 1 == 0.0:
    add((a, b, c))

    print clock() – start

    The gain comes from using a C implemented sqrt (which is the 0.5 power) instead of the Python one, which is also imported.

  20. Stuart Dootson Says:
    June 2nd, 2007 at 4:09 pm

    Haskell – I use GHC 6.6.1 from http://www.haskell.org/ghc

    module Main where

    isPythag :: Int -> Int > Bool
    isPythag c b =
    (a*a)==diff
    where a = ratSqrt diff
    diff = (c*c)    (b*b)

    ratSqrt :: Int -> Int
    ratSqrt = truncate.sqrt.fromIntegral

    main = (putStrLn.show.length) [ 1 | c

  21. Stuart Dootson Says:
    June 2nd, 2007 at 4:10 pm

    My last comment got chopped off halfway (does your commenting system have a limit?) – here’s the remainder

    main = (putStrLn.show.length) [ 1 | c

  22. Stuart Dootson Says:
    June 2nd, 2007 at 4:11 pm

    Sorry – it was the less-then sign – here’s my ‘main’...

    main = (putStrLn.show.length) [ 1 | c< -[2..5000],b<-[1..c-1], isPythag c b ]

  23. Stuart Dootson Says:
    June 2nd, 2007 at 4:13 pm

    Final comment – compilation tips:

    Put the code into a file called a.hs and compile with ‘ghc -O2 a.hs -o a’

  24. Giovanni Intini Says:
    June 4th, 2007 at 12:07 pm

    I’m going to install ghc right now :)

  25. Stuart Dootson Says:
    June 6th, 2007 at 7:05 am

    Giovanni – I’ve just realised that the displayed Haskell code in my comment(s) has lost all indentation. Haskell is a little like Python, in that indentation can be significant. Hopefully, this repost won’t lost the indentation (I’m not 100% sure about what I can and can’t post in the comments re: HTML tags…)

    module Main where

isPythag :: Int -> Int <del>> Bool
isPythag c b =
   (a*a)==diff
   where a = ratSqrt (diff)
         diff = (c*c)</del>(b*b)

ratSqrt :: Int <del>> Int
ratSqrt = truncate.sqrt.fromIntegral

main = (putStrLn.show.length) [ 1 | c<</del>[2..5000],b<-[1..c-1], isPythag c b ]
  26. Stuart Dootson Says:
    June 6th, 2007 at 7:08 am

    Bah – I put it in 

     tags and it's still lost the indentation.

    OK - the line starting 'where a =' should be indented (by a tab-stop, or the equivalent in spaces), and the next line I have indented so that the start of 'diff =' lines up with the start of 'a ='.

  27. Dmitrii 'Mamut' Dimandt Says:
    June 6th, 2007 at 1:26 pm

    This is going to be rather longish and slightly offtopic…

    Here’s some code from a Russian site, http://rsdn.ru/forum/message/2515740.1.aspx (you may llok there to see pretty printed code):

    Original author is not me :)

    [start quote]
    Haskell’s GHC compiler is pretty bad when it comes to double-precision floating point arythmetic (or maybe I’m doing something wrong)

    If we directly rewrite the test:

    pythags :: Double -> Int
    pythags mp = pyth 2 0
    where
    pyth c i | c > mp = i
    | otherwise = pyth (c+1) (i + (pyth’ 1 0))
    where
    pyth’ b j | b c = j
    | otherwise = let a = sqrt (c*c - b*b)
    in if a fromIntegral ((truncate a)::Int)
    then pyth’ (b+1) (j+1)
    else pyth’ (b+1) j

    or like this:

    pythags :: Double -> Int
    pythags mp = length [ () | c

    then it will be approx. 40 times slower than VisualC or 25 times slower than GCC:

    int pyphags(double mp)
    {
    double c, b;
    int i = 0;
    double a;

    for (c = 2; c

    If we, however, rewrite the test using integers only:

    pythags :: Int -> Int
    pythags mp = length [ () | c

    then the difference between GHC and GCC will be less than that between VisualC and GCC:

    int pyphags(int mp)
    {
    int a, b, c, s, i=0;

    for (c = 2; c

    When mp = 5000 my computer gives:

    Double Int
    VisualC 8.0 0.9 sec 0.7 sec
    GCC mingw 3.4.5 1.4 sec 1.0 sec
    GHC 6.6 34 sec 1.3 sec

    Note. GCC 6.2 that comes with GHC 6.6 (Win32) has a slow implementation of sqrt in math.h, so I defined fastDoubleSqrt and fastIntSqrt for GCC as follows:

    __inline double fastDoubleSqrt(double x)
    {
    register double res;
    __asm volatile (“fsqrt” : ”=t” (res) : “0” (x));
    return res;
    }

    __inline int fastIntSqrt(int x)
    {
    return (int)fastDoubleSqrt((double)x);
    }

    For VisualC (it’s ok in this department):

    inline double fastDoubleSqrt(double x)
    {
    return sqrt(x);
    }

    inline int fastIntSqrt(double x)
    {
    return ((int)sqrt((double)x);
    }

    [end quote]

  28. Dmitrii 'Mamut' Dimandt Says:
    June 6th, 2007 at 1:28 pm

    I wonder if my previous comment has been lost…

    This is going to be rather longish and slightly offtopic…

    Here’s some code from a Russian site, http://rsdn.ru/forum/message/2515740.1.aspx (you may llok there to see pretty printed code):

    Original author is not me :)

    [start quote]
    Haskell’s GHC compiler is pretty bad when it comes to double-precision floating point arythmetic (or maybe I’m doing something wrong)

    If we directly rewrite the test:

    pythags :: Double -> Int
    pythags mp = pyth 2 0
    where
    pyth c i | c > mp = i
    | otherwise = pyth (c+1) (i + (pyth’ 1 0))
    where
    pyth’ b j | b c = j
    | otherwise = let a = sqrt (c*c - b*b)
    in if a fromIntegral ((truncate a)::Int)
    then pyth’ (b+1) (j+1)
    else pyth’ (b+1) j

    or like this:

    pythags :: Double -> Int
    pythags mp = length [ () | c

    then it will be approx. 40 times slower than VisualC or 25 times slower than GCC:

    int pyphags(double mp)
    {
    double c, b;
    int i = 0;
    double a;

    for (c = 2; c

    If we, however, rewrite the test using integers only:

    pythags :: Int -> Int
    pythags mp = length [ () | c

    then the difference between GHC and GCC will be less than that between VisualC and GCC:

    int pyphags(int mp)
    {
    int a, b, c, s, i=0;

    for (c = 2; c

    When mp = 5000 my computer gives:

    Double Int
    VisualC 8.0 0.9 sec 0.7 sec
    GCC mingw 3.4.5 1.4 sec 1.0 sec
    GHC 6.6 34 sec 1.3 sec

    Note. GCC 6.2 that comes with GHC 6.6 (Win32) has a slow implementation of sqrt in math.h, so I defined fastDoubleSqrt and fastIntSqrt for GCC as follows:

    __inline double fastDoubleSqrt(double x)
    {
    register double res;
    __asm volatile (“fsqrt” : ”=t” (res) : “0” (x));
    return res;
    }

    __inline int fastIntSqrt(int x)
    {
    return (int)fastDoubleSqrt((double)x);
    }

    For VisualC (it’s ok in this department):

    inline double fastDoubleSqrt(double x)
    {
    return sqrt(x);
    }

    inline int fastIntSqrt(double x)
    {
    return ((int)sqrt((double)x);
    }

    [end quote]

  29. Alex Says:
    November 28th, 2007 at 9:05 am

    Python:

    from time import clock

    start = clock()
    from math import sqrt

    results = [(sqrt(c*c – b*b),b,c) for c in xrange(2,5001) for b in xrange(1,c) if sqrt(c*c – b*b) %1 0.0]

    print clock() - start

    And if I wanted to cheat and beat everything, including Fortran, in the speed department:

    from time import clock

    start = clock()
    from math import sqrt

    results = ((sqrt(c*c - b*b),b,c) for c in xrange(2,5001) for b in xrange(1,c) if sqrt(c*c - b*b) %1 0.0)

    print clock() – start

    :P

  30. Jaroslaw Zabiello Says:
    January 12th, 2009 at 4:37 pm

    It all depends what you test… Why not add JRuby and RUby 1.9? They kill PHP. http://gist.github.com/42915. For web frameworks see: http://www.slideshare.net/mattetti/merb-presentation-at-orug-presentation

  31. Jaroslaw Zabiello Says:
    January 12th, 2009 at 5:35 pm

    I have slighty different results:

    Lua 5.1.4: 2.95s
    JRuby 1.1.7 (trunk)—fast—server: 4.93s
    Python 2.6.1: 7.92s
    PHP 5.2.8: 8.20s
    Ruby EE 1.8.6: 10.08s

    platform: Mac OS-X 10.5.6, PowerMac 2×2.8GHz