Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#11849 closed defect (fixed)

cddlib test in ppl.pyx takes a very long time

Reported by: jdemeyer Owned by: was
Priority: blocker Milestone: sage-4.7.2
Component: interfaces Keywords: sd34 Parma Polyhedra Library
Cc: vbraun, leif Merged in: sage-4.7.2.alpha3
Authors: Volker Braun Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by jdemeyer)

From the file sage/libs/ppl.pyx starting at line 112:

The computation finishes without noticeable delay on my desktop
(timeit measures it to be 35msec). Cddlib needs about 3 minutes on the
same hardware::

    sage: basis = range(0,6)
    sage: x = [ Variable(i) for i in basis ]
    sage: gs = [ tuple(coeff) for coeff in permutations(basis) ]
    sage: Polyhedron(vertices=gs)   # long time
    A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 720 vertices.

This test takes minutes (as is claimed). This regularly causes timeouts when testing Sage on Skynet.

On sage.math.washington.edu, sage-4.7.2.alpha0:

sage: from sage.libs.ppl import Variable, Generator_System, point, C_Polyhedron
sage: basis = range(0,6)
sage: x = [ Variable(i) for i in basis ]
sage: gs = [ tuple(coeff) for coeff in permutations(basis) ]
sage: time Polyhedron(vertices=gs)
A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 720 vertices.

Time: CPU 0.14 s, Wall: 218.94 s

See also: #10039, #11534.

Apply trac_11849_shorter_long_ppl_test.patch and 11849_reviewer.patch

Attachments (2)

trac_11849_shorter_long_ppl_test.patch (1.9 KB) - added by vbraun 10 years ago.
Initial patch
11849_reviewer.patch (1.9 KB) - added by jdemeyer 10 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 10 years ago by jdemeyer

  • Description modified (diff)
  • Keywords Parma Polyhedra Library added

comment:2 follow-up: Changed 10 years ago by vbraun

You are looking at the wrong code. The

sage: Polyhedron(vertices=gs)   # long time

call takes a very long time, as stated. The PPL computation is a few lines above, and completes within miliseconds:

sage: C_Polyhedron(gs)

We could turn the Polyhedron() call into a shorter # long time example.

Also, I have some patches on trac to switch Polyhedron to PPL, as well.

comment:3 in reply to: ↑ 2 Changed 10 years ago by jdemeyer

Replying to vbraun:

sage: C_Polyhedron(gs) }}} We could turn the Polyhedron() call into a shorter # long time example.

Yes, please do that. I think you should aim for something taking at most 10 seconds or so on sage.math.

Also, I would rephrase the paragraph starting from line 112 as

The above computation (using PPL) finishes without noticeable delay (timeit measures it to be 5ms on sage.math). Below we do the same computation with cddlib, which needs about 10 seconds on the same hardware::

    sage: basis = range(0,6)
    sage: x = [ Variable(i) for i in basis ]
    sage: gs = [ tuple(coeff) for coeff in permutations(basis) ]
    sage: Polyhedron(vertices=gs)   # long time (10s on sage.math, 2011)
    A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 720 vertices.

Changed 10 years ago by vbraun

Initial patch

comment:4 Changed 10 years ago by vbraun

  • Authors set to Volker Braun
  • Description modified (diff)
  • Status changed from new to needs_review

The attached patch switches to an computationally easier doctest problem. Now it should complete in < 5.

comment:5 Changed 10 years ago by jdemeyer

  • Description modified (diff)
  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to positive_review

positive_review modulo the reviewer patch.

comment:6 Changed 10 years ago by jdemeyer

  • Description modified (diff)
  • Summary changed from ppl.pyx test takes a very long time contrary to what is claimed to cddlib test in ppl.pyx takes a very long time

comment:7 Changed 10 years ago by vbraun

Great, thanks!

comment:8 Changed 10 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:9 Changed 10 years ago by vbraun

  • Keywords sd34 added

Changed 10 years ago by jdemeyer

comment:10 Changed 10 years ago by jdemeyer

Fixed commit message of my reviewer patch.

Note: See TracTickets for help on using tickets.