Re: Sieve of Eratosthenes performance question

[Philippe Lhoste <PhiLho@...>]

On 06/06/2007 10:32, Ketmar Dark wrote:
> operation "not". remember, Lua is not an optimizing compiler. and
> 5000000 "nots" is definitely slower thant 5000000 "nothings". %-)

No, it is not a compiler, but it generates (more or less) optimized 
bytecode, so in the end it shouldn't make a big difference.
Testing composite[i] == nil is slow too.
The following code shows similar performance:

local t1, t2
local max = 5000000

do

t1 = os.clock()

local n = max or 1000
local prime = {}
local primes = {}

for i = 2, n do prime[i] = true end

for i = 2, n do
 if prime[i] then
   primes[#primes+1] = i
   for j = i*2, n, i do prime[j] = false end
 end
end

t2 = os.clock()
print("First: " .. (t2 - t1) .. " seconds.")

--~ print(table.concat(primes, " "))

end

collectgarbage("collect")

do

t1 = os.clock()

local n = max or 1000
local composite = {}
local primes = {}

for i = 2, n do composite[i] = false end

for i = 2, n do
 if not composite[i] then
   primes[#primes+1] = i
   for j = i*2, n, i do composite[j] = true end
 end
end

t2 = os.clock()
print("Second: " .. (t2 - t1) .. " seconds.")

--~ print(table.concat(primes, " "))

end

I believe the difference is because I made 'composite' an array with 
contiguous numerical indexes, with optimized access in Lua 5.1 (direct 
offset computing), while in the previous code, Lua probably has to make 
more complex tests (hashing the index?) to see if the slot is empty.

--
Philippe Lhoste
--  (near) Paris -- France
--  http://Phi.Lho.free.fr
--  --  --  --  --  --  --  --  --  --  --  --  --  --