huge array lookup?

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|724\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> C/C++/C#/Other -> huge array lookup?
Sun, 13 Mar 2011, 12:44
spinal	Hi guys, I am currently attempting to replace an equation in my program with a lookup table, however,I don't seem to be getting back the results I expect Have I done something stupid in the following code? int pixelMix[3232255]; void makeMix(void) { int back=0, front=0, alpha=0; for(front=0; front<32; front++){ for(back=0; back<32; back++){ for(alpha=0; alpha<256; alpha++){ pixelMix[front+(32back)+(256alpha)] = back+(((front-back)(255-alpha))>>8); } } } } int mix(int back, int front, int alpha) { // return back+(((front-back)(255-alpha))>>8); return pixelMix[front+(32back)+(256alpha)]; } --v I'm not quite sure what I'm doing wrong? could it be the way I am filling the array? -=-=- Check out my excellent homepage!
Sun, 13 Mar 2011, 13:30
JL235	Your replacing an add, a multiply and a right shift: back+(((front-back)(255-alpha))>>8) --v with 2 adds, 2 multiplies and a memory lookup: pixelMix[front+(32back)+(256*alpha)] --v That's why it's slower. But you could try replacing the power of two multiplies with left-shifts: pixelMix[front+(back << 5)+(alpha << 8)] --v ... that should be faster then your current approach, but I'd be skeptical it'll be faster then the original (at least not by much if it is). You could also make the function 'inline', but compilers today should be able to inline anyway if appropriate.
Sun, 13 Mar 2011, 13:42
Jayenkai	"wrong" not slower! The wrong is the alpha256.. (c(a'sb's))+(ba's)+a -=-=- ''Load, Next List!''
Sun, 13 Mar 2011, 13:57
JL235	Really? but he's doing more work! How can that not be slower???
Sun, 13 Mar 2011, 14:10
Jayenkai	It probably is slower.. But I'm guessing this is for something pallette based that'll be outputted for reuse later.. I'm only guessing that, mind! Spinal does a lot of imagey stuff... This could, quite frankly, be ANYTHING!!!! -=-=- ''Load, Next List!''
Sun, 13 Mar 2011, 14:34
spinal	I might not have been very clear with the initial question... I currently have this - int mix(int back, int front, int alpha) { return back+(((front-back)*(255-alpha))>>8); } Which I am using to calculate a mixture of two colours. Currently I am calculating this 3 times per rendered pixel (r,g,b), as part of my bitmap routine, which could easily be called a lot more than 49152 times per frame, depending on how many images I am drawing. I figured as my 3 inputs are maxed at 32,32,255, it would be quicker to calculate the whole lot at the start, then just look up the values for each pixel instead of calculating them. -=-=- Check out my excellent homepage!
Sun, 13 Mar 2011, 15:03
Jayenkai	Ah, then yeah, DDs is quicker. Just do the maths on the fly. Otherwise you're doing different maths, AND a lookup. It'd be marginally quicker to just do the maths on it's own. I figured you'd be doing your usual number juggling stuff!! -=-=- ''Load, Next List!''
Sun, 13 Mar 2011, 16:08
JL235	First, none of us really know if it's faster or slower. You can only find that out by profiling your code! Unless you do this you won't get any real speed-ups! There is this: int colora = 0xFFFFFF; // a color int colorb = 0xFF007F; // other color int rb = (colora & 0xFF00FF) + (alpha * (colorb & 0xFF00FF)); int g = (colora & 0x00FF00) + (alpha * (colorb & 0x00FF00)); return (rb & 0xFF00FF) + (g & 0x00FF00); --v that I just found on Stack Overflow. It works by calculating two colors at once, allowing you to make it a little faster. I've also just dusted down my own fast alpha routine from one of my first Blitz Basic projects! Turns out I'm doing very similar: Function fastAlpha(argb1, argb2) alpha=argb1 Shr 24 r_b1=argb1 And $00ff00ff gre1=argb1 And $0000ff00 r_b2=argb2 And $00ff00ff gre2=argb2 And $0000ff00 r_b0=(r_b1alpha+r_b2(255-alpha))And $ff00ff00 gre0=(gre1alpha+gre2(255-alpha))And $00ff0000 Return (r_b0 Or gre0)Shr 8 End Function --v Finally if you can represent the pixels different (so it's optimized to make the lookup calculation as fast as possible) then the lookup method could be faster. But again, you'll only know if you profile your code!
Sun, 13 Mar 2011, 16:23
JL235	You could also try: #define pixelLocation( front, back, alpha ) ( ((front) << 13) \| ((back) << 8) \| (alpha) ) // maximum location + 1 to include 0 int pixelMix[ pixelLocation(31, 31, 255) + 1 ]; void makeMix(void) { int back=0, front=0, alpha=0; for(front=0; front<32; front++){ for(back=0; back<32; back++){ for(alpha=0; alpha<256; alpha++){ pixelMix[ pixelLocation(front, back, alpha) ]; } } } } int mix(int back, int front, int alpha) { return pixelMix[ pixelLocation(front, back, alpha) ]; } --v There I'm performing 2 bitwise shifts and 2 bitwise or's to calculate the location of the pixel. But with the lookup, I still don't know if it would be faster or slower.