Lua Integer type

Question

i really need to have an integer type in Lua.

What i mean by integer type is a type defining the usual operators (/ * + etc) and behaving like an integer, the internal representation doesn't matter.

Doing such a thing with tables is very simple, the problem is, i tried that, and the performance is terribly poor (of course). Here is my partial implementation :

function num_op(a, b, calc_func)
    local atype = pytype(a)
    local btype = pytype(b)
    local a_val, b_val

    a_val = (atype == "Integer" or atype == "Double") and a[1] or a
    b_val = (btype == "Integer" or btype == "Double") and b[1] or b
    val = calc_func(a_val, b_val)

    if atype == "Integer" and btype == "Integer" then
        return Integer:create(val)
    else
        return Double:create(val)
    end
end

numeric_mt = { 
    __add = function(a, b)
        return num_op(a, b, function(a,b) return a + b end)
    end,

    __sub = function(a, b)
        return num_op(a, b, function(a,b) return a - b end)
    end,

    __div = function(a, b)
        return num_op(a, b, function(a,b) return a / b end)
    end,

    __mul = function(a, b)
        return num_op(a, b, function(a,b) return a * b end)
    end,

    __tostring = function(a)
        return tostring(a[1])
    end
}

-----------------------------
-- Integer type definition --
-----------------------------

Integer = {}
Integer_mt = table.copy(numeric_mt)
Integer_mt["__index"] = Integer

function Integer:create(value)
    local new_inst = {math.floor(value)}
    setmetatable(new_inst, Integer_mt)
    return new_inst
end

function Integer:className()
    return "Integer"
end

The main performance penalty from what i gather is (of course) the very numerous allocations. LuaJit is able to optimize the operators functions quite well, but not the metatables allocations.

Do anybody think it would be possible to do better with a custom c implementation and userdata ? Or is what i'm pursuing impossible to attain ?

NB : i know lua doesn't have integers. I also know that i can obtain the same results using the math lib. What i want is complete transparency when using integers, except for the creation phase.

EDIT : I'm gonna add additional information in here so that everything is still centralized

@Mud: I need, to a certain degree to have transparent mixed arithmetics in the same way you have in python/ruby/etc, but with the best performance possible. I'm using luaJIT as a target for a compiler, with regular Lua as a fallback for platforms not supported by luaJIT. This is very important for the performance characteristics.

It means that i would like to be able to do this:

a = int(5) -- Integer value
b = int(2) -- Another Integer
c = 2      -- Double
d = a / b  -- == 2 , integer arithmetics
e = a / c  -- == 2.5, floating point arithmetics

I can reach that to a certain point, with the implementation showed above. The problem is that i'm slowing operations on every numbers, since regular numbers are boxed too. I could overload the metatable of numbers with the debug lib, but

• I don't know how reliable this feature is for use in production quality software
• It will still slow down the performance of numbers since, to be able to have an unified interface to numbers, i'll have to use (number):get(), which will slow down operation in any case.

I rolled my own Integer implementation in C last night. The thing is, although it is an improvement over my naive implementation in regular lua, and also and improvement over inline calls to math.floor, it's much less clear when using LuaJIT, where inline calls are still a lot faster than the C implementation.

Another solution would be to always use unboxed numbers, and use some kind of type propagation in my compiler to track integers and use proper inline operations on them when needed, but the complexity of this solution is a lot bigger, and kind of defeats the whole purpose of using Lua/LuaJIT as a backend.

I'm gonna try your implementation, but i doubt it will be better than inline calls in LuaJIT. It may very well be that what i'm shooting for (having both transparent operation of double and integers, and performance close to inline calls on luaJIT) is plain impossible. Thank you very much for your help.

@miky : Thanks, this is looking nice, but i doubt i can patch luaJIT with it, and if i can't, it looses all its interrest for my goal.

Answer 1

Why do you need them? The best way to help you find a performant solution to your problem is to understand the problem. What specifically do you need integers for?

The main performance penalty from what i gather is (of course) the very numerous allocations.

Well, you're creating closures on every operation, and I don't understand why you have a Double class at all, given that Lua's number type is already a double. Couldn't you do something like this?

Integer = {}
local function val(o) return type(o) == 'number' and o or o[1] end
function Integer.__add(a,b) return Integer:create(val(a) + val(b)) end
function Integer.__sub(a,b) return Integer:create(val(a) - val(b)) end
function Integer.__div(a,b) return Integer:create(val(a) / val(b)) end
function Integer.__mul(a,b) return Integer:create(val(a) * val(b)) end
function Integer:__tostring() return tostring(self[1]) end
function Integer:create(value)
   return setmetatable({math.floor(value)}, Integer)
