Re: How fast is LuaJIT supposed to be?

[Mike Pall <mikelu-1101@...>]

Michal Kolodziejczyk wrote:
> On 21.01.2011 20:08, Steve Litt wrote:
> > You know what I might try someday? Make a C module to store each number in a 
> > bit instead of a byte.
> 
> Be careful here, this actually may be slower than pure lua version,
> because there is a cost of crossing Lua/C boundary. Been there...
> I would go with pure lua on luajit2 if you want performance.

Using the classic Lua/C API is almost certainly slower than
writing pure Lua code and running it under LuaJIT.

The LuaJIT bit operations library allows you to store bits in Lua
numbers (with a certain overhead). The LuaJIT FFI allows you to
store raw bits in memory with no overhead.

A version of the Sieve of Eratosthenes with bit operations is here:
  http://lua-users.org/lists/lua-l/2010-04/msg00133.html

Attached is a version using bit ops + the FFI. Only two lines
had to be changed and it's ~2x faster than before.

--Mike

-- This is the (naive) Sieve of Eratosthenes. Public domain.

local ffi = require("ffi")
local bit = require("bit")
local band, rshift, rol = bit.band, bit.rshift, bit.rol

local function nsieve(m)
  local p = ffi.new("int32_t[?]", rshift(m, 5)+1, -1)
  local count = 0
  for i=2,m do
    if band(rshift(p[rshift(i, 5)], i), 1) ~= 0 then
      count = count + 1
      for j=i+i,m,i do
	local jx = rshift(j, 5)
	p[jx] = band(p[jx], rol(-2, j))
      end
    end
  end
  return count
end

local N = tonumber(arg and arg[1]) or 1000
io.write(string.format("Primes up to %d: %d\n", N, nsieve(N)))