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;

   http://rubyforge.org/projects/rubyinline

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

*snip*

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.

Pete

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

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

$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)

thanks

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!

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

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.

Cheers,

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.

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

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.

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