Mailing List Archive: even hash tables sizes, FAQ entry

even hash tables sizes, FAQ entry

jacob at internet24

Jul 19, 2007, 4:47 PM

Post #1 of 8 (4190 views)

The FAQ says

"Please note that due to the nature of the current hashing algorithm, an even hash bucket count (and esp. values of the power of two) are a bad choice."

Is this still true? What is the reason for this? And: Does
any odd hashtable size work as well as other odd hash tables sizes
in the same order of magnitude?

Re: even hash tables sizes, FAQ entry [ In reply to ]

david.lang at digitalinsight

Jul 19, 2007, 5:13 PM

Post #2 of 8 (4059 views)

On Fri, 20 Jul 2007, Thomas Jacob wrote:

> The FAQ says
>
> "Please note that due to the nature of the current hashing algorithm, an even hash bucket count (and esp. values of the power of two) are a bad choice."
>
> Is this still true? What is the reason for this? And: Does
> any odd hashtable size work as well as other odd hash tables sizes
> in the same order of magnitude?

changing conntrack_max is not chaning the hash bucket count, that change can
only be done in the code or as a module parameter at module load time.

David Lang

Re: even hash tables sizes, FAQ entry [ In reply to ]

jacob at internet24

Jul 20, 2007, 12:41 AM

Post #3 of 8 (4064 views)

On Thu, Jul 19, 2007 at 05:13:11PM -0700, David Lang wrote:
[..]
> >Is this still true? What is the reason for this? And: Does
> >any odd hashtable size work as well as other odd hash tables sizes
> >in the same order of magnitude?
>
> changing conntrack_max is not chaning the hash bucket count, that change
> can only be done in the code or as a module parameter at module load time.

Sure, I meant odd hash bucket counts of course, so is this
FAQ still accurate?

Re: even hash tables sizes, FAQ entry [ In reply to ]

david.lang at digitalinsight

Jul 20, 2007, 10:44 AM

Post #4 of 8 (4050 views)

On Fri, 20 Jul 2007, Thomas Jacob wrote:

> On Thu, Jul 19, 2007 at 05:13:11PM -0700, David Lang wrote:
> [..]
>>> Is this still true? What is the reason for this? And: Does
>>> any odd hashtable size work as well as other odd hash tables sizes
>>> in the same order of magnitude?
>>
>> changing conntrack_max is not chaning the hash bucket count, that change
>> can only be done in the code or as a module parameter at module load time.
>
> Sure, I meant odd hash bucket counts of course, so is this
> FAQ still accurate?

as far as I know.

David Lang

Re: even hash tables sizes, FAQ entry [ In reply to ]

Jul 20, 2007, 10:50 AM

Post #5 of 8 (4058 views)

David Lang wrote:
> On Fri, 20 Jul 2007, Thomas Jacob wrote:
>
>> On Thu, Jul 19, 2007 at 05:13:11PM -0700, David Lang wrote:
>> [..]
>>
>>>> Is this still true? What is the reason for this? And: Does
>>>> any odd hashtable size work as well as other odd hash tables sizes
>>>> in the same order of magnitude?
>>>
>>>
>>> changing conntrack_max is not chaning the hash bucket count, that change
>>> can only be done in the code or as a module parameter at module load
>>> time.
>>
>>
>> Sure, I meant odd hash bucket counts of course, so is this
>> FAQ still accurate?
>
>
> as far as I know.

None of this is :) hash_buckets can be changed at runtime through the
sysfs module parameter and the size can be chosen arbitary, in fact
the current -git tree will round it up to the next multiple of
PAGE_SIZE / (sizeof(struct hlist_head)) to avoid memory wastage.

Re: even hash tables sizes, FAQ entry [ In reply to ]

david.lang at digitalinsight

Jul 20, 2007, 11:08 AM

Post #6 of 8 (4066 views)

On Fri, 20 Jul 2007, Patrick McHardy wrote:

> David Lang wrote:
>> On Fri, 20 Jul 2007, Thomas Jacob wrote:
>>
>>> On Thu, Jul 19, 2007 at 05:13:11PM -0700, David Lang wrote:
>>> [..]
>>>
>>>>> Is this still true? What is the reason for this? And: Does
>>>>> any odd hashtable size work as well as other odd hash tables sizes
>>>>> in the same order of magnitude?
>>>>
>>>>
>>>> changing conntrack_max is not chaning the hash bucket count, that change
>>>> can only be done in the code or as a module parameter at module load
>>>> time.
>>>
>>>
>>> Sure, I meant odd hash bucket counts of course, so is this
>>> FAQ still accurate?
>>
>>
>> as far as I know.
>
>
> None of this is :) hash_buckets can be changed at runtime through the
> sysfs module parameter and the size can be chosen arbitary, in fact
> the current -git tree will round it up to the next multiple of
> PAGE_SIZE / (sizeof(struct hlist_head)) to avoid memory wastage.

not knowing what that sizeof evaluates to, has anyone checked to make sure that
this doesn't cause pathalogical performance or distribution problems with this
hash?

David Lang

Re: even hash tables sizes, FAQ entry [ In reply to ]

Jul 20, 2007, 8:44 PM

Post #7 of 8 (4084 views)

David Lang wrote:
> On Fri, 20 Jul 2007, Patrick McHardy wrote:
>>
>> None of this is :) hash_buckets can be changed at runtime through the
>> sysfs module parameter and the size can be chosen arbitary, in fact
>> the current -git tree will round it up to the next multiple of
>> PAGE_SIZE / (sizeof(struct hlist_head)) to avoid memory wastage.
>
>
> not knowing what that sizeof evaluates to

Its not something a user needs to know, but its 4 bytes on 32 bit and
8 bytes on 64 bit.

> has anyone checked to make
> sure that this doesn't cause pathalogical performance or distribution
> problems with this hash?

Yes. jhash has been extensively scrutinzed before becoming standard
for basically everything under net/. You can safely assume that all
hashsizes behave similar (and patches for outdates FAQs are welcome).

Re: even hash tables sizes, FAQ entry [ In reply to ]

ged at jubileegroup

Jul 20, 2007, 11:41 PM

Post #8 of 8 (4081 views)

Hi guys,

On Sat, 21 Jul 2007 Patrick McHardy wrote:

> >> ... is this FAQ still accurate?
> >
> > as far as I know.
>
> None of this is :)

Is this?

http://www.wallfire.org/misc/netfilter_conntrack_perf.txt

--

73,
Ged.