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

 Submitted by: Rik Submitted on: 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

Add a New Comment (Rich Markup):

You are not logged in

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>
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.

And when run

Rik <rik5>

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

Attach File(s):

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
• -unavailable- added by rik5 (Submitted the item)
•

Do you think this task is very important?
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):