Slow evaluation of H-polyhedron

[schillic]

Is there anything that can be done to improve the first-time evaluation of polyhedra? Seven minutes is quite impressive. The construction itself is fast, but I guess the real computation is just delayed. Also note that in previous Julia versions this was considerably faster.

julia> using Polyhedra
julia> A, b = [1.0 0.0; 0.0 1.0; -1.0 0.0; 0.0 -1.0], [0.5, 1.0, 1.0, 0.5];
julia> H = hrep(A, b);
julia> lib = default_library(2, Float64);
julia> P = polyhedron(H, lib);  # this is fast

# Julia v1.4.1
julia> @time print(P); nothing  # first time is slow
HalfSpace([1.0, 0.0], 0.5) ∩ HalfSpace([0.0, 1.0], 1.0) ∩ HalfSpace([-1.0, 0.0], 1.0) ∩ HalfSpace([0.0, -1.0], 0.5)
466.502759 seconds (805.85 M allocations: 59.368 GiB, 4.43% gc time)

julia> @time print(P); nothing  # second time is fast (as expected)
HalfSpace([1.0, 0.0], 0.5) ∩ HalfSpace([0.0, 1.0], 1.0) ∩ HalfSpace([-1.0, 0.0], 1.0) ∩ HalfSpace([0.0, -1.0], 0.5)
0.000255 seconds (141 allocations: 8.766 KiB)

# Julia v1.0.5
julia> @time print(P); nothing  # first time is slow
HalfSpace([1.0, 0.0], 0.5) ∩ HalfSpace([0.0, 1.0], 1.0) ∩ HalfSpace([-1.0, 0.0], 1.0) ∩ HalfSpace([0.0, -1.0], 0.5)
77.888212 seconds (535.31 M allocations: 27.871 GiB, 10.59% gc time)

julia> @time print(P); nothing  # second time is fast (as expected)
HalfSpace([1.0, 0.0], 0.5) ∩ HalfSpace([0.0, 1.0], 1.0) ∩ HalfSpace([-1.0, 0.0], 1.0) ∩ HalfSpace([0.0, -1.0], 0.5)
0.000454 seconds (93 allocations: 3.109 KiB)

[blegat]

I noticed that too, it seems to be https://github.com/JuliaPolyhedra/Polyhedra.jl/issues/128 coming back. We should report the issue upstream (maybe with https://julialang.org/blog/2020/05/rr/)

[joehuchette]

I'm observing the same very slow behavior on first print:

julia> @time print(P); nothing
HalfSpace([1.0, 0.0], 0.5) ∩ HalfSpace([0.0, 1.0], 1.0) ∩ HalfSpace([-1.0, 0.0], 1.0) ∩ HalfSpace([0.0, -1.0], 0.5)
278.871120 seconds (649.93 M allocations: 45.619 GiB, 5.37% gc time)

julia> @time print(P); nothing
HalfSpace([1.0, 0.0], 0.5) ∩ HalfSpace([0.0, 1.0], 1.0) ∩ HalfSpace([-1.0, 0.0], 1.0) ∩ HalfSpace([0.0, -1.0], 0.5)  
0.000704 seconds (125 allocations: 8.609 KiB)

Interestingly, I've also observed this very slow behavior in a test set I'm writing that doesn't call print/show on any polyhedra. It takes ~5 minutes to run the fairly trivial tests; am working to try to isolate where the slowdown occurs in my code.

[schillic]

The JuliaLang issue was closed. In Julia v1.7.2:

julia> @time print(P);  # first time
HalfSpace([1.0, 0.0], 0.5) ∩ HalfSpace([0.0, 1.0], 1.0) ∩ HalfSpace([-1.0, 0.0], 1.0) ∩ HalfSpace([0.0, -1.0], 0.5)
  3.051096 seconds (7.38 M allocations: 428.249 MiB, 6.66% gc time, 99.96% compilation time)

julia> @time print(P);  # second time
HalfSpace([1.0, 0.0], 0.5) ∩ HalfSpace([0.0, 1.0], 1.0) ∩ HalfSpace([-1.0, 0.0], 1.0) ∩ HalfSpace([0.0, -1.0], 0.5)
  0.000186 seconds (103 allocations: 7.844 KiB)

@blegat I think you can close all four related issues.

[blegat]

Yes, glad this is fixed !