VMs that aren't stack-based

Basically, there''s stack-based, and there''s register-based. Stack-based has the advantage of being easier to do, as well as simpler conceptually. Register-based may be more efficient at times; I''ve heard differing reports. Lua recently went from a stack-based VM to a register-based VM, and according to its authors, that really improved the speed.

---

"Sneftel is correct, if rather vulgar." --Flarelocke

quote:

---

Original post by krez
almost every "make your own scripting language and virtual machine" tutorial i have seen use a stack-based VM... is this because they are the easiest to program (good tutorial material), or they are more efficient than other types, or what? what other types of virtual machines are there (so i can get some new search terms)?

---

The other type of virtual machine available (like a "real" computer) is a register-based virtual machine. The fact that most virtual machines are written as stack machines is that it is easier to manage (theoretically speaking a stack machine is a machine with an infinite number of registers).

So why are the tutorials mainly about creating virtual machines? Simple: most people don''t even begin to understand how to do register allocation - not only is it an NP-hard optimisation problem, but it is also technically difficult to make a decent heuristics implementation, particularly for multi-size register machines such as the IA-32 architecture.

If you want to learn more about register allocation then there are plenty of good papers on the subject, from the original graph colouring register allocation (with the "pessimistic" heuristic) published by Chaitin and his IBM research team in ''81 in Computer Languages. Briggs et al provide an improved heuristic (also known as the "optimistic" heuristic) in his ph.d. thesis of ''92 (Technical Report 92-183 from Rice University). Andrew W. Appel makes a good rehash of various techniques employed by those two, plus further improvements of his own (and Lal George) on iterated coalescing.

If you want a different approach to graph colouring register allocation there is also priority-based colouring register allocation as proposed by Fred C. Chow and John L. Hennessy in ACM SIGPLAN ''84 on behalf of their employer, MIPS Microsystems.

Lastly a newer approach, graph fusion, as proposed by Lueh in Programming Languages and Systems 22(3) has other merits and different problems of implementation (as far as I know it is mainly used for programming languages that auto-compile to parallel processors).

The graph colouring approach (as proposed by Chaitin and successors) is the most widely applied approach for allocating registers on platforms with uniformly sized registers. I hope that helped clarify a few points for you (and at least should give you a good deal more to search for). If you happen to know Danish you can read my b.sc. thesis on this stuff here: http://unprompted.com/hstuart/files/rapport.pdf.

thank you both. i guess there wasn''t any conspiracy

I think it''s a practical reason - if you''re going to go through the trouble of creating a register based machine, you may as well emit real op codes and use real registers (and now it''s not a VM anymore).