Speed Optimization

[SirDzstic]

Hello,

I am developing a 3d engine for about two weeks now, which I would like to use on my GP2X.
Sadly, the performance is abysmal. I get about 1-2 FPS on the GP2X. When I run it natively
I get about 130. Then of course, my computers is some orders of magnitude more powerful.

I would be grateful, if you could tell me some general steps to gain performance on the GP2X,
like CFLAGS, or some tips specific to my program.
I hope the source and my comments are comprehensible. If you have questions, I will answer
them as good as I can.

Profiling output:

% cumulative self self total
time seconds seconds calls us/call us/call name
51.47 0.35 0.35 54964 6.37 10.73 drawslice
35.29 0.59 0.24 13214110 0.02 0.02 setpixel
8.82 0.65 0.06 54964 1.09 1.09 castray
4.41 0.68 0.03 renderscene
0.00 0.68 0.00 12288 0.00 0.00 getpixel
0.00 0.68 0.00 16 0.00 0.00 printc
0.00 0.68 0.00 3 0.00 0.00 loadtexture
0.00 0.68 0.00 2 0.00 0.00 data_start
0.00 0.68 0.00 2 0.00 0.00 gettime
0.00 0.68 0.00 1 0.00 0.00 defaults
0.00 0.68 0.00 1 0.00 0.00 initif
0.00 0.68 0.00 1 0.00 0.00 initvideo
0.00 0.68 0.00 1 0.00 0.00 precompute

drawslice() accounts for half of the time of the process. So I think it would be reasonable to try
and make this function faster. Any suggestions are appreciated.

Source: http://dzs.gaenseblum.org/raycast-0.0.7.tar.gz

TARGET=native ./configure
make

Run with bin/ray in the main directory of the archive or give the path to data/ as parameter.

€: You may have to change the CFLAGS in the Makefile to get the program to compile.

 

[mrsnature]

just having a quick look, and it seems there is a lot of multipling with 'ratio', a double, in the drawslice function?

 

[SirDzstic]

Yes, that's correct. It is the ratio of the actual height of the texture to the height that will be drawn
on the screen. I could just use "GRID_SIZE / renderheight" (which are both integers) instead of that,
but the value is constant for the whole column of the screen that is being rendered, so I let it be
precomputed.

