You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@trafficserver.apache.org by Phil Sorber <so...@apache.org> on 2013/02/18 20:50:54 UTC
RamCacheCLFUS
In looking through RamCacheCLFUS I came upon this:
static const int bucket_sizes[] = {
127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071,
262139,
524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859,
134217689, 268435399, 536870909, 1073741789, 2147483647
};
Looking through git blame and JIRA it looks like it was part of the initial
patch for CLFUS. In talking with James in IRC he pointed out that it looks
like the largest prime less than a power of 2. This seems like a very
deliberate choice, but I can't figure out why and there are no docs
explaining. Can someone, perhaps John, shed some light on it?
Thanks.
Re: RamCacheCLFUS
Posted by Leif Hedstrom <zw...@apache.org>.
On 2/18/13 4:07 PM, Phil Sorber wrote:
>
> Upon further inspection it seems like this is duplicated code in both
> RamCache implementations. Perhaps this should be abstracted out and added
> to libts. Or replaced with a libts implementation if it already exists.
>
+1. Things shared across implementations ought to be, ehm, reused :). For
bonus points, change the code such that we can write these RAM caches as
plugins ;-).
-- Leif
Re: RamCacheCLFUS
Posted by Phil Sorber <ph...@sorber.net>.
On Mon, Feb 18, 2013 at 4:59 PM, Phil Sorber <ph...@sorber.net> wrote:
>
> On Mon, Feb 18, 2013 at 4:41 PM, Tomasz Kuzemko <to...@kuzemko.net>wrote:
>
>> Did not look at the code, but seems like it is part of some general hash
>> table implementation.
>>
>>
> It is for a hash table AFAICT.
>
>
>> Good explanation why these are primes:
>>
>> http://stackoverflow.com/**questions/1145217/why-should-**
>> hash-functions-use-a-prime-**number-modulus<http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus>
>>
>>
> Ah, that is very interesting and makes good sense. I will add a comment.
>
>
Upon further inspection it seems like this is duplicated code in both
RamCache implementations. Perhaps this should be abstracted out and added
to libts. Or replaced with a libts implementation if it already exists.
> Thanks.
>
>
>> Best regards,
>> Tomasz Kuzemko
>> tomasz@kuzemko.net
>>
>> W dniu 18.02.2013 20:50, Phil Sorber pisze:
>>
>> In looking through RamCacheCLFUS I came upon this:
>>>
>>> static const int bucket_sizes[] = {
>>> 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071,
>>> 262139,
>>> 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393,
>>> 67108859,
>>> 134217689, 268435399, 536870909, 1073741789, 2147483647
>>> };
>>>
>>> Looking through git blame and JIRA it looks like it was part of the
>>> initial
>>> patch for CLFUS. In talking with James in IRC he pointed out that it
>>> looks
>>> like the largest prime less than a power of 2. This seems like a very
>>> deliberate choice, but I can't figure out why and there are no docs
>>> explaining. Can someone, perhaps John, shed some light on it?
>>>
>>> Thanks.
>>>
>>>
>
Re: RamCacheCLFUS
Posted by Phil Sorber <ph...@sorber.net>.
On Mon, Feb 18, 2013 at 4:41 PM, Tomasz Kuzemko <to...@kuzemko.net> wrote:
> Did not look at the code, but seems like it is part of some general hash
> table implementation.
>
>
It is for a hash table AFAICT.
> Good explanation why these are primes:
>
> http://stackoverflow.com/**questions/1145217/why-should-**
> hash-functions-use-a-prime-**number-modulus<http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus>
>
>
Ah, that is very interesting and makes good sense. I will add a comment.
Thanks.
> Best regards,
> Tomasz Kuzemko
> tomasz@kuzemko.net
>
> W dniu 18.02.2013 20:50, Phil Sorber pisze:
>
> In looking through RamCacheCLFUS I came upon this:
>>
>> static const int bucket_sizes[] = {
>> 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071,
>> 262139,
>> 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393,
>> 67108859,
>> 134217689, 268435399, 536870909, 1073741789, 2147483647
>> };
>>
>> Looking through git blame and JIRA it looks like it was part of the
>> initial
>> patch for CLFUS. In talking with James in IRC he pointed out that it looks
>> like the largest prime less than a power of 2. This seems like a very
>> deliberate choice, but I can't figure out why and there are no docs
>> explaining. Can someone, perhaps John, shed some light on it?
>>
>> Thanks.
>>
>>
Re: RamCacheCLFUS
Posted by Tomasz Kuzemko <to...@kuzemko.net>.
Did not look at the code, but seems like it is part of some general hash
table implementation.
Good explanation why these are primes:
http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus
Best regards,
Tomasz Kuzemko
tomasz@kuzemko.net
W dniu 18.02.2013 20:50, Phil Sorber pisze:
> In looking through RamCacheCLFUS I came upon this:
>
> static const int bucket_sizes[] = {
> 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071,
> 262139,
> 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859,
> 134217689, 268435399, 536870909, 1073741789, 2147483647
> };
>
> Looking through git blame and JIRA it looks like it was part of the initial
> patch for CLFUS. In talking with James in IRC he pointed out that it looks
> like the largest prime less than a power of 2. This seems like a very
> deliberate choice, but I can't figure out why and there are no docs
> explaining. Can someone, perhaps John, shed some light on it?
>
> Thanks.
>