bugGNU Octave - Bugs: bug #40663, scatter and scatter3 terribly slow...

 
 

bug #40663: scatter and scatter3 terribly slow with real-valued color vector

Submitter:  José Luis García Pallero <jgpallero>
Submitted:  Thu 21 Nov 2013 05:50:43 PM UTC
   
 
Category:  Plotting 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

Sun 08 Dec 2019 04:59:03 PM UTC, comment #16: 

The examples given in this report seem to execute quickly now.

Closing as fixed.

Markus Mützel <mmuetzel>
Group administrator
Sun 01 Dec 2019 10:05:35 AM UTC, comment #15: 

Maybe some change in the graphics backend has caused that the single patch now is so much faster than calling patch repeatedly with smaller subsets.

I didn't notice a regression and also the issue with the colorbar on scatter plots seems to be fixed. So I went ahead and pushed the change here:
http://hg.savannah.gnu.org/hgweb/octave/rev/fc8668e1cb26

Markus Mützel <mmuetzel>
Group administrator
Sun 17 Nov 2019 09:39:03 AM UTC, comment #14: 

Is there a particular reason why we don't use a single patch for all scatter points?
The attached patch performs quite fast on my machine with Windows 10 using hg id 12a53552db92. Also the demos for scatter and scatter3 still look correct to me.

One difference is that the scatter points are no longer sorted by value (i.e. the largest value on top) but they are plotted in whatever order they are given in the input. However, it is questionable whether the previous behaviour was correct.

Do we need to distinguish between many and few scatter points?

