For performance, write it in C - Part 3, Source code now available

[Peter Hickman]

New update to the web site. I have added the language versions to the
page and another timing.

Isaac Gouy created a Java version that output the data in binary format
so as to circumvent any overhead in the conversions. It didn't seem to
improve much on his previous version but to be honest I no longer
believe that my system can reliably time such short runs.

The source code is available from
http://peterhi.dyndns.org/write_it_in_c/index.html

I started to get my AMD64 4400 box set up to the 6 x 6 grids. It is
probably going to take me a week or more running the tests to get the
timings for this. Is anyone actually that interested or shall we knock
this thread on the head?

I'll leave the web page up.

 

[Jon Harrop]

I don't think the fact that everyone in one language's community does
something that people in other languages' communities don't so they can
get better performance makes what they're doing any less an
optimization. It just makes it an exceedingly common optimization (and
might indicate that language implementation defaults should be changed).

Precisely.

 

[Jon Harrop]

True,

Even for such a simple task, the ability to use sophisticated data
structures, higher-order functions and other constructs can make a solution
practically feasible in some languages and infeasible in others.

Simulated annealing solution to the travelling salesman problem is another
seemingly simple task that benefits enormously from high-level constructs.
The naive Fortran code given in Numerical Recipies (the de-facto standard
monologue) has an O(n) bottleneck that can be trivially reduced to O(sqrt
N) using closures or O(ln n) using balanced trees, neither of which are
feasible in C/Fortran for most science students.

but as I've said before C is a fragile language to work in if
you've come from a scripting background. A program will compile and then
crash with not the slightest hint at what went wrong, so any language
that will allow me to get that sort of performance with a better support
is a good thing. I will be learning Ocaml for this reason alone.

Absolutely, C is a systems programming language. People are abusing it when
they advocate it for tasks like this. C++ is slightly better but, as I've
shown, you've lost the performance advantage that you thought you had once
you start using its features. OCaml's great. It's succinct, safe and fast.
The main downside is probably that you have to get to grips with its type
system.

Here are my benchmarks for the final versions:

0.368s gcc -O2
0.458s ocamlopt -inline 100 -unsafe
0.605s g++ -O2
0.644s java

I can't seem to run the Perl or Ruby out of the box: how do I get the extra
packages that I need?

 

[Kristof Bastiaensen]

Even for such a simple task, the ability to use sophisticated data
structures, higher-order functions and other constructs can make a solution
practically feasible in some languages and infeasible in others.

Simulated annealing solution to the travelling salesman problem is another
seemingly simple task that benefits enormously from high-level constructs.
The naive Fortran code given in Numerical Recipies (the de-facto standard
monologue) has an O(n) bottleneck that can be trivially reduced to O(sqrt
N) using closures or O(ln n) using balanced trees, neither of which are
feasible in C/Fortran for most science students.


Absolutely, C is a systems programming language. People are abusing it when
they advocate it for tasks like this. C++ is slightly better but, as I've
shown, you've lost the performance advantage that you thought you had once
you start using its features. OCaml's great. It's succinct, safe and fast.
The main downside is probably that you have to get to grips with its type
system.

Here are my benchmarks for the final versions:

0.368s gcc -O2
0.458s ocamlopt -inline 100 -unsafe
0.605s g++ -O2
0.644s java

I can't seem to run the Perl or Ruby out of the box: how do I get the extra
packages that I need?

For my and Simon Kroegers version you need the permutation.rb file, which
you can install with rubygems, or extract it from the sourcepackage at
http://permutation.rubyforge.org/ (which I did). Perhaps it would be
better to include the permutation.rb file on the webpage?

Kristof

 

[Isaac Gouy]

Peter Hickman wrote:
-snip-

It's the degree of speed up that I felt that people are overlooking,
lets take the following:

Ruby 10.060 (user + sys)
C 3.350
Ocaml 2.558

C doesn't just shave a few percentage points off, you get a massive
boost without having to do anything weird. C seems to be /too hard/ for
many people, especially people who have never used it.

However Ocaml is an eye opener.

Browse the Language Shootout
http://shootout.alioth.debian.org/gp4/index.php

Here's something that generates permutations of a small integer array
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=fannkuch&lang=all

The far-left column shows the relative slow-down compared to the
fastest program - find Ruby, find YARV, find Perl, find OCaml, find
GCC.

