Chron Bag Chron Bag - 6 months ago 10
HTML Question

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?

K3N K3N
Answer

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. :-)

Comments