[PPL-devel] PPL timings depend on sort (ordering) of input?

[Enea Zaffanella]

Il 01/10/2011 16:03, Nestor Aguilera ha scritto:
> Hi Enea,
> 
> Thank you very much for your answers.
> 
> On 29 Sep 2011, at 16:23, Enea Zaffanella wrote:
> 
>> Il 28/09/2011 22:56, Nestor Aguilera ha scritto:
>>> Hi,
>>>
>>> I am new to PPL, coming from CDD (and PORTA), and I am using
>>> "ppl_lcdd" (replacing "lcdd_gmp").
>>>
>>> I found PPL quite fast on my problems as compared to CDD, so I am
>>> quite happy with it.
>>>
>>> However, working with circulant matrices I found that the timings
>>> depend very much on how the problem is presented.
>>>
>>> I am enclosing two files with the same vertices: those in the
>>> "ppl_7.ext" are those in "ppl_1.ext" rotated by 6 places, and the
>>> problem is to find the inequalities description of the convex hull.
>>>
>>> In my machine, "ppl_lcdd" takes about 1.2s to solve "ppl_1" and about
>>> 18.3s to solve "ppl_7", although they are essentially the same
>>> problem.
>>>
>>> Can anyone tell me why this is so?, does it depend on any special
>>> sorting in the input?
>>>
>>> Thank you very much.
>>>
>>> Néstor Aguilera
>>
>>
>> Hello Néstor.
>>
>> I have not checked carefully your input files, but I guess that when you
>> say "rotated by 6 places" you are meaning that the space dimensions in
>> the input polyhedron (i.e., the columns of the matrices) have been
>> subject to a permutation.
> 
> That is right, although I might add that the permutation is cyclic.
> 
> For example, in the .ext representation, the point
> 
>    1 1 0 0 0 0 1 0 0 0 0 0
> 
> in one file goes to
> 
>    1 1 0 0 0 0 0 1 0 0 0 0
> 
> in the other file.
> 
>> If that is the case, then some difference in the time needed to perform
>> a conversion is to be expected.
>>
>> The PPL library (like other polyhedra libraries) speculatively sorts the
>> input representation using (a variant of) a lexicographic ordering.
>> This is a known heuristics that quite often is successful in reducing
>> the size of intermediate conversion results (and hence, computation
>> time). In unlucky cases, the heuristics may be less effective or even
>> totally ineffective ... but usually it behaves as a significant improvement.
> 
> Thanks, I understand that.
> 
> However, I would have guessed that the sorting procedure on both
> inputs would take very little time (much less than a second for my
> inputs) and should take about the same timings once done. Recall that
> in my test files and my machine, PPL takes about 1.2 seconds for one
> file and 18.3 seconds for the other, more that 10 times the first one
> and way beyond what sorting would take.
> 
> Could you elaborate a little more on the sorting used (the variant of
> lexicografphic order)? E.g., does it include the support (for
> instance, (1,0,0) comes before (0,1,1) unlike the lexicographic
> order)?, is it dynamical or done only once at the beginning?, is
> there a way I could "preprocess" and test my files looking for a
> "good" sorting procedure (perhaps without PPL doing the sorting)?


The sorting procedure used by the PPL only sorts the *rows* of the
matrix. Since you are permuting the columns, the sorting procedure will
*not* yield the same result for the two inputs you are mentioning.
In practice, this means that it is not the sorting being slow in your
second example; rather, it is the incremental conversion procedure that
happens to generate (much) bigger intermediate results.

Regarding the details of the row comparison function used in the PPL,
see the documentation of

int compare (const Linear_Row &x, const Linear_Row &y)

http://bugseng.com/products/ppl/documentation//devref/ppl-devref-0.11.2-html/classParma__Polyhedra__Library_1_1Linear__Row.html#a52ce05b13ba01eb64bb899ad154f921d

Currently there is no support for dynamically changing this comparison
function. We might want to consider such an addition, if someone
provides us evidence of the effectiveness of the approach.

If you want to perform experiments with a different comparison function,
you can simply replace the default one. Note however that there are
places where we may have made assumption about sortedness: e.g., we may
have assumed that in a sorted constraint system all equalities come
before all inequalities.

If you want to perform experiments with a different ordering of space
dimensions (i.e., columns), then you might be interested in the
following method:

template<typename Partial_Function >
void Polyhedron::map_space_dimensions (const Partial_Function &pfunc)

For its documentation (in particular, for the specification of the
partial function that, in your case, should be a total function encoding
a permutation), see the PPL manual.

Cheers,
Enea.


> Thank you very much for your answers.
> 
> All the best,
> 
> Néstor Aguilera