Make Parma Polyhedra Library a standard library

[vbraun]

The Parma Polyhedra Library (ppl) is for many workloads the fastest library for polyhedral computations. It is also high-quality code, for example GCC uses it (optionally) to optimize loops.

• ppl has already been widely tested on a multitude of platforms.
• Native C++ with a pure C interface.
• Contains a huge testsuite _and_ passes its own testsuite (in contrast to some other polydedral library that shall remain unnamed)

Official webpage: http://www.cs.unipr.it/ppl/

My plan is to

1. Create a PPL spkg.
2. Write a Cython interface.
3. Base sage.geometry.cone.Cone on PPL instead of Polyhedron/cddlib
4. Split sage.geometry.polyhedra.Polyhedron into an abstract base class and derived classes that use different polyhedral computation libraries.

Current status:

1. My cython wrapper for PPL is attached. It has full doctest coverage and any invalid input is caught and raises ValueError.
2. Is split off into trac Base sage.geometry.cone on the Parma Polyhedra Library (PPL) #10140.

For convenience I mirrored the reference manual page here: http://www.stp.dias.ie/~vbraun/Sage/html/en/reference/sage/libs/ppl.html

To apply this ticket:

• download the new spkg http://boxen.math.washington.edu/home/jdemeyer/spkg/ppl-0.11.2.spkg
• copy the spkg to $SAGE_ROOT/spkg/standard
• apply attachment: trac_10039_parma_polyhedra_library.patch to the Sage library
• apply attachment: trac_10039_ppl_fix_extremize.patch to the Sage library
• apply attachment: 10039_manifest.patch to the Sage library
• apply attachment: trac_10039_root_repo.patch the sage root repository
• apply attachment: trac_10039_SAGE_LOCAL_bin_repo.patch to the $SAGE_LOCAL/bin repository

CC: @novoselt @jdemeyer @kiwifb

Component: geometry

Keywords: ppl spkg

Author: Volker Braun

Reviewer: Marshall Hampton, Jeroen Demeyer

Merged: sage-4.7.alpha4

Issue created by migration from https://trac.sagemath.org/ticket/10039

[sagetrac-mhampton]

comment:1

Rather than retire cddlib, it would be better I think to have cddlib as an optional backend, along with lrs. If ppl is consistently better than those then it could be the default.

[novoselt]

comment:2

If there will be a Cython interface to PPL, it definitely should become the default backend as it must be drastically faster on simple cases then the current situation. And for "complicated" cases users should be willing to spend some time to learn about advantages of different systems and pick the right one, if speed becomes an issue.

[sagetrac-mhampton]

comment:3

This package installed fine on Kubuntu 10.04 and OS X 10.6. It does take a while to compile - 10 minutes on the first machine and 15 on the other.

[vbraun]

comment:4

Yes, templated C++ code is really giving the compiler something to do.

But if you think thats slow then don't run the testsuite (SAGE_CHECK=yes)...

[sagetrac-mhampton]

comment:5

One reason I gave up any hope of making polymake standard was the compilation time; it was one reason I began writing polyhedra.py instead of improving the polymake interface.

Are there many things in PPL that go beyond cddlib? I am having trouble wading through their documentation so its unclear to me.

[novoselt]

comment:7

I read the module documentation and it looks quite nice, although the PPL interface and their documentation do not seem to be very clear to an unfamiliar user (as Marshall has already noted above). So if eventually Sage front-end is structured more like current geometric classes, it would be better - I guess that's exactly your plan in 4.

Can PPL compute integral points inside a bounded polytope?

[vbraun]

comment:8

Just to be clear, the PPL wrapper is not going to be exposed to the end user by default. She/he is supposed to use the higher-level Polyhedron and Cone classes.

The PPL sports grids (lattices defined through generators or congruences) and a MIP solver but, as far as I know, no function that directly enumerates grid points (i.e. the intersection of a grid with a polyhedron). Though it probably would not be too difficult to write one with these building blocks. In any case, I haven't cython-wrapped grids or MIPs so far.

[mwhansen]

comment:11

This does build successfully on Cygwin, but it does take _quite_ awhile:

real    346m56.531s
user    22m33.908s
sys     26m33.122s
Successfully installed ppl-0.11.p0

[vbraun]

