RE: Sieve of Eratosthenes performance question

["Jerome Vuarand" <jerome.vuarand@...>]

Shoaib Meenai wrote:
> On 6/6/07, Philippe Lhoste <PhiLho@gmx.net> wrote:
>> ... 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 ... 
> 
> Might be a stupid question, but would the optimization apply even if
> the first index was, say, 1296? 

AFAIK the array part or a table t goes from index 1 to index #t. #t is
defined as an integer so that t[#t] is non nil and t[#t+1] is nil,
nothing more precise. This means that the array part *may* stop at the
first nil value (it can be index 1), or it *may* extend to the last
non-nil integer index. The only way to know exactly the size of the
array part is to make sure that these two potential sizes are the same.
And to do that you have to fill the array.