4 ms·

It's easy to parallelize this, and at a certain recursion level the whole block will fit into cache, so this might avoid inefficient memory access compared to a

It's easy to parallelize this, and at a certain recursion level the whole block will fit into cache, so this might avoid inefficient memory access compared to a naive for-loop that just moves every pixel to its rotated position.

dan-robertson 5y ago
Except you need to access each pixel log(n) times and it doesn’t obviously work for non-square images (or for non-right rotations). Compare to the normal way you rotate things by right angles where e.g. new_image(x,y) = old_image(y, old_height - x), which is extremely embarrassingly parallel. The actual reason is that it is fun.
- CyberShadow 5y ago
  > new_image(x,y) = old_image(y, old_height - x) If you implement this as a view (rather than imperatively), you can get the compiler to optimize out four successive rotations to nothing :) https://blog.cy.md/2014/03/21/functional-image-processing-in-d/ https://blog.cy.md/2014/03/21/functional-image-processing-in...
- gsliepen 5y ago
  I assume that in an actual implementation you are not really processing every pixel log(n) times, but rather do something like new_image = rotate(old_image, 1), where 1 is the recursion level, and rotate(image, level) calls rotate(subset_of(image), level + 1) recursively until it reaches a single pixel, which is then returned as-is. Combined with return value optimization, that should avoid any temporaries being stored. But yes, it's mostly fun :)
  - dan-robertson 5y ago
    In that world doesn’t it just compile to the thing I wrote above (if you’re lucky)? In the GP you said it would be more cache-efficient or something but that’s just not true if it compiles to the same code is it?
    - gsliepen 5y ago
      No, the order in which things happen would be different, and this is what might make it more cache-efficient for rotating large images. It should look like this: https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve
      - dan-robertson 5y ago
        I’m really confused by what you mean. If you’re not executing the line I wrote above (in parallel) then what are you doing? The things I could think you meant were: - moving data in stages like the OP video which might be better for the cache (I don’t believe this) but would require writing to/from me more multiple times per pixel which I think would make it slower - Accessing memory in a certain order when doing this on a cpu. Certainly that is a reasonable thing to expect to improve performance (roughly breaking the image into blocks that fit exactly into N cache lines, rotating in registers/memory, then writing into exactly N cache lines means you aren’t reading data from RAM/cache that you can’t use), but I don’t think that is related to the recursive process described in the article, unless you mean that you can use this process to get some operations like block(x,y,16) moves to block(s,t,16) and those could be executed cache-efficiently? But then this recursive method is more confusing and more restrictive on the image size than the thing I tried to describe at the start of this bullet point

dan-robertson 5y ago

Except you need to access each pixel log(n) times and it doesn’t obviously work for non-square images (or for non-right rotations). Compare to the normal way you rotate things by right angles where e.g. new_image(x,y) = old_image(y, old_height - x), which is extremely embarrassingly parallel. The actual reason is that it is fun.

CyberShadow 5y ago
> new_image(x,y) = old_image(y, old_height - x) If you implement this as a view (rather than imperatively), you can get the compiler to optimize out four successive rotations to nothing :) https://blog.cy.md/2014/03/21/functional-image-processing-in-d/ https://blog.cy.md/2014/03/21/functional-image-processing-in...
gsliepen 5y ago
I assume that in an actual implementation you are not really processing every pixel log(n) times, but rather do something like new_image = rotate(old_image, 1), where 1 is the recursion level, and rotate(image, level) calls rotate(subset_of(image), level + 1) recursively until it reaches a single pixel, which is then returned as-is. Combined with return value optimization, that should avoid any temporaries being stored. But yes, it's mostly fun :)
- dan-robertson 5y ago
  In that world doesn’t it just compile to the thing I wrote above (if you’re lucky)? In the GP you said it would be more cache-efficient or something but that’s just not true if it compiles to the same code is it?
  - gsliepen 5y ago
    No, the order in which things happen would be different, and this is what might make it more cache-efficient for rotating large images. It should look like this: https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve
    - dan-robertson 5y ago
      I’m really confused by what you mean. If you’re not executing the line I wrote above (in parallel) then what are you doing? The things I could think you meant were: - moving data in stages like the OP video which might be better for the cache (I don’t believe this) but would require writing to/from me more multiple times per pixel which I think would make it slower - Accessing memory in a certain order when doing this on a cpu. Certainly that is a reasonable thing to expect to improve performance (roughly breaking the image into blocks that fit exactly into N cache lines, rotating in registers/memory, then writing into exactly N cache lines means you aren’t reading data from RAM/cache that you can’t use), but I don’t think that is related to the recursive process described in the article, unless you mean that you can use this process to get some operations like block(x,y,16) moves to block(s,t,16) and those could be executed cache-efficiently? But then this recursive method is more confusing and more restrictive on the image size than the thing I tried to describe at the start of this bullet point