Identical method redefinition suspiciously optimizes runtime and allocations

Benny · September 12, 2025, 2:33pm

First off, that’s impressive. Only thing I would suggest is commenting out multiple lines between #= and =# instead of # leading each line to make copy-pasting convenient.

Second, I tried @code_warntype right out the gate before any execution, and it appears as type-stable as your reports after benchmarks. However, if we Cthulhu.@descend deeper, we run into recursion with changing argument types:

305  all(f::Main.Euler2D_MWE.var"#1#2"{SClosedPolygon{4, Float64}}::Function, a::SVector{4, SVector{2, Float64}}::StaticArray; dims::Core.Const(Colon())=:)::Bool = _mapreduce(x->f(x)::Bool, &::Core.Const(&), dims::Core.Const(Colon()), true, Size(a::SVector{4, SVector{2, Float64}})::Core.Const(Size(4,)), a::SVector{4, SVector{2, Float64}})
Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.
Toggles: [w]arn, [h]ide type-stable statements, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native, [j]ump to source always.
Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code
Actions: [E]dit source code, [R]evise and redisplay
   Size(a::SVector{4, SVector{2, Float64}})
 • _mapreduce(x->f(x)::Bool, &::Core.Const(&), dims::Core.Const(Colon()), true, Size(a::SVector{4, SVector{2, Float64}})::Core.Const(Size(4,)), a::SVec…
   ↩
_mapreduce(args::Vararg{Any, N}) where N @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:153
┌ Warning: Inference terminated in an incomplete state due to argument-type changes during recursion

despite the ultimate return value of all being inferred as Bool. The implied recursion isn’t clear because some metaprogramming obscured calls on top of the compromised type information; in other words, it’s hard to pick which lines to manually descend further.

Fortunately, `JET.@reportopt` automatically ''descends'' into all the calls to filter out instability and dispatch issues, and it spots an explicit recursion becoming unoptimized and runtime-dispatched. It seems to corroborate your comment about `all(Base.Fix2(...),...)` being a potential issue for `point_inside_strict`, a function called in the input function for `all` in the benchmarked function.

julia> @report_opt Euler2D_MWE.is_cell_contained_by(test_cell, test_poly1)
═════ 8 possible errors found ═════
┌ is_cell_contained_by(cell1::TangentQuadCell_MWE{Float64, 3, 12}, poly::SClosedPolygon{4, Float64}) @ Main.Euler2D_MWE ./REPL[7]:35
│┌ all(f::Main.Euler2D_MWE.var"#1#2"{SClosedPolygon{4, Float64}}, a::SVector{4, SVector{2, Float64}}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:305
││┌ all(f::Main.Euler2D_MWE.var"#1#2"{SClosedPolygon{4, Float64}}, a::SVector{4, SVector{2, Float64}}; dims::Colon) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:305
│││┌ _mapreduce(::StaticArrays.var"#214#215"{…}, ::typeof(&), ::Colon, ::Bool, ::Size{…}, ::SVector{…}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:153
││││┌ _mapfoldl(f::StaticArrays.var"#214#215"{…}, op::typeof(&), dims::Colon, init::Bool, ::Size{…}, a::SVector{…}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:180
│││││┌ (::StaticArrays.var"#214#215"{Main.Euler2D_MWE.var"#1#2"{SClosedPolygon{4, Float64}}})(x::SVector{2, Float64}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:305
││││││┌ (::Main.Euler2D_MWE.var"#1#2"{SClosedPolygon{4, Float64}})(pt::SVector{2, Float64}) @ Main.Euler2D_MWE ./REPL[7]:36
│││││││┌ point_inside_strict(poly::SClosedPolygon{4, Float64}, pt::SVector{2, Float64}) @ Main.PlanePolygons_MWE ./REPL[6]:71
││││││││┌ all(f::Base.Fix2{…}, a::SVector{…}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:305
│││││││││┌ all(f::Base.Fix2{…}, a::SVector{…}; dims::Colon) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:305
││││││││││┌ _mapreduce(::StaticArrays.var"#214#215", ::typeof(&), ::Colon, ::Bool, ::Size{…}, ::SVector{…}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:153
│││││││││││ runtime dispatch detected: StaticArrays._mapfoldl(%1::StaticArrays.var"#214#215", &, Colon(), %2::Bool, [quote]::Size{(4,)}, %3::SVector{4, Main.PlanePolygons_MWE.Line{Float64}})::Bool
││││││││││└────────────────────
│││││││││┌ all(f::Base.Fix2{…}, a::SVector{…}; dims::Colon) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:305
││││││││││ failed to optimize due to recursion: StaticArrays.var"#all#213"(::Colon, ::typeof(all), ::Base.Fix2{…}, ::SVector{…})
│││││││││└────────────────────
││││││││┌ all(f::Base.Fix2{…}, a::SVector{…}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:305
│││││││││ failed to optimize due to recursion: all(::Base.Fix2{…}, ::SVector{…})
││││││││└────────────────────
│││││││┌ point_inside_strict(poly::SClosedPolygon{4, Float64}, pt::SVector{2, Float64}) @ Main.PlanePolygons_MWE ./REPL[6]:70
││││││││ failed to optimize due to recursion: Main.PlanePolygons_MWE.point_inside_strict(::SClosedPolygon{4, Float64}, ::SVector{2, Float64})
│││││││└────────────────────
││││││┌ (::Main.Euler2D_MWE.var"#1#2"{SClosedPolygon{4, Float64}})(pt::SVector{2, Float64}) @ Main.Euler2D_MWE ./REPL[7]:36
│││││││ failed to optimize due to recursion: (::Main.Euler2D_MWE.var"#1#2"{SClosedPolygon{4, Float64}})(::SVector{2, Float64})
││││││└────────────────────
│││││┌ (::StaticArrays.var"#214#215"{Main.Euler2D_MWE.var"#1#2"{SClosedPolygon{4, Float64}}})(x::SVector{2, Float64}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:305
││││││ failed to optimize due to recursion: (::StaticArrays.var"#214#215"{Main.Euler2D_MWE.var"#1#2"{SClosedPolygon{4, Float64}}})(::SVector{2, Float64})
│││││└────────────────────
││││┌ _mapfoldl(f::StaticArrays.var"#214#215"{…}, op::typeof(&), dims::Colon, init::Bool, ::Size{…}, a::SVector{…}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:155
│││││ failed to optimize due to recursion: StaticArrays._mapfoldl(::StaticArrays.var"#214#215"{…}, ::typeof(&), ::Colon, ::Bool, ::Size{…}, ::SVector{…})
││││└────────────────────
│││┌ _mapreduce(::StaticArrays.var"#214#215"{…}, ::typeof(&), ::Colon, ::Bool, ::Size{…}, ::SVector{…}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:153
││││ failed to optimize due to recursion: StaticArrays._mapreduce(::StaticArrays.var"#214#215"{…}, ::typeof(&), ::Colon, ::Bool, ::Size{…}, ::SVector{…})
│││└────────────────────

These reports persist after the 0 allocation benchmark. These reports also show up if run fresh after your MWE completed the 0 allocation benchmark. Like @code_warntype etc, these packages seem to perform type inference fresh, so it’s still possible it diverges from the actually compiled code. Not great in the exceptional cases like these where state matters.

nsajko · September 12, 2025, 4:35pm

A workaround is to convert the SArray to a Tuple before calling all:

all(Tuple(edge_starts(cell_poly)))

This avoids the ancient and hacky StaticArrays.jl code, instead relying on Base Julia code.

Benny · September 13, 2025, 10:29pm

Haven’t examined it, but do you know how introducing that Tuple conversion avoids the type-varying recursion issue? It ought to have the same recursive all via the input function, right?

nsajko · September 13, 2025, 10:39pm

Converting to Tuple avoids the method of all added by StaticArrays.jl.

See:

github.com/JuliaArrays/StaticArrays.jl

src/mapreduce.jl

bb20cf40b


      
          @inline iszero(a::StaticArray{<:Tuple,T}) where {T} = reduce((x,y) -> x && iszero(y), a, init=true)
          
          @inline sum(a::StaticArray{<:Tuple,T}; dims=:, init=_InitialValue()) where {T} = _reduce(+, a, dims, init)
          @inline sum(f, a::StaticArray{<:Tuple,T}; dims=:, init=_InitialValue()) where {T} = _mapreduce(f, +, dims, init, Size(a), a)
          @inline sum(f::Union{Function, Type}, a::StaticArray{<:Tuple,T}; dims=:, init=_InitialValue()) where {T} = _mapreduce(f, +, dims, init, Size(a), a) # avoid ambiguity
          
          @inline prod(a::StaticArray{<:Tuple,T}; dims=:, init=_InitialValue()) where {T} = _reduce(*, a, dims, init)
          @inline prod(f, a::StaticArray{<:Tuple,T}; dims=:, init=_InitialValue()) where {T} = _mapreduce(f, *, dims, init, Size(a), a)
          @inline prod(f::Union{Function, Type}, a::StaticArray{<:Tuple,T}; dims=:, init=_InitialValue()) where {T} = _mapreduce(f, *, dims, init, Size(a), a)
          
          @inline count(a::StaticArray{<:Tuple,Bool}; dims=:, init=0) = _reduce(+, a, dims, init)
          @inline count(f, a::StaticArray; dims=:, init=0) = _mapreduce(x->f(x)::Bool, +, dims, init, Size(a), a)
          
          @inline all(a::StaticArray{<:Tuple,Bool}; dims=:) = _reduce(&, a, dims, true)  # non-branching versions
          @inline all(f::Function, a::StaticArray; dims=:) = _mapreduce(x->f(x)::Bool, &, dims, true, Size(a), a)
          
          @inline any(a::StaticArray{<:Tuple,Bool}; dims=:) = _reduce(|, a, dims, false) # (benchmarking needed)
          @inline any(f::Function, a::StaticArray; dims=:) = _mapreduce(x->f(x)::Bool, |, dims, false, Size(a), a) # (benchmarking needed)
          
          @inline Base.in(x, a::StaticArray) = _mapreduce(==(x), |, :, false, Size(a), a)

This file has been truncated. show original

nsajko · September 14, 2025, 7:11pm

Too quick to disrespect StaticArrays.jl

After a few hours I’m still not able to make a PR to StaticArrays.jl to fix the issue. Some observations:

The input array to all is a nested static array, with static arrays as elements. This complicates the recursion, making inference give up.
The all for Tuple does not have to support a dims argument, simplifying the problem.

My conclusion, for now, is to convert static arrays to tuples as eagerly as possible.

I guess the important thing about the workaround is that the conversion to tuple happens before any all(f, c) call.

afleming · September 15, 2025, 12:39am

Thanks for the help! Converting the SArray to a tuple before feeding it to all works like a charm. Benchmarks on my machine are even faster, down to 13ns instead of 40ns.

I’ll have to write specializations for boundary polygons that don’t have a compile-time number of vertices, but that’s okay.

Topic		Replies	Views
How to optimize such a program Performance question	8	1027	October 20, 2017
Regression in v0.7 due to weird inference failure for function with Lisp-y recursion Internals & Design inference	14	1636	March 23, 2018
Reducing allocations to optimize (to match Java speed) Performance	22	1373	December 10, 2018
What's the best practice in Julia for research (often changed codes)? General Usage design-pattern	26	1618	April 20, 2021
Inappropriate memory allocation? Julia at Scale question , memory	24	2185	September 4, 2017

Identical method redefinition suspiciously optimizes runtime and allocations

Related topics