2
\$\begingroup\$

I tried to implement a very simple color flood fill to experiment a bit with Javascript. All comments about the code are welcome but I am especially interested in performance as it seems to be a bit slow. The browser tools only tell me that there is apparently a bunch of minor garbage collecting going on.

function setPixelColor(cvs, data, row, col, color) {
  const [red, green, blue] = color;
  data[4 * (row * cvs.width + col)] = red;
  data[4 * (row * cvs.width + col) + 1] = green;
  data[4 * (row * cvs.width + col) + 2] = blue;
  data[4 * (row * cvs.width + col) + 3] = 255;
}

function getPixelColor(cvs, data, row, col) {
  return [data[4 * (row * cvs.width + col)],
          data[4 * (row * cvs.width + col) + 1],
          data[4 * (row * cvs.width + col) + 2]];
}

function arr_eq(arr1, arr2) {
  if(arr1.length != arr2.length) {
    return false
  }

  for(let i=0; i<arr1.length; i++) {
    if(arr1[i] !== arr2[i]) {
      return false
    }
  }

  return true;
}

(function () {
  const cvs = document.getElementById("paint");
  const ctx = cvs.getContext('2d');

  // black background
  ctx.fillStyle='black';
  ctx.fillRect(0, 0, cvs.width, cvs.height);

  const imageData = ctx.getImageData(0, 0, cvs.width, cvs.height);
  const data = imageData.data;

  const start = [[40, 40, [255, 0, 0]],
                 [10, 20, [0, 255, 0]],
                 [23, 42, [0, 0, 255]],
                 [300, 333, [255, 255, 0]],
                 [200, 333, [255, 0, 255]]];

  for(point of start) {
    let [r, c, v] = point;
    setPixelColor(cvs, data, r, c, v);
  }

  let queue = start.slice(0); // clone

  while(queue.length > 0) {
    p = queue.shift();
    let [r,c] = p;
    const vcur = getPixelColor(cvs, data, r, c);
    for (const n of [[r+1,c], [r-1,c], [r,c+1], [r,c-1]]) {
      const [rn, cn] = n;
      if (rn >= 0 && rn < cvs.height && cn >= 0 && cn < cvs.width) {
        const vn = getPixelColor(cvs, data, rn, cn);
        if (arr_eq(vn, [0, 0, 0])) {
          setPixelColor(cvs, data, rn, cn, vcur);
          queue.push(n);
        }
      }
    }
  }

  for(point of start) {
    let [r, c, v] = point;
    setPixelColor(cvs, data, r, c, [0, 0, 0]);
  }

  ctx.putImageData(imageData, 0, 0);
})();
<!doctype html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <title>test</title>
  </head>
  <body>
  <canvas id="paint" width=500px height=500px />
  <script src="test.js"></script>
  </body>
</html>

\$\endgroup\$
  • \$\begingroup\$ how are you preventing processing same cell twice? \$\endgroup\$ – juvian Feb 6 at 16:58
  • \$\begingroup\$ It only processes black pixels. \$\endgroup\$ – Corporal Touchy Feb 6 at 17:07
2
\$\begingroup\$

Performant code requires a different style.

When you are working with a lot of data, or need it done fast, it pays to optimise everything. That means that you have to forgo many of the idiomatic coding styles that have come around since ES6.

