Invalidations - Githubissues

fingolfin commented 1 year ago

Loading Polymake.jl introduces a lot of invalidations, more if we load it into Oscar. Here's a quick report using Julia master:

julia> using SnoopCompileCore

julia> invalidations = @snoopr begin using Polymake end; using SnoopCompile ;

julia> trees = invalidation_trees(invalidations); length(uinvalidated(invalidations))
344

Some more details:

julia> using PrettyTables ; report_invalidations(;invalidations, n_rows=0)
[ Info: 344 methods invalidated for 20 functions
┌─────────────────────────────────────────────────────────────────────────────────────┬────────────────┬───────────────┬─────────────────┐
│ <file name>:<line number>                                                           │ Function Name  │ Invalidations │ Invalidations % │
│                                                                                     │                │               │     (xᵢ/∑x)     │
├─────────────────────────────────────────────────────────────────────────────────────┼────────────────┼───────────────┼─────────────────┤
│ ~/.julia/dev/CxxWrap/src/CxxWrap.jl:121                                             │     Number     │      128      │       32        │
│ ~/.julia/dev/Polymake/src/std/pairs.jl:6                                            │    convert     │      49       │       12        │
│ ~/julia.master/usr/share/julia/stdlib/v1.10/SparseArrays/src/sparsematrix.jl:2316   │      _all      │      35       │        9        │
│ ~/julia.master/usr/share/julia/stdlib/v1.10/SparseArrays/src/sparsematrix.jl:2314   │      _any      │      35       │        9        │
│ ~/.julia/dev/Polymake/src/integers.jl:57                                            │ trailing_zeros │      32       │        8        │
│ ~/.julia/dev/Polymake/src/integers.jl:49                                            │    convert     │      27       │        7        │
│ ~/.julia/dev/Polymake/src/convert.jl:57                                             │    convert     │      17       │        4        │
│ ~/.julia/dev/Polymake/src/integers.jl:12                                            │      zero      │      15       │        4        │
│ ~/.julia/dev/CxxWrap/src/StdLib.jl:101                                              │      cmp       │      11       │        3        │
│ ~/.julia/dev/Polymake/src/integers.jl:11                                            │      zero      │       7       │        2        │
│ ~/.julia/dev/Polymake/src/meta.jl:358                                               │     getdoc     │       7       │        2        │
│ ~/julia.master/usr/share/julia/stdlib/v1.10/SparseArrays/src/readonly.jl:33         │    resize!     │       7       │        2        │
│ ~/.julia/dev/Mongoc/src/bson.jl:494                                                 │      keys      │       6       │        2        │
│ ~/.julia/dev/DecFP/src/DecFP.jl:540                                                 │     isnan      │       5       │        1        │
│ ~/.julia/dev/CxxWrap/src/CxxWrap.jl:107                                             │  promote_rule  │       5       │        1        │
│ ~/.julia/dev/Polymake/src/convert.jl:59                                             │    convert     │       4       │        1        │
│ ~/julia.master/usr/share/julia/stdlib/v1.10/SparseArrays/src/solvers/cholmod.jl:983 │     eltype     │       4       │        1        │
│ ~/.julia/dev/CxxWrap/src/CxxWrap.jl:687                                             │    convert     │       2       │        1        │
│ ~/.julia/dev/Polymake/src/integers.jl:9                                             │      one       │       1       │        0        │
│ ~/.julia/dev/Polymake/src/integers.jl:55                                            │    convert     │       1       │        0        │
└─────────────────────────────────────────────────────────────────────────────────────┴────────────────┴───────────────┴─────────────────┘

For the ones in the Julia stdlib SparseArrays I submitted an issue). For DecFP and Mongoc I got some PRs merged there which help this. I haven't yet looked into CxxWrap.

That still leaves quite a few in Polymake. Some of them perhaps can't be helped, or really should be dealt with by changes to the Julia library or other packages.

But a few maybe should be changed in Polymake.jl. E.g. this method:

Base.convert(::Type{CxxWrap.CxxLong}, n::Integer) = Int64(n)

Base.convert(::Type{CxxWrap.CxxLong}, r::Rational) = new_int_from_rational(r)

where Integer is Polymake.Integer, a subtype of Base.Integer; and similar for Rational.

This causes invalidations because the Julia library generally defines

convert(::Type{T}, x::T)      where {T<:Number} = x
convert(::Type{T}, x::Number) where {T<:Number} = T(x)::T

One way to address this might be to replace those convert methods by

CxxWrap.CxxLong(n::Integer) = Int64(n)
CxxWrap.CxxLong(r::Rational) = new_int_from_rational(r)

and similar for multiple other convert methods. But I did not really try this, and it may be necessary to make further adjustments.

benlorenz commented 1 year ago

I tried looking into those, I could remove a few but got stuck with some other ones:

Base.trailing_zeros(int::Integer) = trailing_zeros(BigInt(int)) This is only reported on 1.10 but not on 1.9 and I cannot find any method this invalidates.

