Experilous

LuaJIT

Lua is a dynamically typed language, with only a small selection of primitive types. Any aggregate or otherwise complex types must use tables (i.e., dictionaries/associative arrays) in some form, which will significantly impact the performance of field/method access as well as the efficiency of data storage (and thus cache usage). LuaJIT’s foreign function interface (FFI) let’s us work around those limitations by offering us the ability to use C declarations to define new types with much greater control and efficiency. In this blog post, I’ll share how, for my Worldbuilder project, I used the FFI to implement a fairly performant fixed point number type. Public domain source code can be downloaded here.

The first step is to use the FFI to declare a C struct which will represent our new type and store its data. We cannot simply use the primitive type directly, because LuaJIT does not allow us to attach metatables to primitive types. Therefore, wrapping the primitive value in a named struct grants us the power afforded by metatables. It also improves the clarity of diagnostic messages for erroneous type conversions and such, by assigning the type a distinct name. For this example, we’ll assume that our underlying storage is a 32-bit integer. (Aside from implementing the multiplication and division operations, supporting 64-bit fixed point numbers is a trivial extension.) I’ll wrap the definition in a function, so that local variables can be used as upvalues within the type’s various functions without polluting any other namespace. I’ll also name the data field _v; it’s not meant to be public, but I do not think it is possible to hide fields of a struct with LuaJIT, hence the underscore as a hint that this is hands-off for any user of the fixed point type.

The next step is to be able to construct instances of this type. We cannot just rely on using the C type produced by LuaJIT, however, because that would merely try to convert the constructor argument to an int32_t, oblivious to our desired fixed point semantic. Instead, we’ll create a table to represent our type, and give it an appropriate __call metamethod. (Sidenote: Take care to use the correct period (.) or colon (:) syntax when defining a function. I prefer to use the colon and implicit self parameter wherever relevant.)

I’ll get to the asRaw(n) function in a moment. For now, just realize that it’s purpose is to return an int32_t instance which is the fixed point representation of its parameter, and it will be used in a variety of places. Given that definition, you can see that the __call metamethod will simply construct an instance of the C type using the appropriate int32_t initializer value, or it will create a default initialized C type if no parameter was passed to the constructor. (Technically, this implementation allows you to also pass nil or false to the constructor to get a default instance, but that’s only accidental.)

Next up is to round-trip the value. Assuming asRaw() has an implementation, we can construct a fixed point number given a Lua number, so it would be nice to be able to get a Lua number back, given a fixed point number. Similarly, being able to convert directly to a string would be useful too. Both of these operations will take advantage of LuaJIT’s ability to attach metatables to C types, just as we can to normal Lua tables. I’ll also include a convenience field to get the type given an instance, which can come in handy when implementing further infrastructure that utilizes a variety of types.

Like with asRaw(), rawToNumber() is going to be a private function that takes an int32_t representation of our fixed type and converts it to a Lua number. That’s why we pass in the _v field directly.

Now that we have a metatable for our C type, we might as well implement the other obvious metamethods: the mathematical and comparison operators.

There are a few different things going on here to note. The first is that I have used asRaw() on all of the binary operator parameters. This is so that math and comparisons between a fixed point number and a Lua number are simple and do the right thing.

Another is that I have referenced some more yet-to-be-defined private functions, one for each operation. Their definitions, along with asRaw() and rawToNumber() are coming up next. The five mathematical operations all return a raw int32_t value, thus they are wrapped in an initializer for the C type. The three comparison functions all return a bool which can be returned directly.

Third, you’ll notice that I perform what amounts to a nil test for the parameters to __eq. Contrary to the wording in the official Lua 5.1 documentation, LuaJIT’s documentation is clear that all binary operators apply to mixed types, including between C data and nil. With the other functions, I consider it acceptable to treat a nil parameter as producing undefined behavior. But for an equality comparison, checking against nil is a useful operation and should have the obvious behavior. Fortunately, we don’t have to check to see if both parameters are nil, because if they were, we’d never be within the body of this metamethod. So if either one of the parameters is nil, then we know that the other is not, and therefore the two are not equal.

