bugGNU Octave - Bugs: bug #48085, Slow solving simultaneous...

 
 

bug #48085: Slow solving simultaneous equations by LU decomposition for octave 4 on windows

Submitter:  Tatsuro MATSUOKA <tmacchant>
Submitted:  Thu 02 Jun 2016 05:24:46 AM UTC
   
 
Category:  Performance Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Invalid / Not an Octave Bug Assigned to:  None
Originator Name:  Tatsuro MATSUOKA Open/Closed:  * Closed
Release:  * other Operating System:  * Microsoft Windows
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 20 Jun 2016 04:00:09 PM UTC, comment #20: 

@Tatsuro: Closing this report per your request.  File a new bug report for any additional problems such as slow decomposition when one of the matrices is triangular.

Rik <rik5>
Group administrator
Mon 20 Jun 2016 06:55:49 AM UTC, comment #19: 

As I wrote comment #18, please close this.

Tatsuro MATSUOKA <tmacchant>
Mon 20 Jun 2016 03:51:09 AM UTC, comment #18: 

Dmitiri

You are right. And thanks for your correcting my misleading.

The for 4.1.0+ binaries, the refblas is default unlike 4.0.x.
I replaced libblas by libopenblas.
The bentimark results are


Simple left division
Elapsed time is 1.9463 seconds.
LU decomposition
c=P*B
Elapsed time is 0.038023 seconds.
y=L\c
Elapsed time is 0.656441 seconds.
x=U\y
Elapsed time is 0.647431 seconds.


The above are almost the same as those on 4.0.2 (x64).

Sorry for the noise.

So please close this tracker.

However, LU decomposition does not have merit on octave.
But this is not a topic that are discussed here.

I will raise post in the octave ML.

Anyway please close this post.
 


Tatsuro MATSUOKA <tmacchant>
Mon 20 Jun 2016 03:29:05 AM UTC, comment #17: 

I re-run the test on the same computer/same octave binary but
preloading reference blas library:

LD_PRELOAD=/usr/lib64/libblas.so octave-cli

octave:1> lutest_vp2
Simple left division
Elapsed time is 3.4795 seconds.
LU decomposition
c=P*B
Elapsed time is 0.0395591 seconds.
y=L\c
Elapsed time is 14.4594 seconds.
x=U\y
Elapsed time is 15.1527 seconds.

So it looks like your octave 4.1.0 uses reference blas rather than openblas...

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Mon 20 Jun 2016 03:06:28 AM UTC, comment #16: 


I have executed the same script on Ubunu 14.04 LTS amd64
(Athlon X2 (old))
All versions are built from source using the same libraries.

3.8.2

Simple left division
Elapsed time is 27.0865 seconds.
LU decomposition
c=P*B
Elapsed time is 0.09763 seconds.
y=L\c
Elapsed time is 9.60967 seconds.
x=U\y
Elapsed time is 9.72021 seconds.



4.0.2

Simple left division
Elapsed time is 26.9563 seconds.
LU decomposition
c=P*B
Elapsed time is 0.107472 seconds.
y=L\c
Elapsed time is 9.70008 seconds.
x=U\y
Elapsed time is 9.71262 seconds.



4.1.0+

Simple left division
Elapsed time is 26.8803 seconds.
LU decomposition
c=P*B
Elapsed time is 0.092479 seconds.
y=L\c
Elapsed time is 9.71794 seconds.
x=U\y
Elapsed time is 9.85034 seconds.


On linux results are essentially the same for 3.8.2, 4.0.2 and 4.1.0+.

Now issue is narrowed to 4.1.0+ on windows.

Tatsuro MATSUOKA <tmacchant>
Mon 20 Jun 2016 02:46:44 AM UTC, comment #15: 

At least 4.0.2 (x64) and 4.1.0+ (x64) are built with the same version of LAPACK and openblas on mxe-octave.

The slowness on 4.1.0+ seems to be windows specific!

Tatsuro MATSUOKA <tmacchant>
Mon 20 Jun 2016 02:40:13 AM UTC, comment #14: 

OK. Again I got essentially the same numbers in octave 4.0.2 and 4.1.0:
octave:1> lutest_vp2
Simple left division
Elapsed time is 1.48758 seconds.
LU decomposition
c=P*B
Elapsed time is 0.0369399 seconds.
y=L\c
Elapsed time is 0.62088 seconds.
x=U\y
Elapsed time is 0.619237 seconds.

