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".