One last thing I’ll point out in this section is the extra set of parentheses around each of the C type initializers. Without the parentheses, these return statements would represent tail calls, and in Lua, tail call runtime behavior is mandatory, whereas in other languages it might only be an optional optimization that the compiler or interpreter is free to ignore. Due to the nature of LuaJIT’s code execution tracing, tail calls to built-in LuaJIT functions will cause the compiler to abort and fallback to the interpreter, and the initializer of a C type is indeed treated as a built-in function. Adding the extra parentheses causes the initializer to be called in the normal manner rather than as a tail call, allowing the tracing compiler to continue along merrily. It would be disastrous to performance to fallback to the interpreter whenever performing math or comparisons between numbers, so this is a subtle but crucial point to make.

Okay, now to get around to defining those private functions I’ve been referencing. These in turn will be referencing C functions defined outside of Lua, and are mostly convenience wrappers around these C functions. So I’ll start by pulling those C declarations in through the FFI, and then defining the private Lua wrappers around them.

The asRaw() function expects either a fixed point instance or a Lua number. Anything else is undefined behavior. In particular, anything that is C data but is not a struct with a _v field will produce an error. And if it is a struct with a _v field that represents something other than this fixed point type’s raw value, then who knows what will happen further on in the code.

Also, a number of these operations require the fractional bit count in order to perform their computations, so the Lua wrapper functions capture this parameter as an upvalue. The others could be done away with, calling the exe version directly, but for consistency, I’ve left them as is.

At this point, our fixed point number type is shaping up to be fairly usable, but let’s add some extra features that will greatly extend it’s usability. I’m only going to outline a general pattern, but it can be easily extended to include similar functionality.

The member function variants defined first are mutating and chainable functions. This allows expressions such as Q1616(4.1):Power(3):Floor():Clamp(0, 100). In my production code I’ve included the basic mathematical and comparison operations too, along with a few other helper functions like Clone() and Set(). For these functions that have operator equivalents (+ - * / = == ~= < <= > >=), I drop the calls to asRaw(), and require that their inputs already be of fixed point type. This grants the user a way to perform micro-optimizations if necessary, for example in a tight loop performing a lot of math. Why bother executing the branch contained in asRaw() if you know that all values are already fixed point?

For the constants, I return a newly constructed instance each time the constant is accessed, since LuaJIT will often operate with reference semantics, not value semantics, and I don’t want something like Q1616.pi:Sqrt() to suddenly change the value of pi everywhere.

I’ve glossed over an important step in defining the type; the metatables of course need to be attached to their type tables. Now that I have all the metatables and helper tables and defined, we can do that. For the type table, we’ll use the standard Lua function setmetatable(), while for the C type, we’ll instead use ffi.metatype().

As an added bonus, we can put together a collection of type details that can be used for reflective purposes elsewhere in code. For example, if defining a matrix type that uses fixed point numbers, the matrix definition code can request the details of its number type, and adjust its definition accordingly. In particular, it can store an array of int32_t instances directly, and use the private fixed point functions defined above to implement standard matrix operations. This will avoid a lot of unnecessary overhead with C data construction and parameter type checks. I discovered that it is also necessary because LuaJIT will not compile the initialization of a C type if it is a struct that contains nested structs. Thus, constructing a 2D vector of fixed point numbers that is defined as struct { struct { int32_t _v; } _x; struct { int32_t _v; } _y; } will fallback to the interpreter, but if instead it is defined as struct { int32_t _x; int32_t _y; }, the compiler will be able to handle that just fine.

The final line of our DefineFixedPointType() function can return both typeTable and typeDetails. When we call it, we can then put the typeTable into the global namespace, or whatever other namespace we wish. We can also stuff the typeDetails table into a lookup table keyed by the type itself. I’m going to put these operations in a small helper function.

From this point, usage of the fixed type might look something like the following:

That concludes the basic definition of a 32-bit fixed point number type in LuaJIT. The full source and some basic usage can be downloaded here, with both C++ and Lua portions. The contents of this download, and all source code excerpts within this blog post, are released into the public domain. For more information, please refer to unlicense.org.

3 Comments

Leave a comment