17. Memory is one long array

Where does the object go?

Part I gave you two pictures that never quite met. In chapter 4, a variable held an arrow to an object. In chapter 16, a Float64Array was a block of raw bytes. So where does the arrow actually point? And what is it made of?

Here’s a small puzzle to keep in mind:

const xs = new Float64Array(1000000);
xs[999999] = 1;           // instant

const ps = [];
for (let i = 0; i < 1000000; i++) {
  ps.push({ x: i });
}
ps[999999].x = 1;         // also instant

Both lines are fast. But they find their target in different ways, and by the end of Part II that difference will be worth a several-fold speed-up. To see it, you need one picture of the machine.

One long row of bytes

Step through it. The row is far too long to draw in one line, so it wraps like text: each line of boxes continues where the last one stopped.

You can’t see real addresses from JavaScript, but a typed array shows you the arithmetic. Each element of a Float64Array takes 8 bytes, and the elements sit back to back:

const xs = new Float64Array(3);
console.log(xs.BYTES_PER_ELEMENT); // 8
console.log(xs.byteLength);        // 24

Element i starts i × 8 bytes after the first one. That is why xs[999999] is instant: the machine computes the spot, then goes there.

Arrows are addresses

Now the arrows from chapter 4 make sense. An object occupies some bytes starting at some address. A variable that “points at” the object simply stores that address: a number. Copying the variable copies the number, so two variables hold the same address, and that’s aliasing.

How big is a pointer? On a 64-bit machine an address is 64 bits, so a full pointer takes 8 bytes. V8, the engine in Chrome and Node, can squeeze them into 4 bytes by storing a 32-bit offset from a base address instead, a trick called pointer compression^[2]. Either way, an arrow costs real bytes.

Two neighbourhoods: the stack and the heap

Memory is one row, but programs divide it into regions with different jobs. Two matter to us. You met the first in chapter 9: the call stack, where each active call keeps a frame for its local variables. The second is the heap: a large region where objects are put as they are created^[1].

Look at the two collections in that picture. They hold the same kind of data, but in very different shapes:

• ps, an array of objects, is really a row of pointers. Each one leads somewhere else. To read every x, the machine reads a pointer, jumps to an object, reads x, comes back, and repeats.
• xs, a Float64Array, is the numbers, packed side by side. To read them all, the machine walks straight along one block.

Build your own memory

You can model all of this with an ordinary array of numbers. Let mem be memory and its indexes be addresses. A list node takes two slots: a value, then the address of the next node. Address 0 means “no next node”, the way null does:

const mem = [0, 0, 10, 5, 0, 20, 0];
// address 2: value 10, next node at 5
// address 5: value 20, next 0 (the end)

Start at address 2, read the value, then follow the pointer stored next to it. Run it, then change the pointers to reorder the list without moving a single value.

// mem is memory; indexes are addresses.
// A node: [value, address of next node]
const mem = [0, 0, 10, 5, 0, 20, 0];

let p = 2; // address of the first node
while (p !== 0) {
  console.log('at', p, 'value', mem[p]);
  p = mem[p + 1]; // follow the pointer
}

Your turn

function sumList(mem, head) {
  // your code here
}

const mem = [0, 0, 10, 5, 0, 20, 0];
console.log(sumList(mem, 2)); // 30

function fieldAddr(base, i, f) {
  // your code here
}

// mass (field 4) of particle 2:
console.log(fieldAddr(0, 2, 4)); // 128

What you learned

• Memory is one long array of bytes. A byte’s index is its address.
• Contiguous values sit side by side. In a Float64Array starting at b, element i is at b + i × 8.
• A pointer is a stored address. JavaScript references are pointers that the engine manages for you. A full one is 8 bytes on a 64-bit machine.
• The stack and heap: call frames on the stack, objects on the heap.
• An array of objects is a row of pointers to objects that may be anywhere. A typed array is one contiguous block of numbers.