Linked List Traversal Micro-Benchmark

A short note that I've written, entitled Benchmark Health Considered Harmful, demonstrates that the program health is flawed and not suitable for use as a benchmark. It is dominated by an enormous linked list traversal. If it is necessary to demonstrate the behavior of such code, it is preferable to use a micro-benchmark, like llubenchmark.c, so it is clear to readers what the program-under-test is doing.

llubenchmark.c is configurable. The comment at the beginning of the file discribes its configuration:

/*
 * The benchmark executes for a proscribed number of iterations (-i),
 * and on every iteration the lists are traversed and potentially
 * extended.  The number of lists can be specified (-n) as well as the
 * size of the elements in the list (-s).  The initial length of the
 * lists can be set (-l) as well as the growth rate (-g).  The growth
 * rate must be non-negative, but can be a floating point number, in
 * which case random numbers are used to determine whether a list is
 * extended on a particular cycle (all lists are extended
 * independently).  If the -t option is specified, the insertion
 * occurs at the tail, otherwise at the head.  If the -d option is
 * specified, the elements are dirtied during the traversal (which
 * will necessitate a write-back when the data is evicted from the
 * cache).
 * 
 * To approximate the non-benchmark Health, use the options:
 *     -i  -g .333 -d -t -n 341
 * 
 * (the growth rate of the lists in health is different for different
 * levels of the hierarchy and the constant .333 is just my approximation
 * of the growth rate).
 */

Craig Zilles / zilles@cs.uiuc.edu
Last updated January 3rd 2001.