[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Sieve of Eratosthenes performance question
- From: "Shoaib Meenai" <shobiz91@...>
- Date: Thu, 7 Jun 2007 00:36:23 +0500
On 6/7/07, Rici Lake <firstname.lastname@example.org> wrote:
On 6-Jun-07, at 2:05 PM, Shoaib Meenai wrote:
> On 6/6/07, Rici Lake <email@example.com> wrote:
>> On 6-Jun-07, at 1:27 PM, 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
>> >> 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?
>> Probably not. The optimization requires (roughly) that the array uses
>> than half of the indices in the range [1, 2^k] for some integer k (and
>> applies to the indices in that range: anything outside of the range is
>> stored in the hash part of the table).
> But if I used, for example, indices 1296 to 65536 (which is 2^16),
> would the optimization apply? Or does k have some preset value which
> varies from system to system?
Lua chooses the largest k which satisfies the criterion (with some
which is 24 by default if I recall correctly). So that would trigger
the optimization, eventually, as the table grows in size.
Thank you very much. Just one last thing: is the limit customizable?