merge_benchmark.jl

struct B{T}
    val::T
end

f(x::B{T}, y::B{T}) where T = B{T}(x.val + y.val) #always returns same type as x and y


__merge(f, unused_ys, x_i) = x_i, unused_ys
__merge(f, unused_ys, x_i::T, y_j::T, y...) where T = f(x_i, y_j), (unused_ys..., y...)
__merge(f, unused_ys, x_i, y_j, y...) = __merge(f, (unused_ys..., y_j), x_i, y...)

_merge(f, results, remaining_ys) = (results..., remaining_ys...)
function _merge(f, results, remaining_ys, x_i, x...)
    _result, _remaining_ys = __merge(f, (), x_i, remaining_ys...)
    return _merge(f, (results..., _result), _remaining_ys, x...)
end

merge(f, x, y) = _merge(f, (), y, x...)

@inline _mergeo(f, results, remaining_ys) = (results, remaining_ys)
@inline function _mergeo(f, results, remaining_ys, x_i, x...)
    _result, _remaining_ys = __merge(f, (), x_i, remaining_ys...)
    return _mergeo(f, (results..., _result), _remaining_ys, x...)
end

@inline function mergeo(f, x::T, y) where T
    let (res::T, rem) = _mergeo(f, (), y, x...)
        return (res..., rem...)
    end
end


_merge1(f, x, y_acc) = (x, y_acc...)
_merge1(f, x::T, y_acc, y::T, y_rest...) where T = (f(x, y), y_acc..., y_rest...)
_merge1(f, x, y_acc, y, y_rest...) = _merge1(f, x, (y, y_acc...), y_rest...)
merge1(f, x, ys) = _merge1(f, x, (), ys...)

merge2(f, ::Tuple{}, ys) = ys
merge2(f::F, xs, ys) where F = merge2(f, Base.tail(xs), merge1(f, first(xs), ys))

using BenchmarkTools, Random

const types = [ map.([identity,unsigned], Ref([Int8, Int16, Int32, Int64, Int128])) |>
                    x -> [x...;];
                map.([identity,T->Complex{T}], Ref([Float16, Float32, Float64])) |>
                    x -> [x...;] ]

function benchmark_merges(xargs, yargs, xysame=0)
    shuffled_types = shuffle(types)
    xtypes = ( (shuffled_types[1:xargs] |> shuffle)...,)
    ytypes = ( (shuffled_types[range(xargs-xysame+1, length=yargs)] |> shuffle)...,)

    println("xtypes = $xtypes, ytypes = $ytypes")

    xs, ys = (rand.(xtypes), rand.(ytypes))

    println("\nmerge_tamas:\n" * repeat('-', 40))
    show(stdout, MIME("text/plain"), @benchmark merge2(f, $xs, $ys))

    println("\n\nmerge_simeon:\n" * repeat('-', 40))
    show(stdout, MIME("text/plain"), @benchmark merge(f, $xs, $ys))

    println("\n\nmerge_type-inferable_simeon:\n" * repeat('-', 40))
    show(stdout, MIME("text/plain"), @benchmark mergeo(f, $xs, $ys))
end