Plotting points representing many events on a canvas

Question

I have a web app which uses Node canvas to plot points on a graph. Each point is called an 'event'. An event is an array of usually 6 'parameters' represented as numbers. My app allows users to plot 2 different numbers from each event on an XY graph.

E.g. say one event is:

// Event 1 (e1) is
[69876, 7, 210089, 122000, 7676, 189909]

// Event 2 (e2) is
[78, 23782, 66976, 253990, 2310, 88213]

If the user chooses to plot the 3rd and 5th parameter then then e1 is represented as 210089, 7676 and e2 is 66976, 2310. A typical plot might look like:

Typically, a graph is 300 pixels. In this case above, the maximum values any parameter can be is 262144. So to figure out where to plot I just work out the ratio:

300 / 262144 = 0.001144409

Then multiple the ratio by the x, y numbers.

So e1 will be shown at 240, 9 (210089 * 0.001144409 = 240 etc) and e2 will be shown at the pixels 77, 3.

This all works fine when there are less than 100k events. However, when there are, say, 800k events, this becomes very slow.

Is there any way of doing this more efficiently by somehow preprocessing the data? So say there are 800k events and you know the maximum value of each one is 262144 and that the graph size will be 300px, could some sort of data binning be done?

For example, the numbers 400, 550, 650 will all appear in the first pixel (since anything from 0 to 873 (262144 / 300) will fall into the first pixel on a 300px graph). Is there a method I could use to condense all this data down so that I can loop through much quicker and plot?

The code is:

for (var i = 0; i < dataAsNumbers.length; i++) {

    x = dataAsNumbers[i][paramX];
    y = dataAsNumbers[i][paramY];

    pointX = getPointOnCanvas({
        value: x
        ratio: ratio
    });

    pointY = getPointOnCanvas({
        value: y,
        ratio: ratio
    });

    toPlotColors.push({
        pointX: pointX,
        pointY: pointY               
    });
}


paintDotsAtOnce(toPlotColors);

var getPointOnCanvas = function(params) {

    var value = params.value;
    var ratio = params.ratio;

    return Math.floor(ratio * value);
};

var paintDotsAtOnce = function(plotColors) {

    plotColors.forEach(function(plotColor){

        if(plotColor.plotDot) {
           memoized(plotColor.pointX, plotColor.pointY, plotColor.color);                
        }
    });
};

var paintDotS = function(pointX, pointY, color) {
        context.fillStyle = color;
        context.fillRect(pointX, pointY, 1, 1);
};

var memoized = memoize(paintDotS);

So if dataAsNumbers.length is 800k, it has to loop that many times. I'm worndering if data binning could reduce the need to do this.

Answer 1

Optimising for performance.

Javascript has a way encouraging people to write code that is terribly inefficient.

You are lucky the problem is one that can get a lot of benefit from just some minor changes.

Memorize (binning) is not going to help, it will actually significantly decrease performance and massively increase your memory load. The crazy thing is you are already binning all the data in your code.

First the rendering

var paintDotS = function(pointX, pointY, color) {
        context.fillStyle = color;
        context.fillRect(pointX, pointY, 1, 1);
};

You are only plotting single pixels. For javascript to draw a pixel via the fillRect method there are 100's of CPU cycles needed, and all you do is set a single 32bit word.

To render pixels write them directly to a pixel buffer. When all the pixels have been rendered move the pixel buffer to the canvas.

var imageData = ctx.getImageData(0,0,ctx.canvas.width,ctx.canvas.height);
var dat32 = new Uint32Array(imageData.data.buffer);

The variable dat32 holds each pixel as a 32bit integer. The channel order is from high byte Alpha to low byte Red. Eg to write a yellow you would assign an array item dat32[index] = 0xFF00FFFF;

To write a pixel at a coord x,y

 const w = 300;  // the canvas width in pixels
 dat32[x + y * w] = colour;

Loops and function calls

A big performance killer is the context change required when you call a function. This is compounded if the function being called is indirectly called from another. Many times that calling function does a lot of vetting to ensure nothing goes wrong so more cpu cycles used for no reason.

The arrays iteration methods, forEach, Map, etc are agonisingly slow when compared to standard loops.

your code

var paintDotsAtOnce = function(plotColors) {
    plotColors.forEach(function(plotColor){
        if(plotColor.plotDot) {
           memoized(plotColor.pointX, plotColor.pointY, plotColor.color);                
        }
    });
};

Array.forEach calls a function, that starts, then maintains the iteration, (first context change) it calls your iterator function (second context change), your iterator calls the memoized function (third context change) it makes a memory assignment and then calls your paintDots function (fourth context change).

Remember you are just setting 1 32bit word and you are already 4 levels deep into the call stack, each needs to create closures and context, and the memoize need to allocate memory. You paint the pixel and the whole process need to be undone.

Memory and Objects.

Creating objects is slow, like snail pace slow.

Your code

for (var i = 0; i < dataAsNumbers.length; i++) {
    x = dataAsNumbers[i][paramX];  // 1st copy x
    y = dataAsNumbers[i][paramY];  // 1st copy y
      // 1st object 
    pointX = getPointOnCanvas({  // 4th copy of x in the function return
        value: x           // 2nd copy of x
        ratio: ratio
    });                    // 3rd copy of x in the function
      // 2nd object 
    pointY = getPointOnCanvas({ // 4th copy of y in the function return
        value: y,          // 2nd copy of y
        ratio: ratio
    });                    // 3rd copy of x in the function
      // 3rd object 
    toPlotColors.push({
        pointX: pointX,    // 5th copy of x
        pointY: pointY     // 5th copy of y          
    });
}
paintDotsAtOnce(toPlotColors);

var getPointOnCanvas = function(params) {

    var value = params.value;
    var ratio = params.ratio;

    return Math.floor(ratio * value);
};

You could not have found a worse way to do this. remember you are writing 1 32Bit pixel, but you create x,y coordinates, then copy x to an object, which you pass to a function in which creates another copy, you return the computed value and store it in yet another copy. Then do it again for y. And once y is done you make yet another copy to be pushed to an array as a reference (even more memory used) (remember that memorize will also be making a copys).

X and y should be immediate, on the heap and then forgotten, no variables need be created, no object constructed, no allocation requests made.

The performance rewrite.

Move one 32Bit word to an array of pixels for each item in dataAsNumbers.

const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
const dat32 = new Uint32Array(imageData.data.buffer);
const w = canvas.width;
const color = 0xFFFFFFFF; // white
for (var i = 0; i < dataAsNumbers.length; i++) {
     dat32[(dataAsNumbers[i][paramX] * ratio | 0) + 
           (dataAsNumbers[i][paramY] * ratio | 0) * w] = color;
}
ctx.putImageData(imageData, 0, 0);

Your code did not show where plotColor and plotDot came from. But they should be handled in the same way as above, without making function calls or creating objects. Everything is immediate and on the heap, and not making allocation requests.

The beauty is that it is also has binned the data for you as the pixel array. You can make a copy and next time you need that data set just dump the pixel array to the canvas, in less than 1 ms