CODEWITHSUNDEEP
c#bytecodediscriminated-union
Andy Isbell
Andy Isbell

Reputation: 259

Implementing ByteCode interpreter in c#

My question: is there a memory-efficient way to mimic the c++ union concept while allowing for string datatype, or some other efficient way to include data types and values in bytecode with minimal pointer chasing so as to take advantage of instruction caching?

I'm trying to write a VM bytecode interpreter in C#. I'd like to keep it in C# for simplicity, security, and familiarity reasons, mostly because I want to interact with a library of C# code I've already written.

There's information about how to do so online readily enough, except that it uses 'union' in c++, for which I can't seem to find an equivalent. Specifically, any kind of values (that is, anything that isn't an instruction) are stored as a tagged union.

I've searched and found questions like: Discriminated union in C#, but their answers don't make for efficient code - using inheritance still involves pointer chasing.

C++ union in C# proposes using StructLayout. It works until you need string values, and then throws:

[StructLayout(LayoutKind.Explicit)]
public struct SampleUnion
{
    [FieldOffset(0)] public byte typeTag;
    [FieldOffset(1)] public int num;
    [FieldOffset(1)] public bool flag;
    [FieldOffset(1)] public string c;
}

Could not load type ... because it contains an object field at offset 1 that is incorrectly aligned or overlapped by a non-object field.

I also tried messing around with just passing around arrays of bytes but then I get burned in perf costs when I have to use the value, because I have to convert it.

I've considered using dynamic. Maybe that will work, but it's at best a waste of memory for some types, and at worst I'm uncertain what shenanigans it might try to pull behind the scenes.

I mean, worst case scenario I suppose I could write the byte code interpreter in c++ and call it within the c# code, but I'd rather avoid that if I can, especially because I don't love the idea of messing around with the unsafe keyword, and it introduces a lot of complexity into my project.

Upvotes: 1

Views: 468

Answers (1)

Axel Kemper
Axel Kemper

Reputation: 11322

As described in this article, the pseudocode of a bytecode interpreter is:

load the bytecode into memory
initialize interpreter state
repeat {
   fetch the next instruction,    advance the instruction pointer
   decode the instruction 
   execute the instruction
}

Depending on the bytecode format or structure, the instruction can have either fixed or dynamic length. Data like arrays or strings are typically referenced as (fixed length) memory offsets. The data is embedded in the bytecode separate from the instructions. The data address/offset is an index within the bytecode, as data is stored as sequence of bytes. An instruction to load a string would contain the string offset but not the string data itself.

To fetch and decode the next instruction, it is common to analyze the first one or two bytes which is/are usually the opcode. From this opcode, the length of the instruction is derived. The bytes belonging to the instruction can then be copied into a struct(ure) to disect it further and extract the instruction operand(s).

I can't see where a union would help in this process.

A simple C++ bytecode interpreter is described in XIDEK Extensible Interpreter Development Kit

Upvotes: 0

Related Questions