It really looks like the issue with the openblas library.
Do you use the same library for all your octave binaries?


Dmitri.

Dmitri A. Sergatskov <dasergatskov>
Mon 20 Jun 2016 02:01:42 AM UTC, comment #13: 


>Try to increase

both numbers by factor of 10.
(Num=10000; ItNum=100;)

The above cause out of memory for 32 binaries so it is not realistic.
Instead I changed to
 (Num=3000; ItNum=3000;)


% lutest_vp2.m
more off

Num=3000; ItNum=3000;
rand('seed',1);
A=rand(Num)-0.5;
rand('seed',2);
B=rand(Num,ItNum)-0.5;
[L U P]=lu(A);
%
disp('Simple left division');
tic;
x=A\B;
toc;
x1=x(:,end);
%
disp('LU decomposition');
disp('c=P*B');
tic;
c=P*B;
toc;
disp('y=L\c');
tic;
y=L\c;
toc;
disp('x=U\y');
tic;
x=U\y;
toc;
x2=x(:,end);
id=1:Num;
plot(id,x1, 'o1',id,x2, '+2');


Here the test on windows
3.8.2 (x86)

Simple left division
Elapsed time is 2.29253 seconds.
LU decomposition
c=P*B
Elapsed time is 0.0350242 seconds.
y=L\c
Elapsed time is 0.715478 seconds.
x=U\y
Elapsed time is 0.720481 seconds.


4.0.2 (x86)

Simple left division
Elapsed time is 2.25751 seconds.
LU decomposition
c=P*B
Elapsed time is 0.0360239 seconds.
y=L\c
Elapsed time is 0.759509 seconds.
x=U\y
Elapsed time is 0.770514 seconds.


4.0.2 (x64)

Simple left division
Elapsed time is 1.93629 seconds.
LU decomposition
c=P*B
Elapsed time is 0.037025 seconds.
y=L\c
Elapsed time is 0.645431 seconds.
x=U\y
Elapsed time is 0.638431 seconds.


4.1.0+ (x64)

Simple left division
Elapsed time is 36.5474 seconds.
LU decomposition
c=P*B
Elapsed time is 0.0380249 seconds.
y=L\c
Elapsed time is 15.6344 seconds.
x=U\y
Elapsed time is 16.0377 seconds.


2. Slowness of left division by triangular matrix on octave ver. 4

seem not be an issue (Perhaps overhead time differences.)

However, slowness of left division 4.1.0+ on windows really annoying issue.

I will test also on linux and reports the results.

Tatsuro MATSUOKA <tmacchant>
Sun 19 Jun 2016 11:14:32 PM UTC, comment #12: 

I think the size of the benchmark is too small. Try to increase
both numbers by factor of 10.
(Num=10000; ItNum=100;)


octave-cli (4.0.1 -- as provided by Fedora 24)
octave:1> lutest_v
Simple left division
Elapsed time is 13.3167 seconds.
LU decomposition
Elapsed time is 1.77494 seconds.

same octave (with gui):

>> lutest_v

Simple left division
Elapsed time is 12.9441 seconds.
LU decomposition
Elapsed time is 1.8458 seconds.

same octave ( --no-gui):

>> lutest_v

Simple left division
Elapsed time is 13.6711 seconds.
LU decomposition
Elapsed time is 1.78795 seconds.

octave 4.1.0+ (SELF-COMPILED):

>> lutest_v

Simple left division
Elapsed time is 13.1303 seconds.
LU decomposition
Elapsed time is 1.77669 seconds.

(i7-2600K CPU @ 3.40GHz)

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Sun 19 Jun 2016 04:07:41 AM UTC, comment #11: 

I have built octave-3.8.2 on native windows using the same LAPACK (3.5.0) and openblas (0.2.18) that are used for 4.0.2 and 4.1.0+.

And execute


Simple left division
Elapsed time is 0.0590401 seconds.
LU decomposition
c=P*B
Elapsed time is 0 seconds.
y=L\c
Elapsed time is 0.002002 seconds.
x=U\y
Elapsed time is 0.00100088 seconds.


Elapsed time for y=L\c and x=U\y on 3.8.2 is faster that those on octave 4 also on windows.

Thus this issue is not related to the LAPACK and blas version and seems to be platform independent except for slowness of all left division on 4.1.0+ on windows.

I propose that
1. I will make a new file of bug tracker for slowness all left division on 4.1.0+ on windows

and

