Compiled by Anand Kishore
For performance, write it in C
100 messages
Peter Hickman <peter@semantico.com> Wed, Jul 26, 2006 at 2:17 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Whenever the question of performance comes up with scripting languages
such as Ruby, Perl or Python there will be people whose response can be
summarised as "Write it in C". I am one such person. Some people take
offence at this and label us trolls or heretics of the true programming
language (take your pick).

I am assuming here that when people talk about performance they really
mean speed. Some will disagree but this is what I am talking about.

In this post I want to clear some things up and provide benchmarks as to
why you should take "Write it in C" seriously. Personally I like to
write my projects in Ruby or Perl or Python and then convert them to C
to get a performance boost. How much of a boost? Well here I will give
you some hard data and source code so that you can see just how much of
a boost C can give you.

The mini project in question is to generate all the valid Latin squares.
A Latin square is a grid of numbers (lets say a 9 x 9 grid) that has the
numbers 1 to 9 appear only once in each row and column. Sudoku grids are
a subset of Latin squares.

The approach taken is to create a list of all the permutations and then
build up a grid row by row checking that the newly added row does not
conflict with any of the previous rows. If the final row can be added
without problem the solution is printed and the search for the next one
starts. It is in essence depth first search. The first version of the
program that I wrote in Perl took 473 minutes to generate all the valid
5 x 5 Latin squares, version four of the program took 12 minutes and 51
seconds. The C version of the program took 5.5 seconds to produce
identical results. All run on the same hardware.

[Latin]$ time ./Latin1.pl 5 > x5

real    473m45.370s
user    248m59.752s
sys     2m54.598s

[Latin]$ time ./Latin4.pl 5 > x5

real    12m51.178s
user    12m14.066s
sys     0m7.101s

[Latin]$ time ./c_version.sh 5

real    0m5.519s
user    0m4.585s
sys     0m0.691s

This is what I mean when I say that coding in C will improve the
performance of your program. The improvement goes beyond percentages, it
is in orders of magnitude. I think that the effort is worth it. If a 5 x
5 grid with 120 permutations took 12 minutes in Perl, how long would a 6
* 6 grid with 720 permutations take? What unit of measure would you be
using for a 9 x 9 grid?

Size   Permutations
====   ============
  1              1
  2              2
  3              6
  4             24
  5            120
  6            720
  7           5040
  8          40320
  9         362880

Now lets look at first version of the code:

    1  #!/usr/bin/perl -w

    2  use strict;
    3  use warnings;

    4  use Algorithm::Permute;

    5  my $width_of_board = shift;

    6  my @permutations;

    7  my $p = new Algorithm::Permute( [ 1 .. $width_of_board ] );

    8  while ( my @res = $p->next ) {
    9      push @permutations, [@res];
   10  }
   11  my $number_of_permutations = scalar(@permutations);

   12  for ( my $x = 0 ; $x < $number_of_permutations ; $x++ ) {
   13      add_a_line($x);
   14  }

Lines 1 to 11 just build up a list of all the permutations using the
handy Algorithm::Permute module from CPAN. Lines 12 to 14 starts on the
first row of the solution by trying out all possible permutations for
the first row.

   15  sub add_a_line {
   16      my @lines = @_;

   17      my $size = scalar(@lines);

   18      my $ok = 1;
   19      for ( my $x = 0 ; $x < $size ; $x++ ) {
   20          for ( my $y = 0 ; $y < $size ; $y++ ) {
   21              if ( $x != $y ) {
   22                  $ok = 0 unless compare( $lines[$x], $lines[$y] );
   23              }
   24          }
   25      }

   26      if ($ok) {
   27          if ( $size == $width_of_board ) {
   28              print join(':', map { p($_) } @lines) . "\n";
   29          }
   30          else {
   31              for ( my $x = 0 ; $x < $number_of_permutations ;
$x++ ) {
   32                  add_a_line( @lines, $x );
   33              }
   34          }
   35      }
   36  }

The add_a_line() function first checks that none of the lines so far
conflict (have the same digit in the same column), if it passes and the
number of lines equals the size of the board then the result is printed
and another solution is looked for. Failing that another line is added
and add_a_line() is called.

Here is the function that tells if two lines conflict.

   37  sub compare {
   38      my ( $a, $b ) = @_;

   39      my $ok = 1;

   40      my @aa = @{ $permutations[$a] };
   41      my @bb = @{ $permutations[$b] };

   42      for ( my $x = 0 ; $x < $width_of_board ; $x++ ) {
   43          $ok = 0 if $aa[$x] == $bb[$x];
   44      }

   45      return $ok == 1;
   46  }

The p() function is a little utility to convert a list into a string for
display.

   47  sub p {
   48      my ($x) = @_;

   49      my @a = @{ $permutations[$x] };
   50      my $y = join( '', @a );

   51      return $y;
   52  }

Well I have just exposed some pretty crap code to eternal ridicule on
the internet, but there you have it. The code is crap, even non Perl
programmers will be able to point out the deficenties with this code. It
works, even though a 5 x 5 grid took 473 minutes to run. Lets try and
salvage some pride and show version four and see how we managed to speed
things up.

    1  #!/usr/bin/perl -w

    2  use strict;
    3  use warnings;

    4  use Algorithm::Permute;

    5  my $width_of_board = shift;

    6  my @permutations;
    7  my @output;
    8  my %compared;

    9  my $p = new Algorithm::Permute( [ 1 .. $width_of_board ] );

   10  while ( my @res = $p->next ) {
   11      push @permutations, [@res];
   12      push @output, join( '', @res );
   13  }
   14  my $number_of_permutations = scalar(@permutations);

Lines 1 to 14 are doing pretty much what version one was doing except
that a new list, @output, is being built up to precalculate the output
strings and remove the need for the p() function. A minor speed up but
useful.

   15  for ( my $x = 0 ; $x < $number_of_permutations ; $x++ ) {
   16      for ( my $y = 0 ; $y < $number_of_permutations ; $y++ ) {
   17          my $ok = 1;

   18          my @aa = @{ $permutations[$x] };
   19          my @bb = @{ $permutations[$y] };

   20          for ( my $z = 0 ; $z < $width_of_board ; $z++ ) {
   21              if ( $aa[$z] == $bb[$z] ) {
   22                  $ok = 0;
   23                  last;
   24              }
   25          }

   26          if ( $ok == 1 ) {
   27              $compared{"$x:$y"} = 1;
   28          }
   29      }
   30  }

Lines 15 to 30 introduces new code to precalculate the comparisons and
feed the results into a hash. Lines 31 to 33 start the work in the same
way as version one.

   31  for ( my $x = 0 ; $x < $number_of_permutations ; $x++ ) {
   32      add_a_line($x);
   33  }

And now to the improved add_a_line() function. The code has been
improved to only check that the newly added line does not conflict with
any of the existsing lines rather than repeatedly comparing the existing
(valid) lines.

   34  sub add_a_line {
   35      my @lines = @_;

   36      my $size = scalar(@lines);

   37      my $ok = 1;

   38      if ( $size > 1 ) {
   39          for ( my $x = 0 ; $x < ( $size - 1 ) ; $x++ ) {
   40              unless ( defined $compared{ $lines[$x] .':'.
$lines[-1] } ) {
   41                  $ok = 0;
   42                  last;
   43              }
   44          }
   45      }

   46      if ($ok) {
   47          if ( $size == $width_of_board ) {
   48              print join( ':', map { $output[$_] } @lines ) . "\n";
   49          }
   50          else {
   51              for ( my $x = 0 ; $x < $number_of_permutations ;
$x++ ) {
   52                  add_a_line( @lines, $x );
   53              }
   54          }
   55      }
   56  }

These changes took us down from 473 minutes to just 12. The elimination
of unnessessary comparisons in add_a_line() helped as did the
precalculation of those comparisons. There are lessons to be learnt
here, write decent code and cache repetetive comparisons. There are no
great tricks, just that bad code can cost you dearly and simple things
can bring big improvements. So with such a massive improvement how could
we make our code any faster?

Write it in C.

