Repository navigation
Conversation
Add a simplification rule: in a block, after declare(a, init, op) with a
literal init, each read of a in the following statements is init, up to the
first statement which may write a (an assign to a, or a declare or thaw of
it). Every element of a declared tensor holds init until it is written.
This lets Finch skip the gaps of a sparse walk when the loop body resets an
accumulator and then copies it out, e.g.
for i = _, j = _
acc .= 0
for k = _
acc[] += V[i] * A[j, i] * A[k, i]
end
if acc[] != 0
X[j, i] = acc[]
end
end
Where V[i] or A[j, i] is zero, the update simplifies away, but the guard
read acc as a run-time value, so the body was not empty and Finch iterated
every j. The declared value was only substituted at lowering, after the
simplifier had decided which phases are empty. With the rule the guard
folds to false, the copy drops, and the gap needs no iterations: on a
20,000 x 20,000 example with an output of SparseByteMap(SparseList), the
kernel goes from 139 ms to 0.26 ms. In finch-tensor-lite, this pattern
comes from per-row accumulators, and on a dblp subgraph-matching query the
kernel goes from 26 s to 18 ms.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
kylebd99
added a commit
to finch-tensor/finch-tensor
that referenced
this pull request
Nov 11, 2026
accumulator_pays kept an accumulator only where its reset and copy couldn't make Finch iterate a sparse loop densely. With finch-tensor/Finch.jl#839, Finch.jl reads a declared tensor as its initial value until it is written, so where a sparse input leaves nothing to accumulate, the copy of the fill simplifies away and the loop skips those points as it would without the accumulator. The gate's estimate also let through accumulators which did densify loops (dblp sparse_8_120: 17 ms to 26 s with Finch.jl 2.2.0). With #839, SDDMM at density 1e-3 goes from 33.5 ms to 9.6 ms and at 1e-2 from 312 ms to 65 ms against main, where the gate had kept 1e-3 unchanged. This needs #839: with Finch.jl 2.2.0, accumulators on sparse loops densify them. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Once reads of a declared tensor simplify away, the gaps of a sparse walk can
be left with loops whose bodies only declare and freeze an accumulator, e.g.
for j = 1:n
acc_data.val = 0.0
end
LLVM removes some of these, but not all: on a dblp subgraph-matching query,
loops like this over every point of two dimensions took the kernel from
146 ms to 1.28 s. Declaring, freezing, and thawing are idempotent, so such a
loop has the effect of one iteration whenever it runs any. Rewrite it as
its body under a sieve on the extent being nonempty, as collapsed does for
idempotent updates. That query is back to 150 ms.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
kylebd99
added a commit
to finch-tensor/finch-tensor
that referenced
this pull request
Nov 12, 2026
This PR's accumulators need #839 so that a sparse loop isn't iterated densely. Revert to the released version once #839 is in one. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
kylebd99
added a commit
to finch-tensor/FinchLiteBenchmarks
that referenced
this pull request
Nov 12, 2026
It pins Finch.jl to finch-tensor/Finch.jl#839, which its accumulators need. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
A workspace which a loop declares and freezes in every iteration, but which few iterations write, pays the whole freeze in each of them. A SparseHash freeze allocated three vectors and a sortperm every time, and counting its buckets divided and resized; a SparseByteMap freeze resized and sorted its list of written positions. When nothing was written since the declare, the level is empty: every parent's run is empty, so the freeze now sets the positions to match and returns. In SpGEMM over A with 4,194,304 rows of which 16 have entries, with a row workspace under the loop over the rows, the kernel takes 54 ms rather than 168 ms with a SparseHash workspace (181 allocations rather than 12.6 million), and 19 ms rather than 26 ms with a SparseByteMap one. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
kylebd99
added a commit
to finch-tensor/finch-tensor
that referenced
this pull request
Nov 12, 2026
accumulator_pays kept an accumulator only where its reset and copy couldn't make Finch iterate a sparse loop densely. With finch-tensor/Finch.jl#839, Finch.jl reads a declared tensor as its initial value until it is written, so where a sparse input leaves nothing to accumulate, the copy of the fill simplifies away and the loop skips those points as it would without the accumulator. The gate's estimate also let through accumulators which did densify loops (dblp sparse_8_120: 17 ms to 26 s with Finch.jl 2.2.0). With #839, SDDMM at density 1e-3 goes from 33.5 ms to 9.6 ms and at 1e-2 from 312 ms to 65 ms against main, where the gate had kept 1e-3 unchanged. This needs #839: with Finch.jl 2.2.0, accumulators on sparse loops densify them. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
kylebd99
added a commit
to finch-tensor/finch-tensor
that referenced
this pull request
Nov 12, 2026
This PR's accumulators need #839 so that a sparse loop isn't iterated densely. Revert to the released version once #839 is in one. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
kylebd99
added a commit
to finch-tensor/finch-tensor
that referenced
this pull request
Nov 12, 2026
finch-tensor/Finch.jl#839 now freezes an untouched SparseHash or SparseByteMap level without allocating or sorting (84eed4b5b), so a workspace which a loop declares and freezes in every iteration but rarely writes costs far less per iteration. Also strip a trailing space from the workspace write comment. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
kylebd99
added a commit
to finch-tensor/FinchLiteBenchmarks
that referenced
this pull request
Nov 12, 2026
Its cost model now counts a workspace's writes in every iteration of the loop it is fused under, and it pins Finch.jl to finch-tensor/Finch.jl#839 at 84eed4b5b, which freezes an untouched SparseHash or SparseByteMap level without allocating or sorting. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Codecov Report❌ Patch coverage is
🚀 New features to boost your workflow:
|
kylebd99
added a commit
to finch-tensor/finch-tensor
that referenced
this pull request
Nov 12, 2026
accumulator_pays kept an accumulator only where its reset and copy couldn't make Finch iterate a sparse loop densely. With finch-tensor/Finch.jl#839, Finch.jl reads a declared tensor as its initial value until it is written, so where a sparse input leaves nothing to accumulate, the copy of the fill simplifies away and the loop skips those points as it would without the accumulator. The gate's estimate also let through accumulators which did densify loops (dblp sparse_8_120: 17 ms to 26 s with Finch.jl 2.2.0). With #839, SDDMM at density 1e-3 goes from 33.5 ms to 9.6 ms and at 1e-2 from 312 ms to 65 ms against main, where the gate had kept 1e-3 unchanged. This needs #839: with Finch.jl 2.2.0, accumulators on sparse loops densify them. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
kylebd99
added a commit
to finch-tensor/finch-tensor
that referenced
this pull request
Nov 12, 2026
This PR's accumulators need #839 so that a sparse loop isn't iterated densely. Revert to the released version once #839 is in one. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
kylebd99
added a commit
to finch-tensor/finch-tensor
that referenced
this pull request
Nov 12, 2026
finch-tensor/Finch.jl#839 now freezes an untouched SparseHash or SparseByteMap level without allocating or sorting (84eed4b5b), so a workspace which a loop declares and freezes in every iteration but rarely writes costs far less per iteration. Also strip a trailing space from the workspace write comment. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
ubuntu-latest is now Ubuntu 26.04, whose glibc refuses to load a shared library that asks for an executable stack. Julia 1.10.6's libopenlibm.so asks for one, so Julia 1.10.6 can't start there; from 1.10.9 on it doesn't. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
… into kbd/declared-reads
willow-ahrens
approved these changes
Nov 13, 2026
willow-ahrens
left a comment
Member
There was a problem hiding this comment.
I'm happy to merge this, and I'd like to see this become part of a more generalized constant propagation pass, as part of finch-tensor/finch-tensor#727. Additionally, we might be able to do this sort of thing more robustly at runtime, if we add a SparseTensor class which holds a boolean sparsity, we could skip the whole array depending on runtime zero-ness or nonzero-ness. This was the idea of the SparseScalar class, which I wonder if you could also use? I remember encoding this transformation a while ago, then removing it, but if you have a use for it I'm happy to merge.
kylebd99
added a commit
to finch-tensor/finch-tensor
that referenced
this pull request
Nov 17, 2026
…ars (#792) * Fix walked() for a MapJoin with arguments it doesn't walk LoopSpaces.walked dropped the arguments that aren't walked (literals, follows, gallops) and applied the op to the rest, so x ** 2 called pow with one argument and the protocolizer crashed with "_Pow.__call__() missing 1 required positional argument: 'b'". When some arguments aren't walked, combine the walked supports as the op would: intersect those whose fill annihilates it, and union the others. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Accumulate fixed output entries in 0-d workspaces, kept in Finch scalars LogicWorkspacer now ends by redirecting each query whose output fields are its outermost loops, and which reduces over further inner loops, into a workspace fused over every output field (add_accumulators). The workspace stores nothing, so it is declared once per outer iteration, accumulates one entry, and is copied into the output after the inner loops. This is unconditional: the protocol cost model has no notion of the load/store chain it removes, and the copy costs one write per outer iteration. The Julia backend passes a 0-d element tensor which a kernel neither reads before resetting nor returns as a fresh Finch.Scalar, through a thin wrapper, so Finch.jl keeps it in a local variable rather than loading and storing lvl_val[1] per update, which LLVM can't promote when other output arrays may alias it. LogicFuseMerger no longer counts reads of a workspace at its fused positions as reads with the loop field, so loops that copy accumulators still merge, and LogicFillDropper drops fills copied out of an accumulator into a sparse output. Row Lp norms (50k x 50k, 25M nnz, COMPILE_JULIA_GALLEY): features_2..4 go from ~70-77 ms to 17-22 ms; features_1 is unchanged at ~15 ms. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Add accumulators only where their copy doesn't densify the loops; fix dropped copies An accumulator's reset and copy run at every point of the loops over the output's fields, so Finch.jl iterates those loops densely even where a sparse input would let it skip points (SDDMM at density 1e-3 went from 37 to 45 ms). LogicWorkspacer now adds an accumulator only where accumulator_pays finds that every table stores the output's fields in dense levels, or the output has no more points than the terms the reduction visits (by the stats). SDDMM 1e-3 is back to 37 ms, 1e-2 goes from 322 to 116 ms, and the row norms keep their accumulators. A copy out of an accumulator into a sparse output, with its fill dropped, is now an overwrite Aggregate, as FormattedForm requires, rather than a bare MapJoin. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Mark accumulators as Temp0D instead of finding them in the Julia backend A Temp0D is a zero dimensional FiberTensor of one element level which a kernel resets before every read and never returns. LogicWorkspacer binds each accumulator it adds to a Temp0DFType, which the formatter keeps, so the Julia backend constructs it as a Finch.Scalar by its type alone: in the kernel prototype, and when a Temp0D is passed in. This replaces local_argument_positions, its dataflow analysis, and the kernel wrapper that substituted fresh scalars. Other backends handle a Temp0D as the zero dimensional FiberTensor it is. Accumulators are only added for outputs with a static fill, which is part of the Finch.Scalar type. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Add accumulators without a cost gate accumulator_pays kept an accumulator only where its reset and copy couldn't make Finch iterate a sparse loop densely. With finch-tensor/Finch.jl#839, Finch.jl reads a declared tensor as its initial value until it is written, so where a sparse input leaves nothing to accumulate, the copy of the fill simplifies away and the loop skips those points as it would without the accumulator. The gate's estimate also let through accumulators which did densify loops (dblp sparse_8_120: 17 ms to 26 s with Finch.jl 2.2.0). With #839, SDDMM at density 1e-3 goes from 33.5 ms to 9.6 ms and at 1e-2 from 312 ms to 65 ms against main, where the gate had kept 1e-3 unchanged. This needs #839: with Finch.jl 2.2.0, accumulators on sparse loops densify them. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Choose COMPILE_JULIA_GALLEY's formats with CostFormatter COMPILE_JULIA_GALLEY now searches formats under the protocol cost model with a CostFormatter, and its workspacer prices workspaces with the default format_cost, which searches formats the same way, rather than with galley_format_cost. Galley's rules stored intermediates that a later query walks as SparseByteMaps, whose rows are read scattered across a dense value array, and stored fairly dense outputs as SparseByteMaps, whose positions are sorted when frozen. For the A @ B @ C microbenchmark (5000 x 5000, C density d), with the same plans otherwise: d GalleyFormatter CostFormatter 1e-4 95.5 ms 24.5 ms output Dense(Dense), not Dense(SparseByteMap) 1e-3 317.1 ms 95.8 ms BC through a workspace into Dense(SparseList) The other densities are unchanged, and the results match. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * simplify fix * drop test * Satisfy ty in the Temp0D scalar test Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Pin Finch.jl to finch-tensor/Finch.jl#839 until it is released This PR's accumulators need #839 so that a sparse loop isn't iterated densely. Revert to the released version once #839 is in one. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Fix walked() for a MapJoin with arguments it doesn't walk LoopSpaces.walked dropped the arguments that aren't walked (literals, follows, gallops) and applied the op to the rest, so x ** 2 called pow with one argument and the protocolizer crashed with "_Pow.__call__() missing 1 required positional argument: 'b'". When some arguments aren't walked, combine the walked supports as the op would: intersect those whose fill annihilates it, and union the others. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * simplify fix * drop test * Accumulate fixed output entries in 0-d workspaces, kept in Finch scalars LogicWorkspacer now ends by redirecting each query whose output fields are its outermost loops, and which reduces over further inner loops, into a workspace fused over every output field (add_accumulators). The workspace stores nothing, so it is declared once per outer iteration, accumulates one entry, and is copied into the output after the inner loops. This is unconditional: the protocol cost model has no notion of the load/store chain it removes, and the copy costs one write per outer iteration. The Julia backend passes a 0-d element tensor which a kernel neither reads before resetting nor returns as a fresh Finch.Scalar, through a thin wrapper, so Finch.jl keeps it in a local variable rather than loading and storing lvl_val[1] per update, which LLVM can't promote when other output arrays may alias it. LogicFuseMerger no longer counts reads of a workspace at its fused positions as reads with the loop field, so loops that copy accumulators still merge, and LogicFillDropper drops fills copied out of an accumulator into a sparse output. Row Lp norms (50k x 50k, 25M nnz, COMPILE_JULIA_GALLEY): features_2..4 go from ~70-77 ms to 17-22 ms; features_1 is unchanged at ~15 ms. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Add accumulators only where their copy doesn't densify the loops; fix dropped copies An accumulator's reset and copy run at every point of the loops over the output's fields, so Finch.jl iterates those loops densely even where a sparse input would let it skip points (SDDMM at density 1e-3 went from 37 to 45 ms). LogicWorkspacer now adds an accumulator only where accumulator_pays finds that every table stores the output's fields in dense levels, or the output has no more points than the terms the reduction visits (by the stats). SDDMM 1e-3 is back to 37 ms, 1e-2 goes from 322 to 116 ms, and the row norms keep their accumulators. A copy out of an accumulator into a sparse output, with its fill dropped, is now an overwrite Aggregate, as FormattedForm requires, rather than a bare MapJoin. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Mark accumulators as Temp0D instead of finding them in the Julia backend A Temp0D is a zero dimensional FiberTensor of one element level which a kernel resets before every read and never returns. LogicWorkspacer binds each accumulator it adds to a Temp0DFType, which the formatter keeps, so the Julia backend constructs it as a Finch.Scalar by its type alone: in the kernel prototype, and when a Temp0D is passed in. This replaces local_argument_positions, its dataflow analysis, and the kernel wrapper that substituted fresh scalars. Other backends handle a Temp0D as the zero dimensional FiberTensor it is. Accumulators are only added for outputs with a static fill, which is part of the Finch.Scalar type. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Add accumulators without a cost gate accumulator_pays kept an accumulator only where its reset and copy couldn't make Finch iterate a sparse loop densely. With finch-tensor/Finch.jl#839, Finch.jl reads a declared tensor as its initial value until it is written, so where a sparse input leaves nothing to accumulate, the copy of the fill simplifies away and the loop skips those points as it would without the accumulator. The gate's estimate also let through accumulators which did densify loops (dblp sparse_8_120: 17 ms to 26 s with Finch.jl 2.2.0). With #839, SDDMM at density 1e-3 goes from 33.5 ms to 9.6 ms and at 1e-2 from 312 ms to 65 ms against main, where the gate had kept 1e-3 unchanged. This needs #839: with Finch.jl 2.2.0, accumulators on sparse loops densify them. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Choose COMPILE_JULIA_GALLEY's formats with CostFormatter COMPILE_JULIA_GALLEY now searches formats under the protocol cost model with a CostFormatter, and its workspacer prices workspaces with the default format_cost, which searches formats the same way, rather than with galley_format_cost. Galley's rules stored intermediates that a later query walks as SparseByteMaps, whose rows are read scattered across a dense value array, and stored fairly dense outputs as SparseByteMaps, whose positions are sorted when frozen. For the A @ B @ C microbenchmark (5000 x 5000, C density d), with the same plans otherwise: d GalleyFormatter CostFormatter 1e-4 95.5 ms 24.5 ms output Dense(Dense), not Dense(SparseByteMap) 1e-3 317.1 ms 95.8 ms BC through a workspace into Dense(SparseList) The other densities are unchanged, and the results match. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Satisfy ty in the Temp0D scalar test Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Pin Finch.jl to finch-tensor/Finch.jl#839 until it is released This PR's accumulators need #839 so that a sparse loop isn't iterated densely. Revert to the released version once #839 is in one. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * update cost model * Pin Finch.jl to #839's empty-freeze fast paths finch-tensor/Finch.jl#839 now freezes an untouched SparseHash or SparseByteMap level without allocating or sorting (84eed4b5b), so a workspace which a loop declares and freezes in every iteration but rarely writes costs far less per iteration. Also strip a trailing space from the workspace write comment. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Accumulate fixed output entries in 0-d workspaces, kept in Finch scalars LogicWorkspacer now ends by redirecting each query whose output fields are its outermost loops, and which reduces over further inner loops, into a workspace fused over every output field (add_accumulators). The workspace stores nothing, so it is declared once per outer iteration, accumulates one entry, and is copied into the output after the inner loops. This is unconditional: the protocol cost model has no notion of the load/store chain it removes, and the copy costs one write per outer iteration. The Julia backend passes a 0-d element tensor which a kernel neither reads before resetting nor returns as a fresh Finch.Scalar, through a thin wrapper, so Finch.jl keeps it in a local variable rather than loading and storing lvl_val[1] per update, which LLVM can't promote when other output arrays may alias it. LogicFuseMerger no longer counts reads of a workspace at its fused positions as reads with the loop field, so loops that copy accumulators still merge, and LogicFillDropper drops fills copied out of an accumulator into a sparse output. Row Lp norms (50k x 50k, 25M nnz, COMPILE_JULIA_GALLEY): features_2..4 go from ~70-77 ms to 17-22 ms; features_1 is unchanged at ~15 ms. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Add accumulators only where their copy doesn't densify the loops; fix dropped copies An accumulator's reset and copy run at every point of the loops over the output's fields, so Finch.jl iterates those loops densely even where a sparse input would let it skip points (SDDMM at density 1e-3 went from 37 to 45 ms). LogicWorkspacer now adds an accumulator only where accumulator_pays finds that every table stores the output's fields in dense levels, or the output has no more points than the terms the reduction visits (by the stats). SDDMM 1e-3 is back to 37 ms, 1e-2 goes from 322 to 116 ms, and the row norms keep their accumulators. A copy out of an accumulator into a sparse output, with its fill dropped, is now an overwrite Aggregate, as FormattedForm requires, rather than a bare MapJoin. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Mark accumulators as Temp0D instead of finding them in the Julia backend A Temp0D is a zero dimensional FiberTensor of one element level which a kernel resets before every read and never returns. LogicWorkspacer binds each accumulator it adds to a Temp0DFType, which the formatter keeps, so the Julia backend constructs it as a Finch.Scalar by its type alone: in the kernel prototype, and when a Temp0D is passed in. This replaces local_argument_positions, its dataflow analysis, and the kernel wrapper that substituted fresh scalars. Other backends handle a Temp0D as the zero dimensional FiberTensor it is. Accumulators are only added for outputs with a static fill, which is part of the Finch.Scalar type. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Add accumulators without a cost gate accumulator_pays kept an accumulator only where its reset and copy couldn't make Finch iterate a sparse loop densely. With finch-tensor/Finch.jl#839, Finch.jl reads a declared tensor as its initial value until it is written, so where a sparse input leaves nothing to accumulate, the copy of the fill simplifies away and the loop skips those points as it would without the accumulator. The gate's estimate also let through accumulators which did densify loops (dblp sparse_8_120: 17 ms to 26 s with Finch.jl 2.2.0). With #839, SDDMM at density 1e-3 goes from 33.5 ms to 9.6 ms and at 1e-2 from 312 ms to 65 ms against main, where the gate had kept 1e-3 unchanged. This needs #839: with Finch.jl 2.2.0, accumulators on sparse loops densify them. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Choose COMPILE_JULIA_GALLEY's formats with CostFormatter COMPILE_JULIA_GALLEY now searches formats under the protocol cost model with a CostFormatter, and its workspacer prices workspaces with the default format_cost, which searches formats the same way, rather than with galley_format_cost. Galley's rules stored intermediates that a later query walks as SparseByteMaps, whose rows are read scattered across a dense value array, and stored fairly dense outputs as SparseByteMaps, whose positions are sorted when frozen. For the A @ B @ C microbenchmark (5000 x 5000, C density d), with the same plans otherwise: d GalleyFormatter CostFormatter 1e-4 95.5 ms 24.5 ms output Dense(Dense), not Dense(SparseByteMap) 1e-3 317.1 ms 95.8 ms BC through a workspace into Dense(SparseList) The other densities are unchanged, and the results match. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Satisfy ty in the Temp0D scalar test Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * Pin Finch.jl to finch-tensor/Finch.jl#839 until it is released This PR's accumulators need #839 so that a sparse loop isn't iterated densely. Revert to the released version once #839 is in one. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * update cost model * Pin Finch.jl to #839's empty-freeze fast paths finch-tensor/Finch.jl#839 now freezes an untouched SparseHash or SparseByteMap level without allocating or sorting (84eed4b5b), so a workspace which a loop declares and freezes in every iteration but rarely writes costs far less per iteration. Also strip a trailing space from the workspace write comment. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> * loosen 0d workspace guard * cleanup --------- Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
This branch has not been deployed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Does two things 1) it adds better simplification for the case where a tensor is never actually written to after being declared (this comes up with scalar workspaces a lot), essentially just replacing it with its declare value for reads before any writes. 2) it adds some fast paths to speed up freeze statements in SparseBytemap and SparseHash in the case that no writes were performed.
CLAUDE SLOP BELOW
Adds a simplification rule. In a block, after
declare(a, init, op)with a literalinit, each read ofain the following statements becomesinit, up to the first statement that may writea: an assignment to it, or anotherdeclareorthawof it. The rule holds for any tensor, because every element of a newly declared tensor holdsinituntil something writes it.Why. Without the rule, a loop body that resets an accumulator and then copies it out stops Finch from skipping the gaps of a sparse walk:
Where
V[i]orA[j, i]is zero, the update simplifies away, but the guard readsaccas a value only known at run time. So the body isn't empty, and Finch iterates everyj. Finch already substitutes the declared value, but only during lowering, after the simplifier has decided which phases are empty. The generated gap loops containcond = 0.0 != 0.0. With the rule, the guard folds tofalseand the copy is dropped.Measurements:
SparseByteMap(SparseList)Results are unchanged.
A second rule handles what the first leaves behind. Once those reads simplify away, a gap can be left with loops whose bodies only declare and freeze the accumulator (
for j = 1:n; acc_data.val = 0.0; end). LLVM removes some of these loops, but not all. On a dblp query, such loops over every point of two dimensions took the kernel from 146 ms to 1.28 s. Declaring, freezing and thawing are idempotent, so a loop whose body only does those has the effect of one iteration whenever it runs any. The rule rewrites it as its body under a sieve on the extent being non-empty, ascollapsedalready does for idempotent updates. That query is back to 150 ms, against 146 ms without accumulators.Tests. Adds a regression test to
issue_tests.jl. It checks that the generated code neither compares the reset value with0(which fails without the first rule) nor contains a loop that only resets the accumulator (which fails without the second). It also checks the result against a dense computation. A full localPkg.testrun, excludingparallel, gave 298,766 passed, 2 broken and 1 failed. The failure isbinsparse_compliance: its shell script callsjuliaby name, and Julia wasn't onPATHon that machine. The Python part of that test passed. The reference-output comparisons all pass, so no generated references needed regenerating.🤖 Generated with Claude Code