(file #47878)

Markus Mützel <mmuetzel>
Group administrator
Sun 17 Nov 2019 07:45:29 AM UTC, comment #13: 

comment #12:

> There are no visual differences if the one-line fix from comment #5 is used in your code.  Nor are there compatibility differences as that line will work under Matlab as well.  Use the one-line fix for now.


Indeed there is a difference:
When you use the colorbar to see the scale of the data, you get a scale which not the original one.

almog
Tue 31 Jul 2018 05:25:42 PM UTC, comment #12: 

There are no visual differences if the one-line fix from comment #5 is used in your code.  Nor are there compatibility differences as that line will work under Matlab as well.  Use the one-line fix for now.

Rik <rik5>
Group administrator
Tue 31 Jul 2018 02:43:14 PM UTC, comment #11: 

I am using octave 4.4.0 and it seems the problem is still present. Are there any plans to fix it?

Fabio <efferre79>
Wed 23 Nov 2016 10:10:10 PM UTC, comment #10: 

This issue is still present in Octave 4.2.0.

When I run the example code from comment #3 (with graphics_toolkit qt) then the plot still takes forever.

Hartmut <hardy>
Fri 22 Nov 2013 05:14:40 PM UTC, comment #9: 

José,

Once you have 64 discrete values it's just a linear transform to change them from the range [0 64] to the old range [c_min c_max].

Rik <rik5>
Group administrator
Fri 22 Nov 2013 05:12:00 PM UTC, comment #8: 

I believe Jordi was the one who benchmarked scatter early on and came up with the policy of accumulating multiple colors under the same patch.  We could move everything to a single patch command along the lines of


patch (x(1:1000), y(1:1000), c(1:1000), 'marker', 'o', 'linestyle', 'none', 'facecolor', 'none')


But I benchmarked it and it is still pretty slow.



   #                Function Attr     Time (s)        Calls
-----------------------------------------------------------
   1                            R        5.491           47
  68                 drawnow             4.467            1
  18             __go_axes__             0.010            1
  66            __go_patch__             0.006            1
  28                     set             0.003            1
  30               __patch__             0.001            1
  45             __isequal__             0.001            2
  53 __patch__>setvertexdata             0.000            1
   2                   patch             0.000            1
  16                    axes             0.000            1
  55                ismember             0.000            2
  54     __patch__>delfields             0.000            2
  20                ancestor             0.000            1
  15                     get             0.000            4
  12                     gca             0.000            1
  44                 isequal             0.000            2
  67             addlistener             0.000            7
   3    __plt_get_axis_arg__             0.000            1
  38                isvector             0.000            4
  52                     isa             0.000            2


Rik <rik5>
Group administrator
Fri 22 Nov 2013 10:45:54 AM UTC, comment #7: 

The suggestion if Rik is a good solution:

c_discrete = fix (rows (colormap) / range (c(:)) * (c + abs (min (c(:)))));

But it has the problem that if after the scatter() I call to colormap() function, the colormap has the range [0 64] instead of the range of the original data

José Luis García Pallero <jgpallero>
Fri 22 Nov 2013 01:34:09 AM UTC, comment #6: 

My apologies if this sounds naive, but can't we have a single patch object, and assign a different color to each vertex? This assumes our patch objects interpret this correctly, but eventually it should.

Michael Goffioul <goffioul>
Fri 22 Nov 2013 12:38:37 AM UTC, comment #5: 

The issue is going to occur whenever you have huge numbers of colors.  In this case the scatter script is trying to consolidate and call the patch function the minimum number of times necessary.  It does this by finding out which points have the same color and grouping them.  The first examples you sent work because the number of colors is small.  In the biggest case it is equal to the average size colormap of 64 and the plot is nearly instantaneous.

But with 10,000 unique colors it needs to call the patch function once for each point and that is a lot of overhead.  There might be ways to reduce this.  One way would be to reduce the colors to the size of the colormap, since that is the largest number that will be displayed anyways.  Before calling scatter, for example, you could do


c_discrete = fix (rows (colormap) / range (c(:)) * (c + abs (min (c(:)))));


Longer term, patch and _go_patch_ (C++) need to be overhauled.  Not only are they slow, but they fail to reproduce the correct coloring behavior as I reported in another bug.  Here is some empirical data from the Octave profiler where I used just 1,000 points (which still takes 10 seconds).  The problem function is _go_patch_.


   #                      Function Attr     Time (s)        Calls
-----------------------------------------------------------------
   1                                  R       12.056          105
  77                  __go_patch__             9.250         1000
  73                      ancestor             0.444         1000
  16                           get             0.299         6010
  71 __scatter__>render_size_color             0.235         1000
  80                       drawnow             0.205            1
  26                   __scatter__             0.194            1
  23              __go_axes_init__             0.100            1
  70                      isscalar             0.055         2000
   4                       strcmpi             0.024         3002
   8                     binary ==             0.021         5040
  19                          true             0.019         5003
  14                        nargin             0.014         5038
   6                         numel             0.013         6009
  10                      prefix !             0.011         4021
  76                      ishandle             0.010         3000
   9                       isempty             0.009         4021
  45                           any             0.006         3008
  75                      num2cell             0.006         1000
  74                          cell             0.005         1000



Rik <rik5>
Group administrator
Thu 21 Nov 2013 09:06:02 PM UTC, comment #4: 

Ok, I see slow performance with this example, definitely due to the presence of the 4th argument.

These three uses do not appear to me to be any different in performance:


octave:1> a = randn (1e4, 2);
octave:2> scatter (a(:,1), a(:,2));
octave:3> c = randi (64, 1e4, 1);
octave:4> scatter (a(:,1), a(:,2), [], c);
octave:5> c = fix(randn (1e4, 1));
octave:6> scatter (a(:,1), a(:,2), [], c);


but the following usage is extremely slow (I haven't waited long enough to let it finish yet)


octave:7> c = randn (1e4, 1);
octave:8> scatter (a(:,1), a(:,2), [], c);


It's not clear to me from the help for scatter what the expected behavior is when the color argument is a vector with the same length as X but consists of non-integral values instead of integer-valued indices.

Mike Miller <mtmiller>
Group Member
Thu 21 Nov 2013 08:27:14 PM UTC, comment #3: 

I'm not now at my office, so I can't inform about execution times. I'm calling scatter() in a similar way as:

a = randn(10000,3);
scatter(a(:,1),a(:,2),[],a(:,3));

José Luis García Pallero <jgpallero>
Thu 21 Nov 2013 08:13:16 PM UTC, comment #2: 

We do need a test case.  But first, some observations.  The gnuplot backend will always be slower because the communication is done over pipes, choose fltk for speed.  Second, the scatter routines were overhauled in the current development branch and 3.6.4 is not worth comparing for speed.  Third, there are breakpoints in the code.  Below 100 points a different algorithm is used so it is important to know which regime you are finding slow.  Fourth, scatter relies internally on the patch function which has yet to be overhauled for speed.  Improving patch() may solve most of the problems.

Rik <rik5>
Group administrator
Thu 21 Nov 2013 07:50:45 PM UTC, comment #1: 

I think more information is needed here, such as an example script that shows what you would call slow performance so others can evaluate it on their systems.

I just did a simple scatter plot with FLTK,


x = randn (10000, 1);
scatter (1:10000, x);


and I don't see any performance issues, plot appears and draws as quickly as the plot function.

Mike Miller <mtmiller>
Group Member
Thu 21 Nov 2013 05:50:43 PM UTC, original submission:  

I'm trying to use the scatter and scatter3 functions with vectors containing around ~10000 points and I see that the functions are terribly slow. I've tested the stable 3.6.4 version and the developments sources, and I've used as graphics backend both gnuplot and fltk. These functions in Matlab are fast as the normal plot command.

Any idea about the poor performance in Octave of scatter and scatter3?

José Luis García Pallero <jgpallero>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #47878:  bug40663_scatter_single_patch.patch added by mmuetzel (2KiB - 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 mmuetzel (Updated the item)
  • -email is unavailable- added by almog (Posted a comment)
  • -email is unavailable- added by efferre79 (Posted a comment)
  • -email is unavailable- added by hardy (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 jgpallero (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 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-12-08 mmuetzel StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2019-12-01 mmuetzel StatusConfirmed Ready For Test
    2019-11-17 mmuetzel Attached File- Added bug40663_scatter_single_patch.patch, #47878
        Operating SystemGNU/Linux Any
    2018-07-31 efferre79 Carbon-CopyRemoved efferre79 -
    2018-07-31 efferre79 Carbon-Copy- Added efferre79
    2013-11-21 mtmiller StatusNeed Info Confirmed
        Summarystatter and scatter3 terribly slow scatter and scatter3 terribly slow with real-valued color vector
    2013-11-21 mtmiller Item GroupNone Performance
        StatusNone Need Info

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code