Having learnt the lessons developing the code in Perl I am not going to
start the whole thing over in C. Using version four I used the
precalculation phase of the Perl scripts to write out a C header file
with data structures that would be useful for the C program.

    1  #define WIDTH_OF_BOARD 5
    2  #define NUMBER_OF_PERMUTATIONS 120
    3  char *output_strings[] = {
    4      "54321",

  123      "12345",
  124  };
  125  bool compared[NUMBER_OF_PERMUTATIONS][NUMBER_OF_PERMUTATIONS] = {
  126      {false, false, ...

  245      {false, false, ...
  246  };
  247  int work[WIDTH_OF_BOARD];

This then leaves the C code itself. Lines 1 to 7 includes a load of
useful stuff, infact it is also probably including some quite
unneccessary stuff too, I just cut and paste it from another project.

    1  #include <stdio.h>
    2  #include <stdlib.h>
    3  #include <stdbool.h>
    4  #include <err.h>
    5  #include <string.h>
    6  #include <unistd.h>
    7  #include <sys/types.h>

Line 8 is the header file that Perl precalculated.

    8  #include "Latin.h"

Now the meat. The code is pretty much the same as version four just
adapted to C. No special C tricks, no weird pointer stuff, an almost
line for line translation of the Perl code.

    9  void
   10  add_a_row(int row)
   11  {
   12      bool            is_ok;
   13      int             x,y;

   14      if (row == WIDTH_OF_BOARD) {
   15          for (x = 0; x < WIDTH_OF_BOARD; x++) {
   16              if (x == 0) {
   17                  printf("%s", output_strings[work[x]]);
   18              } else {
   19                  printf(":%s", output_strings[work[x]]);
   20              }
   21          }
   22          puts("");
   23      } else {
   24          for (x = 0; x < NUMBER_OF_PERMUTATIONS; x++) {
   25              work[row] = x;

   26              is_ok = true;
   27              if (row != 0) {
   28                  for( y = 0; y < row; y++ ) {
   29                      if(compared[work[row]][work[y]] == false) {
   30                          is_ok = false;
   31                          break;
   32                      }
   33                  }
   34              }
   35              if (is_ok == true) {
   36                  add_a_row(row + 1);
   37              }
   38          }
   39      }
   40  }

   41  int
   42  main(int argc, char *argv[])
   43  {
   44      add_a_row(0);
   45  }

And the C version ran in 5.5 seconds. In fact the 5.5 seconds includes
the Perl program that does all the precalculation to write the Latin.h
header file, the compiling of the C source and finally the running of
the program itself. So we have not cheated by doing some work outside
the timings.

Just think of it, 12 minutes down to 5.5 seconds without having to write
any incomprehensible C code. Because we all know that C code is
completely incomprehensible with it doing all that weird pointer stuff
all the time.

Now the Perl code could be improved, there are tricks that could be
pulled out of the bag to trim something off the 12 minutes. Perhaps
another language would be faster? But how far could you close the gap
from 12 minutes to 5.5 seconds?

Just to up the ante I added -fast -mcpu=7450 to the compiler (gcc
optimized for speed on an G4 Macintosh) and ran it again.

[Latin]$ time ./c_version.sh 5 > x5

real    0m3.986s
user    0m2.810s
sys     0m0.540s

Another 30% performance improvement without changing any code.

Lets review the languages we have used and their advantages. C is very
fast without any stupid tricks. C will give you better control over the
amount of memory you use (the Perl code eats up massive amounts of
memory in comparison, the 9 x 9 grid threw an out of memory error on my
1Gb machine).

It is much easier to develop in Perl. Any error message you get is
likely to at least give you a clue as to what the problem might be. C
programmers have to put up with the likes of 'Bus error' or
'Segmentation fault', which is why C programmers are grouches. Perl also
allows you to significantly improve your code without major rewrites.
There is a module called Memoize that can wrap a function and cache the
calls all by adding two extra lines to your code, the same is true for
most scripting languages.

So what am I recommending here, write all your programs in C? No. Write
all your programs in Perl? No. Write them in your favourite scripting
language to refine the code and then translate it into C if the
performance falls short of your requirements. Even if you intend to
write it in C all along hacking the code in Perl first allows you to
play with the algorithm without having to worry about memory allocation
and other such C style house keeping. Good code is good code in any
language.

If you really really want that performance boost then take the following
advice very seriously - "Write it in C".
Dr Nic <drnicwilliams@gmail.com> Wed, Jul 26, 2006 at 2:33 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Do you have any preferred tutorials on wrapping Ruby around C libraries?

--
Posted via http://www.ruby-forum.com/.
Pit Capitain <pit@capitain.de> Wed, Jul 26, 2006 at 2:53 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Peter Hickman schrieb:
> (Example of Perl and C Code)

Peter, is there any chance you could test your program with Ruby Inline?

  http://rubyforge.org/projects/rubyinline

I'm on Windows, so I can't use Ruby Inline (+1 for MinGW btw :-)

Regards,
Pit
benjohn@fysh.org <benjohn@fysh.org> Wed, Jul 26, 2006 at 3:10 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Peter Hickman gave a very good article about prototyping in a scripting
language, and then re-coding in c:

*snip*

> If you really really want that performance boost then take the following
> advice very seriously - "Write it in C".

I totally agree that with the current state of the art, this is the
right approach.

Maybe it doesn't need saying, but I'm going to... in the vasy majority
of applications, almost all of their run time is a tiny wee small
fraction of the code. This is the part that I would write in c (or c++).
The vast majority of the code (and it's not there just for fun, it's
still completely important to the application) will use a vanishingly
small fraction of processor time. This is the bit that I would probably
leave in Ruby.

People talk about the 80:20 principle, but in my experience it's much
more like 99:1 for applications. 99% of the code uses 1% of the run
time. 1% of the code consumes 99% of the run time. That could be the
signal processing and graphics heavy applications that I have
experienced though.

Thanks for the comparison, it was great. And thanks for the very nice
pre-generation of look up tables in perl idea. Nice.

Cheers,
 Benjohn
petethebloke@googlemail.com <petethebloke@googlemail.com> Wed, Jul 26, 2006 at 3:15 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
It might be interesting to see how Java fares too - another route
again.

Pete
[Quoted text hidden]
Tomasz Wegrzanowski <tomasz.wegrzanowski@gmail.com> Wed, Jul 26, 2006 at 3:24 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, benjohn@fysh.org <benjohn@fysh.org> wrote:
> Peter Hickman gave a very good article about prototyping in a scripting
> language, and then re-coding in c:
>
> *snip*
>
> > If you really really want that performance boost then take the following
> > advice very seriously - "Write it in C".
>
> I totally agree that with the current state of the art, this is the
> right approach.

Sorry, I just couldn't resist - but maybe you should code Java instead -
http://kano.net/javabench/ ;-)
Robert Dober <robert.dober@gmail.com> Wed, Jul 26, 2006 at 3:40 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
[Quoted text hidden]
> Of course not, but it might be of intereset that there are other
programming languages out there
Ada, ObjectiveC, Scheme, OCAML, Huskell you name it.
That said I agree that one can write code beautifully in C (see GTK for
example).
I do not think that people are treated bad when they say

  "Hmmm, maybe you should know that this kind of performance is not
possible in Ruby or even slightly faster interpreted languages, and that you
should consider writing part of it in C, it is not so difficult, have a look
here or there"

as opposed to those who write

 "Write it in C if you want speed"

That kind of post never gets accepted well and I have the feeling that when
the speed issue comes up there is a certain tendence to reply like that.
Otoh I agree that the speed issue comes up much too often, but I suggest
instead of
replying  "Write it in C if you want speed", one can ignore the post or
point to older posts.

Just my 0.02€.

Cheers
Robert


--
Deux choses sont infinies : l'univers et la bêtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein
Jay Levitt <jay+news@jay.fm> Wed, Jul 26, 2006 at 5:00 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Wed, 26 Jul 2006 17:47:13 +0900, Peter Hickman wrote:

> In this post I want to clear some things up and provide benchmarks as to
> why you should take "Write it in C" seriously.

This is a great post, and should at least be posted to a blog somewhere so
the masses who don't know about USENET can still find it on Google!

Jay
Peter Hickman <peter@semantico.com> Wed, Jul 26, 2006 at 5:17 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Robert Dober wrote:
> "Hmmm, maybe you should know that this kind of performance is not
> possible in Ruby or even slightly faster interpreted languages, and
> that you
> should consider writing part of it in C, it is not so difficult, have
> a look
> here or there"
>
> as opposed to those who write
>
>  "Write it in C if you want speed"
>

Tact has never been one of my strong points. Your phrasing was much
nicer I will agree. The things that has been bugging me with this whole
performance thing is that I am sure that many people do not realise just
how fast a program written in C can run. The people who seem to take
offence at being told to write their code in C seem to have no
significant experience in using C. What also seems to happen is that
after saying that performance is their number 1 absolute top priority
they start to back peddle saying how hard C code is to develop. Yes is
it harder to work with than a scripting language, it is all the rope you
need to hang yourself with but you can write some blindingly fast code
if you are prepared to put in the effort. Wasn't that what they said was
their number 1 absolute top priority?
Peter Hickman <peter@semantico.com> Wed, Jul 26, 2006 at 5:18 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
[Quoted text hidden]
I may well put it in my web site, along with all the source code. Google
and Yahoo hit it enough.
Leslie Viljoen <leslieviljoen@gmail.com> Wed, Jul 26, 2006 at 5:56 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, Peter Hickman <peter@semantico.com> wrote:
> Jay Levitt wrote:
> > On Wed, 26 Jul 2006 17:47:13 +0900, Peter Hickman wrote:
> >
> >
> >> In this post I want to clear some things up and provide benchmarks as to
> >> why you should take "Write it in C" seriously.

Something else to consider is the ease with which Ruby extensions can
be written in C. The first time I tried I has something running in 20
minutes.

Though if I was going to choose a (single) language for raw
performance I'd try to go with Pascal or Ada.


Les
Francis Cianfrocca <garbagecat10@gmail.com> Wed, Jul 26, 2006 at 6:23 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
One important thing about Ruby performance is that Ruby gets very
inefficient very quickly, as the size of the working set grows. This
manifests as an observed performance problem, but the tip-off is that
performance of a particular Ruby program is quite acceptable for small
data-set sizes (such as in your test fixtures), but falls off a cliff with
production data-sets. Most of the times that I have found myself rewriting
slow Ruby code in C have been to get a program that runs in far less memory,
by manually laying out the data structures. This improves performance not
only for the obvious reasons (less thrashing and less contention with other
processes on a busy server), but also because you can "help" the processor's
cache manager to get more hits by creating localities of reference and by
stuffing more of your working set into a smaller number of cache lines. This
matters all the more on multiprocessors, which are severely penalized by
cache misses, to the point that some naively-written programs can run
noticeably faster on a uniprocessor.
Charles O Nutter <headius@headius.com> Wed, Jul 26, 2006 at 7:27 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
I'll lob a couple of grenades and then duck for cover.

- Write it in C is as valid as write it in Java (as someone else mentioned).
Java is at least as fast as C for most algorithms. On the JRuby project,
when we need to clone a C extension or library from Ruby, we typically write
it first in Ruby (to get something running quickly) and then reimplement it
in Java (for performance). The sad truth beyond the numbers and quantitative
comparisons is that a dynamic typed language with no primitives is almost
certainly going to be slower than staticly typed with with
everything-is-an-object. Toss out your favorite super-fast dyntyped language
if you will...I'm speaking in generalities.
- Write it in C is also as dangerous (in the grand scheme of things) as
write it in Java, because it has the potential to tie you to a specific
platform. For better or for worse, there's a lot of Windows machines out
there, and practically none of them have compilers. That means anything you
write in C will have to be pre-built for those platforms, or users are SOL.
Java suffers from the same fate...a Java VM is required...but if you're
running JRuby you probably have already made that plunge. There's a balance
to be struck between tying yourself to fast native code or accepting slow
interpreted code. You pay a very specific price either way.

All this said, there's truth to the idea that we shouldn't *have* to write
platform-level code to get reasonable performance, and every effort should
be made to improve the speed of Ruby code as near as possible to that of the
underlying platform code. On JRuby, we are working on various compiler
designs to turn Ruby code directly into Java bytecodes and methods, cutting
out the overhead of node-by-node interpretation. Early returns show as high
as 65% gains for some algorithms. We're also looking at modifications to the
parsing process to structure the AST in ways that makes it easier to
interpret. We in particular have to compete with a vast world of Java code
and Java coders, and although we'll never match the performance of raw Java
we endeavor to get as close as possible.

--
Charles Oliver Nutter @ headius.blogspot.com
JRuby Developer @ www.jruby.org
Application Architect @ www.ventera.com
James Edward Gray II <james@grayproductions.net> Wed, Jul 26, 2006 at 7:32 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Jul 26, 2006, at 8:57 AM, Charles O Nutter wrote:

> - Write it in C is as valid as write it in Java (as someone else
> mentioned).
> Java is at least as fast as C for most algorithms.

I'm Java Certified and I've been hearing people say this for years,
but I just haven't experienced this myself.  You guys must develop on
much faster boxes than my MacBook Pro.  ;)

James Edward Gray II
Peter Hickman <peter@semantico.com> Wed, Jul 26, 2006 at 7:43 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Charles O Nutter wrote:
> I'll lob a couple of grenades and then duck for cover.
>
> - Write it in C is as valid as write it in Java (as someone else
> mentioned).
> Java is at least as fast as C for most algorithms.

As someone who is paid to program in Java I very seriously doubt this.
However I will write a Java version of the code and time it. It should
be interesting to say the least.

> All this said, there's truth to the idea that we shouldn't *have* to
> write
> platform-level code to get reasonable performance, and every effort
> should
> be made to improve the speed of Ruby code as near as possible to that
> of the
> underlying platform code.
We are talking about two different things here. I was talking about
performance as being the number 1 absolute top priority, you are talking
about 'reasonable performance'. As far as I am concerned for those
scripts that I don't convert to C Perl, Ruby and Python are fast enough.
Other people think that they are not, they seem to expect the sort of
performance C gives when they write things in a scripting language. I
think that they are barking.
Kroeger, Simon (ext) <simon.kroeger.ext@siemens.com> Wed, Jul 26, 2006 at 7:48 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Hi Peter!

> Whenever the question of performance comes up with scripting
> languages
> such as Ruby, Perl or Python there will be people whose
> response can be
> summarised as "Write it in C". I am one such person. Some people take
> offence at this and label us trolls or heretics of the true
> programming
> language (take your pick).

The last (and only) time I called someone a troll for saying
'Write it C' it was in response to a rails related question.
Further the OP asked for configuration items and such, but maybe
that's a whole other storry. (and of course you can write
C Extensions for rails... yeah, yadda, yadda :) )

