Need help with efficiency NXC code

[HaWe]

aah, ok, I see -
but what I actually was referring to was the If/else if vs. case/break structure: is here a speed issue detectable?

[spillerrec]

There is and it can give a significant improvement in some cases. And it takes up less space, so if you use it consistently were it is appropriate you will see an improvement in .rxe size.
And programmers are used to see these structures, so it is more readable than using a if-elseif structure.

I format my switches like this:

Code: Select all

switch( var ){
	case 5:	/* do something simple */ break;
	case 10:
			//Do something multi-line
		break;
		
	case 11:{
			//Do something multi-line with scope
		} break;
}

Notice the extra empty line after a multi-line case

[HaWe]

ok - I agree ;)

[afanofosc]

If structures are very inefficiently implemented in NXC (considering what they could be), so avoid them if you can.

The NXC compiler adds some bloat code when converting boolean expressions containing &&. The NXC compiler does a very poor job at converting boolean expressions into NBC in general, and when && is involved it becomes even worse. (Something similar with || iirc.)

I really hope John will improve the compilation of if structures someday...

Please tell me what you think I can do differently/better with respect to if statement code generation - particularly with the apparently very poor job that I currently do for boolean expressions containing && and ||.

Actually, the switch should have placed the default case just under the brcmp opcodes, this removes a jmp opcode (and the extra one which doesn't really do anything shouldn't be there either of course):

I have fixed a bug in switch statement handling so that if the default case is not last it will still generate valid code. If you have a default case it now does not generate the jump statement to the end of the switch. If you put the default case first then at optimization level 2 it removes the jump to the default case (since it immediately follows the jump). It would take a bit of fiddling to make the compiler move the default case code and never make a mistake regardless of what the programmer throws at it. I will probably not make that kind of change. If you want to save a single jump statement that almost certainly has no noticeable impact on execution speed or code size then put your default case first (with a version of the compiler which fixes the "default-not-last" bug).

John Hansen

[spillerrec]

Code: Select all

task main(){
   bool b1, b2, b3;
   
   if( b1 && b2 && b3 )
      Wait( 1000 );
}

becomes:

Code: Select all

	mov __DU0main, __main_7qG2_b1_7qG2_000
	tst 5, __zfmain, __DU0main
	mov __D0main, __zfmain
	brtst 4, __NXC_Label_605, __zfmain
	mov __signed_stack_001main, __D0main
	mov __DU0main, __main_7qG2_b2_7qG2_000
	tst 5, __zfmain, __DU0main
	and __D0main, __signed_stack_001main, __zfmain
	tst 5, __zfmain, __D0main
	mov __D0main, __zfmain
	brtst 4, __NXC_Label_605, __zfmain
	mov __signed_stack_001main, __D0main
	mov __DU0main, __main_7qG2_b3_7qG2_000
	tst 5, __zfmain, __DU0main
	and __D0main, __signed_stack_001main, __zfmain
__NXC_Label_605:
	tst 5, __zfmain, __D0main
	brtst 4, __NXC_Label_606, __zfmain
	wait 1000
__NXC_Label_606:

That is quite a bit of code!
Since a && expression becomes false when just one part is false, we can use this together with short-circuiting to just enter the else clause when just one part evaluates to false. There is no need to remember the results of the previous parts.

Code: Select all

brtst NEQ, lblElse, b1
brtst NEQ, lblElse, b2
brtst NEQ, lblElse, b3
lblTrue:
wait 1000
jmp lblEnd
lblElse:
lblEnd:

Notice that the comparison operator is inverted so that is jumps on false. (This is possible with every comparison operator.) || should do the reverse, jump on true and to lblTrue.

If it is an expression like "if( b1 && x+y )" x+y should be evaluated just before the comparison:

Code: Select all

brtst NEQ, lblElse, b1
add __stack, x, y
brtst NEQ, lblElse, __stack

