Optimization Question

Do while loops are a little bit faster than for loops. And if any of your enemies are not transparent then you should make another function for that case.

*** Triality ***

Everything I''m drawing is transparent, so I don''t need a non-transparent function. And, instead of code structure stuff (while vs. for loops) I was thinking of something in the "algorithm" itself. I doubt anything is there to be optimized, but I''m just thinking it''s weird, because when I turn on compiler optimizations, it goes back up to 86 FPS, so it seems the compiler can find something...

That algorithm is O(n^2), because you have a loop nested within another loop. Very slow.

Usually you''d do something like this:

DWORD ScreenLine = Top * ScreenPitch;
DWORD PicLine = 0;
DWORD PicDelta = (Right - Left) * (ScreenBits >> 3);
for( Y = Top; Y < Bottom; Y ++ )
{
    memcpy( &VideoBuffer[ScreenLine + Left], &PicBuffer[PicLine], PicDelta );
    ScreenLine += ScreenPitch;
    PicLine += PicDelta;
}

That''s as fast as DirectDraw''s BltFast, but it doesn''t allow for transparency. You''d have to write an assembly blitter and optimize it (that''s a good idea even for opaque sprites). I''m not sure how the transparency code would be done, though.

~CGameProgrammer( );

CGameProgrammer, it''s not n^2 unless you define n to be the average width of an image. It''s actually linear in the total size of the bitmap ( width*height, which is where the double loop comes from ).
Speeding it up - the only thing I could think of is to RLE the transparency data so you can skip large parts..


#pragma DWIM // Do What I Mean!
~ Mad Keith ~
**I use Software Mode**

Honestly, I doubt it has ANYTHING to do with memory. It''s the fact that your innermost loop contains an ''if''. Remember, ifs mean branch instructions, which means stalling and flushing the pipeline. Putting one in a loop to be executed that many times is a recipe for slowdown. And if the compiler can unroll the loop and schedule things a little better, it would explain the change in a release build.

As for fixing it... You may want to see if there''s some way to avoid the if by using masking operations that will achieve the same end result. It all depends on how your colors are stored.

-Brian

Use Blt, there''s no better way.
Also surfaces in video memory with blt are very fast, since it''s all accelerated and the CPU does virtual squat.


The_Minister

quote:

---

Original post by The_Minister

Use Blt, there''s no better way.

---

If by the best way, you mean the fastest, you are wrong. Compiled sprites still whoop the crap out of blits. Basically, what you do is write a program that takes your sprites and turns them into code. Then you just call that function to display them. Technically, it runs in O(1) time. RLE has been said to run faster than Blits also, and doesn''t take precomputation. But then we are into linear with respect to non-transparent pixels.
However, if by best you mean easiest and laziest way, then you are correct.

Mike

I somehow doubt that you could get straight CPU-only asm code faster than a hardware supported Alpha blit myself...

Did some fast coding once upon a time, and found it sucked. Using other people''s stuff is much more efficient :-).

So basically: if you have HW support for your transparent blits ( or alpha blits ) use that, if you don''t, use a highly optimised ASM version for the software side of things.


#pragma DWIM // Do What I Mean!
~ Mad Keith ~
**I use Software Mode**

But the software blit is faster on small images due to almost zero overhead...

-Dimonic-

Well to that I''d reply - if you''re doing lots of small blits, you''re probably doin something wrong ;-)


#pragma DWIM // Do What I Mean!
~ Mad Keith ~
**I use Software Mode**

Hmm, particle system where particles are very small bitmaps,
is an example. Any hardware blitter will die doing this blits.

> That algorithm is O(n^2), because you have a loop nested > within another loop. Very slow.
>
> Usually you''d do something like this:
[a severely misguided piece of code removed]

Uh, what exactly do you think memcpy() does? Last time I checked, it copied memory in a loop.

> If by the best way, you mean the fastest, you are wrong.
> Compiled sprites still whoop the crap out of blits.
> Basically, what you do is write a program that takes your
> sprites and turns them into code. Then you just call that
> function to display them. Technically, it runs in O(1)
> time.

I really hope that one day, the overwhelming confusion that seems to reign in the game development field regarding the Big-O notation will dissipate and people will stop throwing around sentences like "Technically, it runs in O(insert your favorite low order term here) time" without having absolutely any idea what they''re saying.

>Hmm, particle system where particles are very small bitmaps,
>is an example. Any hardware blitter will die doing this blits.

Have you actually tried comparing 16x16 alpha hardware blit to software compiled sprite blit or are you just talking out of your ass?

Sorry, but the amount of blatant misinformation distributed on the gamedev.net forums is really starting to get to me.

-goltrpoat







--
Float like a butterfly, bite like a crocodile.

wayne,

good to finally see someone with a clue here.

-goltrpoat



--
Float like a butterfly, bite like a crocodile.

oh, also, depending on your compiler's optimization abilities, it is usually better to increment a pointer instead of an index to the array on x86 processors, i.e.

instead of
for (x = 0; x < n; x++) { data[x] = blah; }

it's faster to do
pdata = data; for (x = 0; x < n; x++, pdata++) { *pdata = blah; }

-goltrpoat




--
Float like a butterfly, bite like a crocodile.



Edited by - goltrpoat on 4/25/00 2:09:27 PM

goltrpoat - It''s ironic how it is more worth your time to bitch about ''blatent misinformation'' than actually correct anything someone may have said wrong. At least AP Wayne was constructive. I was under the impression (and I may be wrong) that you need a loop for 0(n) time; compiled sprites (at least the way I would do them) would have no loops. Please correct me if I am wrong, not go into some hissy-fit about blatent misinformation.


Mike

you are wrong and you have been corrected.
for further correction, consult your local library. i''m not here to explain CS 101 to you.

-goltrpoat


--
Float like a butterfly, bite like a crocodile.

wayne - in my experience, most compilers automatically expand for loops to a dec/jnz pair even with optimization off.. but yeah, it''s probably better to declare them that way just in case

-goltrpoat




--
Float like a butterfly, bite like a crocodile.

And we''re not here to listen to your arrogant remarks.

Qoy, you''ve probably already heard this and are using it already, but here it is:

1.Don''t lock the surface more than once per frame. Lock it, blit, blit, blit, blit, etc., and unlock it.

2.Don''t use the Windows GDI for anything other than debug text that won''t be in the final version. (If you''re printing debug labels on the sprites, this will affect you.)

Other than that, I don''t know what could be slowing down your code other than unoptimized pre/post-blit sprite handling.

Hope this helps

[ ^L _N ^T _A ^K _I ^T _O ^P _I ]
http://geocities.com/guanajam/