Some points regarding your code

  • Don't repeat calculations. Eg you calculate the pixel chanel index 4 times in setPixelColor. Should be once.
  • Destructuring is SLOW, I mean forever slow, until browsers get round to making destructuring as performant as standard assignment dont use it in performance code.
  • Move frequent code and variables close to the scope you use the, You have setPixelColor and getPixelColor outside the function, thus it takes extra time to locate these functions.
  • Most devices are 64bit these days, and low end is 32 bits. Moving a byte takes just as long as moving a 4 bytes as a 32bit long or 8 bytes as 64bit long. Create a 32bit typed array so you can move a pixel in a quarter of the time.
  • Use 32Bit variables to store colors (eg [255, 0, 0] is 0x0000FF (NOTE 32bit pixels are backwards ABGR the opposite to CSS colors RGBA))
  • The source of your GC overload is the line for (const n of [[r+1,c], [r-1,c], [r,c+1], [r,c-1]]) { You create an array that contains 4 populated array. A million pixels in a image is small fry, but 5 million arrays is crazy.
  • Avoid getting values from getters, eg cvs.width is likely a getter. Get the value and store it in a variable scoped as close as possible to where you use it.
  • You work in rows, and columns (x,y) but the pixel data is a single array. Index directly when you can.
  • Use local scope, rather than pass variables if you must call functions inside performance loops..
  • If you can avoid calling functions, its quicker inline.
  • Use lookup tables to reduce math calculations.
  • Run in strict mode as it give a slight performance increase, and would also have spotted the undeclared variable p. Because you did not declare it, it becomes a global, and thus access would be much slower than a local. As it is in the heart of the function this will cost you many CPU cycles.

Example

The following does it all in about 1/4 of the time.

See comments for info relating to above comments.

(function () {
    "use strict"; // Always for performant code

    // Colors as 32bit unsigned ints. Order ABGR
    const black = 0xFF000000;
    const red = 0xFF0000FF;
    const green = 0xFF00FF00;
    const blue = 0xFFFF0000;
    const yellow = red | green;
    const magenta = red | blue;

    const cvs = document.getElementById("paint");
    const width = cvs.width;  // Get potencial slow accessors into vars.
    const w = cvs.width;  // alias
    const height = cvs.height;
    const size = width * height;
    const ctx = cvs.getContext('2d');

    // black background
    ctx.fillStyle = "black";
    ctx.fillRect(0, 0, width, height);

    const imageData = ctx.getImageData(0, 0, width, height);

    // Use 32bit buffer for single pixel read writes
    const d32 = new Uint32Array(imageData.data.buffer);  

    const start = [
        [40 * w + 40, red],  // work in precalculated pixel indexes
        [10 * w + 20, green],
        [23 * w + 42, blue],
        [300 * w +333, yellow],
        [200 * w + 333, magenta]
    ];
    const pixOff = [w, -w, 1, -1];  // lookup for pixels left right top bottom
    const pixOffX = [0, 0, 1, -1];  // lookup for pixel x left right

    const queue = [];  // keep queue content as simple as possible.
    for (const pixel of start) { 
        queue.push(pixel[0]);     // Populate the queue
        d32[pixel[0]] = pixel[1]; // Write pixel directly to buffer
    }
    
    while (queue.length) {
        const idx = queue.shift();
        const x = idx % w; // Need the x coord for bounds test
        for (let i = 0; i< pixOff.length; i++) {
            const nIdx = idx + pixOff[i]; 
            if (d32[nIdx] === black) {   // Pixels off top and bottom 
                                         // will return undefined
                const xx = x + pixOffX[i];
                if (xx > -1 && xx < w ) {
                    d32[nIdx] = d32[idx];
                    queue.push(nIdx);
                }
            }
        }
     }
     for (const pixel of start) { d32[pixel[0]] = pixel[1] }
     ctx.putImageData(imageData, 0, 0);
})();
<canvas id="paint" width=500px height=500px />

\$\endgroup\$
  • \$\begingroup\$ This really is an excellent answer! Is there something you would recommend for profiling to see the difference in timing for the various optimizations? \$\endgroup\$ – Corporal Touchy Feb 6 at 23:49
  • \$\begingroup\$ Where did you find the information on how to access the pixels as raw data via getImageData().data.buffer? \$\endgroup\$ – Corporal Touchy Feb 7 at 8:52
  • \$\begingroup\$ @CorporalTouchy MDN is a good reference developer.mozilla.org/en-US/docs/Web/JavaScript as for the optimisations that is something that comes from experiance. Chrome DevTools can give some insight but there is no easy way to compare one technique against another, \$\endgroup\$ – Blindman67 Feb 7 at 9:01
  • \$\begingroup\$ Okay, got it developer.mozilla.org/en-US/docs/Web/API/ImageData/data \$\endgroup\$ – Corporal Touchy Feb 7 at 9:04
1
\$\begingroup\$

Your getPixelColor function creates a new array every time it's called, which is likely what ends up triggering the garbage collector.

When dealing with pixel data, libraries often handle each pixel as a single 4-byte integer: the top 8 bits are the red value, the next are the green, the next are the blue, and the last are the alpha. This allows you to eschew arrays by using some simple bitwise arithmetic:

function setPixelColor(cvs, data, row, col, color) {
  const offset = col + cvs.width * row;
  data[offset] = (color >>> 24);
  data[offset + 1] = ((color >>> 16) & 0xff);
  data[offset + 2] = ((color >>> 8) & 0xff);
  data[offset + 3] = ((color >>> 0) & 0xff);
}

function getPixelColor(cvs, data, row, col) {
  const offset = col + cvs.width * row;
  return (
      (data[offset] << 24)
      | (data[offset + 1] << 16)
      | (data[offset + 2] << 8)
      | (data[offset + 3] << 0)
  );
}

Note: caching the offset value in a local variable saves us some calculations. color >>> 0 doesn't affect the value, it's there to coerce the value into an integer instead of the default floating point value JS uses for numbers.

This also makes the arr_eq function unnecessary, since you can just use a simple equality operator === to check if two colors match.

\$\endgroup\$
  • \$\begingroup\$ Is there by any chance a version of getImageData that will return such a format? Ah, maybe this is allowed const d32 = new Uint32Array(imageData.data.buffer); \$\endgroup\$ – Corporal Touchy Feb 6 at 23:48
  • \$\begingroup\$ That is a lot simpler, yes :) \$\endgroup\$ – Máté Safranka Feb 7 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.