bugGNU Octave - Bugs: bug #55751, scatter3 performance regression...

 
 

bug #55751: scatter3 performance regression bug in Octave 5.0.91

Submitter:  Rick T <ratulloch>
Submitted:  Wed 20 Feb 2019 09:23:52 PM UTC
   
 
Category:  Plotting Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * 5.0.91 Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 12 Mar 2019 06:06:44 PM UTC, comment #23: 
Markus Mützel <mmuetzel>
Group administrator
Tue 12 Mar 2019 05:58:23 PM UTC, comment #22: 

I would love to. Just use the name in the commit (and email there if needed). Thank you.

Eddy <count>
Mon 11 Mar 2019 09:59:38 PM UTC, comment #21: 

I just now realized that this was your first contribution. Would you like to be added to the contributors list?

Markus Mützel <mmuetzel>
Group administrator
Mon 11 Mar 2019 09:55:37 PM UTC, comment #20: 

Thanks for your excellent work. I changed the lambda to a function and pushed your patch here:
http://hg.savannah.gnu.org/hgweb/octave/rev/1aed0bccd5dc

Markus Mützel <mmuetzel>
Group administrator
Mon 11 Mar 2019 08:58:34 PM UTC, comment #19: 

@Markus
Done some tests, and based on these observation, I tend to suggest include the initial coplanar test. See attached file bug55751_inc_coplanar_v2.patch for corresponding patch.

BTW, I forgot to turn off the check: facecolor_is ("none") && edgecolor_is ("none") in previous tests.

The (correct) time cost is:


                                   case 1,  case 2,  case 3,
scatter3 (no coplanar test)     :  0.095 s  0.095 s  0.097 s
__go_patch__ (+coplanar test)   :  0.094 s  0.227 s  0.225 s
coplanar split                  :  0.003 s  0.142 s  0.132 s
coplanar split + init full test :  0.003 s  0.145 s  0.003 s


Case 1: peaks (32).
Case 2: "2D Pseudo Quaterion Rotation Program", the ever-running one.
Case 3: coplanar point set. N = 45001; vecs=rand(N,2)*orth(rand(3,2))';

Test code of _go_patch_ (mimic implementation of scatter3):


  tic
  hax = newplot ();
  edgecolor = "r";  % trigger coplanar test, "none" to suppress.
  feval ('__go_patch__', hggroup (),
         "xdata", x, "ydata", y, "zdata", z,
         "facecolor", "none", "edgecolor", edgecolor,
         "faces", 1:numel (x), "vertices", [x, y, z],
         "marker", "o",
         "markeredgecolor", "none",
         "markerfacecolor", "b",
         "markersize", 3, "linestyle", "none");
  toc


So the impact of initial overall coplanar test is very minor, and the improvement to coplanar input case is huge.

A more detailed time cost of different cases (test code below, time in table below is only for the coplanar test C++ code):


with initial coplanar test
nc        4       5       10      20      50      1e6
random  : 1.974   2.297   2.818   3.107   3.307   3.391
coplanar: 1.157   0.919   0.492   0.263   0.139   0.067

no initial coplanar test
nc        4       5       10      20      50      1e6
random  : 1.193   1.585   2.396   2.806   3.118   3.227
coplanar: 1.115   1.478   2.185   2.605   2.779   2.830


nc: number of corners in a face, total number of vertex is 1e6.
random: random non-coplanar data.
coplanar: coplanar data.


# random
N = 1e6;
nc = 5;
vertices = rand(N, 3);
faces = 1:N;
faces = reshape (faces, nc, [])';
tic
hp = patch ('Vertices', vertices, 'Faces', faces);
toc

# coplanar
N = 1e6;
nc = 5;
vertices = rand(nc, 2) * orth(rand(3,2))';
faces = 1:nc;
faces = faces .* ones(N / nc, 1);
tic
hp = patch ('Vertices', vertices, 'Faces', faces);
toc


This time table provide information that when should we disable the overall coplanar test. i.e. it should be disabled if nc == 4, otherwise the test should be beneficial on average, assuming more than half cases are coplanar.

