Need help with efficiency NXC code

[nxtboyiii]

So how else can I speed it up?

[linusa]

So how else can I speed it up?

Did you do the local precaching of arrays where possible and the re-ordering of logical expressions? How much faster did your program run?

Do you have an estimate how many loops per second you've got and how many you need?

[linusa]

So, I did the profiling-code myself now. I took your original version and just added the sections at some places that might be interesting... It compiles on my machine. Could you please just compile and run the code on your brick? Just play "a normal game", like 20 seconds or 1 minute or so (maybe 10 secs is enough already). The game might run slower. Then make sure you exit gracefully. Maybe crosscheck the code, I included PROFILER_STOP() at some places before StopAllTasks(), I hope those are the right places. The command has to be executed once, but no more than once (dunno what could otherwise happen).

Anyway, I hope this should work. Could you grab the "game.prf" file from your NXT, and send it to me (or upload it here), together with the mGameTask.nxc file that you used (if my current version works, then no need to upload). I'm excited, thanks.

[HaWe]

So how else can I speed it up?

I often had speed issues by my own, and I experienced the following (as partially Linusa said before):

- avoid repetitive array lookups of the same unchanged array cells, but store their values intermediately in temp variables. Looking up only twice the same cell will make not much difference though, but more often (while values stay unchanged) this trick will speed up some percents each time.

- use integrated array operations like ArrayBuild, ArrayInit, ArraySort etc instead of initializing by counting loops (for, while)

- use integrated advanced graphic functions rather than homebrewed

