Neto's Laws of Algorithmic Experimentation

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 Experimentation, 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 my name 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

Part 2: Coding

1. Use deterministic algorithms where possible. This helps you find bugs in your code because execution paths are repeatable.
2. 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.
3. 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 -Wstrict-prototypes -Wmissing-prototypes . The prototype 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.)
4. If you must use randomization:
   • Use a portable pseudo-random number generator 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.
5. Beware of qsort:
   • Don't trust qsort to behave the same way in two different environments. 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.
   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.

   If the last is a problem, then code your own sorting function. I very strongly suggest 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.

6. Once you're finished coding, search the literature again. Things may have changed.

Part 3: Experimenting

1. 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.
2. 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 this way:

   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.

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

4. 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.
5. Try to imagine worst-case inputs for your program. Try them out. Include them in your source code if possible. Literate programming tools like CWEB 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

1. Make sure your audience can, in principle, repeat your experiments. One way to do this is to give your code away. :)
   
2. Tell your audience what your data was like. For the TSP, you should at least include instances from TSPLIB.
3. Report the results on your worst-case inputs. How bad are they? Why?
4. How do your results fit in with the work of others?
5. How one might build on this work?