clox

A Bytecode Virtual Machine written in C for the Lox language from Crafting Interpreters.

NOTE: I did one of the challenges that adds support for 3-byte long operands, that's why there are additional xxx_LONG instructions being emitted and handled throughout the VM.

TODO:

Lox is a pretty small toy language missing some standard language features, this is more of learning project for me so I think I'll only add the following:

• Multi-line comments

• More arithmetic operators (pow/**, modulo/%)

• Jump statements (break, continue)

• Arrays

  • Initializing arrays
  • Printing arrays
  • Indexing into arrays
  • Assigning at array indices

• String indexing

  • NOTE: Because strings are interned, I'm only adding indexing for get operations.

• Type methods

  Array methods (arr.push(), arr.pop(), arr.len(), etc.)

  • arr.len()
  • arr.push(val)
  • arr.pop()
  • arr.get(i)
  • arr.set(i, val)
  • arr.insert(i, val)
  • arr.remove(i)
  • arr.contains(val)
  • arr.indexOf(val)
  • arr.slice(a, b=n)
  • arr.concat(other)
  • arr.reverse()
  • arr.join(sep)
  • arr.clear()
  • arr.isEmpty()
  • arr.copy() (shallow copy)
  String methods (str.len(), str.replace(), etc.)

  • str.len()
  • str.replace(old, new)
  • str.contains(sub)
  • str.startsWith(pre)
  • str.endsWith(suf)
  • str.indexOf(sub)
  • str.slice(a, b)
  • str.toUpper()
  • str.toLower()
  • str.trim()
  • str.trimStart()
  • str.trimEnd()
  • str.split(sep)
  • str.isEmpty()
  • str.repeat(n)

Other than that, I'm planning on adding some additional optimizations to the interpreter, here's what I'm thinking:

• Inline Caching for property access (i.e. for OP_GET_PROPERTY/OP_SET_PROPERTY - apparently one of the instructions that take the longest amount of time)

  • NOTE: To make the inline caching implementation as easy as possible, I made property access/storage use a hash table and array together. The array stores the values of the fields for an ObjInstance, whereas the hash table (which is in ObjClass) maps the field name to the index of its value in that array. The reason I went with this instead of keeping a single hash table mapping field names to field values is because hash table resizes would instantly invalidate the cache and make this more complex.

    The overall access/storage time complexity stays the same since I still use the hash table to check if a property exists on an instance, and access using indexes on an array is O(1).

    One caveat is that the inline caching assumes all instances have the same object layout, so if you add a property to a certain instance outside of init(), accessing the same field (if not set or out-of-sync) on another instance is UB. It sucks but eh, learning project, toy language, it is what it is.

  • RESULTS (using -O3): ~35-37% speedup on Binary Trees benchmark, ~15-17% speedup on Trees benchmark, ~1-3% speedup on Properties benchmark.

• x86-64 Baseline JIT (compiling the instructions in ObjFunction to machine code when a certain call threshold is reached at runtime)