...snip 52 lines Perl, some hundred lines C ...

> [Latin]$ time ./Latin1.pl 5 > x5
>
> real    473m45.370s
> user    248m59.752s
> sys     2m54.598s
>
> [Latin]$ time ./Latin4.pl 5 > x5
>
> real    12m51.178s
> user    12m14.066s
> sys     0m7.101s
>
> [Latin]$ time ./c_version.sh 5
>
> real    0m5.519s
> user    0m4.585s
> sys     0m0.691s

Just to show the beauty of ruby:
-----------------------------------------------------------
require 'rubygems'
require 'permutation'
require 'set'

$size = (ARGV.shift || 5).to_i

$perms = Permutation.new($size).map{|p| p.value}
$out = $perms.map{|p| p.map{|v| v+1}.join}
$filter = $perms.map do |p|
 s = SortedSet.new
 $perms.each_with_index do |o, i|
   o.each_with_index {|v, j| s.add(i) if p[j] == v}
 end && s.to_a
end

$latins = []
def search lines, possibs
 return $latins << lines if lines.size == $size
 possibs.each do |p|
   search lines + [p], (possibs -
$filter[p]).subtract(lines.last.to_i..p)
 end
end

search [], SortedSet[*(0...$perms.size)]

$latins.each do |latin|
 $perms.each do |perm|
   perm.each{|p| puts $out[latin[p]]}
   puts
 end
end
-----------------------------------------------------------
(does someone has a nicer/even faster version?)

would you please run that on your machine?
perhaps you have to do a "gem install permutation"
(no I don't think it's faster than your C code, but
it should beat the perl version)

> If you really really want that performance boost then take
> the following
> advice very seriously - "Write it in C".

Agreed, 100%, for those who want speed, speed and nothing
else there is hardly a better way.

thanks

