I have a problem where I am using a Uint32Array in JavaScript as a store:

const store = new Uint32Array(1 << 16)

I am going to use this store like a runtime environment. Basically, everything occurs within this store (all functions are defined here, all data is stored here). Ignore the implementation detail of having to call "native" driver methods in the actual environment to perform the real action (like addition, saving to store, reading from store, etc.). For now just assume that the main problem is how to read and write to the store without creating any temporary variables.

That is, how do I allocate stuff on "the stack" and know where I can actually place something new? And how do I keep it organized, knowing where things are in the store?

What I'm stuck at is step number 1 basically.

store[0] = 1
store[1] = 2
store[2] = store[0] + store[1]

This is different than cheating and using temporary variables:

let a = 1
let b = 2
store[2] = a + b

Imagine it gets more complicated and I am dynamically reading a stream of input and parsing it. Not only that, say our store has already been filled in to some degree. So it's not just as easy to do this:

let address = 0
let i = 0
while (input.length) {
  store[address] = input[i++]
  store[address + 1] = input[i++]
  store[address + 2] = store[address] + store[address + 1]
  store[address + 3] = store[address + 1] << store[address + 2]
  address = address + 4

Well really it's like this (no temporary variables, other than the input which comes from the environment):

store[0] = 0 // first address
store[1] = 0 // i
while (input.length) {
  store[store[0]] = input[i++]
  store[store[0] + 1] = input[i++]
  store[store[0] + 2] = store[store[0]] + store[store[0] + 1]
  store[store[0] + 3] = store[store[0] + 1] << store[store[0] + 2]
  store[0] = store[0] + 4

You need to keep track of something else, like the available places in memory to write to. But where I get lost, and where my question comes about, is if you have the notion of memory allocation blocks, you still need to store those into the store as well! So it's like the chicken and egg problem and my mind shuts down.

How do you handle this situation? What is the key trick or technique? Do you need the notion of magic numbers or special places in the store where certain things are put? That sort of stuff.

  • The trick is that real CPUs use a separate register as stack pointer (indicating where free memory starts) and that assemblers can fix up variable references to absolute or relative memory references. In your example, store[0] almost corresponds to a stack pointer, you should initialize it with location 2 though. If you go on to create a malloc() implementation, one possible technique is to allocate a memory chunk that is one word larger, and to put the size of the chunk in the first cell (and return to the user a pointer to the area starting at the second cell).
    – amon
    Jul 3 '20 at 18:28
  • How do you think malloc works?
    – user253751
    Jul 23 '20 at 20:29
  • Normally, the compiler does this all for you, except for deciding where the stack and heap go.
    – user253751
    Jul 23 '20 at 20:58

What you describe in your question looks very similar to an emulator for a CPU. Even if you are not exactly writing that, you can use the information on CPU emulators as inspiration for solving problems you encounter.

If you are actually writing an emulator, keep in mind that nearly all processors cheat in that they use some non-memory storage for intermediate results and very frequently used bits of information. This non-memory storage is the set of registers of the processor.

One important register is the Instruction Pointer (IP) and it refers to the current (or next, depending on processor architecture) instruction that will be executed. The IP is updated automatically when executing an instruction and saved automatically when calling a subroutine.

Another important register is the Stack Pointer (SP) which points into the stack area of the memory.

As for the memory, that can be divided into three parts:

  • Global variables (or rather, variables with a lifetime equal to that of the application). These variables have a fixed address that is determined when building the application and these addresses are mentioned literally in the instruction stream.
  • Stack-allocated variables. These are often parameters to functions and local variables. During compilation, the compiler determines their location relative to the Stack Pointer register. The variables are then accessed with relative addressing (6 bytes below the SP; 4 bytes above the SP, etc.).
  • Heap allocated variables. The heap is a part of the memory that is managed either by the language runtime or library functions. In either case, there will be global variables keeping track of which parts of the heap are used and which parts are free (often using a tree or list-like data structure where the first node is referenced by a global variable).

Using pointer variables (variables that store a memory location as their value), you can reference from one part of the memory to another part.

  • Registers don't necessarily have to be non-memory locations. You could just used fixed memory locations, for example, the word at location 0x8 could be your stack pointer. Basically a global variable. From a logic point of view, there's very little difference between a register and a fixed memory location, basically just that you can have a pointer to the memory location, but usually not to the register. (In hardware there are probably significant performance differences and possibly significant implementation complexity differences.)
    – 8bittree
    Jul 8 '20 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.