Efficiency using AND and OR

Given:
integer THIS = FALSE;
integer THAT = FALSE;


I asked Kelly Linden if LSL was smart enough, when evaluating "if(THIS && THAT)", to stop after seeing THIS as FALSE.

He came up with the following test:

integer this () { llOwnerSay("this"); return FALSE;}

integer that () { llOwnerSay("that"); return FALSE;}

default
{
    state_entry()
    {
        if (this() && that()) llOwnerSay("TRUE"); else llOwnerSay("FALSE"); 
    }
}

The output was not too surprising:


Additionally, I tested the OR condition:

integer this () { llOwnerSay("this"); return TRUE;}
integer that () { llOwnerSay("that"); return TRUE;}

default
{
    state_entry()
    {
        if (this() || that()) llOwnerSay("TRUE"); else llOwnerSay("FALSE"); 
    }
}

With the output:


So, we concluded that LSL evaluates an entire boolean function regardless of whether it's needed or not.

I decided to test how much more efficient it would be to nest the IFs.

default
{
    state_entry()
    {
        llSay(0, "This or That test ready.");
    }

    touch_start(integer total_number)
    {
        llSay(0, "Beginning This or That test.");
        float time1Start;
        float time1End;
        float time1Dif;
        float time2Start;
        float time2End;
        float time2Dif;
        integer c;
        integer iter = 500;
        time1Start = llGetTimeOfDay();
        for(c=0;c<iter;++c)
        {
            if(FALSE && FALSE)
            {   
            }
        }
        time1End = llGetTimeOfDay();
        time1Dif = time1End - time1Start;
        llOwnerSay((string)time1Dif);
        time2Start = llGetTimeOfDay();
        for(c=0;c<iter;++c)
        {
            if(FALSE)
            {
                if(FALSE)
                {
                    
                }    
            }
        }
        time2End = llGetTimeOfDay();
        time2Dif = time2End - time2Start;
        llOwnerSay((string)time2Dif);

    }
}

At 5000 iterations, I found the output to be 33.159 vs 25.946 seconds.

So essentially, it's 25% faster to do:
if (this) if (that) {foo;}

than

if (this && that) {foo;}

Note, of course, if you're going to do this, and use ELSE:
if (this && that) { foo; } else {fooElse;}
you will need to use redundant ELSEs:

if (this)
{
if (that)
{ foo;}
ELSE
{ fooElse; }
}
ELSE
{ fooElse; }

Note also - THAT runs before THIS.

This is a natural way that a language may choose to run through a boolean snippet.

if(this && that)

is really just shorthand for what is essentially:

if( AND(this, that))

where "this" and "that" both are some unknown type / class. It's really shorthand for:

if( AND(AND(this,AND(that,null))

where AND(SOMETHING,null) evaluates to SOMETHING.

So, since AND(that,null) is really an argument for AND(this,...), THAT needs to evaluate before THIS can evaluate.

Wow, and to think I once said that my learning the Scheme language was completely worthless. I guess I am eating those words.

Now the fact that LL is doing the redundant check doesn't surprise me much.. but the large time difference dose. This is this consistent I assume, ie you did run that script many times right.

I shall have to note this in my more complicated scripts (read as anything with such an if-than-else statement in a loop)

I hated Scheme.

It has been the case since at least SL v1.1 that the boolean operators do not short-circuit as they do in C and related languages; I recall the LSL manual explicitly saying so.

Even in C though, this was a syntactic nicety such that if(a && b) c; would generate the same machine code as the more verbose if(a) if (b) c; as I would expect it would do in LSL. Better still - in the second snippet - order of evaluation of a and b in LSL is guaranteed.

Caveat: I'd actually code the second snippet as if(a) { if(b) c; } because I'm not certain that LSL handles shift/reduce parsing ambiguities in the "expected" way.

...well that is an interesting disaster for just about every script I wrote, Hiro. LOL.

Interesting result.

/esc

Yeah, my main concern is ... say I have an && condition that depends on an integer match and a long operation... like:

if( (thisFeatureIsTurnedOn == TRUE) && ( DoAWholeBunchOfStuffToCheckIfTrueThatWillTakeABunchOfTime() ) )

In this case, if I have whatever feature I have turned off via the integer flag, then I don't want the rest to be checked...


Me too.

It did, however, give me an understanding of how operations break down into simpler operations... sorta like understanding how things are equiv to a Turing machine.

nested IF's may be faster but I seem to have run into a maximum number of ifs in an event and function. actually it could be a maximum number of { } bracket sets. anybody else had to remove some ifs to a function in say a listen even to get it to work?

Im unaware as to any limits on the number of brackets in an event, but I do know of a limit on the number of else-if's a single conditional chain can have. I think the number is around 30.

==Chris

Thanks thats really useful. I seem to spend all my time scripting if statements so that should really increase my script speeds.

I thought of an something today. If you're using integers instead of booleans or in a case where multiple states are necessary for a variable i.e. x can equal 0,1,2 or 3 (requiring 2 bits of data) -- will the LSL or any compiler be intelligent enough to only look at the necessarily bits or am i better off splitting such things down to booleans if its semantically possible? By necessary bits im referring to the fact that the range is 00 to 11 such that 111 would have no or a meaningless effect as it would add 4.

There aren't booleans in LSL, so your question is meaningless.

In short, comparing an integer to 1 and comparing and integer to 8352 should be roughly equivalent.

Hmm... is this the same for strings?

Is:

if("hello" == "jello"

just as inefficient as

if("hello" == "hello"

?

Assuming that string == is implemented internally with C's strcmp(), the first will be faster by a few cycles as it will exit on 'h' == 'j' instead of having to compare all 5 characters. This is probably immeasureably faster at the LSL level.

that was the point of my question, how equivalent is 'roughly'? and if we're talking about the difference between 1 and 248.... in channels, is it a big difference that would affect performance of channel comparisons when listeners are in play.

LSL has 3 types of jump commands in the bytecode. if (true) jump, if (false) jump, jump. Besides that there are no other bytecode flow control commands (ignoring function entry and state entry commands).

LSL order of operations is right to left (except function paramaters are generaly parsed left to right, but the code for each paramater is parsed right to left). Of course parenthasese and some operators take presidence over others.

&& and || would be slower as they both everything, jumping over code is faster then evaluating it. Only disadvantage of jumping over code is that it makes your byte-code more bloated.

LSL is not an optimzed compiler.

one of the stupid things LSL does is pop things from the stack that its just about to push back in. Doesn't take a rocket scientist to optimize this.

b = a;
c = a;
...
push a as integer, peak integer copy into b, pop integer;
push a as integer, peak integer copy into c, pop integer;

c = b = a;
...
push a, peak integer copy into b, peak integer copy into c, pop integer;

-------------------

here is basicly how major flow control compiles.

while(a)
{
    //code
}
....

@b;
!if(a) jump c;
//code
jump b;
@c;

do
{
    //code
}while(a);
....

@b;
//code
if(a) jump b;

for(b;a;c)
{
    //code
}
....

b;
@e;
if(!(a)) jump d;
//code
c;
jump e;
@d;

if
{
    //a-code
}
else
{
    //b-code
}
....

!if(a) jump b;
//a-code
jump c;
@b;
//b-code
@c;

Do we know if even variables are de-allocated once they're no longer needed in scope? Or, are variables always allocated until the scope is completed?

I'll have to check. I'll make some test scripts and decompile them...