[PPL-devel] Re: Question regarding speed of the library

[Roberto Bagnara]

Martin Rohde wrote:
 > I'm using the library now for calculating the intersection of two convex
 > polyhedra. During my calculations, a large number of intersections must
 > be calculated (say 50000 times). The library does its calculations very
 > well, but it costs a lot of time to calculate an intersection. In my
 > code I do the following:
 >
 > 1. Add generators to a polyhedron 1
 > 2. Add generators to a polyhedron 2
 > 3. Calculate the intersection of polyhedra 1 and 2
 > 4. Store the constraints and the generators in an array (I convert all
 > coefficients to doubles)
 >
 > This process costs 100 seconds for 30000 calculations (so 30
 > intersections per second) on a 600MHz machine.
 >
 > When I remove step 3 (so I skip the intersection), the calculation takes
 > about the same amount of time. So, the intersection is not the time
 > consuming step. But removing step 1 and/or 2 speeds up the calculation
 > significantly! So I might conclude that the ph.add_generator(ax+by+cz)
 > is very slow.
 >
 > My questions are now:
 >
 > - is add_generator slow indeed?
 > - How can I speed up the code?

Dear Martin,

I assume you are creating polyhedra p1 and p2 empty.  That is, with
some code like (feel free to substitute `C_Polyhedron' with
`NNC_Polyhedron')

    C_Polyhedron p1(n, C_Polyhedron::EMPTY);
    C_Polyhedron p2(n, C_Polyhedron::EMPTY);

In this case, the computational cost of each call to `add_generator'
you are performing is amortized linear in `n' (the space dimension
of the polyhedron involved).

The cost of obtaining the constraints of the polyhedra starting from
the generators is, in the worst case, exponential.  Since intersection
is computed by performing the union of the constraints for polyhedra
p1 and p2, your step 3 has also exponential complexity (since first it
computes the constraints for both p1 and p2).  Notice also that, if
you omit step 3, you will pay an exponential price in step 4 since, in
order to store the constraints in the array you must first compute the
constraints.  On the other hand, if step 3 is not omitted, step 4 will
be (relatively) very cheap since the constraints have already been
computed.

So the answer to the question "is add_generator slow?" is "no".  In
order to answer the question "how can I speed up the code?"  we would
need to either see your code or to know (much) more about your
application.  For instance, what is the range of dimensions you are
using for your polyhedra?  What is the order of magnitude of the
number of generators you are injecting into the polyhedra?  Are you
using C_Polyhedron or NNC_Polyhedron?  Did you compile the library by
yourself?  If so, which options did you give to configure?  An answer
to these questions may put us on the right track, but seeing the code
would perhaps also allow us to improve the library.
All the best

     Roberto

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it