Hacker News Reader

Comment by shaneos | Hacker News Reader

If a wasm algorithm can run in under 16ms for arbitrarily large images that would be amazing. Hard to beat pre-computing all possible fills however, as the user perceives it as instant.

If you’ve seen a really fast wasm solution I’d love to replace the fill portion with it though.

View on HN

I think people in this thread are being much too optimistic about browser performance. Writing a loop isn't the issue; memory access patterns are. Canvas implementations are just not well suited for the flood fill problem space. (I spent some time with flood fills + canvas ten years ago when I was working on the now-dead library Literally Canvas, but I assume that experience is pretty far out of date now.)

Precomputing fill areas is a really good idea for the situation you're in!

Edit: actually it was 7 years https://github.com/irskep/literallycanvas-pro-tools/blob/mas...

you're calling fillRect in your inner loop

it also has 10 other method and function calls in it, one of which allocates a new 4-element array

also it's maintaining a stack of pixels to paint instead of looping over a scan line

each iteration of the loop paints one pixel

i don't think canvas memory access patterns are the root of the performance problem

i'm not saying it's bad code, just that it doesn't justify your conclusion

actually on further examination i think each four iterations of the loop paint one pixel in the most common case, because each pixel in a large filled area gets visited from each of its neighbors

btw, i want to point out that shaneos's request for an 'algorithm [that] can run in under 16ms for arbitrarily large images' is obviously constructed to be impossible

no flood-fill algorithm can run in less than 16ms, or less than any finite time, for arbitrarily large images; they necessarily require at least linear work and, even with arbitrary parallelism (itself impossible in a finite universe), logarithmic time

you need to bound the image size if you are going to bound the execution time

so this is not a good faith request; it is, rather, a deliberately impossible task, like spinning straw into gold, finding an acre of land between the salt water and the beach, making a cambric shirt with no seams or needlework, or reaping a crop with a sickle of leather

unfortunately my previous comment pointing this out has been flagged and is therefore generally no longer visible; i consider this sort of response to a purely logical argument of impossibility to be astoundingly mean-spirited and contemptible

No, JS and Canvas aren't the issue, there; the code you wrote will perform terribly in any language on any platform. You used a four-way recursive per-pixel fill algorithm. You should probably do a bit of reading on flood fill algorithms (maybe read the Wikipedia flood fill article).

it isn't recursive in the sense of a function calling itself, just in the mathematical sense of using its own previous output as input

i agree that it's easy to better its performance substantially, but i wouldn't go so far as to say 'perform terribly', except in the sense that it's far from optimal. there are applications where it would be adequate

There are situations where bubble-sort is adequate, too, but it's still not a good idea to use it or claim that it performing badly reflects on the implementation language. The code uses an explicit stack in place of recursion, sure, but that's not particularly salient; it's just recursion without stack overflow.

The code allocates data structures at least eight times per pixel, and tests pixels at least four times. It will perform badly in all languages and so cannot be used as a reliable indication of JS/Canvas performance.

agreed, except that the reason it's never a good idea to use bubble sort is that insertion sort is just as simple and always performs much better; there are cases where insertion sort really is the right thing to use despite its usually quadratic performance

there might even be a case where the single-loop sort is the right thing to use, despite its abominable performance, because it's simpler than bubble sort or insertion sort; i think it's 12 amd64 instructions, 40 bytes

    for (i = 1; i < n; i++)
      if (a[i-1] > a[i]) t = a[i], a[i] = a[i-1], a[i-1] = t, i = 0;

but i haven't seen it yet

You're right, the code is not performant at all. At the time I was hacking around and just happy to get something working. I think the code is a tempting distraction, but I was trying to say that browser API performance is not always what you would expect and sometimes you need to get creative in order to get the results you want.

okay but i think we aren't being too optimistic about browser performance, memory access patterns aren't the problem, and canvas implementations are adequately well suited for the flood fill problem space, which directly contradict three assertions you did actually say, even if they weren't what you were trying to say

You can probably make the process extremely fast by replacing the flood-fill approach with a something based on a Connected-Component Labeling algorithm ( https://en.wikipedia.org/wiki/Connected-component_labeling ). There's a good amount of literature on the subject and it's often included in computer vision libraries (e.g. OpenCV).

You'd first threshold the image by checking if a pixel is 'close enough' to the clicked pixel. This will create a B&W image. Then you call the CCL on this binary image to produce a labelled image: each pixel will contain the id of its component (i.e. which enclosed space it belongs to). Once you have this, it's just a matter of replacing colors on the canvas for pixels with the same id as the clicked pixels.

Obviously, that's just the 'theory' part. If you can find a good library that includes one then you'll have to integrate it. Otherwise, you'll have to re-implement that in Javascript, which is easier said than done and may also not reach the desired performance.

Thanks, I’ll take a look at the article. This generally sounds very similar to my pre processing algorithm, setting the id of the enclosing area into each pixel so a fast/instant operation can be applied. Am I missing something though? In my solution, the only thing that happens when the user clicks is a fillRect() call. Is your suggestion similarly fast on click?

I think the main difference is that the CCL would compute 'enclosed areas' on the fly. To be more specific, it would first create a mask (black & white) of pixels that are similar to the clicked pixel, and then find connections between foreground/white pixels.

I don't work in web development but accelerating CCL algorithms do happen to be my area of expertise. While their execution time depends on the image content, you can expect them to be in the tens of milliseconds for a 4K image, at least for the 'modern' one you can find in OpenCV, and on current consumer-level CPUs, without multi-threading.

Of course, implementing these newer algorithms isn't straightforward. That's why you should instead use something like OpenCV if you have the option to.

Moreover, if CCL doesn't fit what you're looking for then you can also check out watershed algorithms ( https://en.wikipedia.org/wiki/Watershed_%28image_processing%... ). Because they don't work on binary image, they might be a better way to describe what you call 'enclosed space'.

One visible difference would be that if there are two identically-colored overlapping objects, the article's method will treat them as two separate areas, whereas the algorithm mentioned above will treat them as one.

There are faster fill algorithms than the above, described on Wikipedia, that don't need you to visit the whole image [1]. In particular, span-based filling.

https://en.wikipedia.org/wiki/Flood_fill

Reply on news.ycombinator.com