2 approaches for building an array in hack assembly

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

2 approaches for building an array in hack assembly

ppfvy
I'm watching the Unit 4 videos and thought I'd try to do a bit more with arrays to get a better sense of how machine code works. I'm trying to make an array of length N with every value set to K, starting at address I, with N = Ram[0], K = Ram[1], I = Ram[2]. Here is the first approach I took (I didn't paste the (End) code here):

@inserted
M=0

(Loop)
    @inserted //current length
    D = M
    @R0 //length we want
    D = M - D
    @End
    D; JLE
   
    //Store start address in D
    @R2
    D=M
    //Add offset (# of elements added already) to start address, put in D
    @inserted
    D=D+M
    //store address (for next insertion) in 'Pointer' variable
    @Pointer
    M=D
    //store value to add in D
    @R1
    D=M
    //dereference memory address stored in Pointer
    @Pointer
    A=M
    //finally, add the value (D is still Val)
    M=D
   
    @inserted
    M=M+1
    @Loop
    0; JMP

This has some juggling around of values between the registers and the pointer variable, but it seems like a pretty faithful translation of a higher-level for loop that sets all the values in an array.
But, it seems like you can cut off some effort by creating the Pointer variable outside of the loop and incrementing it directly - you have to calculate (pointer address - start address) at the beginning of each loop since it doesn't store 'i' (# of values inserted so far) directly, but then you can just insert the R2 value directly into pointer. If I counted correctly this saves ~4 operations inside the loop, but it's a less faithful translation of a high level for loop. Here's the code for the increment-pointer-directly version:

@R2
D=M
@Pointer
M=D

(Loop)
    //set D to the number of values added so far, AKA ptr - start address
    @Pointer
    D = M
    @R2
    D = D - M

    @R0 //length we want
    D = M - D
    @End
    D; JLE
   
    @R1
    D=M
    @Pointer
    A=M
    M=D
   
    @Pointer
    M=M+1
    @Loop
    0; JMP

If each machine instruction takes about the same amount of time to execute, then this version is ~25% faster. Are there any pitfalls to forgoing a 'count' variable completely like this? Am I missing the 'right way' to do it?

Hope it's OK to post this code here, it's working code but not part of the project.
Reply | Threaded
Open this post in threaded view
|

Re: 2 approaches for building an array in hack assembly

cadet1620
Administrator
The second version is a bit cleaner and faster.

If you are treating this as a subroutine, then it is fair game to directly modify the parameters in R0-R3. This lets you write even tighter code.

Another trick in assembly language programming is to count down to 0 instead of counting up to a stop value. This save you needing to subtract the stop value.

The multiple destination registers in Hack C-instructions let you do some nice tricks too. For instance you can load and decrement N in the same instruction which lets you write your while loop very concisely:

(Loop)
    @R0     // while (--N >= 0) {
    MD=M-1
    @Break
    D;JLT

    // Code to set RAM[I] = K and increment I goes here.

    @Loop   // }
    0;JMP
(Break)

[If you are not familiar with it, "--" is the C++ / Java pre-decrement operator. It means decrement the variable before reading its value.]

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

Re: 2 approaches for building an array in hack assembly

ppfvy
Thanks - that makes sense. I haven't thought about the context that this would be executed in - I was thinking of 'get the values from R0..R2' as a placeholder for now when later we'll presumably be getting the values from user input, other routines, etc.

I've seen the pre/post increment and decrement operators before but I've never actually used the value of an expression like i++, it always seemed a bit tricky so I would separate out i++ from anything that used the value of i, basically ignoring the pre/post distinction. But it's cool to see how pre-increment can translate directly into a single machine operation sending the value of a computation to two places.
Reply | Threaded
Open this post in threaded view
|

Re: 2 approaches for building an array in hack assembly

cadet1620
Administrator
ppfvy wrote
Thanks - that makes sense. I haven't thought about the context that this would be executed in - I was thinking of 'get the values from R0..R2' as a placeholder for now when later we'll presumably be getting the values from user input, other routines, etc.
Chapter 4 has the only complete assembly languages you need to write for this course.

In chapters 7 and 8 you will be writing snippets of assembly language code to perform the operations of the various commands in the VM language. Your VM Translator will combine these snippets as required to translate a complete VM language program to assembly language.

To write a complete, non-trivial, program in assembly language you want an assembler that generates relocatable object files, and a Linker that combines multiple object files into an executable. This is basically the same as the way the compilers combine multiple C++ or Python sources into a single program.

You can do this manually with the Hack Assembler by copying multiple smaller .asm files into a single giant .asm file and then assembling that single file, but it is quite tedious.

It's also rather limiting for assembly language programming that there is no hardware stack in the Hack Computer.

--Mark