- counted loops consume more calculation time than if you write spaghetti code (instead of for (i=0; i<5; ++i) {...body...} write this {...body...} 5 times behind each other. Probably this won't make sence if loop limits are as big as 100 or 1000 or even more.

- use global variables rather than the same redundant local variables in several different functions if there will happen no access conflicts.

- inline functions, procedures, and macros may work faster than "simple" functions and safecall functions (but careful, they blow up your code size just like any spaghetti code).

- avoid high-frequent display operations (e.g., better print less than 25 times each second - although NXC writes to a screen buffer, not the screen itself, and thus won't have to wait for screen refresh cycles). Your eyes are not able to recognize changes faster than 25 times per second anyway because of inertia .

- for redrawing parts of the display, don't erase and redraw the whole screen but just the smallest areas as possible

- for multithreading, use Wait(1) or even longer as often and as much as possible for low-level threads to enable other high-level threads to get as much processing power and schedule time for calculations as possible

- for frequent i2c sensor polling use intermediate Wait(20) because of i2c bus delay and for frequent analog sensors Wait(3) (or also maybe longer if possible) because of te same reason.

- NXC code at compiler level 3 is already faster than level 1, but if possible use NBC asm code instead of NXC code if you're able to.

- code optimization strategies like known in C will not always affect NXC code performance perceptibly (like shift <<, >> instead of multiply/divide by 2, i+=1 instead of i=i+1 or x*=3 instead of x=x*3, integer math instead of fp math, and/or pointer-like operations as pass-by-reference instead of pass-by-value)

Consider the following to my personal experience:
- even if single operations could be speeded up to 2x (two times as fast as before) in single cases, the whole code would be affected by all optimizations to max 1.2 - 1.3x (based on NXC compiler level 3 - except of course if you had not used horrible insane code constructions before)
- if you use RobotC or Java, you may speed up your runtime performance up to 10-20x (twenty times as fast as before).
- if you use nxtOSEK ore even embedded C you might speed even up much, much more, just a guess: probably 50-100x as fast.

So maybe you wish to think about the efforts you take to analyse, and profile, and test, and speed up, and again analyse, and profile, and test your NXC code in comparison to your speed benefit you may reach, and on the other hand the ways you may go choosing other platforms...

ps
guess why even games for PCs are widly written in C or asm machine code... ;)

[spillerrec]

If the value of E.mex and E.may change, simply update the cached variable.

Another thing to consider is that n-dimensional arrays in NXC are n times as slow as a 1-dimensional array. Thus another approach is to fake a 2-dimensional array in a 1-dimensional array (like C) like so:

Code: Select all

map_struct map[ width * height ];
map_struct temp = map[ x + y*width ]; //returns map[x][y]

You have some extra math instead each time, but this can be cached:

Code: Select all

map_struct map[ width * height ];
unsigned int xy_pos = E.mex + E.mey * width;
map_struct temp = map[ xy_pos ]; //returns map[x][y]
temp = map[ xy_pos + 1 ]; //returns map[x+1][y]
temp = map[ xy_pos + width ]; //returns map[x][y+1]

It might be a bad idea to use array of structs performance wise. Array look-up shouldn't be affected. Replacing the whole struct like "map[x][y] = temp_map;" shouldn't have any performance penalties either. However "map[x][y].sld = 0;" changes only one member while NBC only allows you to replace the whole struct. (You can't directly access the members of a struct in an array.) In short, the compiler changes it into something like this:

Code: Select all

map_struct temp = map[x][y];
temp.sld = 0;
map[x][y] = temp;

[muntoo]

Your eyes are not able to recognize changes faster than 25 times per second anyway because of inertia .

That's completely wrong.

• The "refresh rate" of your eyes is about ~12fps.
• Humans can tell the difference between ~12fps and ~24fps (movie/cinema speed) and ~30fps.
• Inertia??

Oh, and don't unroll your loops - it may actually make your program slower as well as make it larger! (Reference.)

[linusa]

Oh, and don't unroll your loops - it may actually make your program slower as well as make it larger! (Reference.)

As your link said: Always a trade-off. It doesn't say "don't unroll". What I'd like to know is how the concept of "instruction cache" and alignment and all that is used on the NXT's CPU, and how it's managed by the firmware (with the "code clumps" and all that). But I'm not a hardware/low-level guy, so it's not my field anyway.

But, there's a very easy way for all of us to find out: By experiment. Yey. Go do benchmarks. Find the "magic parameters" when loop-unrolling is worth it and when not (how many iterations, how many local loop variables). It's only by benchmarking I found out that lookup-tables may not be worth it due to slow array access...

[linusa]

Oh, and muntoo or nxtboyiii (or anybody), could you just compile and run https://sourceforge.net/apps/phpbb/mind ... php?id=569 quickly and get me that .prf file? Would be very much appreciated...

[HaWe]

Oh, and don't unroll your loops - it may actually make your program slower as well as make it larger! (Reference.)

I meant "unrolling loops" only if you can reduce counters (for constants instead), but anyway: your reference was not especially for NXC...

inertia should mean "Trägheit", I don't know any better word in English. But 25/sec is about the sensitivity, it won't make any sence to print to a NXT screen much faster than that...

Making tests is good, no doubt, but not for a few percents speed up
- if one already followed the tips above
- but nevertheless it's still by far not fast enough
- and rather 1000-2000 percent (10-20x faster) would be needed and could be reached on a different platform...

[spillerrec]

Unrolling loops should not cause performance penalties in NXC. However I would only recommend you it for short loops with max 10 iterations. Conditional loops are rather ineffective in NXC because of bad compilation of boolean expressions, so it can improve performance some if the loop is short enough.
Anyway unrolling loops easily cause spaghetti code...


About the frame rate, I would say it really depends on the situation. In a FPS game, you can easily see the difference between 45 and 60 fps. (At least I can.) While in a racing game I often let the fps drop as low as 20 fps without caring much. 12 fps is way to slow for many applications though.
For a NXT display I would say 12 fps is just fine in most cases. It is better to have a stable slow frame rate than to have a fast choppy frame rate imo. (Btw, in NXT RPG I use 6.67 fps as frame rate, even though it is more than twice as fast as that.)


I agree with Linusa with testing, first find out which part is slow (in order to not waste time optimizing code which is fast enough). Then figure out why it is slow so you can come up with a new way of doing it which avoids this.
Instead of saying, how can I make this loop run faster you should ask yourself, how can I minimize the need of this loop. Is it possible to do certain task in the loop differently so you can move it out of the loop? Is it possible to reduce the amount of times you need to run the loop? (Delete dead enemies and ignore enemies which are far out of the screen for example.)
Just trying to make your existing code efficient will in most cases not get you very far... (Well, your case is probably an exception.)