comment:12

I take it you are not running the test suite? That one is quite extensive...

The 22 minutes in user space could be realistic for a slow machine. The 26min is sys is a bit suspicious, are you running on swap? But the real question is, why did your computer spend 6h walltime for 40 minutes of work?

I just tried the ppl spkg in an opensolaris virtual machine (single core) and it takes about 7 minutes walltime, 5m user, 1m sys.

[vbraun]

comment:13

I've removed all language interfaces (except the native C++), this shaves off a few minutes. Now on my Fedora 13 box normal compilation takes 1 minute and the testsuite 20 minutes:

[vbraun@volker-desktop spkg]$ /usr/bin/time sage -f ppl-0.11.p0.spkg 
...
35.84user 17.68system 1:02.23elapsed 86%CPU (0avgtext+0avgdata 229008maxresident)k
4240inputs+1152096outputs (37major+5069087minor)pagefaults 0swaps

Testing:

[vbraun@volker-desktop ~]$ SAGE_CHECK=yes time sage -f ppl-0.11.p0.spkg
...
771.04user 281.70system 20:37.31elapsed 85%CPU (0avgtext+0avgdata 453712maxresident)k
13710920inputs+46999048outputs (91major+76885818minor)pagefaults 0swaps

[sagetrac-drkirkby]

comment:14

Replying to @mwhansen:

This does build successfully on Cygwin, but it does take _quite_ awhile:

real    346m56.531s
user    22m33.908s
sys     26m33.122s
Successfully installed ppl-0.11.p0

That sure is a long time. I think it's because autoconf scripts takes ages on Cygwin, because Windows has no fork.

On my Sun Ultra 27, it takes less than 82 seconds to install.

real	1m21.460s
user	4m6.543s
sys	0m27.474s
Successfully installed ppl-0.11.p0
Now cleaning up tmp files.
Making Sage/Python scripts relocatable...
Making script relocatable
Finished installing ppl-0.11.p0.spkg

However, it fails the test suite. To be more precise, the tests it runs pass, but it fails to build some of the code needed for the tests.

I'm not sure what the gcc option -W is supposed to do. According to the gcc manual -w (lower case) is to suppress all warnings. If -W does the same as -w, then it seems the code tries to supporess the warnings, then enable them, which seems a bit illogical. But I can't find out exactly what -W is supposed to do.

BTW, this should be called ppl-0.11 and not ppl-0.11.p0. Only once a version has appeared in Sage, and patches have been applied, should it be called .p0.

A couple more points.

• There is no code to handle 64-bit builds on platforms where SAGE64=yes. It needs something like this:

    if [ "x$CFLAG64" = x ]; then 
        CFLAG64=-m64
    fi

    # If the environment variable SAGE64=yes, force building a 64-bit version:
    if [ "x$SAGE64" = xyes ]; then
        echo "Building a 64-bit version of ppl"
        CC="$CC $CFLAG64"
        export CC
    fi

That needs to be in both spkg-install and spkg-check.

• I don't think Unpack distribution into src/ directory needs to be in the Special Update/Build Instructions section, as that is the same with every single package.

• I would start spkg-check with #!/usr/bin/env bash to be consistent. That said, there's nothing there which should not work with any half-reasonable shell.

• It would be better to use $MAKE in spkg-check so the tests can be run in parallel too, which should speed things up a lot.

[sagetrac-drkirkby]

Log showing how some of the test code failed to build when SPKG_CHECK=yes. Without that, it builds OK in < 82 seconds. This is on a Sun Ultra 27 running OpenSolaris 06/2009

[vbraun]

comment:15

Attachment: ppl-0.11.p0.log

The testsuite fails on Solaris gcc 4.5.0, most likely due to a gcc bug. For reference, the real error is

interval1.cc:76:3: error: no matching function for call to 'Parma_Polyhedra_Library::Interval<float, Parma_Polyhedra_Library::Interval_Restriction_None<Parma_Polyhedra_Library::Interval_Info_Bitset<unsigned int, <unnamed>::My_Interval<float>::Floating_Point_Real_Interval_Info_Policy> > >::join_assign(double)'
interval1.cc:194:3:   instantiated from here