The attached file bug55751_inc_coplanar_v2_timing.diff is what I used for the timing measure of coplanar test/face splitting. Apply after the patch.

Further speed up might be possilbe, such as use "rcond" for rank test, instead of "eig". I didn't try it.

Appendix:

Here is some addtional background math in case someone (or me, in the future) want to fully understand the algorithm and fine tune it.

Suppose [x y z] are always in a plane:
  a x + b y + c z + d = 0
To find {a,b,c,d}, we can minimize the variance of "epsilon" in
  a x + b y + c z + d = epsilon
i.e
   min epsilon' * epsilon
 = min [a b c d] [x y z ones()]' [x y z ones()] * [a b c d]'
Let coor_cov = [x y z ones()]' * [x y z ones()], this is equivalant to
solve the minimum eigenvalue of coor_cov, which equals to min n*var(epsilon),
eigenvector is [a b c d]'. n is the number of points, e.g. length(x).

To avoid the extra "ones()", one need to fit a plane without constant term
  a*(x-mx) + b*(y-my) + c*(z-mz) = 0
where the pivot [mx my mz] = mean([x y z]), then follow the same analysis.
Alternatively, [mx my mz] can be other point (presumably) in the plane,
although different choice introduce diffence bias. Usually "mean([x y z])"
been the most "fair" one.
Other eigenvalues indicate the spreading of the points in other dimensions in the plane.


