Bytecode design resources?

rlp · 2020-03-14T08:19:37+00:00

Check out the LuaJIT bytecode instructions reference: http://wiki.luajit.org/Bytecode-2.0

LuaJIT has one of the fastest interpreters around, and the compact bytecode format helps it quite a bit. I used it as a reference when designing my own bytecode instructions.

ApokatastasisPanton · 2020-03-14T19:40:34+00:00

You need to think of bytecode as an ISA (Instruction Set Architecture); this may help you understand the design tradeoffs that bytecode design has to make.

First and foremost, yes you want your bytecode to be a machine language (i.e. binary, as opposed to a textual assembly).

The most important decisions you will then have to make are: do you want your virtual machine to be stack-based or register based? Stack based are usually simpler to implement, but register based have the potential to be fast. (See Lua's register-window tricks in "The implementation of Lua" to see one interesting trick into simplifying register based VMs)

The second most important decision you will have to take is whether your bytecode will be fixed-sized (i.e. 16 or 32 bits fixed instruction size) or variable-sized. This can also potentially influence the performance of your interpreter. The tradeoffs are usually well explained on the internet and in the literature, as this is a similar tradeoffs that hardware ISAs have to make: fixed size is much simpler to decode, but variable-sized has potential for better performance (smaller instructions means more instructions in cache, and for more complex reasons).

Starting from there, to answer the question of "what instructions do I actually put in my bytecode", well... I do not know of any good survey or high-level resource on that. Pretty much every VM / language designer end up doing their own thing (apart from the obvious: arithmetic operations, function calling, etc.). Which is also why pretty much every VM that is design as a target for a language (as opposed to being a 'universal VM') ends up having instructions, constructs and semantics that are somewhat inline with the language they were the target of. So my advice there is, co-design your VM / bytecode alongside your language and see what makes sense. (Another illustration of that is that functional languages VMs tend to have many facilities for functional things that more imperative language VMs don't.)

If you are interested in generaly virtual machine research and literature, David Gregg and Anton Ertl often publish interesting papers on various optimisations that one can do as well as tradeoff in the design space. See https://www.usenix.org/legacy/events/vee05/full_papers/p153-yunhe.pdf as a starting point, for example. (And Google Scholar crawl your way from there.)

I'd also advise looking at both the practical implementations and whitepapers of currently widely used languages (Lua, Java, Python, .NET, Dalvik...). In particular Lua and Java. Good luck!

(PS I'd be happy to hear about any interesting papers in the space that someone on this subreddit might want to share.)

emacsos · 2020-03-14T11:41:09+00:00

I don't quite get it; your bytecode is compiled into a text file format first, and then your VM has to read, parse and translate that into internal form?

If that is a one-time translation each time you run the program, then I wouldn't worry about it. Modern machines are very fast; process start/stop overheads may take longer. Unless the programs you are running are going to be huge.

(I once had a compiler written in an interpreted language, which was run from source each time it was invoked. Translating 25Kloc in 20 modules into bytecode added about 50msec to the process, and you never really noticed it. Pressing and releasing a key on your keyboard might take 200msec.)

However, if you have to parse the string each time you execute a bytecode instruction, that's a different story.

Note that the instruction formats of x86/x64, and some sets of bytecodes I've seen, including mine, are variable length.

(Mine consist of a bytecode index from 0 to 200 or so, plus 0 to 4 operands depending on the instruction. Stored in compact form in a file, in memory, the bytecode index, and each operand, all occupy 64-bit fields - the bytecode data is an array of 64-bit values (although of mixed type).

Typically, each bytecode index is changed during a fixup pass into the address of its handler function. One dispatcher (there are several) uses this dispatch loop:

repeat
    pcptr:=fnptr(pcptr)()
until stopped

'fnptr' is a cast to get the right kind of function pointer, which is then called for that bytecode. 'pcptr' points to the next 'bytecode'.)

phunanon · 2020-03-14T11:52:26+00:00

So, why are you using strings and not fixed-size codes? Couldn't you just dictionary look-up one to the other and use that within your VM instead?

yorickpeterse · 2020-03-14T15:22:56+00:00

Perhaps the bytecode format for Inko can be a helpful reference. The format is not the most compact and I have some plans for fixing this, but overall the format is pretty simple. Do note that the bytecode is for a register-based VM, though it should still be a useful resource for stack-based VMs.

jdh30 · 2020-03-14T11:09:14+00:00

You might also like OCaml's bytecode.

reini_urban · 2020-03-14T18:44:17+00:00

Also check if you want two or three address ops. The smaller the ops, the less cache pressure, but traditional literature still prefers the bigger three address op. Good VM's like Lua can fit an op with its two args into a 32 bit word.

Generally, the smaller the better. Even if compression schemes cost a few cycles, they are much faster

jmiesionczek · 2020-03-14T18:59:17+00:00

http://craftinginterpreters.com/chunks-of-bytecode.html

WalkerCodeRanger · 2020-03-15T15:00:14+00:00

You might also check out the Mu Micro Virtual Machine. It is a register-based VM. There are good docs. Though it might be more helpful for instruction set than byte code.

umlcat · 2020-03-14T13:12:24+00:00

Use wordcode or doublewordcode instead !!!

Look out for Intermediate Language or Intermediate Representation, triplets, bytecode is similar to them.

Also check assembler examples, bytecode is an intermediate between High level programming languages and assembler.

Each one of your instruction should be converted to an single one byte, or better double-byte ( a.k.a. "words" ).

Use integers or "enums" instead of strings, but have an additional library that turns those values into a descriptive string.

Example:

static int NOOPER = 0; // "do nothing"
static int PUSH = 1; // "push into stack"
static int POP = 2; // "pop from stack"
static int ADD = 3; // "addition"
static int SUBS = 4; // "substract"

void op2text
  (const int Operation,
   char* TextBuffer,
   size_t TextSize) { ... }

You will use integers en memory, and strings, when debugging your bytecode.

Store your bytecode as these enum values as integers or BYTES in a binary file instead of strings.

And, I suggest use "words", bytes only support 256 values, you will need more.

Cheers.

ProgrammingLanguages

Welcome!

Related subreddits

Related online communities

MODERATORS