Peter Hickman
7/26/2006 8:47:00 AM
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".