Look at a something with longer runtimes
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=nbody&lang=all

 

[Austin Ziegler]

Browse the Language Shootout

Better yet, don't. The language shootout is only slightly more useful
than "the end of the Internet" site. Maybe. Throwing darts in a
dartboard and picking out results based on that is certainly more
reliable than the language shootout, because of the completely
dishonest way in which the shootout presents itself and selects
algorithmic representations.

The only benchmark worth measuring is your own application.

-austin

 

[Isaac Gouy]

Better yet, don't. The language shootout is only slightly more useful
than "the end of the Internet" site. Maybe. Throwing darts in a
dartboard and picking out results based on that is certainly more
reliable than the language shootout, because of the completely
dishonest way in which the shootout presents itself and selects
algorithmic representations.

The only benchmark worth measuring is your own application.

-austin

Austin, I knew I could rely on you!

The OP seems surprised by the order of magnitude differences between
Ruby and C performance - if he looked at regex-dna on the Computer
Language Shootout he might be surprised that the Ruby program is
relatively fast.

http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=regexdna&lang=all

 

[Isaac Gouy]

Even for such a simple task, the ability to use sophisticated data
structures, higher-order functions and other constructs can make a solution
practically feasible in some languages and infeasible in others.

Will OCaml make the task of exhaustively generating 9x9 latin squares
feasible?

 

[Austin Ziegler]

Austin, I knew I could rely on you!

Certainly I'll post in response as long as you're going to shill
something as worthless as the shootout.

I'm not surprised when Ruby shows up relatively fast; the choice of
algorithm almost always beats out the choice of language.

I'm just surprised it took you so long in the thread to start pushing
the shootout so hard. You're usually not so restrained before your
shilling starts.

-austin

 

[Isaac Gouy]

Isaac Gouy wrote: -snip-
True, but as I've said before C is a fragile language to work in if
you've come from a scripting background. A program will compile and then
crash with not the slightest hint at what went wrong, so any language
that will allow me to get that sort of performance with a better support
is a good thing. I will be learning Ocaml for this reason alone.

OCaml is a fine programming language... (and so are Haskell, Ruby,
.....)

Tim Bray mentioned the conventional wisdom about premature
optimization, let's be a bit more specific about why bothering about
programming language is a premature optimization in this particular
case.

We've started bothering about how fast the first stage of your
application performs, without knowing anything about the performance of
the rest of the application - that's premature.

Before we start bothering about application performance we need an
end-to-end application, so we can see which parts of the application
are limiting overall performance. There's no point trying to speed-up
generation of latin squares if the application performance is limited
by something else.

Using Perl or Ruby to generate latin squares could be just fine, as
long as they do it faster than the next stage of the application
consumes latin squares.

 

[Kristof Bastiaensen]

<snip>
Will OCaml make the task of exhaustively generating 9x9 latin squares
feasible?

And could anyone actually say what is the purpose of generating all
this data?

 

[Isaac Gouy]

And could anyone actually say what is the purpose of generating all
this data?

afaik it's intended to be a training-set for a program to evolve rules
for solving Sudoku puzzles.

Peter?

Makes me think the program could be fed one latin square at a time -
which sure beats waiting thousands of years to generate all the latin
squares for 9x9.

 

[Rick DeNatale]

Precisely.

It reminds me of Mark Twain's observation about how stupid the French
were, since he could never make them understand their own language!

--
Rick DeNatale

IPMS/USA Region 12 Coordinator
http://ipmsr12.denhaven2.com/

Visit the Project Mercury Wiki Site
http://www.mercuryspacecraft.com/

 

[Isaac Gouy]

Certainly I'll post in response as long as you're going to shill
something as worthless as the shootout.

I'm not surprised when Ruby shows up relatively fast; the choice of
algorithm almost always beats out the choice of language.

I'm just surprised it took you so long in the thread to start pushing
the shootout so hard. You're usually not so restrained before your
shilling starts.

-austin

And I doubt you're surprised when Ruby shows up relatively slow; on the
same algorithm. Language implementation technique almost always beats
out the choice of language - YARV.

But it isn't /your/ lack of surprise that's at issue, it's the
apparently genuine surprise of the OP - "It's the degree of speed up
that I felt that people are overlooking"

http://groups.google.com/group/comp.lang.ruby/msg/566de4c66255dda0

 

