Skip to content

Avoid allocations in views of views#53231

Merged
N5N3 merged 5 commits intomasterfrom
jishnub/subarrayreindexview
Feb 8, 2024
Merged

Avoid allocations in views of views#53231
N5N3 merged 5 commits intomasterfrom
jishnub/subarrayreindexview

Conversation

@jishnub
Copy link
Copy Markdown
Member

@jishnub jishnub commented Feb 7, 2024

Currently, views-of-views construct their re-indexed indices by slicing into the parent indices. This PR changes this to use views of the parent indices instead. This makes the operation faster and non-allocating if the parentindices for the original view are Vectors.

julia> a = rand(200, 200);

julia> av = view(a, collect.(axes(a))...);

julia> @btime view($av, axes($av)...);
  312.393 ns (4 allocations: 3.25 KiB) # master
  7.354 ns (0 allocations: 0 bytes) # PR

Indexing into the resulting view seems equally fast in simple cases:

julia> av2 = view(av, axes(av)...);

julia> @btime sum($av2);
  66.883 μs (0 allocations: 0 bytes) # master
  66.888 μs (0 allocations: 0 bytes) # PR

julia> av2 = view(av, collect.(axes(av))...);

julia> @btime sum($av2);
  66.886 μs (0 allocations: 0 bytes) # master
  66.891 μs (0 allocations: 0 bytes) # PR

@jishnub jishnub added performance Must go faster arrays [a, r, r, a, y, s] labels Feb 7, 2024
@N5N3
Copy link
Copy Markdown
Member

N5N3 commented Feb 7, 2024

IIUC the benchmark above is somehow "biased"
The performance of sequential indexing into a view is more unstable than Array. A simple example

julia> a = randn(100);

julia> b1 = a[100:-1:1]; b2 = view(a, 100:-1:1);   # This is bad

julia> @btime sum($b1)
  6.900 ns (0 allocations: 0 bytes)
-13.657826292798031

julia> @btime sum($b2)
  30.282 ns (0 allocations: 0 bytes)
-13.65782629279803

julia> c1 = a[1:100]; c2 = view(a, 1:100);   # This is good

julia> @btime sum($c1)
  7.000 ns (0 allocations: 0 bytes)
-13.65782629279803

julia> @btime sum($c2)
  7.207 ns (0 allocations: 0 bytes)
-13.65782629279803

In this sense we'd better reduce the reindex layer when possible.

@vtjnash
Copy link
Copy Markdown
Member

vtjnash commented Feb 7, 2024

@N5N3 That is a good observation. Is that something the user can choose however at the point of creating the subarray, as they can either collect indexes into a fast container, or leave them in a slower view?

@N5N3
Copy link
Copy Markdown
Member

N5N3 commented Feb 7, 2024

Is that something the user can choose however at the point of creating the subarray, as they can either collect indexes into a fast container, or leave them in a slower view?

Emm, user can always handle nested view manually if it does matter. In this sense, it looks the correct direction to avoid allocation if possible.

Co-authored-by: N5N3 <2642243996@qq.com>
@N5N3 N5N3 merged commit 2bd4cf8 into master Feb 8, 2024
@N5N3 N5N3 deleted the jishnub/subarrayreindexview branch February 8, 2024 06:22
@KristofferC
Copy link
Copy Markdown
Member

Note, #56760 was bisected to be caused by this PR.

@jishnub
Copy link
Copy Markdown
Member Author

jishnub commented Jan 13, 2025

Given the significant scope of regression in TTFX, we should probably revert this for now.

@oscardssmith
Copy link
Copy Markdown
Member

do we only want to revert the N dimensional case of this? The 1 and 2 dimensional version shouldn't be causing problems.

@mbauman
Copy link
Copy Markdown
Member

mbauman commented Jan 13, 2025

No, this is reproducible with 1-d as well. See my simultaneous MWE over at #56760 (comment). I think the better option would be to add yet more indirection and have reindex call a flavor of maybeview that uses copy-indexing if there's already more than one or two layers of SubArray.

KristofferC pushed a commit that referenced this pull request Jan 14, 2025
oscardssmith pushed a commit that referenced this pull request Jan 14, 2025
This reverts commit 2bd4cf8. (#53231)

The reason for this revert is that it caused exponential blowup of types
in iterated views causing some packages to simply freeze when doing
something that worked ok in 1.10.

In my opinion, the perf gain from the PR is not outweighed by the "risk"
of hitting this compilation blowup case.

Fixes #56760.

Co-authored-by: KristofferC <kristoffer.carlsson@juliacomputing.com>
KristofferC added a commit that referenced this pull request Jan 14, 2025
This reverts commit 2bd4cf8. (#53231)

The reason for this revert is that it caused exponential blowup of types
in iterated views causing some packages to simply freeze when doing
something that worked ok in 1.10.

In my opinion, the perf gain from the PR is not outweighed by the "risk"
of hitting this compilation blowup case.

Fixes #56760.

Co-authored-by: KristofferC <kristoffer.carlsson@juliacomputing.com>
(cherry picked from commit b23f557)
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 this pull request may close these issues.

6 participants