Simon
Charles O Nutter <headius@headius.com> Wed, Jul 26, 2006 at 7:50 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
[Quoted text hidden]
Well la-dee-dah! Seriously though, there's a volume of tests and benchmarks
(for what they're worth) that show this to be true, and for memory-intensive
situations Java almost always wins because lazy memory management allows
work to get done first, faster. Granted, Java's abstractions make it easier
to write bad code...but that's true of every language, including C.

- Charles Oliver Nutter, CERTIFIED Java Developer
[Quoted text hidden]
Francis Cianfrocca <garbagecat10@gmail.com> Wed, Jul 26, 2006 at 7:54 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Peter Hickman wrote:
 > We are talking about two different things here. I was talking about
> performance as being the number 1 absolute top priority, you are talking
> about 'reasonable performance'. As far as I am concerned for those
> scripts that I don't convert to C Perl, Ruby and Python are fast enough.
> Other people think that they are not, they seem to expect the sort of
> performance C gives when they write things in a scripting language. I
> think that they are barking.

I quite agree with this. To Nutter's point, one can make one's own
choice between C and Java once the decision has been made to write
platform-level code. But most code, perhaps nearly all code, should stay
in dyntyped script, in order to optimize the development/runtime
cost-balance. I think you can get tremendous benefits from factoring
code cleverly enough to keep the native-code components as small as
possible. And this is often a nontrivial exercise because it depends on
a good understanding of where performance costs come from in any
particular program.

To the point about Java: as I mentioned upthread, working-set size is
often the key limiting factor in Ruby performance. On a large and busy
server (which is my target environment most of the time), Java can be a
very inappropriate choice for the same reason!
[Quoted text hidden]
Charles O Nutter <headius@headius.com> Wed, Jul 26, 2006 at 7:56 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, Peter Hickman <peter@semantico.com> wrote:
>
> Charles O Nutter wrote:
> > I'll lob a couple of grenades and then duck for cover.
> >
> > - Write it in C is as valid as write it in Java (as someone else
> > mentioned).
> > Java is at least as fast as C for most algorithms.
>
> As someone who is paid to program in Java I very seriously doubt this.
> However I will write a Java version of the code and time it. It should
> be interesting to say the least.


Doubt all you like.

> All this said, there's truth to the idea that we shouldn't *have* to
> > write
> > platform-level code to get reasonable performance, and every effort
> > should
> > be made to improve the speed of Ruby code as near as possible to that
> > of the
> > underlying platform code.
> We are talking about two different things here. I was talking about
> performance as being the number 1 absolute top priority, you are talking
> about 'reasonable performance'. As far as I am concerned for those
> scripts that I don't convert to C Perl, Ruby and Python are fast enough.
> Other people think that they are not, they seem to expect the sort of
> performance C gives when they write things in a scripting language. I
> think that they are barking.


They may be hoping for the impossible, but that doesn't mean they shouldn't
hope and that doesn't mean they shouldn't be frustrated when the stock
answer is "write it in C". The fact that Ruby and other dynamic languages
are not as fast as compiled C is not the language's fault or the user's
fault...it's an implementation flaw. It certainly may be a flaw that can't
be fixed, a problem impossible to solve, but there's nothing about a
language's design that should necessitate it being slower than any other
language. Perhaps we haven't found the right way to implement these
languages, or perhaps some of us have and others just aren't there yet.
Either way, it's not the language that's eventually the problem...it's
simply the distance from what the underlying platform wants to run that's an
issue. C is, as they put it, closer to "bare metal", but only because C is
little more than a set of macros on top of assembly code. If the underlying
processor ran YARV bytecodes, I doubt Ruby performance would be a concern.
[Quoted text hidden]
Ryan McGovern <mcgoverp@labs.uc.edu> Wed, Jul 26, 2006 at 7:59 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Charles O Nutter wrote:
>
> Well la-dee-dah! Seriously though, there's a volume of tests and
> benchmarks
> (for what they're worth) that show this to be true, and for
> memory-intensive
> situations Java almost always wins because lazy memory management allows
> work to get done first, faster. Granted, Java's abstractions make it
> easier
> to write bad code...but that's true of every language, including C.
>
> - Charles Oliver Nutter, CERTIFIED Java Developer
>
I dont doubt for simple applications and algorithms java is nearly as
fast as C if not equivalent.  Though for larger java projects such as
Eclipse, i've had a horrible time of it being slow and cumbersome on the
system, and Visual Studio will run fine and be far more responsive.
I dont really know why that is it could be as simple as some bad code in
the java gui layer that Eclipse is using.
pat eyler <pat.eyler@gmail.com> Wed, Jul 26, 2006 at 8:12 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
[Quoted text hidden]
well, I didn't post the original post (though I did link to it).  I
did post my take
on it.  At it's core:  write it in Ruby and if it's too slow, profile
it and rewrite the
slow parts (in C if need be).   Rewriting the whole app in C when Ruby makes
cohabitating with C (or C++ or Objective C) so easy just seems pointless.

My post is at  http://on-ruby.blogspot.com/2006/07/rubyinline-making-making-things-faster.html




>
> Jay
>
>


--
thanks,
-pate
-------------------------
http://on-ruby.blogspot.com
Sean O'Halpin <sean.ohalpin@gmail.com> Wed, Jul 26, 2006 at 8:31 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, Charles O Nutter <headius@headius.com> wrote:

> there's nothing about a
> language's design that should necessitate it being slower than any other
> language.

While I accept that you shouldn't confuse a language with its implementation,
I find that a mildly surprising statement, especially since you said
in an earlier post:

> for memory-intensive situations Java almost always wins because lazy memory
> management allows work to get done first, faster

Garbage collection seems to me to be an integral part of Java's design.

Off the top of my head, I can think of some other design aspects that
have an effect on performance: method lookup in OO languages, scoping,
continuations, closures, static vs dynamic typing, type inference,
double dispatch, consing + car + cdr in Lisp, direct vs indirect
threading in Forth, etc. These are not just matters of implementation.
Each is a language design decision with a semantic effect which incurs
or avoids a computational cost, regardless of how it's actually
implemented. For example, Ruby has real closures, Python doesn't. I
don't see how you could ever reduce the cost of Ruby having closures
to zero - the memory alone is an implied overhead. Sure you can
optimize till the cows come home but different functionalities have
different costs and you can't ever avoid that.

Regards,
Sean
Dean Wampler <deanwampler@gmail.com> Wed, Jul 26, 2006 at 8:33 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, benjohn@fysh.org <benjohn@fysh.org> wrote:
> ...
>
> People talk about the 80:20 principle, but in my experience it's much
> more like 99:1 for applications. 99% of the code uses 1% of the run
> time. 1% of the code consumes 99% of the run time. That could be the
> signal processing and graphics heavy applications that I have
> experienced though.
> ...

This is the "value proposition" of the "Hot Spot" technology in the
Java Virtual Machine. On the fly, it looks for byte code sections that
get executed repeatedly and it then compiles them to object code,
thereby doing runtime optimization. This allows many Java server
processes to run with near-native speeds. When Ruby runs on a virtual
machine, planned for version 2, then Ruby can do that too. The JRuby
project will effectively accomplish the same goal.

--
Dean Wampler
http://www.objectmentor.com
http://www.aspectprogramming.com
http://www.contract4j.org
Pedro Côrte-Real <pedro@pedrocr.net> Wed, Jul 26, 2006 at 8:37 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, Sean O'Halpin <sean.ohalpin@gmail.com> wrote:
> Off the top of my head, I can think of some other design aspects that
> have an effect on performance: method lookup in OO languages, scoping,
> continuations, closures, static vs dynamic typing, type inference,
> double dispatch, consing + car + cdr in Lisp, direct vs indirect
> threading in Forth, etc. These are not just matters of implementation.
> Each is a language design decision with a semantic effect which incurs
> or avoids a computational cost, regardless of how it's actually
> implemented. For example, Ruby has real closures, Python doesn't. I
> don't see how you could ever reduce the cost of Ruby having closures
> to zero - the memory alone is an implied overhead. Sure you can
> optimize till the cows come home but different functionalities have
> different costs and you can't ever avoid that.

In theory if two programs in two different languages produce the same
exact results the perfect compilers for each of the languages would
end up producing the same code. In theory practice is the same as
theory but in practice it isn't.

Cheers,

Pedro.
Kristof Bastiaensen <kristof@vleeuwen.org> Wed, Jul 26, 2006 at 8:45 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Wed, 26 Jul 2006 17:47:13 +0900, Peter Hickman wrote:

> Whenever the question of performance comes up with scripting languages
> such as Ruby, Perl or Python there will be people whose response can be
> summarised as "Write it in C". I am one such person. Some people take
> offence at this and label us trolls or heretics of the true programming
> language (take your pick).
>
> <snip>

Hi,

When reading your C code, I saw that there is a lot of code that is
generated.  I'd be interested to see how well the C program does if
it can work for any size of the squares. In this case I think the problem
is well suited for logic languages. I wrote a version in the functional
logic language Curry, which does reasonably well.  It will probably not be
faster than the C version, but a lot faster than a program written in
Ruby/Perl/Python.

>If  you really really want that performance boost then take the following
> advice very seriously - "Write it in C".

It can be a good idea to rewrite parts in C, but I would first check if
the algorithms are good, so that it may not even be needed to write any
C code.  And perhaps there are libraries or tools that do the trick
efficiently.  I would keep writing C code as the last option.

Regards,
Kristof

-------------------- start of latin.curry ----------------------------
-- upto is a nondeterministic function that evaluates to
-- a number from 1 upto n
upto 1 = 1
upto n | n > 1 = n ? upto (n-1)

-- check if the lists r s have no element with the same value at the
-- same position
elems_diff r s = and $ zipWith (/=) r s

-- extend takes a list of columns, and extends each column with a
-- number for the next row.  It checks the number agains the column and
-- against the previous numbers in the row.

extend :: [[Int]] -> Int -> [[Int]]
extend cols n = addnum cols [] where
   addnum [] _ = []
   addnum (col:cs) prev
       | x =:= upto n &
         (x `elem` prev) =:= False &
         (x `elem` col) =:= False = (x:col) : addnum cs (x:prev)
       where x free

latin_square n = latin_square_ n
   where latin_square_ 0 = replicate n []  -- initalize columns to nil
         latin_square_ m | m > 0 = extend (latin_square_ (m-1)) n

square2str s = unlines $ map format_col s
   where format_col col = unwords $ map show col

main = mapIO_ (putStrLn . square2str) (findall (\s -> s =:= latin_square 5))
------------------------- end latin.curry -----------------------------
vasudevram <vasudevram@gmail.com> Wed, Jul 26, 2006 at 8:50 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
> > On Wed, 26 Jul 2006 17:47:13 +0900, Peter Hickman wrote:
> > > In this post I want to clear some things up and provide benchmarks as to
> > > why you should take "Write it in C" seriously.

Interesting series of messages! Got to save and read them through at
leisure ...

Just adding my 2c:

[I worked on a fairly complex performance tuning job once, involving
HP-UNIX boxes (multiple),
Informix ESQL/C batch programs, IBM MQ series (now called Websphere
MQ), UNIX IPC, and got a chance to do tuning at several different
levels - SQL queries, MQ logs/partitions, the C code, algorithms in it,
etc. Was very educational ... just sharing some insights gained from
that, from reading on the subject, and from smaller hobby projects
tuning my own code ...]

[Not implying that previous posters on this thread haven't done any of
the below].

Performance tuning in general is *very* complicated. Guesses or
assumptions like "this code tweak should make it run faster" often do
not work. The only way is a (semi)scientific approach to
measure/profile, study profile results, make hypotheses, change code
accordingly, then re-measure to see if the change made a difference.

Tuning can be done at any of several different levels, ranging from:

- hardware (even here, not just throwing more boxes or faster boxes at
the problem, but things like hardware architecture - obviously only if
the skills are available and the problem is worth the effort)

- software architecture

- algorithms and data structures optimization

- plain code tuning (things like common subexpression elimination, e.g.
using C syntax, changing:

for (i = 0; i < getLength(my_collection); i++) { /* do something with
my_collection[i] */ }

to

collLength = getLength(my_collection);
for (i = 0; i < collLength; i++)  { /* do something with
my_collection[i] */ }

/* which removes the repeated/redundant call to the function
getLength() */

Jon Bentley's book "Writing Efficient Programs" is a very good book
which discusses rules, examples and war stories of tuning at almost all
of these levels, including really excellent advice on code-level
tuning, which may sometimes be the easiest one to implement on existing
code.
Though the examples are in a pseudo-Pascal dialect (easily
understandable for those knowing C), and though it may be out of print
now, for those who have a real need for tuning advice, its worth trying
to get a used copy on eBay, from a friend, whatever.

Its chock-full of code examples with the tuning results (verifiied by
measurement, as stated above), when (and when not) to apply them, and
the war stories are really interesting too ...

Googling for "performance tuning" and variants thereof will help ...

There's another book (for Java, mostly server-side programming) by a
guy called Dov (something - forget his last name and the book title, if
I remember it, will post here) that's *really* excellent too - he shows
(again, with actual measurements) how some of the "expected" results
were actually wrong/counter-intuitive. He worked with IBM on the web
software for one of the recent Olympics.

HTH
Vasudev
----------------------------------------------------------------------------------
Vasudev Ram
Custom utility development in UNIX/C/sh/Java/Python/Ruby
Software consulting and training
http://www.dancingbison.com
----------------------------------------------------------------------------------
Peter Hickman <peter@semantico.com> Wed, Jul 26, 2006 at 8:51 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
I will run your Ruby version and the Java version that I write and post
the results here. Give us a week or so as I have other things to be doing.
Charles O Nutter <headius@headius.com> Wed, Jul 26, 2006 at 8:53 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, Sean O'Halpin <sean.ohalpin@gmail.com> wrote:
>
> On 7/26/06, Charles O Nutter <headius@headius.com> wrote:
>
> > there's nothing about a
> > language's design that should necessitate it being slower than any other
> > language.
>
> While I accept that you shouldn't confuse a language with its
> implementation,
> I find that a mildly surprising statement, especially since you said
> in an earlier post:
>
> > for memory-intensive situations Java almost always wins because lazy
> memory
> > management allows work to get done first, faster
>
> Garbage collection seems to me to be an integral part of Java's design.


Garbage collection is a characteristic of the Java VM, not the language.
Nothing in the language specifies garbage collection or how it should be
performed. It could just as easily be implemented with reference-counting,
and the language would still look exactly the same. What IS a characteristic
of the language is that you do not explicitly release objects when you are
finished using them. There are many ways to interpret that and many ways to
implement it. Garbage collection is just one among many.

Off the top of my head, I can think of some other design aspects that
> have an effect on performance: method lookup in OO languages, scoping,
> continuations, closures, static vs dynamic typing, type inference,
> double dispatch, consing + car + cdr in Lisp, direct vs indirect
> threading in Forth, etc. These are not just matters of implementation.
> Each is a language design decision with a semantic effect which incurs
> or avoids a computational cost, regardless of how it's actually
> implemented. For example, Ruby has real closures, Python doesn't. I
> don't see how you could ever reduce the cost of Ruby having closures
> to zero - the memory alone is an implied overhead. Sure you can
> optimize till the cows come home but different functionalities have
> different costs and you can't ever avoid that.


You're mixing language semantics and implementation details here. The
mechanics of method lookup is not a language feature; it's an implementation
detail. On the other hand, the logic of which method gets invoked in a
hierarchy of types is a language detail. Scoping is a language feature, but
the means by which scope is maintained is an implementation detail.
Continuations are a language feature, but the means by which a continuation
and its applicable scoping are memoized is an implementation detail. Static
and dynamic typing are language features; the means by which type is
propagated and used for calls, checks, and memory allocation is an
implementation detail. On and on and on...language features always have an
associated implementation, but there's almost always multiple ways to
implement a given feature, and those different implementations will have
their plusses and minuses.

As for the closure comment...sure, there's overhead in creating closures,
but it's *explicit* overhead. This is no different from creating the
equivalent of closures in languages that don't support them. The concept of
a closure has a clear specification and certainly increases the complexity
of a language and an underlying implementation. But that complexity may not
in itself always represent a decrease in performance, since other means of
accomplishing the same task may be even less performant. That's how it is
for any language feature...you take the good with the bad, and if you don't
use all of the good you may be less-than-optimal. If using a feature has ten
good aspects and five bad, and you only make use of five good aspects, then
your code is sub-optimal. If you use less than five, you're even worse off
and perhaps should consider doing things differently. Nothing about the
feature itself explicitly implies that performance should degrade by using
it...it's a matter of using those features wisely and making optimal use of
their good aspects, balanced with their bad aspects.
[Quoted text hidden]
Doug H <doug00@gmail.com> Wed, Jul 26, 2006 at 8:55 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Peter Hickman wrote:
> If you really really want that performance boost then take the following
> advice very seriously - "Write it in C".

Assuming you have no choice but C/C++.   That's why I like using the
jvm or clr with languages like jruby, groovy, or boo.  You don't have
to use C, you can use java or C# or boo itself (since it is statically
typed with type inference): http://boo.codehaus.org/
or C/C++ as well, although it is 100x easier to interface with a C lib
from the clr than it is from jvm with jni.
vasudevram <vasudevram@gmail.com> Wed, Jul 26, 2006 at 9:05 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>

Kristof Bastiaensen wrote:
> On Wed, 26 Jul 2006 17:47:13 +0900, Peter Hickman wrote:
>
> > Whenever the question of performance comes up with scripting languages
> > such as Ruby, Perl or Python there will be people whose response can be
> > summarised as "Write it in C". I am one such person. Some people take
> > offence at this and label us trolls or heretics of the true programming
> > language (take your pick).
> >
> > <snip>
>
> Hi,
>
> When reading your C code, I saw that there is a lot of code that is
> generated.  I'd be interested to see how well the C program does if
> it can work for any size of the squares. In this case I think the problem
> is well suited for logic languages. I wrote a version in the functional
> logic language Curry, which does reasonably well.  It will probably not be

Interesting ... I read somewhere that the OCaml language, while
higher-level than C (and a functional one too), runs some programs at
least, as fast or faster than C ...
Not sure how true that is ...

Vasudev
http://www.dancingbison.com
Sean O'Halpin <sean.ohalpin@gmail.com> Wed, Jul 26, 2006 at 9:10 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, Pedro Côrte-Real <pedro@pedrocr.net> wrote:
>
> In theory if two programs in two different languages produce the same
> exact results the perfect compilers for each of the languages would
> end up producing the same code. In theory practice is the same as
> theory but in practice it isn't.
>
> Cheers,
>
> Pedro.
>
>
In theory, an infinite number of computer scientists hacking for an
infinite amount of time on a keyboard will eventually almost surely
produce a perfect compiler.

In practice, I can't wait that long ;)

Cheers,
Sean
David Pollak <pollak@gmail.com> Wed, Jul 26, 2006 at 9:12 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Writing code that runs as fast in Java as it does in C is real work,
but it's possible.

Integer (http://athena.com) is a pure Java spreadsheet.  I optimized
the numeric functions and array functions (e.g., SUM(A1:G99)) such
that Integer runs as fast or faster than Excel and OpenOffice Calc on
identical hardware.  However, it required a mind shift from "standard"
Java programming.

In addition, because Java has nice semantics for multithreading, I was
able to implement some very cleaver algorithms such that Integer's
recalculation speed scales nearly linearly with additional CPUs up to
a certain point (the linearity goes away at around 16 processors on a
big Sun box.)  But I digress.

First, I pre-allocated a lot of workspace so that there's little
memory allocation going on during recalculation.

Second, I avoid Monitors (synchronized) as much as possible.

Third, I write "C" style Java (lots of switch statements, putting
parameters and results in buffers rather than passing them on the
stack, etc.)

Memory usage in Java is higher than in C.  If Java has Structs a la
C#/Mono, it'd be possible to squeeze that much more performance from
Java.

There are some applications that will never perform as in Java (e.g.,
stuff that's heavily oriented to bit manipulation.)  But for many
classes of applications (e.g., spreadsheets) Java can perform as well
as C.

When I care about computational performance, I go with Java or in a
rare case, C++ (C style C++, no STL or virtual methods).  If I care
about developer performance, I've been going with Ruby more and more.

My 2 cents.

On 7/26/06, James Edward Gray II <james@grayproductions.net> wrote:
[Quoted text hidden]
--
--------
David Pollak's Ruby Playground
http://dppruby.com
harrisj@schizopolis.net <harrisj@schizopolis.net> Wed, Jul 26, 2006 at 9:25 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
[Quoted text hidden]
You read that correctly. The problem is that nearly every benchmark I've
seen for comparing the performance of various languages has been a
repeated mathematical operation like computing a Mandelbrot Set or running
Fibonacci Sequences that all but guarantees the edge will belong to
functional languages like Haskell and OCAML or stripped-down assembly-like
languages like C (http://shootout.alioth.debian.org/debian/ for samples),
because they are best suited for straight-up number crunching. Are there
good benchmarks for OO languages? Or dynamic languages? Are there good
benchmarks that could actually measure the types of uses I need, where I'm
building a web front end to a DB store? I don't know about you, but my job
has never involved fractals.

I used to put faith into benchmarks like this, but now I think about
developer time and maintenance time as well. That seems to be a more
intelligent approach.

Jake
Gregory Brown <gregory.t.brown@gmail.com> Wed, Jul 26, 2006 at 9:33 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, David Pollak <pollak@gmail.com> wrote:

> In addition, because Java has nice semantics for multithreading, I was
> able to implement some very cleaver algorithms such that Integer's
> recalculation speed scales nearly linearly with additional CPUs up to
> a certain point (the linearity goes away at around 16 processors on a
> big Sun box.)  But I digress.

This must be evidence of true cutting edge development ;)
Isaac Gouy <igouy@yahoo.com> Wed, Jul 26, 2006 at 9:45 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
[Quoted text hidden]
"The results I got were that Java is significantly faster than
optimized C++ in many cases... I've been accused of biasing the results
by using the -O2 option for GCC..."

"...so I took the benchmark code for C++ and Java from the now outdated
Great Computer Language Shootout and ran the tests myself"

Not so outdated
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=all&lang=java&lang2=gpp
Kristof Bastiaensen <kristof@vleeuwen.org> Wed, Jul 26, 2006 at 9:50 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Thu, 27 Jul 2006 00:55:05 +0900, harrisj wrote:

>>
>> Kristof Bastiaensen wrote:
>>>
>>> <snipped a lot>
>> Interesting ... I read somewhere that the OCaml language, while
>> higher-level than C (and a functional one too), runs some programs at
>> least, as fast or faster than C ...
>> Not sure how true that is ...
>>
>> Vasudev
>> http://www.dancingbison.com
>
> You read that correctly. The problem is that nearly every benchmark I've
> seen for comparing the performance of various languages has been a
> repeated mathematical operation like computing a Mandelbrot Set or running
> Fibonacci Sequences that all but guarantees the edge will belong to
> functional languages like Haskell and OCAML or stripped-down assembly-like
> languages like C (http://shootout.alioth.debian.org/debian/ for samples),
> because they are best suited for straight-up number crunching.

In some cases the functional version is faster because the problem can be
more easily described in a functional way.  But in general code produced
by ocaml is about twice as slow as C, because the compiler doesn't do the
same extensive optimizations as for example gcc does.  But that's still
pretty good.

> Are there
> good benchmarks for OO languages? Or dynamic languages? Are there good
> benchmarks that could actually measure the types of uses I need, where I'm
> building a web front end to a DB store? I don't know about you, but my job
> has never involved fractals.
>
> <snip>

True, benchmarks only measure execution speed, but they don't show if a
given programmer will be productive in them.  I think that's also
largely a personal choice.  Some people may be more productive in a
functional language, some people more in Ruby. And others even in perl... :)

Kristof
Charles O Nutter <headius@headius.com> Wed, Jul 26, 2006 at 9:55 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
[Quoted text hidden]
No doubt, I wish I had that kind of problem when running my spreadsheet
application of choice. That's one hell of a business desktop!
[Quoted text hidden]
David Pollak <pollak@gmail.com> Wed, Jul 26, 2006 at 9:58 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Greg,

In spreadsheets, it is cutting edge.  Name one other commercial
spreadsheet that can use more than 1 CPU?

David

On 7/26/06, Gregory Brown <gregory.t.brown@gmail.com> wrote:
[Quoted text hidden]
[Quoted text hidden]
Martin Ellis <me_ncl@hotmail.com> Wed, Jul 26, 2006 at 10:00 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Sean O'Halpin wrote:
> In theory, an infinite number of computer scientists hacking for an
> infinite amount of time on a keyboard will eventually almost surely
> produce a perfect compiler.
>
> In practice, I can't wait that long ;)

You'd be waiting a long time indeed :o).

I believe our good friend Mr. Turing proved [1] that such
a compiler could never exist, some seven decades ago.

Oh well.

Martin


[1] OK.  That wasn't exactly what he proved.
   But only this particular corollary is relevant.
James Edward Gray II <james@grayproductions.net> Wed, Jul 26, 2006 at 10:05 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Jul 26, 2006, at 11:28 AM, David Pollak wrote:

> Greg,
>
> In spreadsheets, it is cutting edge.  Name one other commercial
> spreadsheet that can use more than 1 CPU?

I'm pretty sure Greg was funning around with the comical typo in your
post.  Take a look back at how you spelled "clever."  ;)

James Edward Gray II
Charles O Nutter <headius@headius.com> Wed, Jul 26, 2006 at 10:06 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
I think it's also worth mentioning that talking about the speed of a
*language* is rather absurd. You can't benchmark a language, other than
through mathematical proofs of complexity. What you can benchmark is an
implementation or compiler of a language, which will of course vary widely
from version to version. Ruby's current implementation may be slower than
many other language implementations, but it's not because it's Ruby. C may
be faster than just about anything, but it's not because of C. It's because
the compilers and interpreters for those other languages are unable to
produce code as optimally as current C compilers--which isn't surprising
considering how long C compilers have been around and how little work they
actually have to do.

The whole "write it in C" thing really ends up being a cop-out. So the
current C Ruby implementation isn't fast enough for you? Contribute your
time and resources and fix the implementation! Don't bloody patch around it
by leaving Ruby behind and writing C code! Demand more from your platform!
The community and the fates will thank you.
[Quoted text hidden]
ara.t.howard@noaa.gov <ara.t.howard@noaa.gov> Wed, Jul 26, 2006 at 10:09 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
[Quoted text hidden]
just for fun, here's a ruby version (note that the array would actually need
to be reformed into rows, but someone else can play with that)

  harp:~ > cat a.rb
  require 'gsl'

  n = Integer(ARGV.shift || 2)

  width, height = n, n

  perm = GSL::Permutation.alloc width * height

  p perm.to_a until perm.next == GSL::FAILURE


it's not terribly fast to run - but it was to write!

-a
--
suffering increases your inner strength.  also, the wishing for suffering
makes the suffering disappear.
- h.h. the 14th dali lama
Isaac Gouy <igouy@yahoo.com> Wed, Jul 26, 2006 at 10:15 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
[Quoted text hidden]
Once you ignore the stuff that beats up on hash-tables, character
manipulation, regex, concurrency,  memory allocation, ... you will be
left with array-access and number crunching.

otoh regex-dna makes Tcl look good :-)
http://shootout.alioth.debian.org/gp4/benchmark.php?test=regexdna&lang=tcl&id=2


> Are there good benchmarks for OO languages? Or dynamic languages? Are there good
> benchmarks that could actually measure the types of uses I need, where I'm
> building a web front end to a DB store? I don't know about you, but my job
> has never involved fractals.

Never involved double math in tight loops?


> I used to put faith into benchmarks like this, but now I think about
> developer time and maintenance time as well. That seems to be a more
> intelligent approach.
>
> Jake

"your application is the ultimate benchmark"
http://shootout.alioth.debian.org/gp4/miscfile.php?file=benchmarking&title=Flawed%20Benchmarks#app
Gregory Brown <gregory.t.brown@gmail.com> Wed, Jul 26, 2006 at 10:27 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On 7/26/06, James Edward Gray II <james@grayproductions.net> wrote:
[Quoted text hidden]
James gets right to the point.  I was just taking a slice at your
typo, not Integer. :)
David Pollak <pollak@gmail.com> Wed, Jul 26, 2006 at 11:19 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Guess I should unit test my posts... :-)

