Hacker News Reader

Comment by cwzwarich | Hacker News Reader

Has anybody done a study of dependencies of computations in real programs and compared the efficiency of a stack representation and a register representation?

View on HN

There's https://www.usenix.org/legacy/events/vee05/full_papers/p153-...

But it's more specifically focused on virtual machines than physical hardware.

Stack Machines, Koopman is the only treatise that I have seen that really digs into the question.

http://users.ece.cmu.edu/~koopman/stack_computers/index.html

My memory of the conclusion is that register machines are a bit faster for general programs. Stack machines are better in some special niches. (High volume/rapid Interrupt handling comes to mind)

I should read the book again myself...

A stack processor will always be less efficient than a two or three operand register-based processor. This is because all of the the registers can be used directly without any stack manipulations to access them, and the two or three operand operations usually include a move.

If you examine any stack language code, you should consider any stack manipulation to be a NOP type of inefficiency. And when a virtual stack machine is implemented on non-stack hardware, these inefficiencies are compounded.

I think you have to have a larger view of what is 'efficient' historically instruction fetch bandwidth was scarce, caches were expensive, often tiny or non-existent - stack machines with one byte opcodes (look at the Burroughs large systems) were efficient in context.

We've switched to RISC (despite the above I'm a big fan have built several) these days largely because there came a point where we could push everything onto a chip, RISC started to make sense at about the time where cache went on-chip (or was SRAM closely coupled to a single die) - and for the record I think x86 has survived because its ISA was the most RISCy of it's original stable-mates (68k, 32k, z8k etc) - x86 instructions make at most 1 memory access (with one exception) with simple operands

I think Henry Baker argued otherwise saying that at the circuit level a stack processor can be designed to operate faster (like shorter path, less clock cycles) compared to register ones.

The problem with trivial ops like stack manipulations is that they don't really do anything useful, but they can take as long as multiply in the pipeline.

Stack machines made more sense when memory was limited (small opcodes) and there were no hardware multiplies, but these days they make no sense.

I don't understand all the vague nostalgia for something that never could have panned out outside of the creaky old Apollo flight computer or something.

Fair point. That said it's not nostalgia, Baker's article was about linear logic and that forth was naturally fit for this. Cue Rust borrowing and you see why it may be of interest (if baker was right of course).

Two and (especially) three operand processors spend significantly more space encoding register indexes, though. It's worth it to avoid forth-style pop swap rot, tuck u* spaghetti, but register machines just push the NOP-type inefficiency somewhere else. Eg, obviously most 3ops are the last use of at least one source operand, so there's usually no point encoding separate src1 and dst fields, but also many instructions immediately reuse (often the last and only use) the destination register of the previous instruction as a source.

I'd kinda like to see a machine with a intermediate, one-operand style of instructions. Eg:

  add tos stN # *sp += sp[N]
  add stN pop # sp[N] += *sp++
  ld [stN] # *--sp = mem[sp[N]]

Reply on news.ycombinator.com