Skip to content

the performance of array construction from numbers: SparseArrays piracy and hvcat overhead #58397

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
johnnychen94 opened this issue May 13, 2025 · 1 comment · May be fixed by #58422
Open
Labels
arrays [a, r, r, a, y, s] performance Must go faster

Comments

@johnnychen94
Copy link
Member

johnnychen94 commented May 13, 2025

In julia we have two typical ways to concatenate arrays,

  • [] cat syntax. This is used most frequently due to its simplicity
  • array initialization: out = Array{...}(undef, ...); ... This has the least overhead but it's often too verbose to write it

Let's first give the conclusion and the to-do task list:

Conclusions:

  • [] syntax is always slower than the array init method. And [x x; y y] matrix concatenation is too slow to be acceptable.
  • Type piracy in SparseArrays affected the performance badly since Julia 1.10
  • Julia 1.11 and 1.12 have brought a significant performance boost 🎉 🚀

Todo:

  • the performance gap between [x x; y y] and array init method should be narrowed. (especially for Julia 1.12)
  • We need to eliminate the performance regression brought by using SparseArrays

Because BenchmarkTools depends on SparseArrays (indirectly) in some Julia versions, I use the following script to run the benchmark:

function many_loop(f, n)
    for i in 1:n
        f()
    end
end

f1_row(x, y) = hcat(x, y, x, y)
function f2_row(x, y)
    c = Matrix{Float64}(undef, 1, 4)
    @inbounds begin
        c[1] = x
        c[2] = y
        c[3] = x
        c[4] = y
    end
    return c
end

f1_col(x, y) = vcat(x, y, x, y)
function f2_col(x, y)
    c = Matrix{Float64}(undef, 4, 1)
    @inbounds begin
        c[1] = x
        c[2] = y
        c[3] = x
        c[4] = y
    end
    return c
end

f1_mat(x, y) = hvcat((2, 2), x, y, x, y)
function f2_mat(x, y)
    c = Matrix{Float64}(undef, 2, 2)
    @inbounds begin
        c[1] = x
        c[2] = x
        c[3] = y
        c[4] = y
    end
    return c
end


@assert vec(f1_row(0.3, 0.4)) == vec(f2_row(0.3, 0.4))
@assert vec(f1_col(0.3, 0.4)) == vec(f2_col(0.3, 0.4))
@assert f1_mat(0.3, 0.4) == f2_mat(0.3, 0.4)
many_loop(()->f1_row(0.3, 0.4), 1000000)

function f()
    x, y = rand(), rand()

    @info "row concatenation"
    @time many_loop(()->f1_row(x, y), 1000000)
    @time many_loop(()->f2_row(x, y), 1000000)

    @info "column concatenation"
    @time many_loop(()->f1_col(x, y), 1000000)
    @time many_loop(()->f2_col(x, y), 1000000)

    @info "matrix concatenation"
    @time many_loop(()->f1_mat(x, y), 1000000)
    @time many_loop(()->f2_mat(x, y), 1000000)
end

f()
using SparseArrays

@info "SparseArrays loaded"
f()
julia method version time (ms) time (ms) (after SparseArrays)
1.9.3 row native 29.235 26.248
1.9.3 row init 25.602 24.399
1.9.3 column native 24.030 22.598
1.9.3 column init 25.017 23.616
1.9.3 matrix native 68.152 63.910
1.9.3 matrix init 23.486 24.113
1.10.9 row native 28.702 28.451
1.10.9 row init 24.184 25.074
1.10.9 column native 24.178 22.774
1.10.9 column init 24.048 22.900
1.10.9 matrix native 47.608 334.611
1.10.9 matrix init 22.945 23.823
1.11.5 row native 25.212 19.552
1.11.5 row init 16.931 16.823
1.11.5 column native 16.209 18.608
1.11.5 column init 16.295 18.340
1.11.5 matrix native 49.707 157.885
1.11.5 matrix init 16.765 17.138
1.12.0-beta3 row native 0.224 0.201
1.12.0-beta3 row init 0.354 0.666
1.12.0-beta3 column native 0.338 0.644
1.12.0-beta3 column init 0.339 0.647
1.12.0-beta3 matrix native 151.048 26.780
1.12.0-beta3 matrix init 0.338 0.782
Julia Version 1.11.5
Commit 760b2e5b739 (2025-04-14 06:53 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 20 × 12th Gen Intel(R) Core(TM) i7-12700H
  WORD_SIZE: 64
  LLVM: libLLVM-16.0.6 (ORCJIT, alderlake)
Threads: 1 default, 0 interactive, 1 GC (on 20 virtual cores)
@johnnychen94 johnnychen94 added performance Must go faster arrays [a, r, r, a, y, s] labels May 13, 2025
@johnnychen94 johnnychen94 changed the title cat performance analysis array concatenation performance analysis May 13, 2025
@mcabbott
Copy link
Contributor

ways to concatenate arrays

I think this is exclusively about ways to construct an array from numbers (one of which uses hcat), not the concatenation of two or more arrays. Might be worth adjusting the wording & title -- I had to read the examples.

@johnnychen94 johnnychen94 changed the title array concatenation performance analysis array construction from numbers: SparseArrays piracy and hvcat overhead May 15, 2025
@johnnychen94 johnnychen94 changed the title array construction from numbers: SparseArrays piracy and hvcat overhead the performance of array construction from numbers: SparseArrays piracy and hvcat overhead May 15, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
arrays [a, r, r, a, y, s] performance Must go faster
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants