[PPL-devel] Overhead of the generalization

[Enea Zaffanella]

I suggest to start looking at the implementation of the class Row::Type,
which probably needs some polishing anyway.

There should be an intrinsic overhead of one instruction for each newly 
inserted
row in a Matrix, since we now have to "merge" the Matrix topology kind
(NNC/NC) and the row kind (LINE_OR_EQ/RAY_OR_POINT_OR_INEQ)
in order to obtain the Row::Type ...
I tried to perform this merge only once when adding multiple rows of the 
same kind.

No other "intrinsic" overhead should be expected when working with the class
Polyhedron, apart from the usual topology tests (one for each public method
invoked).

However, we still have un-optimized implementations for, e.g.,
add_constraints() and for limited_widening_assign()
(see the FIXME comments in the code).
You maybe want to use the profiler to see if these are the causes
of the overhead.

ciao,
Enea.


Roberto Bagnara wrote:

> 
> Here is how much time China took for analyzing the entire
> benchmark suite with our domain of closed polyhedra, in random
> days during the development of the generalization that allows
> us to deal with NNC polyhedra:
> 
> Mar 15     2439.11
> Mar 16     2427.51
> Mar 17     2448.84
> Mar 18     2459.51
> Mar 19     2414.16
> Mar 22     2428.86
> Mar 23     2468.88
> Apr 01     2538.46
> 
> The merge took place in the night between Marh 26 and 27.
> It looks like the overhead is greater than 4%. This is not
> very bad, but I expected it to be under 1%.  A figure of >4%
> almost certainly means that we are paying a lot at the
> Row level.  I hope we can improve the implementation so as
> to recover what we have lost.
> Ciao
> 
>      Roberto
>