"Improving" evaluation of expressions?

[FlyHigh]

Hello everyone,

since I have little time I used the supplied VM-Translator for translating my .jack files to .vm files.
However I noticed that the VM-Translator always evaluates the complete boolean expression although there is sometimes no need to do this.

Just to give two examples:

1. if ((8 < 7) && (3 < 4))
    In this case you can already stop evaluating the expression just after you found out that 8 > 7 (and so  
    the expression cannot be true)

2. if((7 < 8) | (4 < 3))
    In this case you can stop evaluating the expression too just after you found out, that the first part of
    the expression is true and so the whole expression must be true.

Since I did not write my own VM-Translator yet I decided to write some VM-Code myself...

Let's assume I have the following .jack-Code:

function boolean trueFalse(){
                if((8<7) & (3<4)){
                        return true;
                }
                return false;
}

This gets translated to (VM-Translator):


function Main.trueFalse 0
push constant 8
push constant 7
lt
push constant 3
push constant 4
lt
and
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push constant 0
not
return
label IF_FALSE0
push constant 0
return

(This makes perfectly sense).
Okay - let's build in the "improved" evaluation of expressions:

function Main.trueFalse 0
push constant 8
push constant 7
lt
not //False => True
if-goto IF_FALSE0 //If first part = False directly jump to the end
push constant 0
not //Otherwise push True again on the stack and continue
push constant 3
push constant 4
lt
and
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push constant 0
not
return
label IF_FALSE0
push constant 0
return

As you can see I had to add 4 more lines.

However: If we now run the file I have "just" 7 steps until the function returns (if first statement is false like in this case), but on the other side I have 15 steps if I have to evaluate a whole function which is true (like: (3<4) & (4<5)).

If you compare this to the unimproved version:
11 steps if statement is fully evaluated

So on the one hand I save 4 steps when the first part of the expression is false but I also have 4 more steps whenever the expression is completly true.

Maybe you already noticed that I wrote "improved" instead of improved, because I am not really sure, whether this is really an improvement or not?

Any thoughts on this (Except from: Depends on the case)?

Best
FlyHigh

[cadet1620]

[FWIW, You mean supplied JackCompiler, not VM Translator.]

The problem is that you need to know the type of the sub-expressions on each side of & and | to tell the difference between logical operations and bit-wise operations.

For example
    if ( (haveValue & haveBit) & ((value & bit) = bit)) )

To make this work correctly would require the Jack compiler to do type checking for variables and sub-expressions.

It would be much easier to borrow from C/Java and add the && and || operators to mean short-cut logical evaluation. Note that this would also require defining operator precedence and order of evaluation. (The Jack language explicitly states that these are undefined.)

--Mark

[FlyHigh]

[Thank you :)]

I see. I only thought about logical operations.
For doing just logical operations would be easier, wouldn't it?

(And btw. you use bitwise operations not too often, do you?)

[cadet1620]

FlyHigh wrote

For doing just logical operations would be easier, wouldn't it?

Shortcut logical operations will sometimes execute faster, but you need to analyze your code when you write your program so that the first term that is evaluated usually causes the short cut. However, on modern processors with instruction caches, shortcuts that jump are often slower than evaluating both terms because the branch makes the pipeline stall.

On the Hack Computer, shorted code is better than faster code because the ROM is small.

(And btw. you use bitwise operations not too often, do you?)

I'm an embedded systems programmer; I use bitwise operations all the time. For example, to turn on or off one bit of a parallel I/O port:

    portA = portA | 0x04;   // This turn on bit 2.
    portB = portB & ~0x01;  // This turns off bit 0.

OS programming also uses lots of bitwise operations; they are very useful in packing and unpacking numeric fields like IP addresses (192.168.200.1, for instance is 4 8-bit numbers crammed into one 32-bit number: 3232286721).

Software that implements mathematical code also uses lots of bit shifts and bitwise operations.

--Mark