Benchmarking

[Alpar Juttner]

Lemon seriously needs a benchmarking environment to test

• the effect of implementation changes on the running time
• performance of different compilers ans optimization settings

This environment should contain

• scripts for automated testing.
• carefully chosen set test files and graph generators.

[Peter Kovacs]

The test file in #309 could be a small step for this task.

[Alpar Juttner]

Peter has put together a repository consisting a couple of benchmarks. Currently, it can be found here at ​http://lime.cs.elte.hu/~kpeter/hgwebdir.cgi/lemon-benchmark/

[Alpar Juttner]

Replying to alpar:

Peter has put together a repository consisting a couple of benchmarks. Currently, it can be found here at ​http://lime.cs.elte.hu/~kpeter/hgwebdir.cgi/lemon-benchmark/

Some comments on this repo.

• It would be important to apply a rule that a test code will never be changed, once it has been settled down. This will however result in a lot of scripts in the long run, thus we need some naming convention on the executables and/or some directory hierarchy.
• For the sake of post processing, the output of the tests should also be standardized. My suggestion is that
  • a test prog can write arbitraty informative msg to stdout, but
  • the real measurements must be printed in a special format that makes it easy to filter them out and interpret. I would suggest a whitespace separated triplet of
    • a prefix, say ***,
    • a label identifying the measurement like ListDigraph-ArcIt and
    • the measured amount itself.

Instead of a single label we might also allow several sublabels, like itertest ListDigraph ArcIt.

• The scripts making the reports should be platform independent (i.e. should work on Win, too), thus probably to be written in Python. It is a good idea to allow executing them from the build system (i.e. e.g. make test-flows)

[Peter Kovacs]

Replying to alpar:

Some comments on this repo.

I agree all your comments. The current version of this repository is far from a good state. I just collected some of my benchmark codes, and I wait for a volunteer to improve the repository. :)

[Alpar Juttner]

Please find a tentative benchmarking framework here:

http://lemon.cs.elte.hu/hg/lemon-benchmark/

It is based on our project template, thus it is possible to build the same source with different lemon versions parallel by setting the LEMON_SOURCE_ROOT_DIR cmake variable like this:

$ hg clone http://lemon.cs.elte.hu/hg/lemon-benchmark/
$ cd lemon-benchmark
$ hg clone http://lemon.cs.elte.hu/hg/lemon-main lemon
$ mkdir build;cd build
$ cmake ..; make
$ cd ..
$ hg clone [...]/mylemon mylemon
$ mkdir build-my;cd build-my
$ cmake -DLEMON_SOURCE_ROOT_DIR=../mylemon ..; make

The directory layout is the following:

• generators/ It contains the source codes that generates input files for the algorithm. Currently only netgen is ported, but other generator are more than welcome.
• data/ The CMakeLists.txt generates the input files. Currently, there is one make target called net-data that generates one DIMACS min cost flow instance called net.net

  $ make net-data
  

• tests/ The actual benchmark codes takes place here. Currently, there is one benchmark code called circulation.cc. In addition there are some utilities here, e.g.
  • benchmark_tools.h contains utility functions for unified run time logging
  • file_main.cc factors out the main() function of benchmark programs that works on a file input. Look at circulation.cc and CMakeLists.txt to see how is works.

The convention for the benchmark codes is that they can write anything to stdout but the actual running time measurements must be in separate lines containing the following fields separated by single spaces.

*** test-name instance-name subtest-name runtime ...

• test-name This refers the name of the test code
• instance-name This is the instance the benchmark code is running on. E.g. the name of the input file of some graph size given as a command line parameter.
• subtest-name A benchmark code may measure more than one things at once. This name identifies those particular measurements
• runtime The (wall clock) running time in seconds.
• ... Other fields are allowed at the and of the line. For example logTime() function for benchmark_tools.h prints the value of realtime/(usertime+systime)-1.0. This value indicated the accuracy of the measurement in some sence.

Is is recommended to use logTime() for printing time reports.

Many-many things to be done, of course. A quick TODO list:

• Port more input file generators.
• Add more test. This is the most important thing, of course.
• Scripts that execute the benchmarks (with different compilers and/or lemon versions) and evaluate the results.
• Ability to switch off the compilation of benchmark codes that are not available using a certain version of LEMON.

Any feedback is very welcome. Contributions are even more welcome :)

[Alpar Juttner]

I added one more field to the running time log lines:

*** build-name test-name instance-name subtest-name runtime ...

Here, build-name refers to the build which is actually running. Using logTime(), it defaults to the last component of the build directory (i.e. build or build-my in the examples above), but it can be overwritten by the CMAKE variable BENCHMARK_BUILD_ID.