[PPL-devel] PPL beats cddlib (on one of its toughest tests).
Enea Zaffanella
zaffanella.enea at tiscali.it
Wed Jul 7 18:30:10 CEST 2004
Hi all.
I was wondering how the conversion algorithm of the PPL compares with
other, freely available conversion algorithms and I decided to try doing
some little experiments with the library cdd by Fukuda.
Since the very first result is somehow surprising, I am attaching all
the details needed to repeat my experiment (so as to obtain a
confirmation or point out any gross error I may have made).
I downloaded cddlib-0.93a (which seems to be the latest release),
configured and build it, using default settings, i.e.,
[zaffanella at spark cddlib-093a]$ ./configure
[...]
[zaffanella at spark cddlib-093a]$ make
[...]
I had a look to the manual and the examples and I found that the
(seemingly) toughest of the examples related to converting a constraint
system into a generator system is examples/sampleh8.ine.
This can be run in two ways: the program
cddlib-0.93a/src/scdd
will compute the dual representation by using floating point
arithmetics, whereas the program
cddlib-0.93a/src-gmp/scdd_gmp
will perform the same computation, but using the library GMP.
I said: let's see how the PPL compares with cddlib on this example.
However, the example was too big (I mean, for my patience, not for the
library) so I decided to throw away half of the constraints
(i.e., I only considered the first 50 of all the 100 constraints):
see the attached input file "sampleh8-half.ine".
As for the PPL, I downloaded version 0.5 (the latest release) and I
configured and build it as follows.
[zaffanella at spark ppl-vs-cdd]$ ../ppl-0.5/configure
--disable-asseretions --disable-debugging --enable-optimization=sspeed
--prefix=/tmp/opt3/ppl-0.5
[...]
[zaffanella at spark ppl-vs-cdd]$ make install
[...]
I produced the PPL version of the input file:
see the attached file "ppl-sampleh8-half.dat", to be read in by the
low-level input method ascii_load(). Note that I was careful to also add
the positivity constraint, so that in the case of the PPL we do have 51
constraints instead of 50.
I then built the test program (see "ppl-scdd-gmp.cc") as follows:
[zaffanella at spark ppl-vs-cdd]$ export
LD_LIBRARY_PATH=/tmp/opt3/ppl-0.5/lib:$LD_LIBRARY_PATH
[zaffanella at spark ppl-vs-cdd]$ g++ -W -Wall -I /tmp/opt3/ppl-0.5/include
-L /tmp/opt3/ppl-0.5/lib -lppl -lgmpxx -lgmp ppl-scdd-gmp.cc -o ppl-scdd-gmp
I ran the test and obtained the following.
===============================
WHEN USING THE PPL
[zaffanella at spark ppl-vs-cdd]$ time ppl-scdd-gmp
real 0m21.481s
user 0m21.250s
sys 0m0.060s
=========================================
WHEN USING CDDLIB (the version using GMP)
[zaffanella at spark ppl-vs-cdd]$ time ../cddlib-093a/src-gmp/scdd_gmp
sampleh8-half.ine
input file sampleh8-half.ine is open
size = 50 x 10
Number Type = integer
(Initially added rows ) = 16 17 19 20 34 39 44 46 47 49
(Iter, Row, #Total, #Curr, #Feas)= 11 22 35 30 0
(Iter, Row, #Total, #Curr, #Feas)= 12 35 75 62 0
(Iter, Row, #Total, #Curr, #Feas)= 13 21 162 124 0
(Iter, Row, #Total, #Curr, #Feas)= 14 23 301 210 0
(Iter, Row, #Total, #Curr, #Feas)= 15 12 497 340 0
(Iter, Row, #Total, #Curr, #Feas)= 16 15 791 510 0
(Iter, Row, #Total, #Curr, #Feas)= 17 28 1208 712 0
(Iter, Row, #Total, #Curr, #Feas)= 18 43 1658 942 0
(Iter, Row, #Total, #Curr, #Feas)= 19 33 2346 1192 0
(Iter, Row, #Total, #Curr, #Feas)= 20 38 3054 1498 0
(Iter, Row, #Total, #Curr, #Feas)= 21 27 3799 1966 0
(Iter, Row, #Total, #Curr, #Feas)= 22 42 4812 2414 0
(Iter, Row, #Total, #Curr, #Feas)= 23 29 6086 3032 0
(Iter, Row, #Total, #Curr, #Feas)= 24 50 7553 3612 0
(Iter, Row, #Total, #Curr, #Feas)= 25 41 9194 4252 0
(Iter, Row, #Total, #Curr, #Feas)= 26 18 11219 4952 0
(Iter, Row, #Total, #Curr, #Feas)= 27 48 13365 5584 0
(Iter, Row, #Total, #Curr, #Feas)= 28 25 16084 6362 0
(Iter, Row, #Total, #Curr, #Feas)= 29 10 17784 7398 0
(Iter, Row, #Total, #Curr, #Feas)= 30 14 20093 8426 0
(Iter, Row, #Total, #Curr, #Feas)= 31 13 23277 9716 0
(Iter, Row, #Total, #Curr, #Feas)= 32 11 26221 10866 0
(Iter, Row, #Total, #Curr, #Feas)= 33 32 29928 12358 0
(Iter, Row, #Total, #Curr, #Feas)= 34 31 34214 13858 0
(Iter, Row, #Total, #Curr, #Feas)= 35 36 37696 15226 0
(Iter, Row, #Total, #Curr, #Feas)= 36 30 41385 16896 0
(Iter, Row, #Total, #Curr, #Feas)= 37 37 47175 17742 0
(Iter, Row, #Total, #Curr, #Feas)= 38 24 52986 18912 0
(Iter, Row, #Total, #Curr, #Feas)= 39 45 58475 20684 9
(Iter, Row, #Total, #Curr, #Feas)= 40 40 62948 22352 9
(Iter, Row, #Total, #Curr, #Feas)= 41 26 67684 24294 9
(Iter, Row, #Total, #Curr, #Feas)= 42 9 77007 19722 21
(Iter, Row, #Total, #Curr, #Feas)= 43 8 84113 17120 86
(Iter, Row, #Total, #Curr, #Feas)= 44 7 91128 16204 186
(Iter, Row, #Total, #Curr, #Feas)= 45 6 97262 12620 467
(Iter, Row, #Total, #Curr, #Feas)= 46 5 102097 10084 1169
(Iter, Row, #Total, #Curr, #Feas)= 47 4 106197 8686 1703
(Iter, Row, #Total, #Curr, #Feas)= 48 3 108821 6626 2141
(Iter, Row, #Total, #Curr, #Feas)= 49 2 110900 4718 3747
(Iter, Row, #Total, #Curr, #Feas)= 50 1 111914 4761 4760
(Iter, Row, #Total, #Curr, #Feas)= 51 51 111923 4769 4769
output file sampleh8-half.ext is open
output file sampleh8-half.ead is open
output file sampleh8-half.iad is open
output file sampleh8-half.ecd is open
output file sampleh8-half.icd is open
real 12m20.755s
user 11m10.130s
sys 0m1.760s
======================================================
WHEN USING CDDLIB (the version using FLOATING-POINT ARITHMETIC)
[zaffanella at spark ppl-vs-cdd]$ time ../cddlib-093a/src/scdd
sampleh8-half.ine
input file sampleh8-half.ine is open
size = 50 x 10
Number Type = integer
(Initially added rows ) = 16 17 19 20 34 39 44 46 47 49
(Iter, Row, #Total, #Curr, #Feas)= 11 22 35 30 0
(Iter, Row, #Total, #Curr, #Feas)= 12 35 75 62 0
(Iter, Row, #Total, #Curr, #Feas)= 13 21 162 124 0
(Iter, Row, #Total, #Curr, #Feas)= 14 23 298 207 0
(Iter, Row, #Total, #Curr, #Feas)= 15 12 481 327 0
(Iter, Row, #Total, #Curr, #Feas)= 16 15 758 482 0
(Iter, Row, #Total, #Curr, #Feas)= 17 28 1147 677 0
(Iter, Row, #Total, #Curr, #Feas)= 18 43 1548 882 0
(Iter, Row, #Total, #Curr, #Feas)= 19 33 2153 1080 0
(Iter, Row, #Total, #Curr, #Feas)= 20 38 2766 1336 0
(Iter, Row, #Total, #Curr, #Feas)= 21 27 3374 1710 0
(Iter, Row, #Total, #Curr, #Feas)= 22 42 4166 2047 0
(Iter, Row, #Total, #Curr, #Feas)= 23 29 5244 2510 0
(Iter, Row, #Total, #Curr, #Feas)= 24 50 6346 3070 0
(Iter, Row, #Total, #Curr, #Feas)= 25 41 7459 3501 0
(Iter, Row, #Total, #Curr, #Feas)= 26 18 8990 3941 0
(Iter, Row, #Total, #Curr, #Feas)= 27 48 10446 4474 0
(Iter, Row, #Total, #Curr, #Feas)= 28 25 12309 4867 0
(Iter, Row, #Total, #Curr, #Feas)= 29 10 13363 5522 0
(Iter, Row, #Total, #Curr, #Feas)= 30 14 14647 6106 0
(Iter, Row, #Total, #Curr, #Feas)= 31 13 16251 6924 0
(Iter, Row, #Total, #Curr, #Feas)= 32 11 17702 7587 0
(Iter, Row, #Total, #Curr, #Feas)= 33 32 19721 8454 0
(Iter, Row, #Total, #Curr, #Feas)= 34 31 22159 9336 0
(Iter, Row, #Total, #Curr, #Feas)= 35 36 24031 10065 0
(Iter, Row, #Total, #Curr, #Feas)= 36 30 25256 10740 0
(Iter, Row, #Total, #Curr, #Feas)= 37 37 28379 11257 0
(Iter, Row, #Total, #Curr, #Feas)= 38 24 30732 12125 0
(Iter, Row, #Total, #Curr, #Feas)= 39 45 33489 13019 9
(Iter, Row, #Total, #Curr, #Feas)= 40 40 35285 13756 9
(Iter, Row, #Total, #Curr, #Feas)= 41 26 36911 14473 9
(Iter, Row, #Total, #Curr, #Feas)= 42 9 42051 11016 21
(Iter, Row, #Total, #Curr, #Feas)= 43 8 45507 8348 78
(Iter, Row, #Total, #Curr, #Feas)= 44 7 48527 7328 177
(Iter, Row, #Total, #Curr, #Feas)= 45 6 51184 5031 449
(Iter, Row, #Total, #Curr, #Feas)= 46 5 53100 4711 1049
(Iter, Row, #Total, #Curr, #Feas)= 47 4 54628 3961 1467
(Iter, Row, #Total, #Curr, #Feas)= 48 3 55737 3853 1772
(Iter, Row, #Total, #Curr, #Feas)= 49 2 56898 2950 2928
(Iter, Row, #Total, #Curr, #Feas)= 50 1 56972 3002 3002
output file sampleh8-half.ext is open
output file sampleh8-half.ead is open
output file sampleh8-half.iad is open
output file sampleh8-half.ecd is open
output file sampleh8-half.icd is open
real 1m2.315s
user 1m0.540s
sys 0m0.100s
=========================================
So, on this example, not only the PPL is greatly outperforming cddlib
when using GMP, but to my even bigger surprise, our library also
outperforms the version of cddlib using floating point arithmetics!
Some inefficiency in program scdd may be due to the fact that a lot of
output is produced. However, even when commenting out all of the output
bu the generator system, I found that the PPL is still enjoying a factor
2 speed-up with respect to cddlib using floating-point arithmetics.
Clearly, I was suspicious about the correctness of the results obtained.
So I checked the output and I found that the PPL is producing a
generator system having 4769 generators, which matches the cardinality
of the generator system produced by the GMP version of cddlib
(I haven't checked for full-correctness of the result).
Moreover, the cddlib floating-point computation seems to be unreliable,
since it produces a generator system of different cardinality (3002):
in particular, it deviates from the result of the GMP version starting
from the 4-th iteration (see the last but one column in the cddlib
output: 210 for GMP, 207 for floating points).
Doesn't this look interesting?
Clearly, this is just a single experiment (maybe it was just luck!)
It would be nice to have a more thourough comparison.
Ciao,
Enea.
PS: I am using GMP 4.1.2 and gcc 3.3.3.
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ppl-scdd-gmp.cc
URL: <http://www.cs.unipr.it/pipermail/ppl-devel/attachments/20040707/5149ddc9/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ppl-sampleh8-half.dat
URL: <http://www.cs.unipr.it/pipermail/ppl-devel/attachments/20040707/5149ddc9/attachment-0001.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: sampleh8-half.ine
URL: <http://www.cs.unipr.it/pipermail/ppl-devel/attachments/20040707/5149ddc9/attachment-0002.ksh>
More information about the PPL-devel
mailing list