From: ara.t.howard@...
Date: 2006-07-27T01:39:29+09:00
Subject: Re: For performance, write it in C

On Wed, 26 Jul 2006, 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).
>
> 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.

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