Total number of lines in output files!

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Total number of lines in output files!

Fredrik Forsberg
Hi,

I would like to thank the authors for an excellent book. I read it as a hobby course during lonely evenings and I marvel at how well-planned all the projects and chapters are. Everything fits nicely together and the informations is sufficient to get a deep understanding, something quite remarkable considering how short each chapter is.

Anyway, I have finished project 7 and everything seems to work. The thing is that I don't know if my assembler coding, used for the vm-translation, is efficient or not.

I would like to compare my results with others to get a feeling about the performance!

Here's my results (all files have got four lines to initialize the SP and the rest is translation of VM-code):

SimpleAdd:     23 lines
BasicTest:    222 lines
PointerTest:  135 lines
StackTest:    155 lines
StaticTest:     71 lines

It would be interesting to know how few assembler instructions it can be condensed into.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

cadet1620
Administrator
Fredrik Forsberg wrote
Here's my results (all files have got four lines to initialize the SP and the rest is translation of VM-code):

SimpleAdd: 23 lines
BasicTest: 222 lines
PointerTest: 135 lines
StackTest: 155 lines
StaticTest: 71 lines

Here are line counts from my output files. Each file has 4 lines of init code and a 3 line halt loop at the end.
File.asm.hack
SimpleAdd2423
BasicTest194193
PointerTest110109
StackTest174161
StaticTest6867
I think that my StackTest is a bit longer because it writes assembly language subroutines for 'lt', 'gt', and 'eq' and calls them when used. This results in a bit longer code for the first usage, but much shorter code for subsequent usages. (I added this when I was working on 'call' and 'return' which generate lots of code and are used many times.)

--Mark

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

Fredrik Forsberg
Interesting!

This means that you completed the SimpleAdd with two-three lines less compared with me in asm. Guess I can modify my push routine to decrease it with one line somehow.

The other results point towards that also the pop can be decreased with at least one row, although it could be due to my implemention of the lt,gt and eq commands also.

Anyway, it seems like it's pretty comparable adjusted for that. The perfectionist in me want to sit down and play around until it's optimized. We'll see if that side or the lazy side in me wins :)

Thanks for the feedback!

Best Regards, Fredrik
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

cadet1620
Administrator
I didn't worry too much about optimization beyond using subroutines for comparisons, calls, and returns until after I wrote my Jack compiler. Then I wanted to see how my output size compared with the authors' compiler and VM, and what I could do to improve mine.

Beyond the obvious, there are tricky optimizations that you can do. For instance 'push constant 0' can be done with less code than 'push constant 42' since you can use M=0 instead of having to move 42 through the D register.  Also consider the indexed segments: 'pop this 0' can be shorter than 'pop this 1' which can be shorter than 'pop this 42'.

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

Fredrik Forsberg
Thanks for the help!

I have managed to optimize it somewhat and is down to:

Each file has 4 lines of init code and a 3 line halt loop at the end.
SimpleAdd:     24 lines
BasicTest:    208 lines
PointerTest:  125 lines
StackTest:    143 lines
StaticTest:     68 lines

which is better than before but still worse than your assembler code.

Best Regards,
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

cadet1620
Administrator
Become a registered forum member and you can send me mail via "More > Reply to author". I'll be happy to discuss details off forum.

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

Krozu
This post was updated on .
I'm currently optimizing the VM translator (Chapter 7). Currently i have only done push and arithmetic. You mentioned you created eq, gt and lt once, and called them as if they are functions. I know this reduces the amount of code by quite a bit, but my question is, does this result in longer runtimes? After all, you have to add some extra lines to make sure you jump to the code, execute the code, and return the right value.

I create them every time i need them, for now.
So far i only translated 2 files, each file has 4 lines of init code and a line halt loop at the end containing 3 lines:
ASM:
SimpleAdd: 18
StackTest: 191
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

cadet1620
Administrator
Krozu wrote
I'm currently optimizing the VM translator (Chapter 7). Currently i have only done push and arithmetic. You mentioned you created eq, gt and lt once, and called them as if they are functions. I know this reduces the amount of code by quite a bit, but my question is, does this result in longer runtimes? After all, you have to add some extra lines to make sure you jump to the code, execute the code, and return the right value.
This does add a little to the runtime, but not much. These are assembly language subroutines so the code required for the call and return is minimal, unlike VM call and return that translate into dozens of instructions.

You can use one of the temporary registers like R15 to hold the return IP so the call and function look something like
    @RIP$123
    D=A
    @GT$SUB
    0;JMP
    (RIP$123)

    (GT$SUB)
    @R15
    M=D
    // code to do VM gt command
    @R15
    A=M
    0;JMP

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

bubkas22
In reply to this post by cadet1620
Okay, I really need a hand here...

SimpleAdd:     20 lines
BasicTest:    190 lines
PointerTest:  106 lines
StackTest:    266 lines
StaticTest:     64 lines

Most of mine are shorter, though I think I don't have the startup code....

Except for StackTest, where I seem to have done something horribly incorrectly...

My maths...
PushConstant - 6 OpCodes x 23 = 138 OpCodes
eq/lt/gt - Function - 16 OpCodes (2 labels) x 3 = 48 OpCodes
eq/lt/gt - Call - 4 OpCodes (1 label) x 9 = 36 OpCodes

add/sub/and/or - 5 OpCodes x 4 = 20 OpCodes
neg/not - 3 OpCodes x 2 = 6 OpCodes

Total = 248


Why is my StackTest so freaking long?  Am I supposed to be doing some sort of clever optimization at this stage?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

cadet1620
Administrator
bubkas22 wrote
StackTest:    266 lines

Why is my StackTest so freaking long?  Am I supposed to be doing some sort of clever optimization at this stage?
Your math is good for an approximate minimum. Your 266 line result is certainly good enough. The difference is that the StackTest.vm file has been improved to cover more test cases.

Keep in mind that for Nand2Tetris the emphasis is not on optimization; it's best to get things working and continue working through the course. You can come back later to do more optimization. (I think I just saw a way to reduce my comparison subroutines by 1 word each. Not worth doing, but it will bug me until I go look at it!)

If you want to compare your code generation to the numbers in other posts on this thread, you'll need to use this VM file:
// OLD VERSION of StackTest.vm

push constant 17
push constant 17
eq
push constant 892
push constant 891
lt
push constant 32767
push constant 32766
gt
push constant 56
push constant 31
push constant 53
add
push constant 112
sub
neg
and
push constant 82
or
(This old version only tests 1 of 3 cases of each comparison and doesn't test 'not'.)

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Total number of lines in output files!

bubkas22
Oh, a new file.  Yeah, that will change things.

I had run through chapter 7 earlier.  Then I got to testing BasicLoop, and seems that the test file wants to run for 300 clock cycles, but my program doesn't end yet, so I figured I had to go back and improve something.

I'll have to look back at the BasicLoop again.

Thanks!
Loading...