On 7/26/06, Gregory Brown <gregory.t.brown@gmail.com> wrote:
[Quoted text hidden]
[Quoted text hidden]
Chad Perrin <perrin@apotheon.com> Wed, Jul 26, 2006 at 11:48 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Wed, Jul 26, 2006 at 11:29:06PM +0900, Ryan McGovern wrote:
> >
> I dont doubt for simple applications and algorithms java is nearly as
> fast as C if not equivalent.  Though for larger java projects such as
> Eclipse, i've had a horrible time of it being slow and cumbersome on the
> system, and Visual Studio will run fine and be far more responsive.
> I dont really know why that is it could be as simple as some bad code in
> the java gui layer that Eclipse is using.

Doubtful.  Java does generally produce notably faster applications than
Ruby, and there are benchmarks that show that in specific instances it
can hustle almost as well as C -- even scalably so.  A more
comprehensive survey of benchmarks, on the other hand, starts to take
its toll on Java's reputation for speed.  The first problem is that C
isn't object oriented and, while OOP can be great for programmer
productivity under many circumstances (particularly involving larger
projects), it introduces a bunch of interface activity between parts of
the program which begins to slow things down.  Furthermore, Java's
bytecode-compilation and VM interpretation can increase execution speed
at runtime by cutting out part of the process of getting from source to
binary, but it still requires interpretation and relies on the
performance of the VM itself (which is, sad to say, not as light on its
feet as many would like).