2. this tracker are kept for slow left division by triangular matrix on octave 4 (platform independent.)
 
The titles proposed are

1. Slowness of left division on 4.1.0+ on windows

2. Slowness of left division by triangular matrix on octave ver. 4

respectively.

I hope that someone improve the title because my English is poor.

Tatsuro MATSUOKA <tmacchant>
Sun 19 Jun 2016 03:39:18 AM UTC, comment #10: 

I have built octave-3.8.2 by myself on Ubuntu 14.04 LTS amd64 to ensure that octave binaries use the same versions of LAPACK (3.5.0) and BLAS(1.2.20110419).

I have executed test on comment #7 on 3.8., 4.0.2 and 4.1.0+(21793:50f49dcae277).

3.8.2

Simple left division
Elapsed time is 0.351762 seconds.
LU decomposition
c=P*B
Elapsed time is 8.79765e-05 seconds.
y=L\c
Elapsed time is 0.0066781 seconds.
x=U\y
Elapsed time is 0.00686312 seconds.


4.0.2

Elapsed time is 0.351755 seconds.
LU decomposition
c=P*B
Elapsed time is 8.01086e-05 seconds.
y=L\c
Elapsed time is 0.0207329 seconds.
x=U\y
Elapsed time is 0.0217681 seconds.


4.1.0+

Simple left division
Elapsed time is 0.349451 seconds.
LU decomposition
c=P*B
Elapsed time is 8.98838e-05 seconds.
y=L\c
Elapsed time is 0.0207131 seconds.
x=U\y
Elapsed time is 0.0217669 seconds.


It seems that slowness of left division by triangular matrix seem not to be related by LAPACK and blas versions.

Tatsuro MATSUOKA <tmacchant>
Fri 17 Jun 2016 10:00:23 AM UTC, comment #9: 

Cannot build lapackver on octave-3.8.2