I have some notes on how this system can be used together with ! and multiple && and || in one expression to allow for every kind of boolean expressions by constructing it recursively. With this system every comparison will end up being one brtst or brcmp (plus anything which needs to be calculated). It might also require a few jmp in some cases where you mix && and ||, I do not quite remember...
If you want, I can compile those notes into something readable and pass it to you.

If you put the default case first then at optimization level 2 it removes the jump to the default case (since it immediately follows the jump).

It is fine for me to just move the default case up, it is minor stuff anyway. But I have never before considered to have the default case somewhere else than in the bottom. Is this legal C? And how will it be affected if you omit the break? Will it continue into the next case, or will it still just exit the switch?


Btw, what is the __initialize_global_data function for? I have never really seen anything put in there as of yet...

[muntoo]

Btw, what is the __initialize_global_data function for? I have never really seen anything put in there as of yet...

I think it's for:

Code: Select all

int count()
{
    static int counter = 0;
    return(counter++);
}

int foo = count(); // This?

int main()
{
    NumOut(0, 0, foo);
    Wait(1000);
}

We're getting way OT.

[linusa]

So, by any chance, now with .ric files etc.: Anybody got the game.prf file for me?

[afanofosc]

Btw, what is the __initialize_global_data function for? I have never really seen anything put in there as of yet...

Code: Select all

float tOutCribSheet[10];
float targOut;
task main()
{
  int j;
  targOut = tOutCribSheet [j] ;
  NumOut(0, LCD_LINE1, targOut);
}

Any global variables that need runtime initialization will be put in the __initialize_global_data function. Here's another example:

Code: Select all

string msgs[] = {"one", "two", "three", "four", "five"};

task main()
{
  TextOut(0, LCD_LINE1, msgs[0]);
  TextOut(0, LCD_LINE2, msgs[1]);
  TextOut(0, LCD_LINE3, msgs[2]);
  Wait(SEC_5);
}

John Hansen

[afanofosc]

Since a && expression becomes false when just one part is false, we can use this together with short-circuiting to just enter the else clause when just one part evaluates to false. There is no need to remember the results of the previous parts.

This looks like a completely safe suggestion and I have implemented this change to BoolSubExpression (which handles BoolTerm || BoolTerm) and to BoolTerm (which handles BitOr && BitOr). Both of these routines used to push the primary register onto the stack after the lhs and then after the rhs they would pop the primary register off the stack and OR or AND it with the value of the rhs. I already had jumps in place for short-circuit evaluation so all I had to do was comment out PushPrim and PopOr|PopAnd in these two routines.

If it is an expression like "if( b1 && x+y )" x+y should be evaluated just before the comparison

This is where your suggestion falls apart. The problem is that you cannot ignore the value of the boolean expression. Its value is not x+y. Its value is 0 or 1. In a simple case like you have shown it does happen to be the case that the expression (or sub-expression) value is discarded so it does not need to be stored in the primary register. But a boolean expression can be the rhs of an assignment like this:

Code: Select all

x = b1 && b2 && x+y;

The parser code that processes the rhs of this assignment is exactly the same code that processes an if-condition. So if I want the value discarded (or never stored) in the case of an if-condition then I would need to set some kind of flag before I parse the if-condition that says 'don't bother storing the value in this situation'. But even then it is not safe to assume that the value of a boolean expression never needs to be stored just because the expression is part of an if-condition. Like this:

Code: Select all

if (x=y=b1&&b2&&x+y)

If I do not store the value of the boolean expression in the primary register then the resulting code is wrong:

Code: Select all

	subcall __initialize_global_data, ____initialize_global_data_return
	mov __D0main, __main_7qG2_b1_7qG2_000
	brtst 4, __ASM_Label_609, __D0main
	mov __D0main, __main_7qG2_b2_7qG2_000
	brtst 4, __ASM_Label_609, __D0main
	add __D0main, __main_7qG2_x_7qG2_000, __main_7qG2_y_7qG2_000
