4 ms·

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 implem

• kragen 3y ago
  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
  • kragen 3y ago
    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
    • kragen 3y ago
      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
• ghusbands 3y ago
  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).
  • kragen 3y ago
    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
    • ghusbands 3y ago
      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.
      • kragen 3y ago
        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
  • irskep 3y ago