end


-- test
a = Integer:create(15.34)
b = Integer:create(775.34433)
print((a*10/2+b-3)/3*a+b) --> 5005

Anybody think it would be possible to do better with a custom c implementation and userdata?

Yes, a C implementation should be faster, because you wouldn't need to create a table for each Integer; your userdata could literally just be an int*. This would also eliminate the need for the floor call.

EDIT: I wrote a test C implementation and it's ~5 times faster than the Lua implementation presented in this post.

EDIT 2: Link to C code is dead, so here's some code I found buried in my hard disk which may or may not be the code that was at that link. I know that it compiles against Lua 5.1, but beyond that.. no clue if it's even a technically valid implementation. Been too long since I wrote any Lua C code.

#include <math.h>
#include "lua.h"
#include "lauxlib.h"

/* get value of Integer userdata or Lua number at index, or die */
static int checkintX (lua_State *L, int index) {
   int result = 0;
   if (lua_isuserdata(L, index) && luaL_checkudata(L, index, "integer")) {
      result = *(int*)lua_touserdata(L, index);
   } else if (lua_isnumber(L, index)) {
      double val = lua_tonumber(L, index);
      int x = (int) val;
      result = (int) lua_tonumber(L, index);
   } else {
      lua_pushstring(L, "Invalid operand. Expected 'integer' or 'number'");
      lua_error(L);
   }
   return result;
}

static int checkint(lua_State* L, int index) {
   int result = checkintX(L, index);
   return result;
}

static int create_integer(lua_State* L, int val) {
   int* ud = lua_newuserdata(L, sizeof(int));
   *ud = val;
   luaL_getmetatable(L, "integer");
   lua_setmetatable(L, -2);
   return 1;
}

static int int_new (lua_State* L) { return create_integer( L, checkint(L,1) ); }
static int int_add (lua_State* L) { return create_integer( L, checkint(L,1) + checkint(L,2) ); }
static int int_sub (lua_State* L) { return create_integer( L, checkint(L,1) - checkint(L,2) ); }
static int int_mul (lua_State* L) { return create_integer( L, checkint(L,1) * checkint(L,2) ); }
static int int_div (lua_State* L) { return create_integer( L, checkint(L,1) / checkint(L,2) ); }
static int int_mod (lua_State* L) { return create_integer( L, checkint(L,1) % checkint(L,2) ); }
static int int_pow (lua_State* L) { return create_integer( L, (int) pow( checkint(L,1), checkint(L,2) ) ); }
static int int_unm (lua_State* L) { return create_integer( L, -checkint(L,1) ); }
static int int_eq  (lua_State* L) { lua_pushboolean( L, checkint(L,1) == checkint(L,2) ); return 1; }
static int int_lt  (lua_State* L) { lua_pushboolean( L, checkint(L,1) <  checkint(L,2) ); return 1; }
static int int_le  (lua_State* L) { lua_pushboolean( L, checkint(L,1) <= checkint(L,2) ); return 1; }
static int int_tostring (lua_State* L) {
   lua_pushnumber(L, checkint(L,1));
   lua_tostring(L, -1);
   return 1;
}

int __declspec(dllexport) __cdecl luaopen_integer (lua_State* L) {
   static const struct luaL_reg integermt[] = {
      { "__add", int_add },
      { "__sub", int_sub },
      { "__mul", int_mul },
      { "__div", int_div },
      { "__mod", int_mod },
      { "__pow", int_pow },
      { "__unm", int_unm },
      { "__eq",  int_eq  },
      { "__lt",  int_lt  },
      { "__le",  int_le  },
      { "__tostring", int_tostring},
      NULL, NULL
   };
   luaL_newmetatable(L, "integer");
   luaL_openlib(L, NULL, integermt, 0);

   lua_register(L, "int", int_new);

   return 0;
}

Answer 2

Integers (64-bit by default) were just added in Lua 5.3!

http://www.lua.org/versions.html#5.3

Answer 3

If you want to only deal with integers you could always #define LUA_NUMBER int in luaconf.h.

Answer 4

You can try one of the arbitrary precision libraries listed at http://www.tecgraf.puc-rio.br/~lhf/ftp/lua/ . In particular, lbn is integer-only and fast but you need OpenSSL. For a simple self-contained library, see lbc.

Answer 5

You could try the LNUM patch, it modifies the Lua core to add integer numeric types, like 32 and 64 bit integers along with doubles. It also supports complex numbers.