bugGNU Octave - Bugs: bug #42716, Transpose multiply not detected

 
 

bug #42716: Transpose multiply not detected

Submitter:  Ceral Paquet <octavebugs>
Submitted:  Wed 09 Jul 2014 10:57:02 AM UTC
   
 
Category:  Libraries Severity:  4 - Important
Priority:  5 - Normal Item Group:  Regression
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 03 Feb 2015 08:32:09 PM UTC, comment #9: 

I applied just the portion of David's patch which dealt with rvalues for binary operators with a transposed operand (http://hg.savannah.gnu.org/hgweb/octave/rev/bf88eab464b8).

The multiply/transpose is detected and executes much faster than before.  'make check' passes all tests.  I verified that the final results of the multiplication of random matrices was the same in both 3.8.2 and the dev branch.

Closing report.

Rik <rik5>
Group administrator
Sat 12 Jul 2014 01:25:56 PM UTC, comment #8: 

In the #41428 I'd assumed that as Jaroslav didn't supply the

tree_compound_binary_expression::rvalue

method the compound operator code was in fact never used, however this bug report implies that the underlying code was in fact used at one time, so if there are bugs lurking in the existing code we should have seen reports from the 3.4 and 3.6 versions of Octave.

Adding the rvalue method definitely makes 3.8 use the code, and I don't understand yet why it was used in 3.6, but since the underlying code was being used I think we code probably apply the rvalue part of the patch to the stable branch without too much risk, especially as it seems to pass correctly "make check"

D.

David Bateman <dbateman>
Group Member
Fri 11 Jul 2014 06:22:23 PM UTC, comment #7: 

Maybe it should just be applied to the default branch since this is just a performance regression and could cause some trouble if there are bugs lurking in the code that has not been used until now?

John W. Eaton <jwe>
Group administrator
Fri 11 Jul 2014 03:51:02 PM UTC, comment #6: 

The backport is easy. You'd just have to take the

tree_compound_binary_expression::rvalue
tree_compound_binary_expression::rvalue1
tree_compound_binary_expression::rvalue_ok

methods and their declarations from my patch and leave the rest. The rest is for the !&& and !|| operators. I suppose it should be two changesets in any case.

I'm fairly confident the patch is ok, but I know some of the corners case of the !&& and !|| operators aren't accelerated but probably could be, so the patch is functional but not complete

David

David Bateman <dbateman>
Group Member
Fri 11 Jul 2014 03:44:24 PM UTC, comment #5: 

@David: I applied your patch and, indeed, it fixes the problems with transpose/multiply detection.

The patch is in areas of the source code where I rarely work so I don't feel comfortable reviewing it.  If you're confident, go ahead and push it or maybe ask jwe to take a look.

Since this is a regression, we'd like to backport the fix to the stable branch as well.  Is this possible without breaking the stable 3.8 ABI?  I'm not sure it is without separating the fix for transpose/multiply from the addition of the new operatiors such as &~.

Rik <rik5>
Group administrator
Fri 11 Jul 2014 02:34:20 PM UTC, comment #4: 

Rik,

In fact the patch I submitted in #41428

http://savannah.gnu.org/bugs/index.php?41428

should fix this problem. I've always wanted to finish it off with some more testing, but by applying the patch in #41428 it should be easy to confirm that the approach proposed fixes the issue

David

Anonymous
Wed 09 Jul 2014 08:45:23 PM UTC, comment #3: 

This is the same bug as #42314 that you reported earlier, but in a slightly different guise.  Octave correctly detected multiply/transpose combination in 3.6.4, but this broke in 3.8.0 and now all subsequent versions.

Rik <rik5>
Group administrator
Wed 09 Jul 2014 12:16:08 PM UTC, comment #2: 

Confirmed, but no difference for me with ATLAS either. I don't see any speed difference between symmetric and non-symmetric multiplies with your example using any of the 3 BLAS implementations available on Debian.

Mike Miller <mtmiller>
Group Member
Wed 09 Jul 2014 11:17:20 AM UTC, comment #1: 

Following the tip from this page:

http://wiki.octave.org/Tips_and_tricks#Changing_BLAS

I noticed the speedup does occur when using /usr/lib/atlas-base/atlas/libblas.so.3 but not with /usr/lib/openblas-base/libopenblas.so.0. Overall however the OpenBLAS is much faster.

Ceral Paquet <octavebugs>
Wed 09 Jul 2014 10:57:02 AM UTC, original submission:  

I was reading this page

  http://www.walkingrandomly.com/?p=4912

regarding the ability of MATLAB to detect when the result of a matrix multiply is symmetric so it can speed up the calculation. In the comments that Octave too has this ability.

These are the results from the blog (MATLAB):

  >> a=rand(4000);
  >> b=rand(4000);
  >> tic;a*a';toc
  Elapsed time is 0.887524 seconds.
  >> tic;a*b;toc 
  Elapsed time is 1.473208 seconds.
  >> tic;b*b';toc
  Elapsed time is 0.966085 seconds.

However in Octave 3.8.1, I find all the multiplies take the same time, as if the full calculation is done for each.

  >> a=rand(4000);
  >> b=rand(4000);
  >> tic;a*b;toc
  Elapsed time is 2.18606 seconds.
  >> tic;a*a';toc
  Elapsed time is 2.19176 seconds.
  >> tic;b*b';toc
  Elapsed time is 2.18921 seconds.
  >> tic;a'*a;toc
  Elapsed time is 2.21384 seconds.

Ceral Paquet <octavebugs>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Digest:
   bug dependencies.

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by dbateman (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by octavebugs (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.

     

    Follow 10 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-02-03 rik5 StatusConfirmed Fixed
        Open/ClosedOpen Closed
    2014-07-09 rik5 Severity1 - Wish 4 - Important
    2014-07-09 rik5 Dependencies- Depends on bugs #42314
    2014-07-09 rik5 Item GroupPerformance Regression
    2014-07-09 mtmiller CategoryNone Libraries
        Severity3 - Normal 1 - Wish
        Item GroupNone Performance
        StatusNone Confirmed
        Release3.8.1 dev

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code