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@spark cddlib-093a]$ ./configure [...] [zaffanella@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@spark ppl-vs-cdd]$ ../ppl-0.5/configure --disable-asseretions --disable-debugging --enable-optimization=sspeed --prefix=/tmp/opt3/ppl-0.5 [...]
[zaffanella@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@spark ppl-vs-cdd]$ export LD_LIBRARY_PATH=/tmp/opt3/ppl-0.5/lib:$LD_LIBRARY_PATH
[zaffanella@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@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@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@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.
#include "ppl.hh" #include <fstream> #include <iostream>
using namespace std; using namespace Parma_Polyhedra_Library;
void open(fstream& s, const char* path, ios_base::openmode mode) { s.open(path, mode); if (!s) { cerr << "Cannot open `" << path << "'"; if (mode == ios_base::in) cerr << " for reading"; else if (mode == ios_base::out) cerr << " for writing"; else if (mode == ios_base::in | ios_base::out) cerr << " for reading/writing"; cerr << endl; exit(1); } }
void close(fstream& s) { if (s) s.close(); }
static const char* my_file = "ppl-sampleh8-half.dat"; static const char* my_file_out = "ppl-sampleh8-half.out";
int main() { fstream f; open(f, my_file, ios_base::in); C_Polyhedron ph; ph.ascii_load(f); close(f);
// Make sure the polyhedron read is well-formed. if (!ph.OK()) abort();
ph.generators();
open(f, my_file_out, ios_base::out); ph.ascii_dump(f); close(f);
return 0; }
space_dim 9 -ZE -EM -CM -GM +CS -GS -CP -GP -SC -SG con_sys (up-to-date) topology NECESSARILY_CLOSED 51 x 10 (not_sorted) index_first_pending 51 1 0 0 0 0 0 0 0 0 0 >= 0 1 0 0 0 0 0 0 0 0 >= 0 0 1 0 0 0 0 0 0 0 >= 0 0 0 1 0 0 0 0 0 0 >= 0 0 0 0 1 0 0 0 0 0 >= 0 0 0 0 0 1 0 0 0 0 >= 0 0 0 0 0 0 1 0 0 0 >= 0 0 0 0 0 0 0 1 0 0 >= 0 0 0 0 0 0 0 0 1 0 >= 0 0 0 0 0 0 0 0 0 1 >= -10000 651 693 84 697 637 340 368 824 663 >= -10000 725 742 387 219 751 430 202 745 356 >= -10000 377 674 979 167 815 988 412 676 475 >= -10000 710 275 949 284 629 1 422 974 510 >= -10000 692 945 725 488 271 430 724 225 726 >= -10000 465 258 450 343 87 168 161 103 919 >= -10000 86 79 656 493 832 514 791 506 29 >= -10000 63 630 874 918 877 272 992 119 480 >= -10000 598 926 42 378 288 66 927 919 99 >= -10000 256 354 106 979 641 160 395 225 837 >= -10000 202 388 900 471 160 751 300 731 818 >= -10000 342 502 825 563 639 261 194 984 990 >= -10000 266 406 364 216 448 675 145 694 866 >= -10000 362 983 732 378 134 902 946 877 205 >= -10000 926 125 949 888 234 630 275 707 67 >= -10000 634 81 192 768 652 822 311 961 895 >= -10000 983 597 743 314 696 585 367 396 826 >= -10000 511 545 539 97 111 996 477 35 372 >= -10000 474 103 152 753 159 120 929 161 563 >= -10000 549 793 307 456 444 184 149 792 894 >= -10000 839 488 917 192 168 788 959 245 25 >= -10000 750 165 338 182 392 381 962 117 713 >= -10000 738 827 943 507 914 814 951 663 815 >= -10000 493 339 225 351 450 788 992 167 792 >= -10000 174 773 247 247 180 517 445 599 596 >= -10000 303 26 967 39 535 4 7 335 217 >= -10000 772 173 189 291 668 191 610 677 544 >= -10000 848 642 40 125 865 100 259 534 648 >= -10000 501 622 398 624 118 416 30 17 236 >= -10000 218 602 697 892 322 314 361 573 985 >= -10000 958 856 608 492 563 478 311 614 740 >= -10000 582 913 938 949 715 338 39 726 998 >= -10000 521 805 708 221 624 316 24 127 322 >= -10000 491 189 412 774 418 200 193 633 315 >= -10000 144 679 383 447 989 939 441 631 482 >= -10000 940 241 153 215 149 457 254 207 125 >= -10000 80 873 207 904 684 600 940 431 825 >= -10000 75 100 353 637 432 377 940 758 164 >= -10000 627 721 915 710 8 786 96 17 576 >= -10000 247 104 607 432 540 164 597 282 317 >= -10000 553 787 881 942 152 318 44 509 518 >=
gen_sys (not_up-to-date) topology NECESSARILY_CLOSED 0 x 0 (not_sorted) index_first_pending 0
sat_c 0 x 0
sat_g 0 x 0
* testing with half of the constraints of sampleh8.ine H-representation begin 50 10 integer 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 -10000 651 693 84 697 637 340 368 824 663 -10000 725 742 387 219 751 430 202 745 356 -10000 377 674 979 167 815 988 412 676 475 -10000 710 275 949 284 629 1 422 974 510 -10000 692 945 725 488 271 430 724 225 726 -10000 465 258 450 343 87 168 161 103 919 -10000 86 79 656 493 832 514 791 506 29 -10000 63 630 874 918 877 272 992 119 480 -10000 598 926 42 378 288 66 927 919 99 -10000 256 354 106 979 641 160 395 225 837 -10000 202 388 900 471 160 751 300 731 818 -10000 342 502 825 563 639 261 194 984 990 -10000 266 406 364 216 448 675 145 694 866 -10000 362 983 732 378 134 902 946 877 205 -10000 926 125 949 888 234 630 275 707 67 -10000 634 81 192 768 652 822 311 961 895 -10000 983 597 743 314 696 585 367 396 826 -10000 511 545 539 97 111 996 477 35 372 -10000 474 103 152 753 159 120 929 161 563 -10000 549 793 307 456 444 184 149 792 894 -10000 839 488 917 192 168 788 959 245 25 -10000 750 165 338 182 392 381 962 117 713 -10000 738 827 943 507 914 814 951 663 815 -10000 493 339 225 351 450 788 992 167 792 -10000 174 773 247 247 180 517 445 599 596 -10000 303 26 967 39 535 4 7 335 217 -10000 772 173 189 291 668 191 610 677 544 -10000 848 642 40 125 865 100 259 534 648 -10000 501 622 398 624 118 416 30 17 236 -10000 218 602 697 892 322 314 361 573 985 -10000 958 856 608 492 563 478 311 614 740 -10000 582 913 938 949 715 338 39 726 998 -10000 521 805 708 221 624 316 24 127 322 -10000 491 189 412 774 418 200 193 633 315 -10000 144 679 383 447 989 939 441 631 482 -10000 940 241 153 215 149 457 254 207 125 -10000 80 873 207 904 684 600 940 431 825 -10000 75 100 353 637 432 377 940 758 164 -10000 627 721 915 710 8 786 96 17 576 -10000 247 104 607 432 540 164 597 282 317 -10000 553 787 881 942 152 318 44 509 518 end