Wed 06 Sep 2017 01:06:24 AM UTC, comment #8:
Only way to know was to benchmark it. Indeed, the resizing of the SparseRep was not a driver of execution time. However, I did find that using std::fill_n over only the non-zero columns provided ~20% savings.
The benchmark code was
By putting everything in the next to last column this was clearly worst case, but it did beat the handcoded for loop. Replacement code was
I checked in the full cset here (http://hg.savannah.gnu.org/hgweb/octave/rev/584971932def).
|
Mon 04 Sep 2017 08:38:08 AM UTC, comment #7:
Rik, I'm not sure the gains will be great doing what you suggest. Creating an empty SparseRep and then resizing it once doesn't seem to be a large extra cost, as the creation of the empty SparseRep should be a low cost operation
D.
|
Fri 01 Sep 2017 09:22:31 PM UTC, comment #6:
Perhaps we should step away from this and look at it a different way. Why does the constructor need to create an empty SparseRep and then use change_capacity to increase it? I understand from a code clarity point-of-view that it guarantees a valid object is returned by the function regardless of which twists and turns the code takes through the various if/elseif branches. However, given that this is a base library, I think it is more important to emphasize performance.
If we wait in the Sparse constructor until we know the number of elements, then we can use the this SparseRep constructor
Because of the empty initializer list, the variables d, r, and c will all be filled with zeros. That means that only the cidx entries from c(0) to nc need to be filled in rather than running over all columns nc.
Instead of the newly changed code from jwe:
It could be
This would also avoid some for loops and potential new[] operators in change_capacity.
|
Wed 30 Aug 2017 06:56:36 PM UTC, comment #5:
The currently applied patch has a for loop over 'nc' which is the number of columns which could be quite large for a sparse matrix, say 1e7. David's suggestion would improve performance as the for loop would only be over the first c(0) blank columns which should be much less than 'nc' unless all of the data is on the right-hand side of the sparse matrix.
However, I couldn't get the code to work. I tried this
According to David, all values above should be 'nz' already from the call to change_capacity. However, I used an assert and found that wasn't the case.
change_capacity() is in Sparse.h
And change_length is in Sparse.cc
This would seem to set the last entries to the new_nz only on a truncation. So, in the constructor which is growing the sparse array (nz = 0 to true nz0), maybe we have to keep the loop? Comments?
|
Tue 29 Aug 2017 01:59:47 PM UTC, comment #4:
All values of xcidx will be initialised to nz by the call to change_capacity just before hand
D.
|
Tue 29 Aug 2017 01:47:18 PM UTC, comment #3:
I pushed this changeset:
http://hg.savannah.gnu.org/hgweb/octave/rev/520c37805969
This seems to work for me, but if there is a better fix, let me know.
|
Tue 29 Aug 2017 01:34:12 PM UTC, comment #2:
If I understand correctly, the xcidx vector has length nc+1 and with this code, if the specified column is less than nc, then the remaining elements would be uninitialized. Is that OK?
Also, is there any check to ensure that c(0) > 0? Maybe it can't be less than zero since it is supposed to be an element of an index vector?
Anyway, I came up with this instead:
but I don't know whether it is correct to set all the remaining xcidx elements to new_nz.
|
Tue 29 Aug 2017 01:02:48 PM UTC, comment #1:
I haven't done much with Octave for a long while, but as I wrote this code I had a quick look at it.
The specialisation for sparse column vectors was added to my code by Jaroslav, and he didn't take into account the possibility that the sparse column vector could in fact be a matrix. The fix is relatively easy. Looking at lines 362-363 of
These implicitly assume that everything is in the first column. These should be replaced with
I don't even have a octave source tree on my machine to test this so someone else will have to work this up as a hg chageset
D.
|
Mon 28 Aug 2017 07:39:57 PM UTC, original submission:
The following should produce a sparse matrix with non-zeros in the 2nd column.
But it puts them in the first column.
In fact, the following will put the non-zeros in column 1 for any scalar value of j between 1 and 5.
So it appears that it is ignoring any scalar value passed in as a column index and just using 1 instead. A scalar row index, on the other hand, is handled correctly.
And Matlab also handles the scalar column index as expected.
|