In fact, there are cases where the Perl runtime compiler's quickness
makes Java's VM look dog-slow.  If your purpose for using a language
other than whatever high-level language you prefer is maximum
performance (presumably without giving up readable source code), Java
isn't an ideal choice.  If your high-level language of choice is Perl,
there's actually very little reason for Java at all, and the same is
true of some Lisp interpreters/compilers.

For those keen on functional programming syntax, Haskell is a better
choice than Java for performance: in fact, the only thing keeping
Haskell from performing as well as C, from what I understand, is the
current state of processor design.  Similarly, O'Caml is one of the
fastest non-C languages available: it consistently, in a wide range of
benchmark tests and real-world anecdotal comparisons, executes "at least
half as quickly" as C, which is faster than it sounds.

The OP is right, though: if execution speed is your top priority, use C.
Java is an also-ran -- what people generally mean when they say that
Java is almost as fast as C is that a given application written in both
C and Java "also runs in under a second" in Java, or something to that
effect.  While that may be true, there's a significant difference
between 0.023 seconds and 0.8 seconds (for hypothetical example).

--
CCD CopyWrite Chad Perrin [ http://ccd.apotheon.org ]
"The ability to quote is a serviceable
substitute for wit." - W. Somerset Maugham
Chad Perrin <perrin@apotheon.com> Wed, Jul 26, 2006 at 11:57 PM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Thu, Jul 27, 2006 at 12:42:46AM +0900, David Pollak wrote:
> Writing code that runs as fast in Java as it does in C is real work,
> but it's possible.

. . . the problem being that putting the same effort into optimizing a C
program will net greater performance rewards as well.  The only language
I've ever seen stand up to C in head-to-head optimization comparisons
with any consistency, and even outperform it, was Delphi-style Objective
Pascal, and that's only anecdotal comparisons involving my father (who
knows Delphi's Objective Pascal better than most lifelong C programmers
know C), so the comparisons might be somewhat skewed.  My suspicion is
that the compared C code can be tweaked to outperform the Object Pascal
beyond Object Pascal's ability to be tweaked for performance -- the
problem being that eventually you have to stop tweaking your code, so
sometimes the Object Pascal might be better anyway.

