Math.jack running too slow

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Math.jack running too slow

Juan313
This post was updated on .
Hi I've successfully implemented and tested all OS functions with PongGame. However, the math.jack is making the game running really slow. It takes about 4 million steps to past the MathTest. Can someone take a look at my math.jack file and let me where the problem is. I pretty much follow the book's recommendation. Any help is greatly appreciated!
Reply | Threaded
Open this post in threaded view
|

Re: Math.jack running too slow

cadet1620
Administrator
multiply() is probably too slow due to calling bit().

Note that bit() is called in the loop as bit(y,0), bit(y,1), ... bit(y,15).

You can eliminate nearly all of the code in bit() by moving it into the loop.
    var int bit;
    ...
    let bit = 1;
    while (i < 16) {
        if ((y&bit) = bit) {
            let sum = sum + shiftedX;
        }
        bit = bit+bit;
        ...
    }

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: Math.jack running too slow

Juan313
The bitwise AND method is so much better! Thank you Mark. You are awesome!
Reply | Threaded
Open this post in threaded view
|

Re: Math.jack running too slow

cadet1620
Administrator
The way this multiply code uses 'bit' is called bit masking. In addition to bit testing, bit masking can set or clear bits in a variable.
    let x = x | bit;    // Set bit
    let y = y & ~bit;   // Clear bit
You can also set or clear multiple bits at once. For example, in the screen I/O code you might have a pointer into the middle of a line and want to do something at a different offset in the same line. You need to get back to the beginning of the line and add the new offset.  One way to do this would be
    let linePtr = (linePtr/32)*32) + newOffset;
Since all screen rows begin at a multiple of 32, their addresses always have bits 0-4 = 0. Bit masking can clear those bits much faster than the division and multiplication used above!
    let linePtr = (linePtr & ~31) + newOffset;


The bit based multiply code  posted above always loops 16 times. It would be nice if it was faster when multiplying by small numbers; there are lots of x*2, x*32, etc. in the screen code.

You can use bit masking to clear the 'y' bits as you process then and break the loop when 'y' becomes 0.

A nice refinement would be to swap 'x' and 'y' in cases like 3*x, but the overhead to do that might slow down the general case enough to overwhelm the average performance, especially if it needs to call Math.abs().


Here are some other examples -- right shifting and bit reversal:
/// UNSIGNED right shift 'x' one bit.
    function int shr(int x) {
        var int y;  // = 0
        var int i;  // = 0
        while (i < 15) {
            let y = y+y;    // y << 1
            if (x < 0) {    // Test x & 0x8000.
                let y = y | 1;
            }
            let x = x+x;    // x << 1
            let i = i+1;
        }
        return y;
    }

/// Reverse the bits in 'x'.
    function int rev(int x) {
        var int y; // = 0
        var int bit;
        let bit = 1;
        while ( ~ (bit = 0)) {
            if (x < 0) {    // Test x & 0x8000.
                let y = y | bit;
            }
            let bit = bit+bit;  // bit << 1
            let x = x+x;        // x << 1
        }
        return y;
    }

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: Math.jack running too slow

nemethda
Hello,

I know this an old post but didn't want to post the same question again, hopefully someone can help me. So I've also managed to complete the course (what a fantastic journey it was..) but now I tried to run the Pong game with my OS implementation.

Just like Juan313, I noticed that (mainly) because of Math.jack, the game runs extremely slow. In my case it means, that after starting the game it takes ~18 seconds for the paddle to appear and start moving.. This is after I fixed my multiplication to use bit masking as suggested by Mark here (with the only difference that I created a static array in Math.init to hold all values as it was also suggested elsewhere).

When I run Pong with my OS but without my Math module - the paddle appears and starts moving in like a second. After that still pretty slow, but for that my Screen module will be the culprit.

Could anyone has any suggestion what could be so inefficient in my Math module? I don't want to include the code here, but would be happy to share it..

Thanks so much!
Daniel
Reply | Threaded
Open this post in threaded view
|

Re: Math.jack running too slow

nemethda
Sorry, let me be more precise: reading Mark's comment from an another post (http://nand2tetris-questions-and-answers-forum.32033.n3.nabble.com/Quicker-Horizontal-screen-drawings-td4026600.html), I came to understand that it's a better comparison to use the supplied Math.vm file against my OS vm file.

So this way, the speed difference I see is much smaller, although still significant:

Pong with my OS without Math module, using supplied Math.vm: takes ~5 secs for the paddle to move
Pong wiht my OS: takes ~18 sec for the paddle to move.

Any help / suggestion is appreciated!
Thanks
Reply | Threaded
Open this post in threaded view
|

Re: Math.jack running too slow

ivant
A while ago I created a fork of the software suite to try to improve it. I didn't go far (long story), but there are a few nice things there, and one of them is a kind of profiler. It runs as part of the emulator and gives you statistics about function calls, executed instruction per function and such. You can use these tools to compare your implementation against the original one and know where to focus.

You can download the fork from here: https://github.com/itoshkov/nand2tetris-emu/releases/tag/v2.6.2

The profiler is accessible from the Run menu.

(Oh, another nice feature it adds is the ability to step-over, while debugging. The official tool can single step instruction by instruction or run it continuously until it hits a break point or the program ends. Step-over is the same as single-step, except when it comes to function calls. With single step, you are jumping in the called function, and with step-over you don't. Instead, the called function is run without stopping until it returns.)
Reply | Threaded
Open this post in threaded view
|

Re: Math.jack running too slow

nemethda
Thanks Ivant for these tools! Much appreciated!!

It was an eye-opener to profile the Pong game in every combination (with built-in OS, with mine, without my Math module etc). Now I clearly see that my Math module might be kind of okay for now, the Screen module is the one to be optimized: without my Screen the paddle actually appears instantly and the game itself almost playable.

Of course i could have seen this by myself: I'm using drawPixel all the time which is very expensive. Your profiler shows that with my Screen, Math.multiply called more than 40 thousands times before the game even begins :)

Reply | Threaded
Open this post in threaded view
|

Re: Math.jack running too slow

ivant
Yeah, drawing lines by calling drawPixel is very inefficient. Is there a special kind of line you can draw faster than one pixel at a time?
Reply | Threaded
Open this post in threaded view
|

Re: Math.jack running too slow

nemethda
Yep, horizontal lines should be drawn faster, I actually saw your excellent post earlier. I'll try to implement those suggestions!