Cache misses


Loonie

Active Member
Joined
Apr 1, 2003
Messages
753
Hello programmer types with Pandora experience,

I'm creating some elaborate bitmap transforms for a game background, basically precalculated stuff stored in a 2D one-dimensional integer array. The array contains which pixel of the bitmap should be displayed in which pixel of screen. This is all working great, except as you can guess from the title, I'm running into some performance issues.

The arrays are getting cached, but since the image array is accessed in a rather non-uniform fashion (especially with the more complex and fancy transforms), I am running into some rather costly performance issues with what appear to be cache misses. It seems to be to such an extent that performance would be improved if the arrays were not cached at all.

I understand cache misses are quite severe with this architecture. What tricks are there for getting around this? I could reduce the amount of data by using tricks like pixel-doubling, but I would rather use the full resolution, as it looks pretty damn nice. I may not have much choice though.

Is there a way to access arrays directly from the memory and not have them get cached, or is this something I have no control over? Any performance enhancing tricks I'm unaware of? Perhaps goat sacrifice to the dark snake-headed lord?


Edited because: derp.
 
Last edited by a moderator:
So what you're saying is that your loads are random and your stores are linear. Is it possible to invert the transformation so your loads are linear and your stores random? That will perform better, because stores fill up a write coalescing buffer instead of immediately blocking. You'll want to then prefetch the loads.

If you're using an indirection array over the whole screen (assuming 800x480) that'll miss L2 as well. If you can do anything to lower the size of this array it'll help, like if you can use delta encoding. These loads should also be prefetched.

I don't think going uncached is the answer you're looking for, unless you really have no locality of reference at all.
 
Last edited by a moderator:
So what you're saying is that your loads are random and your stores are linear. Is it possible to invert the transformation so your loads are linear and your stores random? That will perform better, because stores fill up a write coalescing buffer instead of immediately blocking. You'll want to then prefetch the loads.


If you're using an indirection array over the whole screen (assuming 800x480) that'll miss L2 as well. If you can do anything to lower the size of this array it'll help, like if you can use delta encoding. These loads should also be prefetched.
That's basically it. The load is fairly random, or at least jumping frequently between extremes. The hurdle I have with the data restructuring is that I'm not accessing the same area of the image data every time. There's an offset applied to the point of where the image data is initially accessed, and this is incremented each frame to pan the image through the transform. I've improved the situation a little, by only using the blue channel of the image, thus allowing me to store the image data in a Uint8 array, rather than a Uint32, then using that data to access a colour table.

Delta encoding is an interesting idea. I guess that means rather than storing an absolute image position, I simply store the offset from the current image pixel to the next one, right? Especially if that difference is always under 256, I could use a Uint8 array to store the data. That would cut the memory usage down to 25%. Apart from that, I guess the remaining avenue is pixel-doubling on the background, which would certainly reduce memory cost, if impact the visuals a little.

I especially want to make sure this will work on the older Pandoras, as I'm developing on a 1GHz unit, so I'll probably make a PND and get some performance feedback from users, once I've played around more.

Thanks for the reply, Exo. Most helpful.
 
What's the nature of these transforms? If they good spatial locality of reference in 2D but not 1D your best bet is to store the image tiled and process it in blocks. This could also fit well with delta encode spanning a block.
 
The transform looks like this:


int zxcyscale;
int zxcxscale;
for (int zxcy=0; zxcy<480; zxcy++)
{
zxcyscale = (tan ((zxcy+395) / 202.0)) * 240;

for (int zxcx=0; zxcx<800; zxcx++)

{
zxcxscale = (zxcx-400) * (( sin(zxcy/152.788745368) *1.2) +1);

imgtransform[zxcx+(zxcy*800)] = (Uint32) (zxcxscale+400)+(zxcyscale*2048);
}

}

The part writing to the screenbuffer:


while (zxcplot<384000)
{

screenpixels [zxcplot] = img2048 [ (imgtransform [zxcplot] + zxcoffset) & imglimit];
zxcplot ++;

}

(Imglimit is image width*image height, the image dimensions are always a factor of 2, so it can easily be prevented from going beyond the image buffer)

Edit: Oh, and I was mistaken in my original post. All the arrays are one dimensional, not 2D. 2D arrays are hugely slow.
 
Last edited by a moderator:
Hmm... I did a quick std::cout of the deltas involved, and apart from the end-line parts of the array, the numbers involved are pretty small. Since I know that the big number is going to come every 800 steps, I reckon I could use a Uint8 array for the majority of the transform, and an int array to store the 480 large values of the line-feed. That should help quite a bit.

I shall try this out ASAP! Thanks again Exo, always good to have a far more experienced mind to offer ideas.
 
You could do an encoding where a 255 (or whatever of the 256 values isn't used much) means to use the value in the next 2 (or however many) bytes. That'll improve locality.
 
You could do an encoding where a 255 (or whatever of the 256 values isn't used much) means to use the value in the next 2 (or however many) bytes. That'll improve locality.
Another interesting idea. Although wouldn't that introduce an "if" statement for every pixel?

Man, you sure can tell I don't come from a C/C++ background.
 
I'd like to help with this, but can you post or attach or privately send a small complete program or .zip if you need to load an image,

which uses this to draw or animate something pretty on the screen?

If I can actually see what it's doing, I'll be more motivated to try and optimize it!  and might better understand the intent of the code.

FWIW, Exophase idea of processing in tiles sounds like a good one...
 
Last edited by a moderator:
Another interesting idea. Although wouldn't that introduce an "if" statement for every pixel?

Man, you sure can tell I don't come from a C/C++ background.
It'll introduce if statements but so would something that checks for another array every 800 iterations. You can unroll the latter, but you can do something similar for the former too, ie check for 4 pixels at a time or so.

If you really have it every 800 you can hardcode that, but I still think you should interleave that data.

I get the feeling if you block things your deltas will be a bit different anyway.. and you won't have something at the end of scanlines like that.
 
Well, some progress. I've gone from an original render time of 20mS per frame to 12 mS per frame using the colour look-up to 9mS per frame using a delta method. That would likely leave enough room for the game on the 1GHz unit at 60 fps, though I'm still not sure about the 600 MHz units.

I shall try it as you suggest tomorrow, Exo. Thanks for the advice.

Thanks too for your offer, Dredd. I may take you up on that, but for now I best get to sleep. Stupid work grumble grumble.
 
I did the trick of incorporating the large end-of-line number into the Uint8 string, and every 800th position I treat as a signed short. Works like a charm, though performance has improved by a fraction, down to an average of 8mS per frame. Fast enough for the 1GHz, but I suspect in the interests of supporting older Pandoras, I may still use pixel-doubling. I'll try to get a test-case up for some feedback.
 
Back
Top