table.insert and negative numbers

[Matthew Paul Del Buono <delbu9c1@...>]

In my testing I encountered an issue where the following line would cause the system to go into (what seemed to be, at the time) an infinite loop:

t = {};
table.insert(t, 2^31, 1);


After researching, however, it appears that this is due to the fact that 2^31 becomes a negative number. I expanded my search and found that tinsert() attempts to copy every value up one index until it reaches the pos value (2^31, or approx. -2 billion), which is an extremely expensive operation if the index doesn't presently exist (especially if the table is empty). Even numbers as low as -1000000 take a long time on an empty table (tested on an AMD64 x2 4400+).

While it's conceivable to say that Lua doesn't support negative numbers in table.insert, or that the value -1000000 will likely never be reached, is there any particular reason that the negative case is going completely unchecked? A simple test can speed up the operation significantly for those rare cases where such a table structure might be desired. The price to pay for such a check would is practically zero when compared to the expense of the table.insert operation itself. Patched test cases and patch follows. If anyone has any recommendations or comments here I'd love to hear them.

Regards,
-- Matthew P. Del Buono

P.S. I had several iterations of this patch, including one which just plain didn't support negative numbers and gave an error, but I figured that for backwards compatibility reasons, functionality should remain in-tact. I don't particularly like this solution due to the double-traversal on negative positions, but I couldn't think of a better solution to acquiesce to everyone. Perhaps someone else has another idea.

Lua 5.1.3  Copyright (C) 1994-2008 Lua.org, PUC-Rio
> t = {1,2,3};
> table.insert(t, 2, 0)
> for k,v in pairs(t) do print(k,v) end
1       1
2       0
3       2
4       3
> t = {[-1]=-1,[-2]=-2,[-3]=-3};
> for k,v in pairs(t) do print(k,v) end
-2      -2
-1      -1
-3      -3
> table.insert(t, -2, 0)
> for k,v in pairs(t) do print(k,v) end
-2      0
0       -1
-1      -2
-3      -3
> t = {};
> table.insert(t, 2^31, 1)
> for k,v in pairs(t) do print(k,v) end
-2147483648     1

----- Patch follows

101c101,119
<       if (pos > e) e = pos;  /* `grow' array if necessary */
---
>         if (pos < 0)                   /* Determine how much we need to move */
>         {
>               i = pos;
>               lua_rawgeti(L, 1, i);
>               while (!lua_isnil(L, -1))
>               {
>                       lua_pop(L, 1);
>                       lua_rawgeti(L, 1, ++i);
>               };
>               lua_pop(L, 1);
>               /* Now i is the first nil index greater than pos */
>               for (; i > pos; i--) {          /* Move them up */
>                       lua_rawgeti(L, 1, i-1);
>                       lua_rawseti(L, 1, i);   /* t[i] = t[i-1] */
>               }
>               break;
>         }
>         /* Non-negative, just move backwards */
>         if (pos > e) e = pos;  /* `grow' array if necessary */