search

JuliaPolyhedra / Polyhedra.jl

Polyhedral Computation Interface
Other
172 stars 27 forks source link

Lots of time spent interpolating strings #279

Closed plut closed 2 years ago

plut commented 2 years ago

When computing a somewhat small convex hull (215 vertices in total), I found (using ProfileView) that this package spends most of its time (roughly 95%!; I don't have the exact figure, only a flame graph...) interpolating the following string:

            if  is_feasible(model, "attempting to determine whether $element of index $idx is redundant.")

(redundancy.jl line 156). In that interpolation, the longest time is spent computing the text form of the data types...

The most obvious fix would be replacing the string by a lazy form (either by defining some LogMessage structure, or simply by passing a Vector{Any} and concatenating the strings thereof when needed).

blegat commented 2 years ago

I would be surprised if the string interpolation was the bottleneck. is_feasible ends up calling a linear programming solver: https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/0288f2758e1e84f2896122b08a010febd0b6a2a2/src/opt.jl#L164 which is expected to be the bottleneck. Which LP solver are you using ?

plut commented 2 years ago

Here is the relevant extract from Profile.print() showing that _redundant_indices spends about 90% of its time in io.jl.

  ╎    ╎    ╎    ╎    ╎    ╎    ╎   509 ...ndancy.jl:156; _redundant_indi...
 1╎    ╎    ╎    ╎    ╎    ╎    ╎    458 ...ngs/io.jl:174; string

[snip]

  ╎    ╎    ╎    ╎    ╎    ╎    ╎    51  ...rc/opt.jl:163; is_feasible(mod...

The linear solver is GLPK.

blegat commented 2 years ago

Indeed, it seems to be in io.jl. Could you share the code of your example ?

plut commented 2 years ago

Attached as a .txt file since github doesn't like .jl files

blegat commented 2 years ago

Thanks a lot for reporting this! The string interpolation can indeed take quite a large portion of time.