Java doesn't even come close to that level of performance optimization,
alas.  At least, not from what I've seen.


>
> There are some applications that will never perform as in Java (e.g.,
> stuff that's heavily oriented to bit manipulation.)  But for many
> classes of applications (e.g., spreadsheets) Java can perform as well
> as C.

Is that heavily optimized Java vs. "normal" (untweaked) C?

--
CCD CopyWrite Chad Perrin [ http://ccd.apotheon.org ]
Brian K. Reid: "In computer science, we stand on each other's feet."
Chad Perrin <perrin@apotheon.com> Thu, Jul 27, 2006 at 12:13 AM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Wed, Jul 26, 2006 at 11:26:45PM +0900, Charles O Nutter wrote:
> On 7/26/06, Peter Hickman <peter@semantico.com> wrote:
> >
> >Charles O Nutter wrote:
> >> I'll lob a couple of grenades and then duck for cover.
> >>
> >> - Write it in C is as valid as write it in Java (as someone else
> >> mentioned).
> >> Java is at least as fast as C for most algorithms.
> >
> >As someone who is paid to program in Java I very seriously doubt this.
> >However I will write a Java version of the code and time it. It should
> >be interesting to say the least.
>
> Doubt all you like.

Full disclaimer included:
As someone who is NOT paid to program in Java, and in fact finds Java
rather odious, and would rather write code in almost anything else that
isn't the annoyance factor equivalent of VB, I too doubt it.  Aside from
not being paid to program in Java, though, I have played with Java code,
I have researched Java performance characteristics extensively in the
performance of job tasks, I've looked at hundreds of benchmarks over the
years, and I know a fair bit about programming language interpreters
and parsers in the abstract.  The end result is that characterizing Java
as "at least as fast as C" in most cases and faster in many other cases
sounds like a load of (perhaps well-meaning) hooey to me.


>
> >We are talking about two different things here. I was talking about
> >performance as being the number 1 absolute top priority, you are talking
> >about 'reasonable performance'. As far as I am concerned for those
> >scripts that I don't convert to C Perl, Ruby and Python are fast enough.
> >Other people think that they are not, they seem to expect the sort of
> >performance C gives when they write things in a scripting language. I
> >think that they are barking.
>
> They may be hoping for the impossible, but that doesn't mean they shouldn't
> hope and that doesn't mean they shouldn't be frustrated when the stock
> answer is "write it in C". The fact that Ruby and other dynamic languages
> are not as fast as compiled C is not the language's fault or the user's
> fault...it's an implementation flaw. It certainly may be a flaw that can't
> be fixed, a problem impossible to solve, but there's nothing about a
> language's design that should necessitate it being slower than any other
> language. Perhaps we haven't found the right way to implement these
> languages, or perhaps some of us have and others just aren't there yet.
> Either way, it's not the language that's eventually the problem...it's
> simply the distance from what the underlying platform wants to run that's an
> issue. C is, as they put it, closer to "bare metal", but only because C is
> little more than a set of macros on top of assembly code. If the underlying
> processor ran YARV bytecodes, I doubt Ruby performance would be a concern.

I'd say "yes and no" to that.  There are things about Ruby -- things
that I absolutely would not change -- that necessitate slower runtime
execution.  For instance, for Ruby to work as specced, it needs dynamic
typing, which is simply slower in execution, because typing becomes a
part of execution.  Static typing doesn't require types to be set at
execution: they can be set at compile-time, because they don't have to
change depending on runtime conditions.  Thus, you add an extra step to
runtime execution a variable (pardon the pun) number of times.  It's an
unavoidable execution-speed loss based on how the Ruby language is
supposed to work, and it's a characteristic of Ruby that I absolutely
would not throw away for better runtime performance.  Because of this,
of course, it is effectively impossible to use persistent compiled
executables for Ruby to solve the runtime execution performance gap that
is introduced by dynamic typing as well.  C'est la vie.

Other, similar difficulties arise as well.  Ultimately, it's not the
fact that it's an interpreted language that is the problem.  That can be
solved via a number of tricks (just-in-time compilation similar to Perl,
bytecode compilation, or even simply writing a compiler for it, for
example), if that's the only problem.  The main problem is that, like
Perl, Python, and various Lisps, it's a dynamic language: it can be used
to write programs that change while they're running.  To squeeze the
same performance out of Ruby that you get out of C, you'd have to remove
its dynamic characteristics, and once you do that you don't have Ruby
any longer.
[Quoted text hidden]
Simon Kröger <SimonKroeger@gmx.de> Thu, Jul 27, 2006 at 12:17 AM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Peter Hickman wrote:
> I will run your Ruby version and the Java version that I write and post
> the results here. Give us a week or so as I have other things to be doing.

Hmm, in a week this discussion will be over (ok, it will reappear some time
soon, but nevertheless) and everybody has swallowed your points.

$ ruby -v
ruby 1.8.4 (2005-12-24) [i386-mingw32]

$ time ruby latin.rb 5 > latin.txt

real    0m4.703s
user    0m0.015s
sys     0m0.000s

(this is a 2.13GHz PentiumM, 1GB RAM, forget the user and sys timings, but
'real' is for real, this is WinXP)

My point is: If you choose the right algorithm, your program will get faster by
orders of magnitudes - spending time optimizing algorithms is better than
spending the same time recoding everything in C. In a not so distance future
(when the interpreter is better optimized or perhaps YARV sees the light of day
my version will be even faster than yours. It will be easier to maintain and
more platform independent.

Of course you can port this enhanced version to C and it will be even faster,
but if you have a limited amount of time/money to spend on optimization i would
say: go for the algorithm.

To stop at least some of the flames: I like Extensions, i like them most if
they are generally useful (and fast) like gsl, NArray, whatever. The
combination of such Extensions and optimized algorithms (written in ruby) would
be my preferred solution if i had a performance critical problem that I'm
allowed to tackle in ruby.

cheers

Simon

p.s.: and if my solution is only that fast because of a bug (i really hope
not), i think my conclusions still hold true.
Martin Ellis <me_ncl@hotmail.com> Thu, Jul 27, 2006 at 12:25 AM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Chad Perrin wrote:
> Haskell is a better choice than Java for performance:

I suspect it depends what you're doing...

> in fact, the only thing keeping
> Haskell from performing as well as C, from what I understand, is the
> current state of processor design.

I'm interested to know more about that.
Could you elaborate?  A reference would do.

Cheers
Martin
Chad Perrin <perrin@apotheon.com> Thu, Jul 27, 2006 at 12:29 AM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Thu, Jul 27, 2006 at 12:23:23AM +0900, Charles O Nutter wrote:
>
> You're mixing language semantics and implementation details here. The
> mechanics of method lookup is not a language feature; it's an implementation
> detail. On the other hand, the logic of which method gets invoked in a
> hierarchy of types is a language detail. Scoping is a language feature, but
> the means by which scope is maintained is an implementation detail.

In some ways, you're right: implementation details are being mixed up
with language definition in the preceding list of features.  In the case
of scoping, however, you're not entirely right with regard to "the means
by which scope is maintained".  Dynamic scoping, by definition, requires
runtime scoping.  Static scoping, by definition, does not.  This means
that (to use Perl as an example, since I know it better than Ruby) my(),
which is used to declare variables in lexical scope, can be managed at
compile time, while local(), which is used for dynamic scope, can only
be managed at runtime -- else it will not work as advertised.  That's
more than simply implementation details: implementation is, in this
case, dictated by language features.


>
> As for the closure comment...sure, there's overhead in creating closures,
> but it's *explicit* overhead. This is no different from creating the
> equivalent of closures in languages that don't support them. The concept of
> a closure has a clear specification and certainly increases the complexity
> of a language and an underlying implementation. But that complexity may not
> in itself always represent a decrease in performance, since other means of
> accomplishing the same task may be even less performant. That's how it is
> for any language feature...you take the good with the bad, and if you don't
> use all of the good you may be less-than-optimal. If using a feature has ten
> good aspects and five bad, and you only make use of five good aspects, then
> your code is sub-optimal. If you use less than five, you're even worse off
> and perhaps should consider doing things differently. Nothing about the
> feature itself explicitly implies that performance should degrade by using
> it...it's a matter of using those features wisely and making optimal use of
> their good aspects, balanced with their bad aspects.

I think closures are kind of a bad example for this, actually.  There's
nothing about closures that necessarily harms performance of the
language in implementation.  In fact, closures are in some respects
merely a happy accident that arises as the result of other, positive
characteristics of a language that all can tend to contribute to better
performance of the implementation of a language (such as lexical scope,
which leads to better performance than dynamic scope).  In fact, one of
the reasons Python doesn't have proper closures (lack of strict lexical
scoping) is also likely one of the reasons Python still tends to lag
behind Perl for performance purposes.

The only real overhead involved in closures, as far as I can see, is the
allocation of memory to a closure that doesn't go away until the program
exits or, in some implementations, until the program reaches a point
where it will absolutely, positively never need that closure again
(which is roughly the same thing for most uses of closures).  A little
extra memory usage does not translate directly to performance loss.  In
fact, in any halfway-decent system implementation, it really shouldn't
result in reduced performance unless you start having to swap because
you've overrun "physical RAM", I think.

The day may come when RAM is better managed so that performance gains
can be had for less memory usage, though, so I doubt this will always be
true.

--
CCD CopyWrite Chad Perrin [ http://ccd.apotheon.org ]
"A script is what you give the actors.  A program
is what you give the audience." - Larry Wall
Chad Perrin <perrin@apotheon.com> Thu, Jul 27, 2006 at 12:33 AM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Thu, Jul 27, 2006 at 12:03:50AM +0900, Dean Wampler wrote:
> On 7/26/06, benjohn@fysh.org <benjohn@fysh.org> wrote:
> >...
> >
> >People talk about the 80:20 principle, but in my experience it's much
> >more like 99:1 for applications. 99% of the code uses 1% of the run
> >time. 1% of the code consumes 99% of the run time. That could be the
> >signal processing and graphics heavy applications that I have
> >experienced though.
> >...
>
> This is the "value proposition" of the "Hot Spot" technology in the
> Java Virtual Machine. On the fly, it looks for byte code sections that
> get executed repeatedly and it then compiles them to object code,
> thereby doing runtime optimization. This allows many Java server
> processes to run with near-native speeds. When Ruby runs on a virtual
> machine, planned for version 2, then Ruby can do that too. The JRuby
> project will effectively accomplish the same goal.

This recent mania for VMs is irksome to me.  The same benefits can be
had from a JIT compiler, without the attendant downsides of a VM (such
as greater persistent memory usage, et cetera).

--
CCD CopyWrite Chad Perrin [ http://ccd.apotheon.org ]
"The measure on a man's real character is what he would do
if he knew he would never be found out." - Thomas McCauley
Chad Perrin <perrin@apotheon.com> Thu, Jul 27, 2006 at 12:49 AM
Reply-To: ruby-talk@ruby-lang.org
To: ruby-talk ML <ruby-talk@ruby-lang.org>
On Thu, Jul 27, 2006 at 03:55:10AM +0900, Martin Ellis wrote:
> Chad Perrin wrote:
> > Haskell is a better choice than Java for performance:
>
> I suspect it depends what you're doing...

To clarify: I meant "on average" or "in general".  Obviously, there will
be instances where Java will outperform Haskell or, for that matter,
even C -- just as there are times Perl can outperform C, for an
equivalent amount of invested programmer time, et cetera.  I suspect the
same is true even of Ruby, despite its comparatively crappy execution
speed.  That doesn't change the fact that in the majority of cases,
Haskell will outperform most other languages.  It is, after all, the C
of functional programming.

>
> > in fact, the only thing keeping
> > Haskell from performing as well as C, from what I understand, is the
> > current state of processor design.
>
> I'm interested to know more about that.
> Could you elaborate?  A reference would do.

I'm having difficulty finding citations for this that actually explain
anything, but the short and sloppy version is as follows:

Because imperative style programming had "won" the programming paradigm
battle back in the antediluvian days of programming, processors have
over time been oriented more and more toward efficient execution of code
written in that style.  When a new processor design and a new
instruction set for a processor is shown to be more efficient in code
execution, it is more efficient because it has been better architected
for the software that will run on it, to better handle the instructions
that will be given to it with alacrity.  Since almost all programs
written today are written in imperative, rather than functional, style,
this means that processors are optimized for execution of imperative
code (or, more specifically, execution of binaries that are compiled
from imperative code).

As a result, functional programming languages operate at a slight
compilation efficiency disadvantage -- a disadvantage that has been
growing for decades.  There are off-hand remarks all over the web about
how functional programming languages supposedly do not compile as
efficiently as imperative programming languages, but these statements
only tell part of the story: the full tale is that functional
programming languages do not compile as efficiently on processors
optimized for imperative-style programming.

We are likely heading into an era where that will be less strictly the
case, however, and functional languages will be able to start catching
up, performance-wise.  Newer programming languages are beginning to get
further from their imperative roots, incorporating more chara