The real lesson is: Achieving good performance is hard; it requires
analysis and experimentation, and any simple prescription (e.g. “Use
programming language X”) is dangerously misleading.
And finally: In the real world, the only benchmark that matters is your
application.
-Tim
I’ll accept your real lesson, and add one more
Although “out of the box thinking” is a sickening cliche, our thinking
does often get stuck in box. In this case, we’re stuck in a box
exhaustively generating latin squares.
Once we loosen some constraints and push back the problem boundaries,
maybe we’ll see that there are so many latin squares for 9x9 that they
might as well be infinite.
Maybe we’ll remember that we have techniques for dealing with infinite
sequences - lazy evaluation, streams, generators… let’s assume that
we have a 9x9 lazy latin square generator that we can pause and resume.
Then the interesting question is how do we write generators that
produce different traversals - random traversal, lexicographic
traversal, …
Now the performance question has changed - are the latin squares
streams being consumed faster than the squares are generated, or is the
bottleneck somewhere else?
Man, that “out of the box thinking” is scary stuff !
That all the implementations had to use the same Perl pre compute phase.
That was just the way I did mine and I think that people have taken it
as read that this is a requirement. Despite the Ruby Ocaml and C++
versions not doing this.
Now I’m puzzled - isn’t that just conventional wisdom? Isn’t it
conventional wisdom that a program transformed by an optimizing
compiler will be faster than a program interpreted at runtime?
It’s the degree of speed up that I felt that people are overlooking,
lets take the following:
Ruby 10.060 (user + sys)
C 3.350
Ocaml 2.558
C doesn’t just shave a few percentage points off, you get a massive
boost without having to do anything weird. C seems to be /too hard/ for
many people, especially people who have never used it.
However Ocaml is an eye opener.
The only requirement is that I can get an implementation of the language
in question on my Macintosh.
D and Clean are other languages you might look at, but using a
different language won’t make what you’re trying to do any more
feasible.
True, but as I’ve said before C is a fragile language to work in if
you’ve come from a scripting background. A program will compile and then
crash with not the slightest hint at what went wrong, so any language
that will allow me to get that sort of performance with a better support
is a good thing. I will be learning Ocaml for this reason alone.
The conclusion of this lengthy and interesting thread is obvious: the
original claim, “For performance, write it in C”, has been convincingly
debunked.
Along with all the other conventional wisdom about premature
optimization and profiling and 80/20 points, we have seen it
demonstrated that several other languages, of many different types, can
come so close to C’s performance that it’s difficult to measure the
difference.
The real lesson is: Achieving good performance is hard; it requires
analysis and experimentation, and any simple prescription (e.g. “Use
programming language X”) is dangerously misleading.
And finally: In the real world, the only benchmark that matters is your
application.
I can’t seem to run the Perl or Ruby out of the box: how do I get the extra
packages that I need?
For my and Simon Kroegers version you need the permutation.rb file,
which
you can install with rubygems, or extract it from the sourcepackage at http://permutation.rubyforge.org/ (which I did). Perhaps it would be
better to include the permutation.rb file on the webpage?
D and Clean are other languages you might look at, but using a
different language won’t make what you’re trying to do any more
feasible.
True,
Even for such a simple task, the ability to use sophisticated data
structures, higher-order functions and other constructs can make a
solution
practically feasible in some languages and infeasible in others.
Simulated annealing solution to the travelling salesman problem is
another
seemingly simple task that benefits enormously from high-level
constructs.
The naive Fortran code given in Numerical Recipies (the de-facto
standard
monologue) has an O(n) bottleneck that can be trivially reduced to
O(sqrt
N) using closures or O(ln n) using balanced trees, neither of which are
feasible in C/Fortran for most science students.
but as I’ve said before C is a fragile language to work in if
you’ve come from a scripting background. A program will compile and then
crash with not the slightest hint at what went wrong, so any language
that will allow me to get that sort of performance with a better support
is a good thing. I will be learning Ocaml for this reason alone.
Absolutely, C is a systems programming language. People are abusing it
when
they advocate it for tasks like this. C++ is slightly better but, as
I’ve
shown, you’ve lost the performance advantage that you thought you had
once
you start using its features. OCaml’s great. It’s succinct, safe and
fast.
The main downside is probably that you have to get to grips with its
type
system.
On Tue, 08 Aug 2006 09:56:53 -0700, Isaac G. wrote:
Will OCaml make the task of exhaustively generating 9x9 latin squares
feasible?
And could anyone actually say what is the purpose of generating all
this data?
afaik it’s intended to be a training-set for a program to evolve rules
for solving Sudoku puzzles.
Peter?
Makes me think the program could be fed one latin square at a time -
which sure beats waiting thousands of years to generate all the latin
squares for 9x9.
This is just a note to clarify things in my mind and then ask a
few questions about the language.
Here’s what I think I know:
– The current version of Ruby is 1.8.5.
– There is a 1.9 out there, but it’s a work in progress and not
released
yet.
– There is a 2.0 (YARV) out there, but it’s also a work in progress.
– 1.8.5, 1.9, and 2.0 all support slightly different languages.
– 1.9 is the place where most language experimentation is going on
– 2.0 will support the same language as 1.8, but with a different
underlying
implementation.
– There is no formal language specification (and most of us are working
off
the pickaxe book)
Here’s what I don’t know:
– Is any of the above wrong?
– Are there estimated release dates for 1.9 and 2.0?
– Are there places where changes to the language between 1.8.5, 1.9,
and 2.0
are listed (note: http://wiki.rubygarden.org/Ruby/page/show/Rite
doesn’t
really count) ?
– 2.0 will support the same language as 1.8, but with a different
underlying implementation.
Wrong, AFAIK.
The 1.9 (experimental) would once became 2.0 (stable).
The language WOULD be differ from 1.8, hence the major version.
Doesn’t Ruby version numbering follow the same general scheme as the
Linux kernel?
Version Major.Minor[.sub-version]
Versions with even minor numbers are considered the stable “production”
branch.
Versions with odd minor numbers are considered experimental where
features which might produce incompatibilities and breakage are added,
tried out, and perhaps removed before becoming part of the
specification if not the implementation of the next stable branch.
features which might produce incompatibilities and breakage are added,
tried out, and perhaps removed before becoming part of the
specification if not the implementation of the next stable branch.
Or do I have it wrong?
In general yes, although it seems Matz is considering a production
1.9 release.
I thought that he was joking when he said that the version after 1.9.9
would be 1.9.a.
Now I wouldn’t be surprised if 2.0 weren’t just a tagged version of a
1.9.x release (which is what I meant above by “if not the
implementation of,” but I would be surprised if there was a production
1.9.x release so-named.
Versions with odd minor numbers are considered experimental where
would be 1.9.a.
Now I wouldn’t be surprised if 2.0 weren’t just a tagged version of a
1.9.x release (which is what I meant above by “if not the
implementation of,” but I would be surprised if there was a production
1.9.x release so-named.
