Skip to content
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

Avoid unnecessary rmul! in Bidiagonal*Diagonal #54861

Closed
wants to merge 2 commits into from
Closed

Conversation

jishnub
Copy link
Contributor

@jishnub jishnub commented Jun 20, 2024

This avoids looping over the destination array twice, which improves performance.

julia> using LinearAlgebra

julia> B = Bidiagonal(ones(200), ones(199), :U);

julia> D = Diagonal(ones(size(B,1)));

julia> C = similar(B);

julia> @btime mul!($C, $B, $D);
  635.365 ns (2 allocations: 1.62 KiB) # nightly v"1.12.0-DEV.751"
  454.782 ns (2 allocations: 1.62 KiB) # This PR

@jishnub jishnub added linear algebra Linear algebra arrays [a, r, r, a, y, s] labels Jun 20, 2024
@jishnub
Copy link
Contributor Author

jishnub commented Jun 21, 2024

The test failures should be resolved by #54874

@dkarrasch dkarrasch added the performance Must go faster label Jun 21, 2024
@jishnub
Copy link
Contributor Author

jishnub commented Jun 21, 2024

I'm not convinced about this approach, as it introduces regressions in the case where the destination is a dense zero matrix.

julia> B = Bidiagonal(ones(200), ones(199), :U);

julia> D = Diagonal(ones(size(B,1)));

julia> @btime mul!($(zeros(size(B))), $B, $D);
  7.338 μs (2 allocations: 1.62 KiB) # nightly
  40.437 μs (2 allocations: 1.62 KiB) # This PR

This is because in this case, the isbanded check introduces an extra loop over the destination. What we miss here is a bandwidth function that looks only at the structure of the matrix, and not the values. Perhaps we should add such a function and make it public as well, but we might want a different name to indicate that unlike isbanded, this only infers the bandwidth from the structure of the matrix.

@jishnub jishnub marked this pull request as draft June 21, 2024 09:46
@dkarrasch
Copy link
Member

Perhaps you could put the two versions into a little helper function with two methods, and external packages could hook into that, if they are able to decide for bandedness based on type info.

@jishnub jishnub closed this Aug 22, 2024
@giordano giordano deleted the jishnub/bidimul branch October 7, 2024 08:36
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] linear algebra Linear algebra performance Must go faster
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants