Make setindex! for sparse matrices and vectors not purge stored entries on zero assignment #17404

Sacha0 · 2016-07-13T21:10:43Z

This pull request makes setindex! for SparseMatrixCSCs: (1) not purge allocated entries on zero assignment; and (2) not introduce new allocated entries on zero assignment. See the proposal in #15568 (comment) / extensive discussion in #15568, #9928, #9906, #6769, #5538, #5454, and probably others. Thanks to @KristofferC for getting the ball rolling with #15568!

~~TODO: Expand tests for new behavior.~~ Now with expanded tests!

… expunges stored entries on zero assignment, throws a more explicit BoundsError when needed, and also for simplicity and clarity. Also add tests.

tkelman · 2016-07-14T20:32:28Z

Please see the test failures, can you reproduce them locally? This is a bit of a behavior change but IMO could be okay for before feature freeze if you hurry.

Sacha0 · 2016-07-14T21:30:28Z

The test/show.jl failure should be fixed. Also added a note to NEWS.md. Thanks!

tkelman · 2016-07-14T22:32:46Z

@nanosoldier runbenchmarks(ALL, vs = ":master")

Sacha0 · 2016-07-14T23:50:44Z

AppVeyor i686 string test failure seems unrelated?

tkelman · 2016-07-14T23:54:45Z

I would assume so, but I've never seen that before

From worker 5:       * string               Test Failed
    From worker 5:    Expression: [i for i = eachindex("ḟøøƀäṙ")] == [1,4,6,8,10,12]
    From worker 5:     Evaluated: Array{Dict{VersionNumber,Array{VersionNumber,1}},1}[Dict{VersionNumber,Array{VersionNumber,1}}[#undef],Dict{VersionNumber,Array{VersionNumber,1}}[#undef,#undef,#undef,#undef],Dict{VersionNumber,Array{VersionNumber,1}}[#undef,#undef,#undef,#undef,#undef,#undef],Dict{VersionNumber,Array{VersionNumber,1}}[#undef,#undef,#undef,#undef,#undef,#undef,#undef,#undef],Dict{VersionNumber,Array{VersionNumber,1}}[#undef,#undef,#undef,#undef,#undef,#undef,#undef,#undef,#undef,#undef],Dict{VersionNumber,Array{VersionNumber,1}}[#undef,#undef,#undef,#undef,#undef,#undef,#undef,#undef,#undef,#undef,#undef,#undef]] == [1,4,6,8,10,12]
... snip ...
Exception running test string :
On worker 5:
LoadError: LoadError: There was an error during testing
 in record at .\test.jl:397
 in do_test at .\test.jl:281
 in include_string at .\loading.jl:380
 in include_from_node1 at .\loading.jl:429
 in include_string at .\loading.jl:380
 in include_from_node1 at .\loading.jl:429
 in macro expansion at .\util.jl:180 [inlined]
 in runtests at C:\projects\julia\test\testdefs.jl:7
 in #16 at C:\projects\julia\test\runtests.jl:44
 in #503 at .\multi.jl:1193
 in run_work_thunk at .\multi.jl:844
 in macro expansion at .\multi.jl:1193 [inlined]
 in #502 at .\event.jl:46
while loading C:\projects\julia\test\strings/basic.jl, in expression starting on line 251
while loading C:\projects\julia\test\string.jl, in expression starting on line 5

nanosoldier · 2016-07-15T01:05:53Z

Your benchmark job has completed - no performance regressions were detected. A full report can be found here. cc @jrevels

Sacha0 · 2016-07-15T01:36:58Z

Am I misreading BaseBenchmarks/SparseBenchmarks.jl, or does Nanosoldier not cover sparse setindex! performance?

tkelman · 2016-07-15T01:38:08Z

It might not.

tkelman · 2016-07-15T06:32:24Z

base/sparse/sparsematrix.jl

-    lenI = length(I)
-
-    if (!isempty(I) && (I[1] < 1 || I[end] > m)) || (!isempty(J) && (J[1] < 1 || J[end] > n))
+function setindex!{TvA,Tx<:Number,TiI<:Integer,TiJ<:Integer}(A::SparseMatrixCSC{TvA}, x::Tx,


Tx doesn't need to be a type parameter

Good catch! Related question: To fix the show test failure I reverted comparisons of the form x == zero(Tx) to the former implementation's x == 0, the test failure being due to lack of a zero method for some <:Number. Is zero part of the implicit Number interface? That is, in the long run would keeping x == zero(Tx) and requiring all <:Numbers to implement zero be better than using x == 0, or is x == 0 the preferred expression? Thanks!

I'd rather continue allowing sparse matrices with value types that don't implement zero if at all possible

Cheers, the most recent version should make that so. Thanks!

tkelman · 2016-07-15T06:51:00Z

Is there an API (unexported?) for deleting a specific value from the nonzero structure? dropzeros! does the whole array, is there something more targeted available if you happen to need it?

…expunges stored entries on zero assignment. Also add tests.

…hat, when an assigning zero to entry A[i,j], if A[i,j] is not presently stored, the method does not introduce storage for A[i,j]. Also add tests.

… that it no longer expunges stored entries on zero assignment. Also add tests.

…it no longer expunges stored entries on zero assignment. Also add tests.

Sacha0 · 2016-07-15T18:07:47Z

Is there an API (unexported?) for deleting a specific value from the nonzero structure? dropzeros! does the whole array, is there something more targeted available if you happen to need it?

Not at the moment, but we could introduce one now if you would like that facility to appear in the same PR. If so, name? dropstored! is the best I've thought of so far. Methods? Perhaps introduce a dropstored!(A, i, j) method and rename the existing spdelete!(A, I, J) to dropstored!(A, I, J) for now? Other forms that should exist immediately? Best!

tkelman · 2016-07-15T19:14:36Z

dropstored! does sound like a nicer name than spdelete! I suppose. The implementation should be the same or very close, right?

… from SparseMatrixCSCs.

Sacha0 · 2016-07-15T20:27:50Z

dropstored! does sound like a nicer name than spdelete! I suppose. The implementation should be the same or very close, right?

Prototype implementation of dropstored! (lacking linear and logical indexing) now included. Thoughts? Thanks!

… stored entries on zero assignment. Modify tests accordingly.

Sacha0 · 2016-07-15T21:42:35Z

The most recent commits should make SparseVector behavior consistent with the new SparseMatrixCSC behavior. Best!

…arseVectors. Also introduce associated tests.

…ger purges allocated entries on zero assignment and that dropstored! now exists to drop stored entries.

tkelman · 2016-07-16T09:51:05Z

this may not be all that useful given the likely lack of sparse setindex tests, but it's otherwise probably idle right now so
@nanosoldier runbenchmarks(ALL, vs = ":master")

nanosoldier · 2016-07-16T12:24:19Z

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here. cc @jrevels

KristofferC · 2016-07-17T07:36:47Z

base/sparse/sparsematrix.jl

+
+    if ndel > 0
+        A.colptr[n+1] = rowidx
+        deleteat!(rowvalA, rowidx:nnzA)


This could use resize! instead?

Sacha0 · 2016-07-19T20:34:28Z

Apologies for the slow response (travel Saturday through Monday).

Re. dropstored!(A, I, J), the implementation is cut-and-paste from the former spdelete!. That code would benefit from a thorough rewrite. And likewise for the similarly-written setindex! code. Which is to say that I wholeheartedly agree with the corresponding comments. I forwent most such rewriting to minimize replacement of well-exercised code with unexercised code just prior to the anticipated release candidate freeze and alongside related breaking changes. If such rewriting would be better in this rather than a later PR, however, I can take a shot at it now (timescale unclear). Thanks and best!

tkelman · 2016-07-19T20:37:40Z

I think we'd be fine to merge this now and do cleanup later. Couldn't tell from the diffs that this was reused code.

Sacha0 · 2016-07-19T20:40:51Z

Couldn't tell from the diffs that this was reused code.

Sorry about that. Reshuffling the contents of the commits such that spdelete! clearly transforms into dropstored! might be possible. Should I attempt that?

tkelman · 2016-07-19T20:50:45Z

No, I don't think that's worth the hassle right now. There are other more pressing issues that could use your input.

KristofferC · 2016-07-19T21:09:00Z

+1 for merge as is

Sacha0 · 2016-07-19T22:51:20Z

Thanks for the reviews and merge!

tkelman · 2017-01-31T02:49:34Z

base/sparse/sparsematrix.jl

+    return A
+end
+"""
+    dropstored!(A::SparseMatrix, I::AbstractVector{<:Integer}, J::AbstractVector{<:Integer})


should this say SparseMatrixCSC ?

#20664. Thanks!

Sacha0 force-pushed the reworksetindex branch 2 times, most recently from e4169e0 to e22fe8f Compare July 13, 2016 23:36

Sacha0 changed the title ~~WIP: Make setindex! not purge stored entries on zero assignment~~ Make setindex! not purge stored entries on zero assignment Jul 13, 2016

Sacha0 force-pushed the reworksetindex branch from e22fe8f to 1d4e0d0 Compare July 13, 2016 23:43

KristofferC mentioned this pull request Jul 14, 2016

RFC/WIP: make setindex! not remove zeros from sparsity pattern #15568

Closed

Rewrite setindex!(A::SparseMatrixCSC, v, i, j) such that it no longer…

7241554

… expunges stored entries on zero assignment, throws a more explicit BoundsError when needed, and also for simplicity and clarity. Also add tests.

tkelman added the sparse Sparse arrays label Jul 14, 2016

Sacha0 force-pushed the reworksetindex branch from 1d4e0d0 to f00f724 Compare July 14, 2016 21:24

tkelman reviewed Jul 15, 2016
View reviewed changes

Sacha0 force-pushed the reworksetindex branch from f00f724 to 370ee47 Compare July 15, 2016 17:41

Sacha0 and others added 4 commits July 15, 2016 10:48

Rework setindex!(A::SparseMatrixCSC, v, I, J) such that it no longer …

49712aa

…expunges stored entries on zero assignment. Also add tests.

Revise setindex!(A::SparseMatrixCSC, B::SparseMatrixCSC, I, J) such t…

a464345

…hat, when an assigning zero to entry A[i,j], if A[i,j] is not presently stored, the method does not introduce storage for A[i,j]. Also add tests.

Revise setindex!(A::SparseMatrixCSC, x, I::AbstractMatrix{Bool}) such…

606a8e4

… that it no longer expunges stored entries on zero assignment. Also add tests.

Revise setindex!(A::SparseMatrixCSC, x, I::AbstractVector) such that …

6d3e198

…it no longer expunges stored entries on zero assignment. Also add tests.

Sacha0 force-pushed the reworksetindex branch from 370ee47 to 515e6ff Compare July 15, 2016 17:48

Introduce rudimentary dropstored! methods for dropping stored entries…

de37969

… from SparseMatrixCSCs.

Sacha0 force-pushed the reworksetindex branch from 515e6ff to 67341bf Compare July 15, 2016 20:24

Sacha0 added 2 commits July 15, 2016 14:40

Introduce tests for dropstored!(A, i, j) and dropstored!(A, I, J).

ffc5be2

Revise setindex!(x::SparseVector, v, i) such that it no longer purges…

f98987f

… stored entries on zero assignment. Modify tests accordingly.

Sacha0 force-pushed the reworksetindex branch from 67341bf to 5f0cd08 Compare July 15, 2016 21:40

Sacha0 changed the title ~~Make setindex! not purge stored entries on zero assignment~~ Make setindex! for sparse matrices and vectors not purge stored entries on zero assignment Jul 15, 2016

Sacha0 added 2 commits July 15, 2016 15:06

Introduce rudimentary dropstored! method for dropping entries from Sp…

16971a4

…arseVectors. Also introduce associated tests.

Note in NEWS.md that setindex! for sparse matrices and vectors no lon…

59d3d7c

…ger purges allocated entries on zero assignment and that dropstored! now exists to drop stored entries.

Sacha0 force-pushed the reworksetindex branch from 5f0cd08 to 59d3d7c Compare July 15, 2016 22:07

KristofferC reviewed Jul 17, 2016
View reviewed changes

base/sparse/sparsematrix.jl

if ndel > 0

A.colptr[n+1] = rowidx

deleteat!(rowvalA, rowidx:nnzA)

Copy link

Member

KristofferC Jul 17, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This could use resize! instead?

tkelman merged commit 3647de6 into JuliaLang:master Jul 19, 2016

Sacha0 deleted the reworksetindex branch July 19, 2016 22:50

Sacha0 mentioned this pull request Oct 16, 2016

sparse setindex and stored zeros #9906

Closed

tkelman reviewed Jan 31, 2017

View reviewed changes

Sacha0 mentioned this pull request Feb 18, 2017

Fix typo in dropstored!'s docstring #20664

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Make setindex! for sparse matrices and vectors not purge stored entries on zero assignment #17404

Make setindex! for sparse matrices and vectors not purge stored entries on zero assignment #17404

Sacha0 commented Jul 13, 2016 •

edited

Loading

tkelman commented Jul 14, 2016

Sacha0 commented Jul 14, 2016

tkelman commented Jul 14, 2016

Sacha0 commented Jul 14, 2016

tkelman commented Jul 14, 2016

nanosoldier commented Jul 15, 2016

Sacha0 commented Jul 15, 2016

tkelman commented Jul 15, 2016

tkelman Jul 15, 2016

Sacha0 Jul 15, 2016

tkelman Jul 15, 2016

Sacha0 Jul 15, 2016

tkelman commented Jul 15, 2016 •

edited

Loading

Sacha0 commented Jul 15, 2016

tkelman commented Jul 15, 2016

Sacha0 commented Jul 15, 2016

Sacha0 commented Jul 15, 2016

tkelman commented Jul 16, 2016

nanosoldier commented Jul 16, 2016

KristofferC Jul 17, 2016

Sacha0 commented Jul 19, 2016

tkelman commented Jul 19, 2016

Sacha0 commented Jul 19, 2016

tkelman commented Jul 19, 2016

KristofferC commented Jul 19, 2016

Sacha0 commented Jul 19, 2016

tkelman Jan 31, 2017

Sacha0 Feb 18, 2017

Make setindex! for sparse matrices and vectors not purge stored entries on zero assignment #17404

Make setindex! for sparse matrices and vectors not purge stored entries on zero assignment #17404

Conversation

Sacha0 commented Jul 13, 2016 • edited Loading

tkelman commented Jul 14, 2016

Sacha0 commented Jul 14, 2016

tkelman commented Jul 14, 2016

Sacha0 commented Jul 14, 2016

tkelman commented Jul 14, 2016

nanosoldier commented Jul 15, 2016

Sacha0 commented Jul 15, 2016

tkelman commented Jul 15, 2016

tkelman Jul 15, 2016

Choose a reason for hiding this comment

Sacha0 Jul 15, 2016

Choose a reason for hiding this comment

tkelman Jul 15, 2016

Choose a reason for hiding this comment

Sacha0 Jul 15, 2016

Choose a reason for hiding this comment

tkelman commented Jul 15, 2016 • edited Loading

Sacha0 commented Jul 15, 2016

tkelman commented Jul 15, 2016

Sacha0 commented Jul 15, 2016

Sacha0 commented Jul 15, 2016

tkelman commented Jul 16, 2016

nanosoldier commented Jul 16, 2016

KristofferC Jul 17, 2016

Choose a reason for hiding this comment

Sacha0 commented Jul 19, 2016

tkelman commented Jul 19, 2016

Sacha0 commented Jul 19, 2016

tkelman commented Jul 19, 2016

KristofferC commented Jul 19, 2016

Sacha0 commented Jul 19, 2016

tkelman Jan 31, 2017

Choose a reason for hiding this comment

Sacha0 Feb 18, 2017

Choose a reason for hiding this comment

Sacha0 commented Jul 13, 2016 •

edited

Loading

tkelman commented Jul 15, 2016 •

edited

Loading