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 more humility
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 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

Do it thoroughly. Do it again. Then do it one more time.

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:
  5. 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.

    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?

Back to David Neto's home page