Everything should work fine with gcc 4.5.1. In particular, I could compile and run the testsuite on OpenSolaris/i386 with gcc 4.5.1. Also note that the offending floating point code is currently not used in the Cython wrapper. A similar bug report is here: https://www.cs.unipr.it/mantis/view.php?id=110

About the -W, the gcc manual says:

-Wextra: This enables some extra warning flags that are not enabled by -Wall. (This option used to be called -W. The older name is still supported, but the newer name is more descriptive.)

I have addressed the other issues that you raised. The updated spgk is here:

http://www.stp.dias.ie/~vbraun/Sage/spkg/ppl-0.11.spkg

[vbraun]

comment:16

Sorry, I was too quick. The testsuite does not like "MAKE=make -j8", there is a missing shell escape. So I'll leave it at "make check" in the spkg-check for now. I've reported this upstream at https://www.cs.unipr.it/mantis/view.php?id=118

I'm also getting the testsuite "no matching function call" from Opensolaris/gcc 4.5.1.

[vbraun]

comment:17

I have patched out the PPL testsuite for Box<>, BD_Shape<>, and Octagonal_Shape<>. I think these templated classes are newer and not as well-tested. Note that the polyhedron code does not use templates. In any case, they are not currently exposed by the Cython wrapper and they don't provide any functionality that we need in the near future.

The updated spgk now compiles a) in parallel and b) under Solaris/gcc 4.5.1 without errors, including the testsuite.

As usual, get it here: http://www.stp.dias.ie/~vbraun/Sage/spkg/ppl-0.11.spkg

[novoselt]

comment:18

Some notes based on the posted documentation:

1. "Note that, by convention, every polyhedron must contain a point" can be clarified a little that only generator systems containing a point may define a polyhedron, since there is no point issue in defining a polyhedron by a constraint system. (I would also add that it is natural to think about "just rays" as starting at the origin, but since your goal is to wrap PPL as closely as possible, it is not your design decision.)
2. In the documentation of Generator I see "frac"s instead of fractions.
3. add_space_dimensions_and_embed and add_space_dimensions_and_project - I think you want (x,y)\in P, not R^2. Also the top of the documentation for "project" still says "embed". (I also find names confusing, but I guess that's how PPL calls them.)
4. Why affine_dimension of the empty polyhedron is 0? Shouldn't it be -1 to distinguish it from points?
5. Am I right that "concatenating" polyhedra means taking their Cartesian product? Perhaps, it is a simpler explanation than in concatenate_assign?
6. contains_integer_point has wrong documentation description about being bounded.
7. I don't understand what exactly is done by drop_some_non_integer_points.
8. frequency does not have documentation.
9. Is it necessary to have hash_code, especially if it only returns the dimension? My concern is that it can be confusing how it is related to standard hash in Python, also it seems strange to use it for mutable objects (again, because that's not how things work in Python). If this function is not used anywhere, I would suggest removing it.
10. I got upset when I read in the documentation of max_space_dimension that it is bounded, but the doctest immediately made me happy ;-)
11. clear_mpz_globals, gmp_randrange, init_mpz_globals have no documentation.

[vbraun]

comment:19

I fixed the documentation according to your suggestions.

4. Why affine_dimension of the empty polyhedron is 0? Shouldn't it be -1 to distinguish it from points?

The internal representation of dimensions is an unsigned int. So PPL returns 0 instead of something negative. Using signed integer would half the max_space_dimension() ;-)

5. Am I right that "concatenating" polyhedra means taking their Cartesian product? Perhaps, it is a simpler explanation than in concatenate_assign?

Yes. I just copy/pasted the C++ documentation. I've added a line that this is the Cartesian product.

7. I don't understand what exactly is done by drop_some_non_integer_points.

All that is guaranteed is that the result is non-strictly contained in the original polyhedron and that integral vertices survive. Its not the most useful function, but it is there and was easy to wrap ;-)

8. frequency does not have documentation.

I removed this one, it is only useful for grids (spanned lattices / congruences).

9. Is it necessary to have hash_code, especially if it only returns the dimension? My concern is that it can be confusing how it is related to standard hash in Python, also it seems strange to use it for mutable objects (again, because that's not how things work in Python). If this function is not used anywhere, I would suggest removing it.

Removed.

10. I got upset when I read in the documentation of max_space_dimension that it is bounded, but the doctest immediately made me happy ;-)