[Eric Hodel]

Certainly I'll post in response as long as you're going to shill
something as worthless as the shootout.

I'm not surprised when Ruby shows up relatively fast; the choice of
algorithm almost always beats out the choice of language.

I'm just surprised it took you so long in the thread to start pushing
the shootout so hard. You're usually not so restrained before your
shilling starts.

I have to agree with Austin here. There are benchmarks inside that
specify "this benchmark must use the implementation of the random
number generator from benchmark X".

Requirements like that make the results even more bogus. Sure, Ruby
has slower method dispatch, but now you've got and made the benchmark
unrealistic by skipping over the core libraries of all your
benchmarked applications.

 

[Isaac Gouy]

I have to agree with Austin here. There are benchmarks inside that
specify "this benchmark must use the implementation of the random
number generator from benchmark X".

Requirements like that make the results even more bogus. Sure, Ruby
has slower method dispatch, but now you've got and made the benchmark
unrealistic by skipping over the core libraries of all your
benchmarked applications.

--
Eric Hodel - (e-mail address removed) - http://blog.segment7.net
This implementation is HODEL-HASH-9600 compliant

http://trackmap.robotcoop.com

Thank you for making a specific criticism.

1) iirc We use a random number generator in one benchmark - fasta
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=fasta&lang=all

2) It's very straightforward - if we use Ruby rand instead of
implementing that random number generator we won't get the correct
output.

3) My impression is you feel arbitrary requirements are unrealistic - I
actually worked with a user who required a specific random number
generator, which unfortunately wasn't provided by the language
libraries I had available. In my experience arbitrary requirements are
boringly realistic.

(I wonder what we mean by "unrealistic" in this context? Do we mean
"Not like the programs I work on"?)

 

[ara.t.howard]

Thank you for making a specific criticism.

1) iirc We use a random number generator in one benchmark - fasta
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=fasta&lang=all

2) It's very straightforward - if we use Ruby rand instead of
implementing that random number generator we won't get the correct
output.

can you elaborate?

3) My impression is you feel arbitrary requirements are unrealistic - I
actually worked with a user who required a specific random number
generator, which unfortunately wasn't provided by the language
libraries I had available. In my experience arbitrary requirements are
boringly realistic.

then why not some 'number of lines of code' requirements? like you have to
write fasta in under 30 lines of code otherwise you have to benchmark on a
slower cpu since the cost of your time could have added another node to a
cluster? (kidding - but only a little)

(I wonder what we mean by "unrealistic" in this context? Do we mean
"Not like the programs I work on"?)

it means that if the code one is working on can be asisted by built-in
libraries/features and/or the first few links on google and it's not taken
advantage of that one is not a computer scientist but a masochist and a money
waster - not using ruby's built-in rand is like having a brick moving contest:
not that smart.

regards.

-a

 

[Caleb Clausen]

2) It's very straightforward - if we use Ruby rand instead of
implementing that random number generator we won't get the correct
output.

I have to question your testing strategy, then. I have not looked
closely at your benchmarks... but if you have to have a benchmark
which uses random numbers (say, Monte Carlo integration), then you
shouldn't require an exact result. Can't you verify that it is close
enough to the expected result?

 

[Isaac Gouy]

can you elaborate?


then why not some 'number of lines of code' requirements? like you have to
write fasta in under 30 lines of code otherwise you have to benchmark on a
slower cpu since the cost of your time could have added another node to a
cluster? (kidding - but only a little)


it means that if the code one is working on can be asisted by built-in
libraries/features and/or the first few links on google and it's not taken
advantage of that one is not a computer scientist but a masochist and a money
waster - not using ruby's built-in rand is like having a brick moving contest:
not that smart.

I guess the user I worked with would have demanded you be replaced by
someone willing to work with the requirements rather than produce a
more convenient wrong answer

 

[Isaac Gouy]

I have to question your testing strategy, then. I have not looked
closely at your benchmarks... but if you have to have a benchmark
which uses random numbers (say, Monte Carlo integration), then you
shouldn't require an exact result. Can't you verify that it is close
enough to the expected result?

If you're interested enough to speculate and question, please be
interested enough to click the URL that was provided and find out
something about it before you speculate and question ;-)

Here it is again
http://shootout.alioth.debian.org/gp4/benchmark.php?test=fasta&lang=all#about