Performance issue on linked list example comparing to SumTypes

[Roger-luo]

from @MasonProtter

module SumTypesTest
using BenchmarkTools
using SumTypes
@sum_type List{T} begin
    Nil
    Cons{T}(::T, ::List{T})
end
Base.sum(l::List{T}; init=zero(T)) where {T} = @cases l begin
    Nil => init
    Cons(head, tail) => head + sum(tail; init)
end
display(@benchmark sum(l) setup=(l = foldr(Cons, 1:100, init=List{Int}'.Nil)))
end

gives

BenchmarkTools.Trial: 10000 samples with 303 evaluations.
 Range (min … max):  274.380 ns … 446.855 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     290.071 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   291.778 ns ±  12.205 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

         ▁▄▆██▇▅▂                                                
  ▁▁▁▂▃▅▆████████▇▄▃▃▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  274 ns           Histogram: frequency by time          358 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

and

module MoshiTest
using BenchmarkTools
using Moshi.Data: @data
using Moshi.Match: @match
@data List{T} begin
    Nil
    Cons(T, List{T})
end
Base.sum(l::List.Type{T}; init=zero(T)) where {T} = @match l begin
    List.Nil() => init
    List.Cons(head, tail) => head + sum(tail; init)
end
display(@benchmark sum(l) setup=(l = foldr(List.Cons, 1:100, init=List.Nil{Int}())))
end

gives

BenchmarkTools.Trial: 10000 samples with 7 evaluations.
 Range (min … max):  4.139 μs …  1.419 ms  ┊ GC (min … max): 0.00% … 99.49%
 Time  (median):     4.546 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   5.212 μs ± 17.040 μs  ┊ GC (mean ± σ):  5.17% ±  1.71%

      ▃██▆▆▆                                                  
  ▁▂▃▅██████▇▂▁▁▁▁▁▁▁▁▁▁▁▁▁▂▃▅▆▆▆▇▆▅▄▃▃▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  4.14 μs        Histogram: frequency by time        6.76 μs <

 Memory estimate: 3.05 KiB, allocs estimate: 195.

[Roger-luo]

@MasonProtter what's your versioninfo? I cannot reproduce

[Roger-luo]

@MasonProtter what's your versioninfo? I cannot reproduce

[MasonProtter]

julia> versioninfo()
Julia Version 1.11.0-rc3
Commit 616e45539db (2024-08-26 15:46 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 12 × AMD Ryzen 5 5600X 6-Core Processor
  WORD_SIZE: 64
  LLVM: libLLVM-16.0.6 (ORCJIT, znver3)
Threads: 6 default, 0 interactive, 3 GC (on 12 virtual cores)
Environment:
  JULIA_NUM_THREADS = 6

and

julia> versioninfo()
Julia Version 1.10.4
Commit 48d4fd48430 (2024-06-04 10:41 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 12 × AMD Ryzen 5 5600X 6-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, znver3)
Threads: 6 default, 0 interactive, 3 GC (on 12 virtual cores)
Environment:
  JULIA_NUM_THREADS = 6