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

 
 

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

Submitted by:  Tatsuro MATSUOKA <tmacchant>
Submitted on:  Thu 02 Jun 2016 05:24:46 AM UTC  
 
Category: PerformanceSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Performance
Status: InvalidAssigned to: None
Originator Name: Tatsuro MATSUOKAOpen/Closed: Closed
Release: otherOperating System: Microsoft Windows

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission 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>
Project 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

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

4.0.2

4.1.0+

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;)

Here the test on windows
3.8.2 (x86)

4.0.2 (x86)

4.0.2 (x64)

4.1.0+ (x64)

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

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

4.0.2

4.1.0+

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_'

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>
Project Member
Fri 17 Jun 2016 09:21:05 AM UTC, comment #7:

Change a test code according to advise from Marco

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)

4.0.2(x86)

4.0.2(x64)

4.1.0+(x86)

4.1.0+(x64)

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>
Project 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>
Project 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)

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

Octave-3.2.4 mingw (32 bit)

Octave-3.6.4 msvc (32 bit)

Octave-3.6.4 mingw (32 bit)

Octave-3.8.2 mingw (32 bit)

Octave-4.0.0 mingw (32 bit)

Octave-4.0.2 mingw (32 bit)

Octave-4.0.2 mingw (64 bit)

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

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

3.8.1 from Ubuntu repository

4.0.0 bult myself (gcc 4.8.4)

4.0.2 bult myself (gcc 4.8.4)

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

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 File(s):
   
   
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
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by dasergatskov (Posted a comment)
  • -unavailable- added by caliari (Posted a comment)
  • -unavailable- added by siko1056 (Updated the item)
  • -unavailable- added by tmacchant (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    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):

     

     

    Follow 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 20 Jun 2016 04:00:09 PM UTCrik5StatusConfirmed=>Invalid
      Open/ClosedOpen=>Closed
    Fri 17 Jun 2016 09:40:10 AM UTCcaliariAttached File-=>Added lapackver.cc, #37511
    Fri 03 Jun 2016 06:24:16 AM UTCsiko1056StatusNone=>Confirmed
    Thu 02 Jun 2016 07:01:20 AM UTCsiko1056Summaryslow 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.1-cleanup1