Fast integer arithmetic

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Fast integer arithmetic

John D. Ramsdell-2
It occurs to me that number intensive applications that rely only on
integral computations would enjoy a strong performance boost if run on
top of a version of Lua that uses integers for all its numerical
operations, instead of computing with doubles, and converting the
results to integers.  A compile option to produce Lua binaries without
floating point instructions would create this faster version of Lua.
Perhaps performance is a more compelling motivation for supporting
floating point instruction free versions of Lua.

John

Reply | Threaded
Open this post in threaded view
|

Re: Fast integer arithmetic

Enrico Colombini
John D. Ramsdell wrote:
A compile option to produce Lua binaries without
floating point instructions would create this faster version of Lua.

I just put this at the end of luaconf.h. It may not be perfect, but it works (some of the redefinitions are identical to the originals, I put them in for clarity).

Re-reading it, I'm not sure about LUAI_MAXNUMBER2STR. Should I count the terminator? I'll have to check.

  Enrico

-----------------------------------------------------------------

/*
 * Notes:
 * - pow() still uses double and is therefore slow
 * - string.format('%f') converts to double with decimal part = 0
 */

/* this line switches LUA_NUMBER from double to int */
#define LUA_NUMBER_INT

/* patch starts here */
#ifdef LUA_NUMBER_INT

#undef LUA_NUMBER_DOUBLE

#undef LUA_NUMBER
#define LUA_NUMBER          int

#undef  LUAI_UACNUMBER
#define LUAI_UACNUMBER	    int

#undef LUA_NUMBER_SCAN
#undef LUA_NUMBER_FMT
#undef LUAI_MAXNUMBER2STR
#undef lua_str2number
#define LUA_NUMBER_SCAN     "%d"
#define LUA_NUMBER_FMT      "%d"
#define LUAI_MAXNUMBER2STR	12 /* 10 digits, sign, point, and \0 */
#define lua_str2number(s,p)	strtol((s), (p), 10)

#undef luai_nummod
#undef luai_numpow
#define luai_nummod(a,b)    ((a) % (b))
#define luai_numpow(a,b)    (int)(pow((double)a,(double)b) + 0.5)

#undef lua_number2int
#undef lua_number2integer
#define lua_number2int(i,d) ((i)=(int)(d))
#define lua_number2integer(i,d) ((i)=(lua_Integer)(d))

#endif /*LUA_NUMBER_INT*/
/* patch ends here */

Reply | Threaded
Open this post in threaded view
|

Re: Fast integer arithmetic

John D. Ramsdell-2
In reply to this post by John D. Ramsdell-2
Enrico Colombini <[hidden email]> writes:

> I just put this at the end of luaconf.h.

To make progress on supporting integer operations, you must change
src/lvm.c so that it correctly handles integer divide by zero.  I've
enclosed a patch that addresses this issue.  It also provides integer
exponentiation. 

John

diff -ur olua-5.1.3/src/lvm.c lua-5.1.3/src/lvm.c
--- olua-5.1.3/src/lvm.c	2007-12-28 10:32:23.000000000 -0500
+++ lua-5.1.3/src/lvm.c	2008-02-20 10:27:15.000000000 -0500
@@ -27,6 +27,37 @@
 #include "lvm.h"
 
 
+#if defined LUA_NUMBER_INTEGRAL
+#define luai_znumdiv(a,b)	\
+  ((b)==0?			\
+   (luaG_runerror(L,"divide by zero"),0): \
+   luai_numdiv(a,b))
+#define luai_znummod(a,b)	\
+  ((b)==0?			\
+   (luaG_runerror(L,"modulo by zero"),0): \
+   luai_nummod(a,b))
+
+LUA_NUMBER luai_ipow(LUA_NUMBER a, LUA_NUMBER b) {
+  if (b < 0)
+    return 0;
+  else if (b == 0)
+    return 1;
+  else {
+    LUA_NUMBER c = 1;
+    for (;;) {
+      if (b & 1)
+	c *= a;
+      b = b >> 1;
+      if (b == 0)
+	return c;
+      a *= a;
+    }
+  }
+}
+#else
+#define luai_znumdiv(a,b)	(luai_numdiv(a,b))
+#define luai_znummod(a,b)	(luai_nummod(a,b))
+#endif
 
 /* limit for table tag-method chains (to avoid loops) */
 #define MAXTAGLOOP	100
@@ -321,8 +352,8 @@
       case TM_ADD: setnvalue(ra, luai_numadd(nb, nc)); break;
       case TM_SUB: setnvalue(ra, luai_numsub(nb, nc)); break;
       case TM_MUL: setnvalue(ra, luai_nummul(nb, nc)); break;
-      case TM_DIV: setnvalue(ra, luai_numdiv(nb, nc)); break;
-      case TM_MOD: setnvalue(ra, luai_nummod(nb, nc)); break;
+      case TM_DIV: setnvalue(ra, luai_znumdiv(nb, nc)); break;
+      case TM_MOD: setnvalue(ra, luai_znummod(nb, nc)); break;
       case TM_POW: setnvalue(ra, luai_numpow(nb, nc)); break;
       case TM_UNM: setnvalue(ra, luai_numunm(nb)); break;
       default: lua_assert(0); break;