__ASM_Label_609:
	mov __main_7qG2_y_7qG2_000, __D0main ; this stores x+y into y (WRONG)
	mov __main_7qG2_x_7qG2_000, __D0main ; this stores x+y into y (WRONG)
	brtst 4, __ASM_Label_610, __D0main
	wait 1000
__ASM_Label_610:

And if your simple variables had a value other than zero or 1 they would also put the wrong value into x and y. Even a boolean variable could have any non-zero value stored in it as TRUE (i.e., 42) but its value in a boolean expression is simply 0 or 1.

And it is not only assignments inside an if-condition that throw a serious wrench into your suggestion. You can compare the value of a boolean expression in >,<,==,!=, <=, and >= comparison expressions. You can bitwise AND or OR the value of a boolean expression into another value. You can add, multiply, subtract, or divide the value of a boolean expression with another value or other boolean expression. Any of these operations will fail if you do not always store the value of each boolean expression into the primary register - in case it is needed subsequently. I can't guess that because the boolean expression happens to be within an if-condition or while-condition that it is safe to discard these values.

Interestingly, every single test program that I have appeared to run correctly yesterday when I was testing the compiler with storing the value of the boolean expression turned off. While the compiler was in this state it was producing code like you see above (which is very much like what you suggested, and with optimization of mov|brtst sequences would be essentially identical). So I can see why it is so enticing to want this kind of simplicity in the code that the compiler generates. And in many typical if-conditions or other uses of boolean expressions it works perfectly fine. It just is not right all the time and figuring out on the front end is nearly impossible.

So maybe I just need to have a really smart optimizer on the back end that can get rid of all the extra code. The problem there is that it is as hard, if not harder, on the back end to be certain that nobody needs the value that you put into the primary register variable. Once you branch or have labels in between two lines of code then pretty much all bets are off. Just look at the NBC code above. I can't know for certain that the 0 or 1 value that I put in the primary register before the first branch will be needed when I store the value of the primary register in X and Y further down.

Anyway, it was a good exercise to go through how the NXC front end handles boolean expressions and thanks to this prodding I was able to come to the realization that I did not need to PushPrim and PopOr|PopAnd like I was doing. This saves a couple lines of code.

John Hansen

[spillerrec]

If it is an expression like "if( b1 && x+y )" x+y should be evaluated just before the comparison

This is where your suggestion falls apart.

With this I just wanted to point out the obvious that if you have and expression "if( true && (5+2) < x )" then "(5+2)" should of be evaluated just after the "true" so short-circuiting works. Is "b1 && x+y" equal to "(b1 && x) + y"?? I'm honestly not too good with operator precedence...

The problem is that you cannot ignore the value of the boolean expression. Its value is not x+y. Its value is 0 or 1. In a simple case like you have shown it does happen to be the case that the expression (or sub-expression) value is discarded so it does not need to be stored in the primary register. But a boolean expression can be the rhs of an assignment like this:

Code: Select all

x = b1 && b2 && x+y;

For cases like this I was thinking that you could just do it like

Code: Select all

if( b1 && b2 && x+y )
   x = true;
else
  x = false;

internally whenever you need the value of an expression. For very small expressions it might be more efficient to use the current method but since saving the result of a boolean expression is kinda rare I decided not to look into how this could be done more efficiently.

I assumed this would solve these rarer situations (also inside other boolean expression), is there still something I'm missing?


EDIT: Ahh, messed up the BBcode...
EDIT:
I guessed the __initialize_global_data function was used like that. However what I did not understand was why it needed to be a separate function. Couldn't it just be placed directly in the main task? Actually, would it be better to place this in a separate task, which starts the main task?

Code: Select all

task __initialize_global_data(){
   Precedes( main );
   //Initialize global variables
}

As far as I understand, it should prevent __initialize_global_data to be rerun in cases like this:

Code: Select all

task main(){
   Precedes( other_task )
}
task other_task(){
   Precedes( main );
}

And On Topic, sorry for not profiling the game yet, Linusa.