8 ms·

Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. This is one of them. Rotatin

Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. This is one of them. Rotating images that way isn’t CPU bound problem. It’s RAM bandwidth and RAM latency bound problem. The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If they are RGB, one good format for those images, optimized for rotations, is BC7 https://www.opengl.org/registry/specs/ARB/texture_compression_bptc.txt https://www.opengl.org/registry/specs/ARB/texture_compressio... the decompressor being implemented right in the graphics hardware. > If we were writing an image manipulation application, we’d provide much snappier behaviour using coloured quadtrees to represent images on screen. That statement was true 30 years ago, no longer a case. Branch misprediction is expensive, memory latency is huge, RAM is a block device now (the block size typically being 16 bytes for dual-channel DDR). In addition, some displays now show 8+ megapixels, and most show 16M colors. For an image manipulation application, that recursive thing ain’t good at all.

taeric 10y ago
At face value, I don't actually see where you contradict the article. The recursive nature of this solution is akin to recursive matrix multiplication. Which can be a way to setup memory fetches to stay optimal. (Could... I have no data to say it is.) Any chance you know of any benchmarks exploring this?
- GFK_of_xmaspast 10y ago
  Recursive matrix multiplication is in general a bad idea (Strassen, for example, loses a little bit of stability and is not cache-friendly)
  - taeric 10y ago
    To be clear, I can see why coding it purely recursively would be a bad idea. Same for using linked structures, if that was the concern with the quad tree. However, it seems that you could use the general recursive definition to find some optimizations that one could do. For example, define a recursive structure to break down a problem until it is small enough that a more traditional method works. (So, don't drop down to the size of a pixel, but do drop down till you have things at cache line size?) Perusing the wikipedia for Strassen, I see that it scoffs at a ~10% benefit for large matrices. Curious how that holds in light of "deep learning" environments. Especially since 1k x 1k matrices are probably not that uncommon nowdays. Seems like every little bit would help. Edit to add: THinking of the context of the original post. Yeah... probably not needed for anything in a "snappy" user application. I was thinking more for very large data sets.
    - rrobukef 10y ago
      Very large matrices is >50kx50k (maybe even bigger). Strassen is then just a tiny bit better when implementing both cache and allocation aware.(Tested in Fortran) At least it's at a non practical size.
      - taeric 10y ago
        It is always interesting to see just how valuable a "tiny bit" can be, though. Granted, I confess most is almost always navel gazing. Increases in the "best" sorting/map algorithm have probably not lead to any noticeable improvements in modern codebases. Usually, those benefit more from being the low hanging fruit, not most computationally complex. (That is, I'm sure in these large matrix problems, there are other low hanging fruit that will yield better improvements.)
    - GFK_of_xmaspast 10y ago
      The mention of "around 10% or less" is based on a 2005 paper, and even in the past ten years there's been a lot of change in computer architecture (the machines used in the paper were mostly ultrasparcs, and they write "Note that for the (pentium 3 system), we could find no problem size for which Strassen’s is faster than ATLAS’s"). See also : https://www.quora.com/What-algorithm-does-BLAS-use-for-matrix-multiplication-Of-all-the-considerations-e-g-cache-popular-instruction-sets-Big-O-etc-which-one-turned-out-to-be-the-primary-bottleneck/answer/Victor-Eijkhout https://www.quora.com/What-algorithm-does-BLAS-use-for-matri... https://github.com/flame/how-to-optimize-gemm/wiki#notice-on-academic-honesty https://github.com/flame/how-to-optimize-gemm/wiki#notice-on... http://www.cs.utexas.edu/~flame/pubs/GotoTOMS_revision.pdf http://www.cs.utexas.edu/~flame/pubs/GotoTOMS_revision.pdf
      - taeric 10y ago
        That is an interesting note. I remember reading that the lower bound on multiplications was lower due to swapping a lot of them for additions. Knuth indicated that this did not matter in practice, since few people are multiplying large matrices. My interest here is really just if that is still a good assumption. With the multiplications that happen in "deep" fields, I'm curious if there are now reasons to look to these algorithms.
empath75 10y ago
I don't think the point of the article was to present an efficient and novel solution for image rotation. It was just a nicely visual example of a recursive data structure.
hinkley 10y ago
For every complex problem there is an answer that is clear, simple, and wrong.
- ivraatiems 10y ago
  A slow solution isn't wrong. Just inefficient.
  - hinkley 10y ago
    We're talking about several orders of magnitude here. Is a web page that loads in fifty seconds 'correct' or is it wrong? Is a video format that can only decode 2 frames per second correct, or wrong? Often, timeliness is an unstated part of the requirements, in which case an academically pleasing solution that isn't practical doesn't fulfill the requirements.
    - lowbloodsugar 10y ago
      >Is a web page that loads in fifty seconds 'correct' or is it wrong? Is a video format that can only decode 2 frames per second correct, or wrong? If your condition of satisfaction is "I am presenting information to someone who will read it", then "loads in fifty seconds" is wrong, yes.
    - yarou 10y ago
      I think you're missing the point. A quadtree is a compact way to store a partition of two-dimensional space, much like you'd store a binary heap in an array. The implementation of a recursive data structure or algorithm can usually take advantage of tail recursion or trampolining. The practical implementation of a theoretical algorithm may look extremely different, much like you wouldn't literally translate abstract pseudocode to the language of your choice.
    - zeveb 10y ago
      > Is a web page that loads in fifty seconds 'correct' or is it wrong? Neither: it's probably using JavaScript to perform an AJAX request to get some data in a bespoke markup format, then using JavaScript to parse that markup format and build DOM entries, all because the developer thinks HTML is 'so 90s, dude!'
inimino 10y ago
>> we’d provide much snappier behaviour using coloured quadtrees > That statement was true 30 years ago, no longer a case. The colored quadtrees are an optimization over the plain quadtrees earlier in the article, reducing the number of comparisons for some images. That will be more efficient 300 years from now just as much as it was 30 years ago. In context it is perfectly obvious that "much snappier" does not refer to the totally different techniques used by actual graphics software. It's a toy implementation used as an example, if you get hung up on the example, you miss the whole point.
- coldtea 10y ago
  >It's a toy implementation used as an example, if you get hung up on the example, you miss the whole point. When to use such techniques, and whether they make sense in the real world, performance wise, should have been part of the "whole point" all along.
  - inimino 10y ago
    By that argument, any blog post that does not contain a comprehensive software development education can be criticized. You should ask whether these techniques are useful in writing correct code and if they save developer effort, rather than picking apart irrelevant aspects of the toy example. I don't think modern graphics code represents individual pixels as strings either, would you dismiss the post for that reason?
munificent 10y ago
> The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If the image is very large and contains large contiguous regions of solid colors, then a quadtree that doesn't subdivide homogeneous regions can be a much faster approach than a flat pile-o-pixels. Either way, this article isn't about rotating images.
- coldtea 10y ago
  >If the image is very large and contains large contiguous regions of solid colors In other words, if the image is not very image-y? (but more vector-y).
  - munificent 10y ago
    You might still want the precision and detail at the boundaries of the shapes that a raster representation would give you. Think big blotchy cow spots or something along those lines.
  - OskarS 10y ago
    It's an entirely plausible scenario. It will rarely be the case with photographs, but graphical images often feature large solid color blocks. It's large reason why the PNG file format exists.
- Const-me 10y ago
  Well, hierarchical representation of those images is indeed a good idea for some data. Saves both RAM space and bandwidth, and CPU time. Just not the quad-tree way described in the article. There are ways to implement hierarchical structures that work well on modern hardware. One is hashmaps keeping dense 2 bits per pixel blocks (again, 16-64 bytes per block) with the values saying filled/empty/mixed. Another one is B-trees or B+ trees.
  - Patient0 10y ago
    How would you improve on the quad-tree representation used to implement hashlife? http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 http://www.drdobbs.com/jvm/an-algorithm-for-compressing-spac...
themckman 10y ago
> Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. I have been doing some data structures/algorithms review as I haven't really used much of that knowledge from my CS degree and, frankly, wasn't that great of a student when I was learning it. I've obviously focused mostly on understanding theoretical performance (Big-O) as I've been implementing and playing with things, but I'd like to know about good resources for things to consider about performance on real systems. I hear about things like cache misses, memory layouts and branch mispredictions, but don't really know how to apply that knowledge or, maybe more importantly, measure the effects of optimizing for some of those things over others. I'd appreciate any advice anyone has to offer.
- Const-me 10y ago
  That Big-O thing is mostly theoretical. Most useful application is job interviews. It might stop you from doing some things, like bubble-sorting 1GB datasets, or inserting many elements to the start of a large array. However, in other cases it’s just fine to bubble-sort (for very small collections), or insert many elements to the start of the array (when you’re reading much more often so the profit from memory locality while reading outweigh the losses from relocating those elements while inserting). Modern hardware is extremely complex. No amount of knowledge will help you to 100% predict the performance effects of your changes. Two advices. (1) Learn to profile your code. Both externally, using a sampling profiler that will tell you where’re you spending the CPU time, and internally using e.g. std::chrono::high_resolution_clock that will tell you the performance effect of your changes. (2) Don’t forget about rollback feature of your version control, and don’t hesitate using that as necessary. I routinely discover some of my changes I viewed as performance optimizations actually decreased performance. The reasons include branch misprediction, compiler optimization issues, cores competition for L3 cache, RAM bandwidth, thermal issues…
  - fanf2 10y ago
    For a dose of real-world big-O I recommend following http://accidentallyquadratic.tumblr.com http://accidentallyquadratic.tumblr.com
braythwayt 10y ago
Although I'm satisfied with the choice I made for what to put in my essay, I want to thank you for pointing out the gaps between my essay and the real world, and for doing so in a forceful way without crossing into being querulous. This kind of discourse is, IMO, an example of Hacker News at its finest.

taeric 10y ago

At face value, I don't actually see where you contradict the article. The recursive nature of this solution is akin to recursive matrix multiplication. Which can be a way to setup memory fetches to stay optimal. (Could... I have no data to say it is.) Any chance you know of any benchmarks exploring this?

GFK_of_xmaspast 10y ago
Recursive matrix multiplication is in general a bad idea (Strassen, for example, loses a little bit of stability and is not cache-friendly)
- taeric 10y ago
  To be clear, I can see why coding it purely recursively would be a bad idea. Same for using linked structures, if that was the concern with the quad tree. However, it seems that you could use the general recursive definition to find some optimizations that one could do. For example, define a recursive structure to break down a problem until it is small enough that a more traditional method works. (So, don't drop down to the size of a pixel, but do drop down till you have things at cache line size?) Perusing the wikipedia for Strassen, I see that it scoffs at a ~10% benefit for large matrices. Curious how that holds in light of "deep learning" environments. Especially since 1k x 1k matrices are probably not that uncommon nowdays. Seems like every little bit would help. Edit to add: THinking of the context of the original post. Yeah... probably not needed for anything in a "snappy" user application. I was thinking more for very large data sets.
  - rrobukef 10y ago
    Very large matrices is >50kx50k (maybe even bigger). Strassen is then just a tiny bit better when implementing both cache and allocation aware.(Tested in Fortran) At least it's at a non practical size.
    - taeric 10y ago
      It is always interesting to see just how valuable a "tiny bit" can be, though. Granted, I confess most is almost always navel gazing. Increases in the "best" sorting/map algorithm have probably not lead to any noticeable improvements in modern codebases. Usually, those benefit more from being the low hanging fruit, not most computationally complex. (That is, I'm sure in these large matrix problems, there are other low hanging fruit that will yield better improvements.)
  - GFK_of_xmaspast 10y ago
    The mention of "around 10% or less" is based on a 2005 paper, and even in the past ten years there's been a lot of change in computer architecture (the machines used in the paper were mostly ultrasparcs, and they write "Note that for the (pentium 3 system), we could find no problem size for which Strassen’s is faster than ATLAS’s"). See also : https://www.quora.com/What-algorithm-does-BLAS-use-for-matrix-multiplication-Of-all-the-considerations-e-g-cache-popular-instruction-sets-Big-O-etc-which-one-turned-out-to-be-the-primary-bottleneck/answer/Victor-Eijkhout https://www.quora.com/What-algorithm-does-BLAS-use-for-matri... https://github.com/flame/how-to-optimize-gemm/wiki#notice-on-academic-honesty https://github.com/flame/how-to-optimize-gemm/wiki#notice-on... http://www.cs.utexas.edu/~flame/pubs/GotoTOMS_revision.pdf http://www.cs.utexas.edu/~flame/pubs/GotoTOMS_revision.pdf
    - taeric 10y ago
      That is an interesting note. I remember reading that the lower bound on multiplications was lower due to swapping a lot of them for additions. Knuth indicated that this did not matter in practice, since few people are multiplying large matrices. My interest here is really just if that is still a good assumption. With the multiplications that happen in "deep" fields, I'm curious if there are now reasons to look to these algorithms.

empath75 10y ago

I don't think the point of the article was to present an efficient and novel solution for image rotation. It was just a nicely visual example of a recursive data structure.

hinkley 10y ago

For every complex problem there is an answer that is clear, simple, and wrong.

ivraatiems 10y ago
A slow solution isn't wrong. Just inefficient.
- hinkley 10y ago
  We're talking about several orders of magnitude here. Is a web page that loads in fifty seconds 'correct' or is it wrong? Is a video format that can only decode 2 frames per second correct, or wrong? Often, timeliness is an unstated part of the requirements, in which case an academically pleasing solution that isn't practical doesn't fulfill the requirements.
  - lowbloodsugar 10y ago
    >Is a web page that loads in fifty seconds 'correct' or is it wrong? Is a video format that can only decode 2 frames per second correct, or wrong? If your condition of satisfaction is "I am presenting information to someone who will read it", then "loads in fifty seconds" is wrong, yes.
  - yarou 10y ago
    I think you're missing the point. A quadtree is a compact way to store a partition of two-dimensional space, much like you'd store a binary heap in an array. The implementation of a recursive data structure or algorithm can usually take advantage of tail recursion or trampolining. The practical implementation of a theoretical algorithm may look extremely different, much like you wouldn't literally translate abstract pseudocode to the language of your choice.
  - zeveb 10y ago
    > Is a web page that loads in fifty seconds 'correct' or is it wrong? Neither: it's probably using JavaScript to perform an AJAX request to get some data in a bespoke markup format, then using JavaScript to parse that markup format and build DOM entries, all because the developer thinks HTML is 'so 90s, dude!'

inimino 10y ago

>> we’d provide much snappier behaviour using coloured quadtrees > That statement was true 30 years ago, no longer a case. The colored quadtrees are an optimization over the plain quadtrees earlier in the article, reducing the number of comparisons for some images. That will be more efficient 300 years from now just as much as it was 30 years ago. In context it is perfectly obvious that "much snappier" does not refer to the totally different techniques used by actual graphics software. It's a toy implementation used as an example, if you get hung up on the example, you miss the whole point.

coldtea 10y ago
>It's a toy implementation used as an example, if you get hung up on the example, you miss the whole point. When to use such techniques, and whether they make sense in the real world, performance wise, should have been part of the "whole point" all along.
- inimino 10y ago
  By that argument, any blog post that does not contain a comprehensive software development education can be criticized. You should ask whether these techniques are useful in writing correct code and if they save developer effort, rather than picking apart irrelevant aspects of the toy example. I don't think modern graphics code represents individual pixels as strings either, would you dismiss the post for that reason?

munificent 10y ago

> The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If the image is very large and contains large contiguous regions of solid colors, then a quadtree that doesn't subdivide homogeneous regions can be a much faster approach than a flat pile-o-pixels. Either way, this article isn't about rotating images.

coldtea 10y ago
>If the image is very large and contains large contiguous regions of solid colors In other words, if the image is not very image-y? (but more vector-y).
- munificent 10y ago
  You might still want the precision and detail at the boundaries of the shapes that a raster representation would give you. Think big blotchy cow spots or something along those lines.
- OskarS 10y ago
  It's an entirely plausible scenario. It will rarely be the case with photographs, but graphical images often feature large solid color blocks. It's large reason why the PNG file format exists.
Const-me 10y ago
Well, hierarchical representation of those images is indeed a good idea for some data. Saves both RAM space and bandwidth, and CPU time. Just not the quad-tree way described in the article. There are ways to implement hierarchical structures that work well on modern hardware. One is hashmaps keeping dense 2 bits per pixel blocks (again, 16-64 bytes per block) with the values saying filled/empty/mixed. Another one is B-trees or B+ trees.
- Patient0 10y ago
  How would you improve on the quad-tree representation used to implement hashlife? http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 http://www.drdobbs.com/jvm/an-algorithm-for-compressing-spac...

themckman 10y ago

> Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. I have been doing some data structures/algorithms review as I haven't really used much of that knowledge from my CS degree and, frankly, wasn't that great of a student when I was learning it. I've obviously focused mostly on understanding theoretical performance (Big-O) as I've been implementing and playing with things, but I'd like to know about good resources for things to consider about performance on real systems. I hear about things like cache misses, memory layouts and branch mispredictions, but don't really know how to apply that knowledge or, maybe more importantly, measure the effects of optimizing for some of those things over others. I'd appreciate any advice anyone has to offer.

Const-me 10y ago
That Big-O thing is mostly theoretical. Most useful application is job interviews. It might stop you from doing some things, like bubble-sorting 1GB datasets, or inserting many elements to the start of a large array. However, in other cases it’s just fine to bubble-sort (for very small collections), or insert many elements to the start of the array (when you’re reading much more often so the profit from memory locality while reading outweigh the losses from relocating those elements while inserting). Modern hardware is extremely complex. No amount of knowledge will help you to 100% predict the performance effects of your changes. Two advices. (1) Learn to profile your code. Both externally, using a sampling profiler that will tell you where’re you spending the CPU time, and internally using e.g. std::chrono::high_resolution_clock that will tell you the performance effect of your changes. (2) Don’t forget about rollback feature of your version control, and don’t hesitate using that as necessary. I routinely discover some of my changes I viewed as performance optimizations actually decreased performance. The reasons include branch misprediction, compiler optimization issues, cores competition for L3 cache, RAM bandwidth, thermal issues…
- fanf2 10y ago
  For a dose of real-world big-O I recommend following http://accidentallyquadratic.tumblr.com http://accidentallyquadratic.tumblr.com

braythwayt 10y ago

Although I'm satisfied with the choice I made for what to put in my essay, I want to thank you for pointing out the gaps between my essay and the real world, and for doing so in a forceful way without crossing into being querulous. This kind of discourse is, IMO, an example of Hacker News at its finest.