I can't cast it to int, because then the texture won't be scaled correctly (It would only be scaled by
a factor that is an integer, so obviously, that won't look as it should).

 

[mrsnature]

if you are set on using floats then make sure the -msoft-float option is set when you compile, and -o3.

 

[PokeParadox]

Also use a float not a double... floats are slow enough doubles... doubly so.

 

[mrsnature]

And use a lookup table for all those sin, cos, and tans in castray()

Edit: and consider using fixed point values for the most repetative bits of the rendering code

i.e.

CODE

int ratio = (GRID_SIZE << 8) / (double)renderheight;
...
...
tex_y = (ratio * i) >> 8;

 

[SirDzstic]

I changed the type of ratio to float. And I guess tomorrow I'll look into setting up some lookup tables for
the trigonometric functions. Although I don't think it's them that significantly slow down the program.

Edit: In fact, I have a reason why don't think that... according to gprof, castray() uses one order of magnitute
less time than setpixel() or drawslice().

 

[PokeParadox]

Well a loopup table for trig functions will gain you some extra CPU time for other uses, so it's always a good thing to do on a console like GP2X.

 

[mrsnature]

have you trid compiling with -msoft-float? i've heard it will make a big difference

 

[SirDzstic]

I tried the shift by 8, but it caused distortion on the textures.
I played around a bit with the operand, and a shift by 11 seemed
to be a good trade-off between performance and distortion.

I gained about 10-20FPS and the image suffers only minor distortions.
Edit2: I mean an increase of 10-20FPS when running it natively.
This is an increase of about 10%, so it is not enough to get an
acceptable framerate on the gp2x.

Thanks for this tip. I guess I can use this technique to avoid a lot
of floats/doubles.

Edit:

I used -msoft-float, but I got a lot of errors about unresolved symbols by the linker.
Do I have to link against a special library to use this flag?

 

[rokdcasbah]

This is an increase of about 10%, so it is not enough to get an
acceptable framerate on the gp2x.

yes but it could make a much larger difference on the gp2x, depending on how much floating point code you are able to replace.

you need to avoid floating point and trig functions at all costs, since the gp2x cannot do these in hardware. but the performance gain you get from doing that is not going to be as evident on a pc, where there's hardware floats.

using a lookup table for trig functions is (at least in my opinion) easier than using fixed-point code in your engine. moving to fixed point can be a lot of work. but a LUT for trig is a simpler switch that you should definitely do.

using the compiler optimized soft floats is much better than letting the gp2x do it. but unfortunately i'm not enough of a coder to help you with the linker issues. but i'm pretty sure that yes there is a soft-float library, but there's a good chance whatever devkit you're using has it included already. dunno though, hopefully someone with more knowledge can answer that.

what dev kit are you using?

 

[Dr_Ian]

you need to avoid floating point and trig functions at all costs, since the gp2x cannot do these in hardware. but the performance gain you get from doing that is not going to be as evident on a pc, where there's hardware floats.

Quoted for truth. This is probably the biggest reason for your slowness.

 

[rabidcow]

Yes, that's correct. It is the ratio of the actual height of the texture to the height that will be drawn
on the screen. I could just use "GRID_SIZE / renderheight" (which are both integers) instead of that,
but the value is constant for the whole column of the screen that is being rendered, so I let it be
precomputed.

I can't cast it to int, because then the texture won't be scaled correctly (It would only be scaled by
a factor that is an integer, so obviously, that won't look as it should).

If you're only drawing surfaces parallel to a screen edge, you can use Bresenham's algorithm to interpolate between screen and texture space using entirely integer math. As I understand it, this was used in Doom to make it run fast enough on the pitiful machines of the time.

I'm not completely clear what the benefit is over using fixed point, other than not having to guess at how many fractional bits you need. (I guess it doesn't multiply, but multiply is fast on ARM.)

 

[SirDzstic]

Thanks for the explanations. I didn't know that floating point math is so expensive on the gp2x :/
I'm going to work on it then.

Edit: More suggestions -- if there are any -- are of course appreciated.

 

[hal9000]

Thanks for the explanations. I didn't know that floating point math is so expensive on the gp2x :/
I'm going to work on it then.

Edit: More suggestions -- if there are any -- are of course appreciated.

- It has been said, but let's make it even more clear: do NEVER use float on the GP2X when speed is an issue.
- Put all your optimization efforts on the bottleneck, which is very often easy to find, especially in small games. In your game, I have not looked at your code, but I am pretty sure it is inside the loop which draw each pixel of a vertical line and has to fetch the right color in the texture.
- Maybe could you have a look at the couple of lines of code corresponding to this previous point in the source code of Wolfenstein 3d or any similar open-source game.

 

[mrsnature]

I used -msoft-float, but I got a lot of errors about unresolved symbols by the linker.
Do I have to link against a special library to use this flag?

I'm not entirely sure, but maybe try adding -static

Of course, you don't need -msoft-float at all if you don't use any floats

as rokdcasbah said, floating point on gp2x is much slower than on your pc, so the difference will be much greater.

I tried the shift by 8, but it caused distortion on the textures.
I played around a bit with the operand, and a shift by 11 seemed
to be a good trade-off between performance and distortion.

Remember binary shifting is super fast, just set the shift number as high as you like (for quality, as far as performance is concerned), bearing in mind though if you shift too far you'll lose the most significant bits.. so work out what the highest value you need is.

 

[mrsnature]

So, how's the performance increase going? I would be interested to hear your findings on how much each of the previously mentioned ideas actually increase your fps.