Search code examples
javascripthtmlcanvasoptimizationflood-fill

Is it possible to optimize this floodfill algorithm any further?

Here's the fiddle for it: https://jsfiddle.net/rujbra6y/3/

I'm already logging the speed so make any changes and just re-run it a couple times to see if the performance increased at all.

Been working on it for a couple hours and I can't think of anything else I can change to make it faster. I'd like it to be as fast as possible because currently there is a small delay when the user uses floodfill and for proper user experience, I'd like that delay to be as short as possible.

Are there any more optimizations or hacks I can use to increase the speed?

Solution

  • There are a couple of things you could do at a brief glance:

    • Replaced Uint8ClampedArray with Uint32Array. This will save you from unnecessary shifting and ANDing ops
    • Replace push/pop with a stack pointer, this way you just update instances
    • You could define a typed array (Int16Array) for the stack using a fixed size (be sure to make it large enough)

    The only thing you need to be aware of for Uint32Array is the byte-order is little-endian, which mean you need to provide the target color in 0xAABBGGRR format (or do an initial bit-shift giving r,g,b as separate values).

    With these changes (except the last) the code went down from about 69-75ms to 58-61ms on my computer (i5 at the moment).

    Updated fiddle

    I'll leave the typed array for stack as an exercise. :-)