Reinterpreting The Lua Interpreter

The idea behind Lua is a beautiful one. A simple and concise syntax offers almost all of the niceties of a first-class language. Moreover, a naive implementation of an interpreter with a giant switch case can be implemented in an afternoon. But assembly is your go-to to get decent performance in a JIT-style interpreter. So [Haoran Xu] started to ask himself if he could achieve better performance without hand-rolled assembly, and after a few months of work, he published a work-in-progress called LuaJIT Remake (LJR).

Currently, it supports Lua 5.1, and on a smattering of 34 benchmarks, LJR beats the leading fastest Lua, LuaJIT, by around 28% and the official Lua engine by 3x. [Haoran] offers a great explanation of interpreters that provides excellent background and context for the problem.

But the long and short of it is that switch cases are expensive and hard to optimize for compilers, so using tail calling is a reasonable solution that comes with some significant drawbacks. With tail calls, each case statement becomes a “function” that is jumped to and then jumped out of without mucking with the stack or the registers too much.

However, the calling convention requires any callee-saved registers to be preserved, which means you lose some registers as there is no way to tell the compiler that this function is allowed to break the calling convention. Clang is currently the only compiler that offers a guaranteed tail-call annotation ([[clang::musttail]]). There are other limitations too, for instance requiring the caller and callee to have identical function prototypes to prevent unbounded stack growth.

So [Haoran] went back to the drawing board and wrote two new tools: C++ bytecode semantical description and a special compiler called Deegen. The C++ bytecode looks like this:

void Add(TValue lhs, TValue rhs) {
  if (!lhs.Is<tDouble>() || !rhs.Is<tDouble>()) {
    ThrowError("Can't add!");
  } else {
    double res = lhs.As<tDouble>() + rhs.As<tDouble>();
    Return(TValue::Create<tDouble>(res));
  }
}
DEEGEN_DEFINE_BYTECODE(Add) {
  Operands(
    BytecodeSlotOrConstant("lhs"),
    BytecodeSlotOrConstant("rhs")
  );
  Result(BytecodeValue);
  Implementation(Add);
  Variant(
    Op("lhs").IsBytecodeSlot(),
    Op("rhs").IsBytecodeSlot()
  );
  Variant(
    Op("lhs").IsConstant(),
    Op("rhs").IsBytecodeSlot()
  );
  Variant(
    Op("lhs").IsBytecodeSlot(),
    Op("rhs").IsConstant()
  );
}

Note that this is not the C keyword return. Instead, there is a definition of the bytecode and then an implementation. This bytecode is converted into LLVM IR and then fed into Deegen, which can transform the functions to do tail calls correctly, use the GHC calling conventions, and a few other optimizations like inline caching through a clever C++ lambda mechanism. The blog post is exceptionally well-written and offers a fantastic glimpse into the wild world of interpreters.

The code is on Github. But if you’re interested in a more whimsical interpreter, here’s a Brainf**k interpreter written in Befunge.

Review: HUZZAH Is The ESP8266 WiFi Setup You Need

A little board that adds WiFi to any project for a few hundreds of pennies has been all the rage for at least half a year. I am referring to the ESP8266 and this product is a marrige of one of those WiFi modules with the support hardware required to get it running. This week I’m reviewing the HUZZAH ESP8266 Breakout by Adafruit Industries.

If you saw the article [cnlohr] woite for us about direct programming this board you will know that a good chunk of that post covered what you need to do just to get the module into programming mode. This required adding a regulated 3.3V source, and a way to pull one of the pins to ground when resetting the power rail. Not only does the HUZZAH take care of that for you, it turns the non-breadboard friendly module into a DIP form factor while breaking out way more pins than the most common module offers. All of this and the price tag is just $9.95. Join me after the break for the complete run-down.

Continue reading “Review: HUZZAH Is The ESP8266 WiFi Setup You Need”

Flashing The ESP8266 In Windows

It’s only been a few months since the ESP8266 rolled out of some factory in China, and already the community is moving from simply getting custom firmware to work on the device to making the development tools easy to use. That’s huge – the barrier to entry is lowered, getting even more people on board with this very cool Internet of Things thing.

While the majority of the community is settling on using the Lua interpreter firmware, there’s still the matter of getting this firmware uploaded to the ESP. [Peter Jennings] of Microchess fame has been working on a Windows app to upload firmware to the ESP via a serial interface. There’s not much to it, but this will allow you to upload the community-created Lua firmware, set the WiFi credentials, toggle GPIO pins, and give you the ability to write a little bit of Lua in the same window.

If you’re looking for something that isn’t designed exclusively for Windows, there’s an alternative firmware flasher over on the nodemcu Github. This flasher also connects the ESP8266 to a network and uploads firmware. It’s a stripped-down programmer without a serial terminal or the ability to toggle pins, but there are plans for making this programmer cross-platform.