bugGNU Octave - Bugs: bug #54005, kron performance affected by...

 
 

bug #54005: kron performance affected by octave_quit() calls

Submitter:  A.R. Burgers <arb>
Submitted:  Tue 29 May 2018 08:34:32 PM UTC
   
 
Category:  Interpreter Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Thu 21 Jun 2018 08:47:00 AM UTC, comment #10: 

Maybe it is not related, but I observe the following thing:


octave:1> tic; a = ones (1e4, 1); b = ones (1, 5e4); toc
Elapsed time is 0.000144958 seconds.
octave:2> tic; kron (a, b); toc
Elapsed time is 1.4675 seconds.
octave:3> tic; kron (a, b); toc
Elapsed time is 32.2755 seconds.
octave:4>


After the second call to kron, my system is quite slow for a couple of minutes.

Marco Caliari <caliari>
Group Member
Wed 20 Jun 2018 09:58:20 PM UTC, comment #9: 

I'm not too worried about it, but I see something like this:


>> tic; a = ones (1e4, 1); b = ones (1, 1e5); toc
Elapsed time is 0.000144958 seconds.
>> tic; kron (a, b); toc
Elapsed time is 4.97241 seconds.
>> tic; kron (a, b); toc
^C^C^C^C^C^C^C^C^C^C^C^C



John W. Eaton <jwe>
Group administrator
Wed 20 Jun 2018 06:44:25 PM UTC, comment #8: 

Human reaction time, at least from what I learned in driver's education, is about 3/4 of a second or 750 milliseconds.  As long as the outermost loop is executed say once every 500 milliseconds a human isn't going to really register the delay.

I tried


A = rand (1e4, 10);
B = rand (1, 1e4);
x = kron (A,B)


There is a slight delay after Ctrl+C but nothing that I couldn't live with.  If I add another factor of 10 to the size of either A or B I get an out-of-memory error, so this is close to the maximum case for my machine and still acceptable.

Rik <rik5>
Group administrator
Wed 20 Jun 2018 06:29:22 PM UTC, comment #7: 

This change does make kron somewhat less responsive to interrupts when the number of columns of A is small and the other dimensions are large.  OTOH, we can't interrupt external library routines at all, so maybe it's not a serious limitation.

John W. Eaton <jwe>
Group administrator
Wed 20 Jun 2018 05:54:20 PM UTC, comment #6: 

I had run that experiment and I thought I had reported on it, but apparently not.  The savings is 17%.  I suppose that is worth it.

I made that change on the development branch here (http://hg.savannah.gnu.org/hgweb/octave/rev/38a07d930ccd).

Marking as fixed and closing report.

Rik <rik5>
Group administrator
Wed 20 Jun 2018 08:20:11 AM UTC, comment #5: 

@Rik: what happens if you move octave_quit() up one level more?

Marco Caliari <caliari>
Group Member
Tue 19 Jun 2018 08:51:41 PM UTC, comment #4: 

I'm not saying we shouldn't do this, but I am seeing only modest improvement when moving octave_quit() up one level.

First, I rewrote the test script to have pre-computed vectors.  The only thing that we want in the tic/toc loop is the test of kron itself, not the actual construction of new vectors each time using ones().  The result is shown here, and attached.


N = 10;
nel = 10_000;

rowvec = ones (nel, 1);
colvec = ones (1, nel);

ver = version
hg_id = __octave_config_info__.hg_id

tic()
for i = 1 : N
  a = kron (rowvec, rowvec);
end
toc()

tic()
for i = 1 : N
  a = kron (colvec, colvec);
end
toc()


Results were:


ver = 5.0.0
hg_id = hg-id-disabled
Elapsed time is 4.4956 seconds.
Elapsed time is 5.72668 seconds.


I then moved octave_quit out of the innermost loop.  I don't think it is necessary to call it that frequently.


diff -r b7db401e1a99 libinterp/corefcn/kron.cc
--- a/libinterp/corefcn/kron.cc        Tue Jun 19 09:18:44 2018 -0700
+++ b/libinterp/corefcn/kron.cc        Tue Jun 19 13:40:26 2018 -0700
@@ -65,12 +65,15 @@ kron (const MArray<R>& a, const MArray<T

   for (octave_idx_type ja = 0; ja < nca; ja++)
     for (octave_idx_type jb = 0; jb < ncb; jb++)
-      for (octave_idx_type ia = 0; ia < nra; ia++)
-        {
-          octave_quit ();
-          mx_inline_mul (nrb, cv, a(ia, ja), b.data () + nrb*jb);
-          cv += nrb;
-        }
+      {
+        octave_quit ();
+        for (octave_idx_type ia = 0; ia < nra; ia++)
+          {
+       //     octave_quit ();
+            mx_inline_mul (nrb, cv, a(ia, ja), b.data () + nrb*jb);
+            cv += nrb;
+          }
+      }

   return c;
 }
@@ -90,12 +93,15 @@ kron (const MDiagArray2<R>& a, const MAr
   MArray<T> c (dim_vector (nra*nrb, nca*ncb), T ());

   for (octave_idx_type ja = 0; ja < dla; ja++)
-    for (octave_idx_type jb = 0; jb < ncb; jb++)
-      {
-        octave_quit ();
-        mx_inline_mul (nrb, &c.xelem (ja*nrb, ja*ncb + jb), a.dgelem (ja),
-                       b.data () + nrb*jb);
-      }
+    {
+      octave_quit ();
+      for (octave_idx_type jb = 0; jb < ncb; jb++)
+        {
+      //    octave_quit ();
+          mx_inline_mul (nrb, &c.xelem (ja*nrb, ja*ncb + jb), a.dgelem (ja),
+                         b.data () + nrb*jb);
+        }
+    }

   return c;
 }


And the result was


ver = 5.0.0
hg_id = hg-id-disabled
Elapsed time is 4.44244 seconds.
Elapsed time is 5.30063 seconds.


The reduction in execution time for column vectors was about 7%.

Marco is correct that we don't want to move octave_quit() completely outside the loops or we would disable Ctrl+C interruption.  Is 7% worth it?



Rik <rik5>
Group administrator
Thu 31 May 2018 09:22:20 PM UTC, comment #3: 

Well, the initial diff was only meant to highlight the issue.
Moving the octave_quit one level up, in case nrb==1 leads to these timings:


Elapsed time is 2.35524 seconds. (column vectors)
Elapsed time is 3.62659 seconds. (row vectors)



diff -r cdaa884568b1 libinterp/corefcn/kron.cc
--- a/libinterp/corefcn/kron.cc Thu May 24 19:20:35 2018 -0700
+++ b/libinterp/corefcn/kron.cc Thu May 31 23:16:56 2018 +0200
@@ -63,15 +63,30 @@
   MArray<T> c (dim_vector (nra*nrb, nca*ncb));
   T *cv = c.fortran_vec ();

-  for (octave_idx_type ja = 0; ja < nca; ja++)
-    for (octave_idx_type jb = 0; jb < ncb; jb++)
-      for (octave_idx_type ia = 0; ia < nra; ia++)
-        {
-          octave_quit ();
-          mx_inline_mul (nrb, cv, a(ia, ja), b.data () + nrb*jb);
-          cv += nrb;
-        }
-
+  if (nrb == 1)
+    {
+      for (octave_idx_type ja = 0; ja < nca; ja++)
+        for (octave_idx_type jb = 0; jb < ncb; jb++)
+          {
+            octave_quit ();
+            for (octave_idx_type ia = 0; ia < nra; ia++)
+              {
+                mx_inline_mul (nrb, cv, a(ia, ja), b.data () + nrb*jb);
+                cv += nrb;
+              }
+         }
+    }
+  else
+    {
+      for (octave_idx_type ja = 0; ja < nca; ja++)
+        for (octave_idx_type jb = 0; jb < ncb; jb++)
+          for (octave_idx_type ia = 0; ia < nra; ia++)
+            {
+              octave_quit ();
+              mx_inline_mul (nrb, cv, a(ia, ja), b.data () + nrb*jb);
+              cv += nrb;
+            }
+    }
   return c;
 }