@@ -480,11 +511,11 @@
         continue;
       }
       case OP_DIV: {
-        arith_op(luai_numdiv, TM_DIV);
+        arith_op(luai_znumdiv, TM_DIV);
         continue;
       }
       case OP_MOD: {
-        arith_op(luai_nummod, TM_MOD);
+        arith_op(luai_znummod, TM_MOD);
         continue;
       }
       case OP_POW: {
Only in lua-5.1.3/src: lvm.c~

Reply | Threaded
Open this post in threaded view
|

Re: Fast integer arithmetic

Leo Razoumov
In reply to this post by John D. Ramsdell-2
On 20 Feb 2008 08:19:05 -0500, John D. Ramsdell <[hidden email]> wrote:
> It occurs to me that number intensive applications that rely only on
>  integral computations would enjoy a strong performance boost if run on
>  top of a version of Lua that uses integers for all its numerical
>  operations, instead of computing with doubles, and converting the
>  results to integers.

Do you have a quantitative evidence of this?
All my anecdotal experience is to the contrary of your statement.
Modern CPUs like x86 have very fast FPUs so that arithmetic operations
with double is very fast (one cycle or sometimes several ops/cycle
with parallel pipelines). In fact, floating point arithmetic is faster
that Lua VM operations. I doubt that changing lua_Number from 'double'
to 'int' will boost up Lua code execution speed.

--Leo--

Reply | Threaded
Open this post in threaded view
|

Re: Fast integer arithmetic

Enrico Colombini
Leo Razoumov wrote:
Do you have a quantitative evidence of this?
All my anecdotal experience is to the contrary of your statement.
Modern CPUs like x86 have very fast FPUs so that arithmetic operations
with double is very fast (one cycle or sometimes several ops/cycle
with parallel pipelines). In fact, floating point arithmetic is faster
that Lua VM operations. I doubt that changing lua_Number from 'double'
to 'int' will boost up Lua code execution speed.

You're right, of course. I assumed John is working on a FPU-less CPU (as a I do).

  Enrico

Reply | Threaded
Open this post in threaded view
|

Re: Fast integer arithmetic

John D. Ramsdell-2
In reply to this post by John D. Ramsdell-2
> Leo Razoumov wrote:
> > Do you have a quantitative evidence of this?
> > All my anecdotal experience is to the contrary of your statement.
> > Modern CPUs like x86 have very fast FPUs so that arithmetic
> > operations with double is very fast (one cycle or sometimes
> > several ops/cycle with parallel pipelines).

Leo, I haven't performed any measurements, however, it would be very
easy to do so, as I have a version of Lua 5.1.3 that has been patched
with the "Go Long Lua" patch already on my machine.  Is there a
standard numerical Lua benchmark or group of benchmarks that people
use when assessing Lua performance?  You have made me so curious right
now.

> Enrico Colombini <[hidden email]> wrote:

> You're right, of course. I assumed John is working on a FPU-less CPU (as 
> a I do).

Actually, my environment is a very light weight operating system that
runs inside a virtual machine.  The hardware on which the hypervisor
runs has floating point instructions, but you can't use them because
the operating system doesn't save and restore any floating point
registers between VM context switches.

John

Reply | Threaded
Open this post in threaded view
|

Re: Fast integer arithmetic

Leo Razoumov
On 20 Feb 2008 17:23:22 -0500, John D. Ramsdell <[hidden email]> wrote:
> Leo, I haven't performed any measurements, however, it would be very
>  easy to do so, as I have a version of Lua 5.1.3 that has been patched
>  with the "Go Long Lua" patch already on my machine.  Is there a
>  standard numerical Lua benchmark or group of benchmarks that people
>  use when assessing Lua performance?  You have made me so curious right
>  now.

Since what you want is to see the performance differential between
lua_Number being "long int" versus "double", you can use a very simple
numeric loops like the following

local sum=0
for x=1,10000000 do
    sum= sum+ 100/50
end

to test it out.

Hope it helps. Also, please, keep in mind that the performance
trade-offs of an emulator (VM+hypervisor)  can be very different from
the actual hardware.

--Leo--

Reply | Threaded
Open this post in threaded view
|

Re: Fast integer arithmetic

John D. Ramsdell-2
For a benchmark, "Leo Razoumov" <[hidden email]> writes:

> local sum=0
> for x=1,10000000 do
>     sum= sum+ 100/50
> end

Leo,

I decided on a different performance test, one that repeatedly
computes a remainder.  On an IBM IntelliStation M Pro, which uses a
32-bit i386, I compiled a patched and an unpatched version of Lua
5.1.3 with "make ansi".  I then ran the following benchmark.

$ cat mod.lua
local sum = 0
for i = 1,100000000 do
   sum = sum + i % 5
end
print (sum)
$ : Unpatched lua 
$ time lua-5.1.3/src/lua mod.lua 
200000000

real    0m8.321s
user    0m8.286s
sys     0m0.003s
$ : Lua patched with "Go Long Lua!"
$ time plua-5.1.3/src/lua mod.lua 
200000000

real    0m6.196s
user    0m6.170s
sys     0m0.002s
$

So there really is a performance difference between longs and doubles,
even on machines with FPUs.  Note that remainder is an important
component in some cryptography algorithms.

Since it's a 32-bit machine, I'm curious to know if ints are faster
than longs, however, that requires modifying my patch.  Maybe I'll try
that experiment when I have some free time.  

I bet longs are even faster on a 64-bit machine, a Core 2 Duo or one
of AMD's processors.  I'll see if I can find a machine that allows
that hypothesis to be tested too.

John