bugGNU Octave - Bugs: bug #48686, Copy of columns of the matrix

 
 

bug #48686: Copy of columns of the matrix

Submitted by:  None
Submitted on:  Wed 03 Aug 2016 10:38:26 AM UTC  
 
Category: PerformanceSeverity: 3 - Normal
Priority: 5 - NormalItem Group: None
Status: NoneAssigned to: None
Originator Name: PolinaOriginator Email: -unavailable-
Open/Closed: OpenRelease: 4.0.3
Operating System: Microsoft Windows

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Wed 08 Mar 2017 09:23:02 PM UTC, comment #6:

Of course, you are right, this is the same bug. I do not have a solution for the problem of the impossibility of deallocation when the slices are assigned to a cell array. But I think in the present case there could be a possible solution. To state the case: when we have

where range is a contiguous range (idx as an arbitrary index vector), then what happens is that the right-side expression is realized as a slice, and the reference counter to T is incremented. Then T is going to be modified, so it has to be allocated again and copied (because of the incremented reference counter), then the actual values are assigned, at which point the right-side expression expires and the space originally pointed to by T is deallocated. In consequence, the whole vector was copied without need. Of course, there are work-arounds, but the casual octave user will not know what is going on, thus violating the principle of least surprise.

What could be done is to check in any assignment of a subset of the elements whether the right-side expression and the left-side expression are referencing the same object. In this case, either an explicit intermediate object would have to be allocated and first all elements copied into the intermediate object and then back into the object to be modified (which is what happens in T(idx)=T(range)+0;), or (better but closer to the metal) a call to memmove be emitted (giving just a single copy operation per element). However, I have far too little knowledge of the internals of octave to be able to judge whether this is realistic.

Anonymous
Wed 08 Mar 2017 05:31:53 PM UTC, comment #5:

I think this bug report is related to bug #42118.

When you do

the variable B is a reference to a slice of A. It is only when you do

that a copy is made. At this point, however, Octave doesn't know that it could just copy the two elements referenced by B and decrement the reference count for A. So instead, it copies all the data of A and then modifies the copy. This is indeed wasteful. It doesn't happen when working with rows of a matrix because Octave uses column-major storage so you can't create a slice using a row.

Maybe some smarter slice management could fix this problem so that Octave could know about the slice B when looking at A. But I'm not sure it's worth the extra complexity. Or, as I think we've discussed in the other bug report, we could make copies instead of slices when the slice size is small (for some definition of "small").

John W. Eaton <jwe>
Project Administrator
Wed 08 Mar 2017 04:49:14 PM UTC, comment #4:

I made a few further test (see attached script), and it seems to be a quite fundamental problem, not only related to row assignments or even matrices. It can easily be demonstrated like this:
The second assignment (and further, all assignments that directly follow a read) take (at my computer) 0.3 seconds. That is an assignment of two scalar values! The test script shows that this has to be a side effect of using ranges. For some reason, it seems that in the assignments of these two elements of a in the code above the whole vector a is copied, because if I do
the first assignment of b goes fast due to lazy copying, and only when b is changed it takes exactly the 0.3 seconds seen also above. I think this is quite a severe bug.

(file #39943)

Anonymous
Wed 03 Aug 2016 04:47:20 PM UTC, comment #3:

Yes I see what you are seeing!

a work around would be to do a transpose first and then do row copies, and then transpose back again.

Doug Stewart <dastew>
Wed 03 Aug 2016 04:12:46 PM UTC, comment #2:

Hello!

The problem doesn't lay in resizing. It stays when I change the for-loop:

6 minutes instead of 1 second is anyhow too much.

Polina <polinash>
Wed 03 Aug 2016 11:28:57 AM UTC, comment #1:

A question for you.

if T is 50x1000
and after your code
T is 50x1001 then it is going to be slow.

if you predefine T to be 50x1010 by doing T(50,1010)=0;
then the copy will be much faster.

Are you doing this?

Doug Stewart <dastew>
Wed 03 Aug 2016 10:38:26 AM UTC, original submission:

Dear Developers!

Thank you for your work on Octave! It's really useful soft for me nowdays.

I noticed a problem and decided to report hoping that this could improve Octave even more.

It seems that implementation of column copy in matrices has some leakage. When I try to copy columns like
it takes increadibly long time for the whole matrix.
For my programming I wanted to optimize code like
for the case when v = 0.
In the end that did slowed my code instead.

I attach a simple test.
It takes 6 minutes for copying of the columns (flag = 0) and less than one second for analogos copy with addition of 0 * column.

P.S. I tested both with Octave for WIndows and with Octave installed in CygWin environment.
P.P.S. I tested the same on copying of rows and it seems to be fine.

Kind regards,
Polina

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #39943:  test_range_copy.m added by None (2KiB - text/x-objcsrc)
file #38084:  test_matrix_copy.m added by None (464B - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by jwe (Posted a comment)
  • -unavailable- added by polinash (Posted a comment)
  • -unavailable- added by dastew (Posted a comment)
  • -unavailable- added by None (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 2 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 08 Mar 2017 04:49:14 PM UTCNoneAttached File-=>Added test_range_copy.m, #39943
    Wed 03 Aug 2016 10:38:26 AM UTCNoneAttached File-=>Added test_matrix_copy.m, #38084

    Back to the top


    Powered by Savane 3.1-cleanup1