`prod(::AbstractVector{BigInt})` is `O(n^2)` when it could be `O(n log n)`

[LilithHafner]

prod(x::AbstractVector{BigInt}) uses foldl which, in the case a large vector x with similarly sized elements (or big elements at the front), results in a lot (n) of operations on large integers (on the scale of the result of prod). Pairwise multiplication can be asymptotically faster.

function _prod(x::Vector{BigInt})
    while length(x) > 1
        for i in 1:length(x)÷2
            x[i] = x[2i-1] * x[2i]
        end
        if length(x) % 2 == 1
            x[length(x)÷2 + 1] = x[end]
        end
        resize!(x, (length(x) + 1) ÷ 2)
    end
    only(x)
end

f(n) = prod([BigInt(rand(UInt)) for i in 1:n])
g(n) = _prod([BigInt(rand(UInt)) for i in 1:n])


using Chairmarks
x = 2000:2000:20000
y = [@b x f,g for x in x]
using Plots
plot(x, getproperty.(first.(y), :time), label="prod",
     xlabel="n", ylabel="time (s)",
     title="Comparison of prod and _prod for BigInt vectors",
     legend=:topleft)
plot!(x, getproperty.(last.(y), :time), label="_prod")
savefig("prod_vs__prod_bigint.png")

[adienes]

is there a such thing as a "Base extension package" ? it mildly feels like there should be a first-class product tree object (and remainder tree) in some computational number theory lib, and Base can use the optimization there for prod if it's loaded

[LilithHafner]

Sorting would also benefit from a "Base extension package".