undefined reference to `ilaver_'


>> mkoctfile -v lapackver.cc
lapackver.o: In function `Z10FlapackverRK17octave_value_listi':
D:\usr\Tatsu\program\Octave\bug48085/lapackver.cc:17: undefined reference to `ilaver_'
collect2.exe: error: ld returned 1 exit status
g++ -c -I/home/benutzer/mxe-octave/usr/i686-w64-mingw32/include  -IC:\octave\Octave-3.8.2\inc
lude\octave-3.8.2\octave\.. -IC:\octave\Octave-3.8.2\include\octave-3.8.2\octave -IC:\octave\
Octave-3.8.2\include -mieee-fp -g -O2 -pthread    lapackver.cc -o lapackver.o
g++ -shared -Wl,--export-all-symbols -Wl,--enable-auto-import -Wl,--enable-runtime-pseudo-rel
oc  -o lapackver.oct  lapackver.o   -LC:\octave\Octave-3.8.2\lib\octave\3.8.2 -LC:\octave\Oct
ave-3.8.2\lib -loctinterp -loctave -Wl,-rpath-link,/home/benutzer/mxe-octave/usr/i686-w64-min
gw32/lib -L/home/benutzer/mxe-octave/usr/i686-w64-mingw32/lib -Wl,--export-all-symbols
warning: mkoctfile exited with failure status


Tatsuro MATSUOKA <tmacchant>
Fri 17 Jun 2016 09:40:10 AM UTC, comment #8: 

So, left division by triangular matrix is managed by LAPACK's dtrtrs. You did not mention LAPACK version in 3.8.2. Maybe the attached file may help you to discover it (mkoctfile lapackver.cc).

(file #37511)

Marco Caliari <caliari>
Group Member
Fri 17 Jun 2016 09:21:05 AM UTC, comment #7: 

Change a test code according to advise from Marco


% lutest\vp1.m
more off

Num=1000; ItNum=10;
rand('seed',1);
A=rand(Num)-0.5;
rand('seed',2);
B=rand(Num,ItNum)-0.5;
[L U P]=lu(A);
%
disp('Simple left division');
tic;
x=A\B;
toc;
x1=x(:,end);
%
disp('LU decomposition');
disp('c=P*B');
tic;
c=P*B;
toc;
disp('y=L\c');
tic;
y=L\c;
toc;
disp('x=U\y');
tic;
x=U\y;
toc;
x2=x(:,end);
id=1:Num;
plot(id,x1, 'o1',id,x2, '+2');


I have tested on windows 10 using five versions:
3.8.2 (x86), 4.0.2(x86),  4.0.2(x64) 4.1.0+(x86) (build June 06), 4.1.0+(x64) (Build May 28). 

3.8.2 (x86)

Simple left division
Elapsed time is 0.097065 seconds.
LU decomposition
c=P*B
Elapsed time is 0 seconds.
y=L\c
Elapsed time is 0.002002 seconds.
x=U\y
Elapsed time is 0.00200081 seconds.


4.0.2(x86)

Simple left division
Elapsed time is 0.060041 seconds.
LU decomposition
c=P*B
Elapsed time is 0 seconds.
y=L\c
Elapsed time is 0.00900602 seconds.
x=U\y
Elapsed time is 0.010006 seconds.


4.0.2(x64)

Simple left division
Elapsed time is 0.0470331 seconds.
LU decomposition
c=P*B
Elapsed time is 0 seconds.
y=L\c
Elapsed time is 0.00500488 seconds.
x=U\y
Elapsed time is 0.00400209 seconds.


4.1.0+(x86)

Simple left division
Elapsed time is 0.062043 seconds.
LU decomposition
c=P*B
Elapsed time is 0 seconds.
y=L\c
Elapsed time is 0.00800514 seconds.
x=U\y
Elapsed time is 0.00900602 seconds.


4.1.0+(x64)

Simple left division
Elapsed time is 0.212145 seconds.
LU decomposition
c=P*B
Elapsed time is 0 seconds.
y=L\c
Elapsed time is 0.011008 seconds.
x=U\y
Elapsed time is 0.0120099 seconds.


Difference which comes from x86 or x64 exists but they are minor.


The version numbers LAPACK and openblas  are the same between
octave 4.0.2 and 4.1.0+.  

Left division by triangular matrix on octave ver 4 is slower
than that of ver. 3.

Two separate problems are considered

1. slowness of left division for triangular matrix for version 4.
2. slowness of all left division for 4.1.0+ on windows.

I will do the test on linux in the near future. 
Revised title proposed is (Marco. Please correct my poor English) 

Tatsuro MATSUOKA <tmacchant>
Thu 16 Jun 2016 10:03:25 AM UTC, comment #6: 


>Before changing the title (but, how can I do?), I suggest to benchmark separately c=P*B, y=L\c and x=U\y.


OK I will manage them tomorrow.

Changing title will be done by those who have admin(?) right.
Only we can do is ask to change title with proposal.
(That was already done once on Comment #1.)

Tatsuro MATSUOKA <tmacchant>
Thu 16 Jun 2016 09:07:08 AM UTC, comment #5: 

Before changing the title (but, how can I do?), I suggest to benchmark separately c=P*B, y=L\c and x=U\y.

Marco Caliari <caliari>
Group Member
Thu 16 Jun 2016 08:35:18 AM UTC, comment #4: 

Marco

Thank you for your reply.
Your comments for title is right.

Please propose correct title because my English is poor.

For windows, LAPACK version is difficult to know.
I will try to build octave-3.8.2, 4.0.2, 4.1.0+ on windows using the same LAPACK (3.5.0) and openblas (0.2.18).

For LAPACK version for Ubuntu 14.04 is the same (3.5.0) for all version except 3.8.1 because 3.8.1 is not built by myself.
I will also try to build octave-3.8.2 using LAPACK 3.5.0.


Tatsuro MATSUOKA <tmacchant>
Wed 15 Jun 2016 12:54:17 PM UTC, comment #3: 

The title is misleading. It is not the lu decomposition itself to be slow (it is not measured), but the solution after a lu decomposition. In particular, one permutation matrix multiplication, one lower triangular solution and one upper triangular solution. Since I'm on linux with no 3.8.x available, can you please measure separately the three steps above? Solution of triangular systems is managed by LAPACK dtrtrs, can you tell us which version of LAPACK are you using?

Marco Caliari <caliari>
Group Member
Fri 03 Jun 2016 12:59:51 AM UTC, comment #2: 

Speed of "Simple left division" is improved on octave 4 except 4.1.0+ on windows. This means that speed of left division has been improved on octave 4 except 4.1.0+ on windows.

However, speed for using "LU composition" is slower on octave 4.  Note that this might not to be a problem LU decomposition itself. But calculation speed of left division with large number of ZEROs (but not sparse).

There must be change in matrix calculation between 3.8 and 4.0 but I do not know what are changed.

Tatsuro MATSUOKA <tmacchant>
Thu 02 Jun 2016 05:35:12 AM UTC, comment #1: 

Oopss The title was wrong.
It should be

Slow solving  simultaneous equations by LU decomposition for octave 4 on windows

How can I do this?

Tatsuro MATSUOKA <tmacchant>
Thu 02 Jun 2016 05:24:46 AM UTC, original submission:  

This is originate from
http://octave.1599824.n4.nabble.com/slow-LU-decomposiotion-for-octave-4-for-windows-td4677291.html

I noticed that bench mark for the lu decomposition is slow on octave 4 (especally on windows). 
 
test script (Thank to Kai for vectorization)


% lutest_v.m
more off

Num=1000; ItNum=10;
rand('seed',1);
A=rand(Num)-0.5;
rand('seed',2);
B=rand(Num,ItNum)-0.5;
[L U P]=lu(A);
%
disp('Simple left division');
tic;
x=A\B;  % vectorized
toc;
x1=x(:,end);
%
disp('LU decomposition');
tic;
c=P*B; y=L\c; x=U\y;  % vectorized
toc;
x2=x(:,end);
id=1:Num;
plot(id,x1, 'o1',id,x2, '+2');

% end of lutest_v.m


Test on Windows (windows 10 Home 64bit core i5 2400)

Octave-3.2.4 mingw  (32 bit)

Simple left division
Elapsed time is 0.114076 seconds.
LU decomposition
Elapsed time is 0.00600397 seconds.


Octave-3.6.4 msvc  (32 bit)

Simple left division
Elapsed time is 0.11 seconds.
LU decomposition
Elapsed time is 0.00399995 seconds.


Octave-3.6.4 mingw  (32 bit)

Simple left division
Elapsed time is 0.0790549 seconds.
LU decomposition
Elapsed time is 0.00300312 seconds.


Octave-3.8.2 mingw  (32 bit)

Simple left division
Elapsed time is 0.096066 seconds.
LU decomposition
Elapsed time is 0.00300384 seconds.


Octave-4.0.0 mingw (32 bit) 

Simple left division
Elapsed time is 0.07305 seconds.
LU decomposition
Elapsed time is 0.01701 seconds


Octave-4.0.2 mingw (32 bit) 

Simple left division
Elapsed time is 0.060039 seconds.
LU decomposition
Elapsed time is 0.0180109 seconds.


Octave-4.0.2 mingw (64 bit) 

Simple left division
Elapsed time is 0.0500329 seconds.
LU decomposition
Elapsed time is 0.00900698 seconds.


octave-4.1.0+ mingw (64bit) 
(hg clone on May 28, 2016) 

Simple left division
Elapsed time is 0.213143 seconds.
LU decomposition
Elapsed time is 0.0230169 seconds.


Test on Ubuntu 14.04 LTS 64 bit (all octave runs on 64 bit)

3.8.1 from Ubuntu repository

Simple left division
Elapsed time is 0.396069 seconds.
LU decomposition
Elapsed time is 0.0427001 seconds.


4.0.0 bult myself (gcc 4.8.4) 

Simple left division
Elapsed time is 0.378708 seconds.
LU decomposition
Elapsed time is 0.071897 seconds.


4.0.2 bult myself (gcc 4.8.4) 

Simple left division
Elapsed time is 0.377592 seconds.
LU decomposition
Elapsed time is 0.0599658 seconds.


4.1.0+ bult myself (gcc 4.8.4) (cloned 2016-06-01 JST)

Elapsed time is 0.378928 seconds.
LU decomposition
Elapsed time is 0.0592132 seconds.


Both windows and ubuntu, tests on Ver 3 are faster than those on ver 4.
However, the difference is bigger on windows.
On windows, surprisingly, results on 4.1.0+ are the worst. This is a bad situation and should be improved.

Tatsuro MATSUOKA <tmacchant>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #37511:  lapackver.cc added by caliari (653B - text/x-c++src)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by caliari (Posted a comment)
  • -email is unavailable- added by siko1056 (Updated the item)
  • -email is unavailable- added by tmacchant (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 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-06-20 rik5 StatusConfirmed Invalid / Not an Octave Bug
        Open/ClosedOpen Closed
    2016-06-17 caliari Attached File- Added lapackver.cc, #37511
    2016-06-03 siko1056 StatusNone Confirmed
    2016-06-02 siko1056 Summaryslow LU decomposiotion? for octave 4 for windows Slow solving simultaneous equations by LU decomposition for octave 4 on windows

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code