Neto's Laws of Algorithmic Experimentation
Updated January 22, 1998:
(January 22, 1998): New edition of -WGeoffrey set of recommended GCC flags
(December 1, 1997): Discuss new edition of Volume 2 of
Knuth's TAOCP, especially in
relation to random number generators.
Added (June 26, 1997): Added comment about worst-case
inputs and how CWEB can help
New (April 2, 1997): Added proper homage
to David Johnson's working
paper and to the Journal of Experimental Algorithmics.
Added IRIX to the list of environments my program runs under.
New (August 20, 1996): Trust optimizers, and
New (August 14, 1996): Warn about optimizers
As part of my research, I experiment with the
Lin-Kernighan algorithm for the Traveling
Salesman Prblem (TSP).
From this work I've formulated Neto's Laws of Algorithmic
for lack of a better name.
It should be applicable to more than just the TSP.
This page was inspired by, and is complementary to, David Johnson's working
paper A Theoretician's Guide to the Experimental
Analysis of Algorithms. His paper is available from his
personal web page.
(Because I'm a student, I can afford to be a bit more pompous. So I've put
in the title of this page.)
I'm just in awe of the new Journal of
Experimental Algorithmics. But be warned: you may have to be an ACM
member to access the articles (and code). If you do download an
article, your member account with the ACM will be charged a prorated
amount from that date. (For example, if you download an article on
April 1, your accout is charged for 9/12 of the annual subscription fee, since
April 1 is the beginning of the fourth month of the year.)
However, they also have institutional subscriptions, authenticated
by IP address. Go figure.
Part 1: Searching the literature
Do it thoroughly. Do it again. Then do it one more time.
Part 2: Coding
- Use deterministic algorithms where possible. This helps you find
bugs in your code because execution paths are repeatable.
- Write portable code. You will eventually move to a new environment.
Right now, my program works in all the environments I've tried it under:
Linux, AIX, IRIX, and SunOS. Then again, it's tackles a vanilla problem.
- Write clean code; use -ansi -pedantic under GCC.
Your path will be made flat, straight, and short this way.
A friend recommends adding
-Wall -W -Wundef -Wshadow -Wpointer-arith
-Wbad-function-cast -Wcast-qual -Wcast-align -Wwrite-strings -Wconversion
options aren't as useful on systems with bad header files.
(This list of warning options has been updated for GCC 2.8.0, now that
GNU has removed some options from -Wall.)
- If you must use randomization:
- Use a portable pseudo-random number
that someone else has written. (Donald Knuth is excepted
from the latter half of this law.) A good one can be
found in Knuth's Stanford GraphBase.
- Add a command-line switch to allow the user (you,
most likely) to specify the seed.
- Knuth has just published (fall 1997) the third edition of Volume 2 of
The Art of Computer Programming. Volume 2 contains Chapter 3, Random
Numbers. The new edition makes new recommendations for using pseudo-random
number generators, and even some C code. In particular, he recommends
using several different generators (not just different seeds) to confirm
experimental results. In that spirit, the generator provided
in C code
in that book is different
from the generator provided in C(WEB) code in the Stanford Graphbase.
- Beware of qsort:
A fix for the first two of these
is to provide
a comparison function that
is as picky as possible:
if it would have ordinarily returned 0,
make it return the pointer difference of its two parameters.
- Don't trust qsort to behave the same way in two different
My supposedly deterministic program was returning different
answers on different platforms. The only external code I was calling
(besides debugging I/O) was qsort.
- Don't expect qsort to be stable. It makes no such promise:
elements that compare equal may be arbitrarily reordered in the output.
- Don't expect qsort to be deterministic. God only knows what
shenangans are used behind the scenes to pick the pivot.
If the last is a problem, then code your own sorting function.
that you look at ``Engineering a Sort Function'',
by Jon Bentley and Douglas McIlroy, Software---Practice and
Experience, Vol 23(11), 1249--1265, November 1993.
- Once you're finished coding, search the literature again. Things may
Part 3: Experimenting
- Don't time a single run. Time at least five runs. Not only will you
have more confidence in the consistency of your program, but you might
catch bugs this way.
- Don't trust the optimizer, part 1. Some optimizers in compilers
are buggy, i.e.
produce incorrect code. The AIX 4.1 cc manual page puts it
The -O3 specific optimizations have the potential to
alter the semantics of a user's program.
This is a Bad Thing(tm).
Potentially, any program might be converted to the ``Hello world!'' program.
Use the -qstrict option to turn off
those semantics-altering optimizations.
Compile both with and without optimization, just to make sure.
Check your result with a different compiler if possible.
Check your result on a different architecture.
- Don't trust the optimizer, part 2.
Turning optimization on sometimes slows down your program.
This can happen for many reasons. For instance, the optimizer might
make your code larger, so the instruction cache isn't as useful.
(Thanks to Wayne Hayes
for reminding me of this.)
On some inputs, my program runs 5 to 8 times slower
when optimization is turned on.
- Trust the optimizer.
Some compilers will produce some warnings only when optimization is
turned on. For example, GCC does dataflow analysis only when its
optimizer is turned on. This analysis detects unused variables and
variables which might be used without initialization. I've detected
a couple of bugs this way and no other way.
- Try to imagine worst-case inputs for your program. Try them out.
Include them in your source code if possible. Literate programming tools
let you generate multiple source files from the same document.
A test program for the module defined in that document can
be one of them. (This is called ``unit testing'', and how I find
most of my bugs.)
Part 4: Reporting your results
- Make sure your audience can, in principle, repeat your experiments.
One way to do this is to give your code away. :)
- Tell your audience what your data was like. For the TSP, you should
at least include instances from
- Report the results on your worst-case inputs. How bad are they? Why?
- How do your results fit in with the work of others?
- How one might build on this work?
Back to David Neto's home page