bugGNU Octave - Bugs: bug #38628, bsxfun slow for complex

 
 

bug #38628: bsxfun slow for complex

Submitter:  John Hunt <huntj>
Submitted:  Fri 29 Mar 2013 07:17:37 PM UTC
 
Category:  Interpreter Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * GNU/Linux
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

( Jump to the original submission )

Thu 19 Nov 2020 02:57:22 PM UTC, comment #11: 

I completely agree.  A slight difference in coding style should not cause a 10X difference in performance.  Seem my comment #9 (admittedly from 2018) where I tracked the problem down somewhat.

Rik <rik5>
Project Administrator
Thu 19 Nov 2020 10:49:37 AM UTC, comment #10: 

Hi, here is a piece of code that I found to be very slow in octave:

G = bsxfun(@times, eye(Nc, Nc), shiftdim(F, -2));

(dimensions for F (complex array) were 7x11189 and Nc was equal to 8, computation time was 8.96s)

Then I found this discussion. I effectively managed to recover a normal execution time using the following trick:

Gr = bsxfun(@times, eye(Nc, Nc), shiftdim(real(F), -2));
Gi = bsxfun(@times, eye(Nc, Nc), shiftdim(imag(F), -2));
G = complex(Gr, Gi);

(computation time down to 0.75s !)

That would be great however if the issue could be fixed in a later revision of octave.

Vincent Gras <gvinc>
Thu 22 Mar 2018 06:28:50 PM UTC, comment #9: 

I just reviewed and updated bsxfun for a failure to operate on float complex values (http://hg.savannah.gnu.org/hgweb/octave/rev/bff4a7c7bc39).

I think we should, in the future, try to get rid of the duplicate code paths and simply forward calls to bsxfun on to the code used for broadcasting.

From what I could determine, the issue seems to be that Octave calls complex_array_value() for every single element of the array.  This is slower than calling complex_array_value() once on the array, and then operating on each of the elements.

Rik <rik5>
Project Administrator
Sun 20 Nov 2016 09:58:41 PM UTC, comment #8: 

This (performance) issue is still present in Octave 4.2.0.

Hartmut <hardy>
Tue 13 Oct 2015 05:07:58 PM UTC, comment #7: 

As a follow-up to comment #2, I think the reason it is slower is that bsxfun doesn't have any special optimizations in place for mixed-type operations.

John W. Eaton <jwe>
Project Administrator
Tue 13 Oct 2015 03:07:36 PM UTC, comment #6: 

@Jordi: Did you write the automatic broadcasting code?  I haven't followed this much, but having two different code paths does seem problematic.  Certainly we need to keep bsxfun to be Matlab-compatible, but maybe it should call to the automatic broadcasting code since it seems to be faster.

Rik <rik5>
Project Administrator
Tue 13 Oct 2015 11:17:01 AM UTC, comment #5: 

The broadcast warning is gone, but it was just replaced by a different warning tag (that change is the subject of another bug report).

Also, since @times is handled as a special case in bsxfun, why is it slow for complex?

I was looking at bsxfun last night to see why it is slow for @bitxor, and I got a bit lost.  It seems quite complicated.  Also bad that we now have two ways of doing these operations.  I thought that broadcasting operators were just syntactic sugar for bsxfun, but it seems there are actually two different code paths for the same thing?

John W. Eaton <jwe>
Project Administrator
Tue 13 Oct 2015 04:30:11 AM UTC, comment #4: 

I replaced bsxfun in all cases in Octave core where there might be complex inputs.  See this cset (http://hg.savannah.gnu.org/hgweb/octave/rev/a3b9ee5c040a)

Rik <rik5>
Project Administrator
Fri 09 Oct 2015 04:50:09 PM UTC, comment #3: 

The bug is still there in 4.0.0.

Anyway, now that the "Octave:broadcast" warning is gone, trapz could use broadcasting ? (patch attached for trapz).

(file #35126)

ederag <ederag>
Thu 04 Apr 2013 02:38:11 AM UTC, comment #2: 

Exceedingly strange.  This is, perhaps, a clue.  If dx is promoted to a complex matrix (with 0 for the imaginary part) then the bsxfun call goes back to being extremely fast.

dxc = complex (dx);
tic; r = bsxfun (@times, dxc, ym); toc
Elapsed time is 0.005 seconds.

Rik <rik5>
Project Administrator
Wed 03 Apr 2013 07:01:30 PM UTC, comment #1: 

Hm, this is quite bizarre. I'll try to remember to look into this later.

Jordi GutiƩrrez Hermoso <jordigh>
Project Administrator
Fri 29 Mar 2013 07:17:37 PM UTC, original submission:  

bsxfun is slow for complex array. Much slower than broadcasting.
trapz which uses bsxfun is impacted for instance.

octave:1> dx = ones(1, 1, 1000);
octave:2> ym = ones(1, 1, 1000, 1, 201)+i;
octave:3> tic; r = bsxfun(@times, dx, ym); toc
Elapsed time is 1.45173 seconds.
octave:4> tic; r = bsxfun(@times, dx, ym); toc
Elapsed time is 1.46083 seconds.
octave:5> tic; r1 = dx .* ym; toc
warning: product: automatic broadcasting operation applied
Elapsed time is 0.000883102 seconds.
octave:6> assert(r1, r)
octave:7>

these outputs are from dev
hg id -in
a695ee2dc17e+ 16392+

but it holds also for 3.6.3 and 3.6.4

John Hunt <huntj>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #35126:  octave-4.0.0_trapz.m.patch added by ederag (456B - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by gvinc (Posted a comment)
  • -email is unavailable- added by hardy (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by ederag (Updated the item)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by jordigh (Posted a comment)
  • -email is unavailable- added by huntj (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 project members can vote.

     

     

     

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-10-09 ederag Attached File- Added octave-4.0.0_trapz.m.patch, #35126
    2013-04-03 jordigh StatusNone Confirmed

    Back to the top


    Powered by Savane 3.9