Yes, should be enough for most applications ;)

11. clear_mpz_globals, gmp_randrange, init_mpz_globals have no documentation.

I didn't define these, they were imported from gmp.pxi and sphinx adds them to the documentation for some reason. Anyways, importing gmp.pxi is not necessary so I removed it.

[jdemeyer]

comment:20

I have tried building with the new spkg and sagelib patch, but I get the following error:

Building modified file sage/libs/pari/gen.pyx.
Traceback (most recent call last):
  File "setup.py", line 855, in <module>
    queue = compile_command_list(ext_modules, deps)
  File "setup.py", line 815, in compile_command_list
    dep_file, dep_time = deps.newest_dep(f)
  File "setup.py", line 722, in newest_dep
    for f in self.all_deps(filename):
  File "setup.py", line 703, in all_deps
    for f in self.immediate_deps(filename):
  File "setup.py", line 685, in immediate_deps
    self._deps[filename] = self.parse_deps(filename)
  File "setup.py", line 675, in parse_deps
    raise IOError, "could not find dependency %s included in %s."%(path, filename)
IOError: could not find dependency ../../local/include/ppl.hh included in sage/libs/ppl.pyx.
sage: There was an error installing modified sage library code.

ERROR installing SAGE

[jdemeyer]

Changed merged from sage-4.7.alpha3 to none

[jdemeyer]

comment:78

On RHEL 5.3-64 (cleo), SUSE ES10-64 (iras), OpenSolaris 06.2009-32 (hawk), SunOS 5.10-32 (t2):

File "/scratch/buildbot/sage/t2-1/t2_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 1413:
    sage: p.minimize( -x )
Expected:
    {'minimum': False, 'bounded': False, 'inf_d': 0, 'generator': None, 'inf_n': 0}
Got:
    {'minimum': True, 'bounded': False, 'inf_d': 0, 'generator': None, 'inf_n': 0}

[jdemeyer]

comment:79

On SunOS 5.10-32 (t2), OpenSolaris 06.2009-32 (hawk):

File "/scratch/buildbot/sage/t2-1/t2_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 1342:
    sage: p.maximize( +x )
Expected:
    {'sup_d': 0, 'sup_n': 0, 'bounded': False, 'maximum': False, 'generator': None}
Got:
    {'sup_d': 0, 'sup_n': 0, 'bounded': False, 'maximum': True, 'generator': None}

[jdemeyer]

comment:80

See #11100 for the timeout problem.

[vbraun]

comment:81

I finally got the problem with the maximize/minimize doctest failure. If the linear function is not bounded on the polyhedron then it doesn't make sense to ask for whether its a maximum or minimum. And PPL then does not return a consistent value for the corresponding field.

In the attached patch I changed return value of the maximize/minimize methods to only return {'bounded':False} if the linear program is unbounded, since all other dictionary entries are not well-defined in that case. If the linear program is bounded then the returned dictionary is the same as before and contains information about the sup/inf value, whether it is a maximum, and where it is attained.

The new patch trac_10039_ppl_fix_extremize.patch needs to be applied on top of trac_10039_parma_polyhedra_library.patch, see also the ticket description. The new patch needs review.

[kiwifb]

comment:82

That's good news and that wasn't just me then! I have my hands full at the moment so I won't be able to review it quickly but I am sure you have another reviewer around :)

[jdemeyer]

Changed reviewer from Marshall Hampton to Marshall Hampton, Jeroen Demeyer

[jdemeyer]

comment:83

New patch looks good to me. Still needs to be tested on the buildbots, but positive review in the hope that everything works fine.

[jdemeyer]

comment:84

Volker, you just need to put a proper commit message on your patch...

[vbraun]

Attachment: trac_10039_ppl_fix_extremize.2.patch.gz

Updated patch

[vbraun]

Attachment: trac_10039_ppl_fix_extremize.patch.gz

Updated patch

[vbraun]

comment:85

Oops, sorry. New trac_10039_ppl_fix_extremize.patch now has a commit message, no other changes. Setting this back to positive review as only metadata changed.

[jdemeyer]

Merged: sage-4.7.alpha4

[jdemeyer]

comment:87

www.stp.dias.ie seems to be down, so I'm mirroring the spkg myself.