It is easier to optimize correct code than to correct optimized code.
--Bill Harlan
One natural question (and one that is indeed asked increasingly often) is how does the efficiency of the Parma Polyhedra Library compare with that of other polyhedra libraries. Of course, such a question does not have a definite answer. Apart from clarifying whether CPU or memory efficiency or both are the intended measures of interest, the answer will depend on the applications one is interested in: with different applications the results can vary wildly. Moreover, even within the same application, big variations may be observed for different inputs.
Caveat emptor: For all the above reasons, the only sensible piece of advice we can offer is: if you really care about performance, measure the performance of your application with the biggest variety of inputs you can come up with. Then choose the library that gives you the best results for your definition of "best result".
Having said all that, it is nonetheless instructive to compare the performance of various polyhedra libraries on a well-defined problem with a large set of freely available inputs. One such problem, called vertex/facet enumeration, is already directly supported by the libraries PPL, New Polka, PolyLib, cddlib, lrslib and by the pd program. Both cddlib and lrslib come with driver programs that support a polyhedra input format that was introduced by Komei Fukuda (the author of cddlib) and extended by David Avis (the author of lrslib); this input format is also supported by the pd program (written by Ambros Marzetta and now maintained by David Bremner). The distributions of lrslib and cddlib (both under the GPL) provide more than 70 different inputs of varying complexity for these programs. What was missing until recently were driver programs that could read the same input format and use the PPL, New Polka and PolyLib. Such a program now exists, and it is called ppl_lcdd. An initial version supporting the PPL only was released with version 0.6, whereas PPL 0.7 contains a version supporting also New Polka and PolyLib.
Here are the results we obtained with the following setting:
- PPL Git HEAD version of January 24, 2005;
- New Polka version 2.0.2;
- PolyLib version 5.20.0;
- cddlib version 0.93c;
- lrslib version 0.42;
- pd version 1.7;
- tests run on a PC equipped with an AMD Athlon 2800+ with 1 GB of RAM and running GNU/Linux;
- all the software compiled with GCC 3.4.2 at the optimization level that is the default for each package (for instance, the PPL was compiled with `-O2', its default; New Polka was compiled with `-O3' that is the default in the considered distribution; similarly, PolyLib was compiled with `-O2').
Notice that the timing for lrslib concerning all the tests named *.ine are set in italic. This is meant to recall that lrslib solves a different, easier problem than the one solved by the other libraries: vertex enumeration without minimization (at least this is what we understand by the sentence inserted by the lrs driver in the output: "Note! Duplicate rays may be present"). Since a similar sentence is not present in the benchmarks involving the facet enumeration problem, we guess minimization is guaranteed in these cases. Notice also the asterisks in the pd's column: these mark the problems that cannot be solved by pd, which can only handle polyhedra that contain the origin.
| Problem | PPL | Polka | PolyLib | cddlib | lrslib | pd |
| ccc4.ext | 0.00 | 0.00 | 0.03 | 0.01 | 0.00 | * |
| ccc5.ext | 0.00 | 0.00 | 0.04 | 0.02 | 0.00 | * |
| ccc6.ext | 0.02 | 0.02 | 0.26 | 0.79 | 3.17 | * |
| ccp4.ext | 0.00 | 0.00 | 0.03 | 0.01 | 0.00 | 0.00 |
| ccp5.ext | 0.00 | 0.00 | 0.04 | 0.03 | 0.00 | 5.28 |
| ccp6.ext | 0.05 | 0.04 | 0.29 | 1.15 | 4.04 | >1h |
| cp4.ext | 0.00 | 0.00 | 0.03 | 0.01 | 0.00 | 0.01 |
| cp5.ext | 0.00 | 0.00 | 0.05 | 0.03 | 0.00 | 5.34 |
| cp6.ext | 0.05 | 0.04 | 0.29 | 1.14 | 4.07 | >1h |
| cube.ext | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | 0.00 |
| cut16_11.ext | 0.00 | 0.00 | 0.04 | 0.03 | 0.00 | 3.58 |
| cut32_16.ext | 0.05 | 0.04 | 0.30 | 1.15 | 4.46 | >1h |
| cyclic10-4.ext | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | 0.01 |
| cyclic12-6.ext | 0.00 | 0.00 | 0.02 | 0.02 | 0.00 | 0.44 |
| cyclic14-8.ext | 0.00 | 0.00 | 0.04 | 0.08 | 0.01 | 172.11 |
| cyclic16-10.ext | 0.02 | 0.02 | 0.06 | 0.30 | 0.03 | >1h |
| dcube10.ext | 0.01 | 0.01 | 0.08 | 0.31 | 0.02 | >1h |
| dcube12.ext | 0.13 | 0.13 | 2.61 | 1.67 | 0.12 | >1h |
| dcube3.ext | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | 0.00 |
| dcube6.ext | 0.00 | 0.00 | 0.03 | 0.01 | 0.00 | 0.36 |
| dcube8.ext | 0.00 | 0.00 | 0.04 | 0.06 | 0.00 | 118.46 |
| irbox20-4.ext | 0.00 | 0.00 | 0.02 | 0.02 | 0.00 | 0.02 |
| irbox200-4.ext | 0.02 | 0.03 | 0.03 | 1.26 | 0.05 | 0.21 |
| mp5.ext | 0.00 | 0.00 | 0.05 | 0.77 | 0.91 | 4.16 |
| redcheck.ext | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | 0.00 |
| reg24-5.ext | 0.00 | 0.00 | 0.02 | 0.02 | 0.00 | 0.02 |
| reg600-5_m.ext | 5.15 | 16.96 | 12.47 | 160.58 | 31.38 | * |
| samplev1.ext | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | * |
| samplev2.ext | 0.00 | 0.00 | 0.02 | 0.01 | 0.00 | * |
| samplev3.ext | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | * |
| tsp5.ext | 0.00 | 0.00 | 0.04 | 0.01 | 0.00 | * |
| 1d.ine | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | * |
| 1da.ine | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | * |
| allzero.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | * |
| cp4.ine | 0.00 | 0.00 | 0.02 | 0.01 | 0.00 | * |
| cp5.ine | 0.01 | 0.01 | 0.05 | 0.18 | 5.99 | * |
| cross10.ine | 0.04 | 0.06 | 0.13 | 12.16 | >1h | 1.32 |
| cross12.ine | 0.62 | 2.88 | 3.04 | 216.91 | >1h | 14.80 |
| cross4.ine | 0.00 | 0.00 | 0.02 | 0.01 | 0.01 | 0.00 |
| cross6.ine | 0.00 | 0.00 | 0.03 | 0.05 | 0.11 | 0.01 |
| cross8.ine | 0.00 | 0.00 | 0.04 | 0.71 | 29.87 | 0.13 |
| cube.ine | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | 0.00 |
| cube10.ine | 0.01 | 0.01 | 0.15 | 0.33 | 0.04 | >1h |
| cube12.ine | 0.14 | 0.13 | 3.92 | 1.76 | 0.19 | >1h |
| cube3.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | 0.00 |
| cube6.ine | 0.00 | 0.00 | 0.03 | 0.01 | 0.01 | 0.36 |
| cube8.ine | 0.00 | 0.00 | 0.04 | 0.06 | 0.00 | 122.40 |
| cubetop.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.01 | * |
| cubocta.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | 0.00 |
| cyc.ine | 0.00 | 0.00 | 0.02 | 0.01 | 0.00 | 0.00 |
| cyclic17_8.ine | 0.04 | 0.05 | 0.13 | 0.42 | 0.09 | >1h |
| diamond.ine | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | 0.00 |
| dodeca_m.ine | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | * |
| ex1.ine | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | * |
| grcubocta.ine | 0.00 | 0.00 | 0.02 | 0.01 | 0.00 | 0.01 |
| hexocta.ine | 0.00 | 0.00 | 0.01 | 0.04 | 0.00 | 0.01 |
| icododeca_m.ine | 0.00 | 0.01 | 0.03 | 0.08 | 0.00 | * |
| in0.ine | 0.00 | 0.00 | 0.03 | 0.00 | 0.00 | * |
| in1.ine | 0.00 | 0.00 | 0.03 | 0.02 | 0.00 | * |
| in2.ine | 0.00 | 0.00 | 0.02 | 0.01 | 0.00 | * |
| in3.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | * |
| in4.ine | 0.00 | 0.00 | 0.03 | 0.02 | 0.00 | * |
| in5.ine | 0.00 | 0.00 | 0.05 | 0.04 | 0.00 | * |
| in6.ine | 0.01 | 0.02 | 0.09 | 0.56 | 0.04 | * |
| in7.ine | 0.18 | 0.29 | 0.45 | 1.23 | 0.09 | * |
| infeas.ine | 0.00 | 0.00 | 0.03 | 0.01 | 0.00 | * |
| integralpoints.ine | 0.00 | 0.00 | 0.04 | 0.07 | 0.00 | * |
| kkd18_4.ine | 0.00 | 0.00 | 0.02 | 0.02 | 0.00 | * |
| kkd27_5.ine | 0.05 | 0.06 | 0.07 | 0.10 | 0.01 | * |
| kkd38_6.ine | 3.30 | 6.98 | 1.59 | 0.38 | 0.06 | * |
| kq20_11_m.ine | 0.19 | 0.29 | 0.44 | 1.19 | 0.08 | * |
| metric40_11.ine | 0.00 | 0.00 | 0.04 | 0.09 | 0.55 | * |
| metric80_16.ine | 0.13 | 0.11 | 0.06 | 0.68 | 30.84 | * |
| mit31-20.ine | 35.68 | 28.24 | 121.33 | 110.64 | 25.11 | >1h |
| mp5.ine | 0.00 | 0.00 | 0.04 | 0.08 | 0.55 | * |
| mp5a.ine | 0.00 | 0.00 | 0.05 | 0.08 | 0.59 | * |
| mp6.ine | 0.37 | 0.30 | 0.76 | 6.03 | 1148.84 | * |
| nonfull.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | * |
| origin.ine | 0.00 | 0.00 | 0.03 | 0.00 | 0.00 | * |
| project1_m.ine | 0.00 | 0.00 | 0.03 | 0.04 | 0.01 | 1.04 |
| project1res.ine | 0.00 | 0.00 | 0.02 | 0.01 | 0.00 | 0.01 |
| project2_m.ine | 0.02 | 0.02 | 0.05 | 0.59 | 0.14 | * |
| project2res.ine | 0.00 | 0.00 | 0.02 | 0.11 | 0.01 | * |
| rcubocta.ine | 0.00 | 0.00 | 0.01 | 0.01 | 0.00 | 0.00 |
| reg24-5.ine | 0.00 | 0.00 | 0.02 | 0.02 | 0.00 | 0.01 |
| rhomtria_m.ine | 0.00 | 0.00 | 0.02 | 0.06 | 0.01 | * |
| sample.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | 0.00 |
| sampleh1.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | * |
| sampleh2.ine | 0.00 | 0.00 | 0.01 | 0.01 | 0.00 | * |
| sampleh3.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | * |
| sampleh4.ine | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | * |
| sampleh5.ine | 0.00 | 0.00 | 0.01 | 0.01 | 0.00 | * |
| sampleh6.ine | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | * |
| sampleh7.ine | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | * |
| sampleh8.ine | 68.44 | 75.89 | 84.11 | >1h | 4.52 | * |
| trunc10.ine | 9.98 | 8.79 | 0.07 | 2.30 | 8.81 | 809.23 |
| trunc7.ine | 0.03 | 0.02 | 0.04 | 0.17 | 0.18 | 19.68 |
| tsp5.ine | 0.00 | 0.00 | 0.04 | 0.02 | 0.01 | * |
| Total | 124.74 | 141.45 | 234.64 |