Jump to content

Processing Left to Right

Recommended Posts

When running the following loop (from codelab):

void Render(Surface dst, Surface src, Rectangle rect)
   for(int y = rect.Top; y     {
       for (int x = rect.Left; x         {

Rick, I tried to reverse these loops (to process left to right instead of top to bottom). But, the preview is slow enough to watch it process and it still goes top to bottom.

Is this right? Is this a limitation?

Link to comment
Share on other sites

Why would you need to do that though?

Seriously -- processing left->right, top->bottom takes most advantage of cache locality. Anytime you access a pixel in memory, the incurred cache miss will bring in the surrounding pixels as well. But 'surrounding' is based on the memory layout, and in our case that means horizontally.

So having left->right as the inner loop exploits this. When you reverse the loops, you nullify your cache. So let's say you start at (0,0) and run all the way to (0,1023). Every one of those memory accesses has brought in pixels (0,n) through (31,n) [for instance]. By the time you get to the bottom, just going based on a simple LRU cache ejection algorithm, you're already kicking out the top rows' cachelines. So when you start your next loop at (0,1) you're back to cache misses. Which means you're doing 8 to 32x the memory bandwidth, depending on the cacheline size of your processor.

But if you access (0,0) and then (0,1) right away, you do a cache miss and then a cache hit: much faster.

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html


Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...