bugGNU Octave - Bugs: bug #39834, vertcat() very slow compared to...

 
 

bug #39834: vertcat() very slow compared to horzcat()

Submitter:  Rik <rik5>
Submitted:  Wed 21 Aug 2013 04:18:10 AM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Thu 24 Nov 2016 11:13:43 PM UTC, comment #3: 

The behavior is still present in 4.2.0.
Moreover if called from the prompt


~$ octave bm_vertcat.m
Elapsed time is 0.020494 seconds.
Elapsed time is 0.0017941 seconds.


while if called from the command window in the GUI


octave-gui:1> bm_vertcat
Elapsed time is 0.0471382 seconds.
Elapsed time is 0.00223804 seconds.


Averages give ~10X for prompt and ~19X for gui.

Juan Pablo Carbajal <juanpi>
Group Member
Fri 06 Sep 2013 03:00:27 PM UTC, comment #2: 

I was aware of the ordering of data in memory; just really surprised that it makes a 9X difference rather than a 2-3X difference.  Matlab is still better than Octave in that they are only 6X slower.  I'll leave the bug open in case anyone else has ideas on how to improve this, or wants to try coding the transpose, horzcat, transpose solution.

Rik <rik5>
Group administrator
Fri 23 Aug 2013 05:38:35 PM UTC, comment #1: 

On the one hand, I would point out that this is an inherent property of how horzcat and vertcat work at a physical level.  Matrices are stored "column at a time" in memory.  Thus, the horzcat operation is completed quite easily by concatenating the N chunks of data, and setting the right array dimensions.  vertcat is inherently more complicated because it requires splicing columns together in order to achieve the desired result.  As such, this performance time difference is also exhibited in MATLAB.

That said, I found this interesting result when run in matlab:

    >> N=1e4;
    >> x = repmat({[1:N]'},N,1);  
    >> tic; y2 = horzcat(x{:}); toc
    Elapsed time is 0.213414 seconds.
    >> x = repmat({[1:N]},N,1);
    >> tic; y1 = vertcat(x{:}); toc
    Elapsed time is 1.277119 seconds.
    >> tic; x=cellfun(@(xx)xx',x,'UniformOutput',0); y1 = horzcat(x{:})'; toc
    Elapsed time is 0.424479 seconds.

In other words, not only do we get much better time performance using horzcat, but it is sufficiently better that in this particular case, it is more performant to transpose, use horzcat, and transpose again, rather than a simple vertcat.  However, the following example demonstrates that this is not true in cases where the first transpose operation is slower:

    >> x = repmat({repmat([1:N],10,1)},N/10,1);                             
    >> clear y1;
    >> tic; y1 = vertcat(x{:}); toc
    Elapsed time is 0.318404 seconds.
    >> clear y1
    >> tic; x=cellfun(@(xx)xx',x,'UniformOutput',0); y1 = horzcat(x{:})'; toc
    Elapsed time is 0.642182 seconds.

Interestingly, the analogous case with just horzcat by itself (i.e. to produce y2) is not appreciably faster in this case than it was before.  The conclusion we reach is that the time required for horzcat is essentially the time required to allocate and copy the necessary memory, whereas vertcat may require some extra time for the control operations that get the memory in the right places.

It might be possible to optimize these operations further, but as you can see, there are lots of cases and lots of trade-offs.  For example, even adding a heuristic to check the sizes of the matrices to try to optimize the examples above would significantly penalize a case in which vertcat needed to be called many times.  Seems to me not to be worth the development time, but I'm not the one who gets to make the call.

Anonymous
Wed 21 Aug 2013 04:18:10 AM UTC, original submission:  

Running what looks to be equivalent workloads through vertcat and horzcat produce very different running times---about 9X slower for vertcat.  The code is attached below as bm_vertcat.m.


N = 1e3;
################################################################################
clear y1;
y1 = zeros (N,N);
x = repmat ({[1:N]}, N, 1);
tic;
y1 = vertcat (x{:});
toc

clear y2;
x = repmat ({[1:N]'}, 1, N);
tic;
y2 = horzcat (x{:});
toc


And when run


Elapsed time is 0.095994 seconds.
Elapsed time is 0.010987 seconds.


Rik <rik5>
Group administrator

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #28891:  bm_vertcat.m added by rik5 (454B - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by juanpi (Posted a comment)
  • -email is unavailable- added by rik5 (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2013-08-21 rik5 Attached File- Added bm_vertcat.m, #28891

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code