(file #46498, file #46499)

Eddy <count>
Sun 10 Mar 2019 06:51:59 PM UTC, comment #18: 

@Eddy: I tried your patch and the performance improvement is impressive!
I ran the example from comment #0 with your patch. Then I reverted the changes to _scatter_.m and ran the same example again: I see hardly any difference. Both times the example ran at about 100ms. So an improvement of several orders of magnitude on my system! But then this is what you already showed with your cost estimate.
I think most of the time for the ever-running example is now spend in the gl-render code (rotating isn't smooth). But that isn't the issue at hand.

I don't know how frequent coplanar vs. non-coplanar patches are.
How big would an initial overall coplanar test impact the performance of case (a)?

Please, let me know when you are done testing. I'd like to push your patch.

Markus Mützel <mmuetzel>
Group administrator
Tue 05 Mar 2019 03:00:23 PM UTC, comment #17: 

New idea comes, try the attached patch, it is the method (2) below. The patch is primary for conceptual verification, no thoughtful test or careful cover of every edge case.

With this patch, the time cost for the initial reported sample is reduced to roughly 0.3 second, and the said ever-running example will end in 0.32 second.

Read a bit about graphics.cc and bug #47677.

The current algorithm there, for non-coplanar random data of n points, the time cost is roughly O(n^3): one n for a single coplanar test, one n for search the largest coplanar point set, last n for repeated search of each plane.

I can see at least two possible optimizations.

1. Use binary search instead of the full linear search.
This reduce the time cost to O(n^2 log(n)).

2. Incremental search for coplanar point set.
This is based on the observation that in the 'eig' method: eig(a'*a), the 3x3 matrix a'*a can be calculated by rank one updates corresponding to each point. Thus we can check if the newly added point is inside the plane or not in O(1) (one eig of 3x3 matrix). Time cost is thus reduced to O(n).

To further speed (if necessary), we may need to know the more frequent use case of patch():
a. large list of many non coplanar input. or
b. coplanar input.

If it is (b), probably adding an initial overall coplanar test can help, at the cost of slow down case (a). Current implementation favors (a).

(file #46431)

Eddy <count>
Sat 02 Mar 2019 10:42:04 AM UTC, comment #16: 

The attached patch implements the eigenvalue approach in graphics.cc.
As far as I can tell this performs about twice as fast on the original example than the current svd approach.

In graphics.cc we need an algorithm that groups the vertices into coplanar subsets. Checking whether the whole set is coplanar is only part of it.

If you have any ideas how to further speed this up, I'd be very interested.

(file #46389)

Markus Mützel <mmuetzel>
Group administrator
Sun 24 Feb 2019 02:26:38 PM UTC, comment #15: 

Not sure if it is proper to post comment when the bug is marked "Fixed"...

@Markus
I tried several coplanar test methods. They all seems slightly faster than your attached checker in comment 14 (file #46341).


N = 1e7;
[Q, ~] = qr(rand(3));           % random orthonormal matrix
vecs = rand(N, 2) * Q(1:2, :);  % random coplanar samples
disp(['Normal vector = ', num2str(Q(3, :))]);
[x, y, z] = deal(vecs(:,1), vecs(:,2), vecs(:,3));

tic; is_coplanar (x, y, z); toc

tic
[copl, normal_vector, eig_vals] = is_coplanar_lsm (x, y, z, [], 'svd');
toc

tic
[copl, normal_vector, eig_vals] = is_coplanar_lsm (x, y, z, [], 'eig');
toc

tic
[copl, normal_vector, eig_vals] = is_coplanar_lsm (x, y, z, [], 'lsm');
toc

octave-gui:>
Normal vector = -0.72582    -0.062478      0.68504
Elapsed time is 0.977858 seconds.
Elapsed time is 0.88521 seconds.
Elapsed time is 0.280604 seconds.
Elapsed time is 0.636894 seconds.


See attachment is_coplanar_lsm.m. There are 3 testers.

  • 'svd': basically the one you are using in libinterp/corefcn/graphics.cc
  • 'eig': mathematically equivalent to 'svd' method (svd(a).^2 <=> eig(a'*a)). But instead of doing SVD of a very tall matrix, here only eigenvalue factorization of 3x3 matrix is needed.
  • 'lsm': find a planar by least square method, i.e. solve [a;b] in ax+by=z.


All of these methods have a clear geometric meaning of tolerance, namely deviation to the best possible planar. In terms of FLOPS, 'lsm' method should be the best, but in practice it is slower than 'eig'.

My feeling is, in order to get better performance, one need some heuristic or greedy algorithm. e.g. first guess the correct planar by a set of good points, then test if all other points are close enough to this planar.

(file #46348)

Eddy <count>
Sat 23 Feb 2019 06:27:17 PM UTC, comment #14: 

Attached is a first shot at a coplanarity check using the volume of tetrahedrons.

It is fairly efficient for random data:

>> N=1e7; x = rand (N, 1); y = rand(N, 1); z = rand(N, 1);
>> tic, is_coplanar (x, y, z), toc
ans = 0
Elapsed time is 1.28589 seconds.


And for coplanar (but not colinear) data:

>> N=1e7; x = y = z = 1:N; y = y.*(-1).^y; z = z.^3;
>> tic, is_coplanar (x, y, z), toc
ans = 1
Elapsed time is 1.25889 seconds.


But not so efficient if all data is colinear:

>> N=1e5; x = y = z = 1:N;
>> tic, is_coplanar (x, y, z), toc
ans = 1
Elapsed time is 6.73134 seconds.


Is there an efficient way to check whether many 3d vectors are colinear?

Also what criteria could we use to define that two vectors are "sufficiently non-colinear" for the cross-product?

The results with the matGeom function as a point of comparison:

>> N=1e3; x = rand (N, 1); y = rand(N, 1); z = rand(N, 1);
>> tic, isCoplanar (x, y, z), toc
error: out of memory or dimension too large for Octave's index type
error: called from
    nchoosek at line 134 column 9
    isCoplanar at line 66 column 5
>> N=1e2; x = rand (N, 1); y = rand(N, 1); z = rand(N, 1);
>> tic, isCoplanar (x, y, z), toc
ans = 0
Elapsed time is 0.337654 seconds.



(file #46341)

Markus Mützel <mmuetzel>
Group administrator
Fri 22 Feb 2019 09:00:39 PM UTC, comment #13: 

Hi Markus,

Check isCoplanar from geometry...ehem.. matGeom

https://github.com/mattools/matGeom/blob/master/matGeom/geom3d/isCoplanar.m

It is doing the nchoosek approach. It is not vectorized.
If you improve it consider submitting to matGeom.

Regards,

Juan Pablo Carbajal <juanpi>
Group Member
Fri 22 Feb 2019 07:36:10 PM UTC, comment #12: 

Sorry, I meant Rik, not Mike.

Markus Mützel <mmuetzel>
Group administrator
Fri 22 Feb 2019 07:34:34 PM UTC, comment #11: 

@Mike: I added a comment to _scatter_.m here:
http://hg.savannah.gnu.org/hgweb/octave/rev/3b0af21841d4

@Juan: Thanks for the hint. Patches can be arbitrary polygons. But maybe it would be quite fast to use the first three vertices to calculate "b" and "c" and check all other vertices by calculating "a" and checking | a . (b x c) | < eps which is only sums and multiplications.

Markus Mützel <mmuetzel>
Group administrator
Fri 22 Feb 2019 07:02:36 AM UTC, comment #10: 

Regarding comment #5.

svd is N^3, and is justified only if the patches are arbitrary polygons. If you are checking for coplanarity of 4 vertices the direct cross-product criteria (volume of the thetahedron http://mathworld.wolfram.com/Tetrahedron.html) is faster.

I guess there is a tradeof depending on the number of vertices N given by

complexity(svd) == complexity(tetahedron_vol) * nchoosek(N,4)

Juan Pablo Carbajal <juanpi>
Group Member
Thu 21 Feb 2019 09:13:58 PM UTC, comment #9: 

@Markus: Could you put a FIXME note in _scatter_.m at the first point that _go_patch_ is called which references this bug number and explains why "facecolor" and "edgecolor" need to appear first?

Otherwise, I'm sure someone will come along a few years from now and think it looks dumb not to have the data first and accidentally revert the change.

Rik <rik5>
Group administrator
Thu 21 Feb 2019 08:01:53 PM UTC, comment #8: 

@Markus: Thanks, closing report as fixed.

Pantxo Diribarne <pantxo>
Group Member
Thu 21 Feb 2019 07:47:39 PM UTC, comment #7: 

I pushed the patch to stable here:
http://hg.savannah.gnu.org/hgweb/octave/rev/8cfe07381fc0

Marking as ready for test.

Markus Mützel <mmuetzel>
Group administrator
Thu 21 Feb 2019 07:40:19 PM UTC, comment #6: 

I can confirm your patch fixes the issue. I know nothing about svd drivers either but I'd go ahead and push this patch to stable for now.

Pantxo Diribarne <pantxo>
Group Member
Thu 21 Feb 2019 07:18:14 PM UTC, comment #5: 

The attached patch fixes the performance regression of scatter3 for me by completely skipping the co-planarity check if there won't be any faces or edges to draw.

We are using svd's to check whether a set of points is in a plane. I am no expert in this field. If someone knows of a check with faster performance, any hint is welcome to improve this long term.

(file #46330)

Markus Mützel <mmuetzel>
Group administrator
Thu 21 Feb 2019 06:12:33 PM UTC, comment #4: 

Thanks for bisecting. I'll try to find out why there is such a huge slow down.

Markus Mützel <mmuetzel>
Group administrator
Thu 21 Feb 2019 02:12:15 PM UTC, comment #3: 

The changeset that triggered the slowdown for me is


changeset:   25418:762eb2e33a7f
user:        Markus Muetzel <markus.muetzel@gmx.de>
date:        Mon Jul 18 18:33:48 2016 +0200
summary:     Enable support of non-coplanar faces in patches for OpenGL (bug #47677).


@Markus: Do you think there is something we can do before 5.1 release? FWIW in scatter3 plots we only draw patch markers (which are coplanar by construction), so testing if faces are coplanar is not useful since we won't draw them.

Pantxo Diribarne <pantxo>
Group Member
Thu 21 Feb 2019 12:53:59 PM UTC, comment #2: 

For me, the original example takes ~155s (with -O0 and debug symbols enabled). I am now trying to find the change that triggered this slowdown and ecc488aa56a0 (default, 1 month after 4.4.0 release) was already bad.

Pantxo Diribarne <pantxo>
Group Member
Wed 20 Feb 2019 09:37:54 PM UTC, comment #1: 

I can confirm a performance regression from 4.4.1 to 5.0.91, with qt as well as gnuplot toolkits. With 1024 points, scatter3 takes about 20 seconds for me with the qt toolkit, about 10 seconds with the gnuplot toolkit. Almost all of the time is spent in the '__go_patch__' function according to profshow.

Mike Miller <mtmiller>
Group Member
Wed 20 Feb 2019 09:23:52 PM UTC, original submission:  

Mike Miller said "... you've found a performance regression in Octave 5. Can you file a bug report?"
The example to test the bug he gave is the one below.

    [x, y, z] = peaks (32);
    [x, y, z] = deal (x(:), y(:), z(:));
    tic;
    scatter3 (x, y, z);
    toc
    $ octave-4.4.1 t.m
    Elapsed time is 0.104946 seconds.
    $ octave-5.0.91 t.m
    Elapsed time is 20.1961 seconds.



My example that had issues with plotting is below (it was never able to finish the plot)


Octave code converted:
%%========================
%%2D Pseudo Quaterion Rotation Program in converted from Scilab 6.01 to Octave 5.0.91
w1=111
w2=333
w3=777
%% No phase differences in this: add in phi1 and phi2 phase differences if desired to the psi and phi angles

n = [0:.001:45];
x1=50.*cos((n./360).*2.*pi.*w1).*(1.144.*n./100); %%w = mu cos theta, the scalar
x2=50.*cos((n./360).*2.*pi.*w2).*(1.144.*n./100); %%cos phi
y1=50.*cos((n./360).*2.*pi.*w3).*(1.144.*n./100); %%cos psi
y2=50.*sin((n./360).*2.*pi.*w1).*(1.144.*n./100); %%sin theta
z1=50.*sin((n./360).*2.*pi.*w2).*(1.144.*n./100); %sin phi
z2=50.*sin((n./360).*2.*pi.*w3).*(1.144.*n./100); %%sin psi
x = y2.*x2;
y=y2.*z1.*y1;
z = y2.*z1.*z2;

scatter3 (x, y, z);  %color can be created based on z

xlabel('X-axis')
ylabel('Y-axis')
zlabel('Z-axis')
grid on

az = 347; %90;
el = 37; %180;
view([az,el]);

Rick T <ratulloch>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #46431:  bug55751_inc_coplanar.patch added by count (5KiB - text/x-patch - Incremental coplanar point set search)
file #46389:  bug55751_coplanar_eig.patch added by mmuetzel (2KiB - application/octet-stream)
file #46348:  is_coplanar_lsm.m added by count (2KiB - text/x-objcsrc)
file #46341:  is_coplanar.m added by mmuetzel (2KiB - application/octet-stream)
file #46330:  bug55751_scatter3_performance.patch added by mmuetzel (7KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by count (Updated the item)
  • -email is unavailable- added by juanpi (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by pantxo
  • -email is unavailable- added by pantxo (Posted a comment)
  • -email is unavailable- added by ratulloch (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 21 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-03-11 count Attached File- Added bug55751_inc_coplanar_v2.patch, #46498
        Attached File- Added bug55751_inc_coplanar_v2_timing.diff, #46499
    2019-03-05 count Attached File- Added bug55751_inc_coplanar.patch, #46431
    2019-03-02 mmuetzel Attached File- Added bug55751_coplanar_eig.patch, #46389
    2019-02-24 count Attached File- Added is_coplanar_lsm.m, #46348
    2019-02-23 mmuetzel Attached File- Added is_coplanar.m, #46341
    2019-02-22 mmuetzel StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2019-02-22 mmuetzel StatusFixed Ready For Test
        Open/ClosedClosed Open
    2019-02-21 pantxo StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2019-02-21 mmuetzel StatusPatch Reviewed Ready For Test
    2019-02-21 pantxo StatusConfirmed Patch Reviewed
    2019-02-21 mmuetzel Attached File- Added bug55751_scatter3_performance.patch, #46330
    2019-02-21 pantxo Carbon-Copy- Added mmuetzel
    2019-02-20 mtmiller CategoryPlotting with OpenGL Plotting
        SummaryPossible regression bug in Octave 5.0.91 scatter3 performance regression bug in Octave 5.0.91
    2019-02-20 mtmiller CategoryNone Plotting with OpenGL
        Item GroupRegression Performance
        StatusNone Confirmed

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code