• Subject: Re: Sieve of Eratosthenes performance question
• From: Philippe Lhoste <PhiLho@...>
• Date: Wed, 06 Jun 2007 11:15:09 +0200

```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
--  --  --  --  --  --  --  --  --  --  --  --  --  --

```