Re: Lua5 / poor performance

[Roberto Ierusalimschy <roberto@...>]

The real problem is related to tables. Lua hashes all numbers to their
integer parts. Lua 5.0 uses an auxiliary table to track constants used
by a function (using the constants as keys). In this particular file,
there are lots of numbers between 0 and 1 (plus other similar ranges).
Then, all these numbers collide in the auxiliary table, and so the
performance problem.

This problem with tables exists in Lua since a long time (version 2.0 at
least), but surprisingly it never happened in a real case before. This
sigle program shows the problem in 4.0:

  local a = {}
  for i=0,1,0.00001 do a[i] = i end

(Warning! It takes a *long* time to run.)


Any solution to this problem must change the way Lua hashes non-integer
numbers. One particular solution is this:

Node *luaH_mainposition (const Table *t, const TObject *key) {
  switch (ttype(key)) { 
    case LUA_TNUMBER: {
      int ikey;
      lua_Number n = nvalue(key);
      lua_number2int(ikey, n);
      if (cast(lua_Number, ikey) == n)  /* is an integer index? */
        return hashnum(t, ikey);
      else {
        int i;
        union {
          lua_Number n;
          int a[sizeof(lua_Number)/sizeof(int)];
        } u;
        memset(&u, 0, sizeof(u));
        u.n = n;
        for (i=1; i<sizeof(lua_Number)/sizeof(int); i++)
          u.a[0] += u.a[i];
        return hashnum(t, u.a[0]);
      }
    }
    ...   /* other cases as before */


This code is not very "religious", but it does the trick. (The
performance for integer keys is not affected by this change.)

-- Roberto