new performance issue with ==

[vtjnash]

Something recently broke == performance for String: https://github.com/JuliaLang/julia/commit/fa3981bf83a016e2fb48f51204ccbf9d8d66397c#commitcomment-83556911

between these commits https://github.com/JuliaLang/julia/compare/5c5af1fffd1bd0a9124415689a4664ab934e79f1...fa3981bf83a016e2fb48f51204ccbf9d8d66397c

[oscardssmith]

what's the benchmark that reproduces this?

[KristofferC]

https://github.com/JuliaLang/julia/commit/fa3981bf83a016e2fb48f51204ccbf9d8d66397c#commitcomment-83556911

[aviatesk]

This performance regression got introduced by https://github.com/JuliaLang/julia/pull/45924. /cc @jakobnissen

[aviatesk]

A MRE would be:

julia> using BenchmarkTools

julia> str = String('A':'Z') ^ 100;

julia> a = SubString(str);

julia> b = reverse(str);

julia> invokecmp(a, b) = @invoke a::AbstractString == b::AbstractString
invokecmp (generic function with 1 method)

julia> @benchmark invokecmp($a, $b)
# before
BenchmarkTools.Trial: 10000 samples with 999 evaluations.
 Range (min … max):  8.281 ns … 97.360 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     8.583 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   8.774 ns ±  2.740 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █▁▇▃ ▆                                                     ▂
  ██████▇█▄▃▃▅▄▄▄▄▄▄▅▅▁▅▃▄▅▃▅▄▁▁▅▄▄▃▄▄▅▄▄▄▅▄▆▁▅▆▆▅▅▆▃▄▄▅▅▅▅▄ █
  8.28 ns      Histogram: log(frequency) by time     15.2 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

# after
BenchmarkTools.Trial: 10000 samples with 8 evaluations.
 Range (min … max):  3.842 μs … 113.077 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     4.649 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   4.655 μs ±   1.640 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

   ▃▄▅▁▃  ▇▂█▂                                                ▂
  ██████▆████████▆▇▆▆▇▆▄▅▅▅▄▅▃▃▆▁▅▅▅▄▅▅▄▄▄▄▃▅▅▅▁▅▃▄▃▄▅▅▄▅▄▄▄▆ █
  3.84 μs      Histogram: log(frequency) by time      8.51 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

[jakobnissen]

I suspect what's happening here is that after my PR, Iterators.Stateful calls length on its underlying iterator on instantiation, which is slow for strings. I'll have a look if I can maybe make Stateful behave more lazily, and only call length when needed, and only once.

Ok, I can't think of a way to keep Stateful behaviour correct without needing a call to length on instantiation. Two solutions I can think of are:

• Good but hard: Figure out how to dispatch on whether an iterator is mutable or not
• Not good but doable: Don't use Stateful in Base.cmp

[Moelf]

actually,

diff --git a/base/strings/basic.jl b/base/strings/basic.jl
index c266689824..69eaef0668 100644
--- a/base/strings/basic.jl
+++ b/base/strings/basic.jl
@@ -298,7 +298,7 @@ julia> cmp("b", "β")
 """
 function cmp(a::AbstractString, b::AbstractString)
     a === b && return 0
-    a, b = Iterators.Stateful(a), Iterators.Stateful(b)
     for (c::AbstractChar, d::AbstractChar) in zip(a, b)
         c ≠ d && return ifelse(c < d, -1, 1)
     end

julia> @benchmark invokecmp($a, $b)
BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  4.919 ns … 10.791 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     5.009 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   5.016 ns ±  0.155 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▃ ▁     ▃        ▄        █ ▃▃    ▂▃                       ▁
  █▁██▁▁▁▁█▁▁█▁▁▃▁▁█▁▁█▁▁█▁▁█▁██▁▄▄▁██▁▇▁▁▁▁▁▃▁▁▁▁▁▁▁▁▃▁▁▁▁▃ █
  4.92 ns      Histogram: log(frequency) by time     5.12 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

do we actually need a Stateful here?