julia> it[12]
inserting trailing_zeros(int::Polymake.LibPolymake.Integer) @ Polymake ~/software/polymake/julia/Polymake-extra.jl/src/integers.jl:63 invalidated:
 mt_backedges: 1: signature Tuple{typeof(trailing_zeros), Any} triggered MethodInstance for iterate(::Base.LogicalIndex{<:Any, <:BitArray}, ::Any) (26 children)

So this seems to invalidate the trailing_zeros call here:

@inline function iterate(L::LogicalIndex{<:Any,<:BitArray}, (i1, Bi, irest, c))
  Bc = L.mask.chunks
  while c == 0
      Bi >= length(Bc) && return nothing
      i1 += 64
      @inbounds c = Bc[Bi+=1]
  end
  tz = trailing_zeros(c)
  c = _blsr(c)
  i1, irest = _overflowind(i1 + tz, irest, size(L.mask))
  return eltype(L)(i1, irest...), (i1 - tz, Bi, irest, c)
end

But it seems to be compiled with Any according to the signature in the invalidation, which probably means that any new definition of trailing_zeros will invalidate this call ?

Base.Docs.getdoc(::Type{$(jlfunc_name)}) = PolymakeDocstring($(doc_string)): This is from meta.jl:

inserting getdoc(::Type{Polymake.polytope.cyclic_caratheodory}) @ Polymake.polytope ~/software/polymake/julia/Polymake-extra.jl/src/meta.jl:359 invalidated:
 backedges: 1: superseding getdoc(x) @ Base.Docs docs/Docs.jl:275 with MethodInstance for Base.Docs.getdoc(::Any) (8 children)

I don't see any way to avoid this, the julia docs recommend exactly that to define custom docs:

Docs.getdoc(t::MyType) = "Documentation for MyType with value $(t.value)"

benlorenz commented 1 year ago

Current invalidations on latest master (together with Mongoc master and julia master):

julia> using PrettyTables ; report_invalidations(;invalidations, n_rows=0)
[ Info: 284 methods invalidated for 15 functions
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┬────────────────┬───────────────┬─────────────────┐
│ <file name>:<line number>                                                                                                 │ Function Name  │ Invalidations │ Invalidations % │
│                                                                                                                           │                │               │     (xᵢ/∑x)     │
├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┼────────────────┼───────────────┼─────────────────┤
│ /home/lorenz/.julia/packages/CxxWrap/aXNBY/src/CxxWrap.jl:136                                                             │    Integer     │      131      │       39        │
│ /cache/build/default-amdci5-4/julialang/julia-master/usr/share/julia/stdlib/v1.10/SparseArrays/src/sparsematrix.jl:2316   │      _all      │      35       │       10        │
│ /cache/build/default-amdci5-4/julialang/julia-master/usr/share/julia/stdlib/v1.10/SparseArrays/src/sparsematrix.jl:2314   │      _any      │      35       │       10        │
│ /home/lorenz/software/polymake/julia/Polymake-git.jl/src/integers.jl:58                                                   │ trailing_zeros │      26       │        8        │
│ /home/lorenz/.julia/packages/DecFP/wSrPR/src/DecFP.jl:642                                                                 │    convert     │      26       │        8        │
│ /cache/build/default-amdci5-4/julialang/julia-master/usr/share/julia/stdlib/v1.10/SparseArrays/src/solvers/cholmod.jl:983 │     eltype     │      21       │        6        │
│ /home/lorenz/.julia/packages/CxxWrap/aXNBY/src/CxxWrap.jl:687                                                             │    convert     │      18       │        5        │
│ /home/lorenz/.julia/packages/CxxWrap/aXNBY/src/StdLib.jl:101                                                              │      cmp       │      11       │        3        │
│ /home/lorenz/software/polymake/julia/Polymake-git.jl/src/meta.jl:359                                                      │     getdoc     │       7       │        2        │
│ /cache/build/default-amdci5-4/julialang/julia-master/usr/share/julia/stdlib/v1.10/SparseArrays/src/readonly.jl:33         │    resize!     │       7       │        2        │
│ /home/lorenz/.julia/dev/Mongoc/src/bson.jl:494                                                                            │      keys      │       6       │        2        │
│ /home/lorenz/.julia/packages/DecFP/wSrPR/src/DecFP.jl:539                                                                 │     isnan      │       5       │        1        │
│ /home/lorenz/.julia/packages/CxxWrap/aXNBY/src/CxxWrap.jl:107                                                             │  promote_rule  │       5       │        1        │
│ /home/lorenz/.julia/packages/DecFP/wSrPR/src/DecFP.jl:642                                                                 │    convert     │       4       │        1        │
│ /home/lorenz/.julia/packages/DecFP/wSrPR/src/DecFP.jl:811                                                                 │    convert     │       2       │        1        │
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┴────────────────┴───────────────┴─────────────────┘

Only getdoc and trailing_zeros remaining from Polymake directly.

fingolfin commented 1 year ago

Great!

(You can probably also dev DecFP fort another reduction)

JamesWrigley commented 5 months ago

FWIW the SparseArrays invalidations seem to have been fixed in 1.11: https://github.com/JuliaSparse/SparseArrays.jl/issues/506#issuecomment-2053595143

oscar-system / Polymake.jl

Invalidations #443