A.R. Burgers <arb>
Thu 31 May 2018 08:03:53 AM UTC, comment #2: 

Of course, it is not Xgemm, but Xscal the proper BLAS routine for scaling a matrix.

Marco Caliari <caliari>
Group Member
Wed 30 May 2018 01:29:29 PM UTC, comment #1: 

@A.R. Burgers: If you move octave_quit() outside, then you will never be able to interrupt the operation with a Ctrl+C, I think. Can you please measure what happens if you move octave_quit() to the other loops?

It seems to me that the operation here is made column by column on b. This is a general question: is scalar times a matrix a column by column operation in octave? Could not it be done by BLAS xgemm (with alpha=0)?

Marco Caliari <caliari>
Group Member
Tue 29 May 2018 08:34:32 PM UTC, original submission:  

Kron execution times of 2 row vectors or 2 column vectors differ significantly:


nrep = 10;
np = 10000;
tic()
ver = version
hg_id = __octave_config_info__.hg_id
for i = 1 : nrep
  a = kron(ones(np,1), ones(np, 1));
end
toc()
tic()
for i = 1 : nrep
  a = kron(ones(1, np), ones(1, np));
end
toc()


The timings are


Elapsed time is 2.40767 seconds. (for the column vectors)
Elapsed time is 5.19106 seconds. (for the row vectors)


Moving the octave_quit() from the innermost loop to outside


diff -r cdaa884568b1 libinterp/corefcn/kron.cc
--- a/libinterp/corefcn/kron.cc Thu May 24 19:20:35 2018 -0700
+++ b/libinterp/corefcn/kron.cc Tue May 29 22:26:22 2018 +0200
@@ -63,11 +63,11 @@
   MArray<T> c (dim_vector (nra*nrb, nca*ncb));
   T *cv = c.fortran_vec ();

+  octave_quit ();
   for (octave_idx_type ja = 0; ja < nca; ja++)
     for (octave_idx_type jb = 0; jb < ncb; jb++)
       for (octave_idx_type ia = 0; ia < nra; ia++)
         {
-          octave_quit ();
           mx_inline_mul (nrb, cv, a(ia, ja), b.data () + nrb*jb);
           cv += nrb;
         }


makes the row vector case quite a bit faster:


Elapsed time is 2.31054 seconds. (column vectors)
Elapsed time is 3.54135 seconds. (row vectors)


A.R. Burgers <arb>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

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 rik5 (Posted a comment)
  • -email is unavailable- added by caliari (Posted a comment)
  • -email is unavailable- added by arb (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 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-06-20 rik5 StatusNone Fixed
        Open/ClosedOpen Closed
        Release4.4.0 dev

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code