Mailing List Archive: iptables: User

even hash tables sizes, FAQ entry

Index | Next | Previous | View Threaded

jacob at internet24

Jul 19, 2007, 4:47 PM

Post #1 of 8 (1511 views)
Permalink

even hash tables sizes, FAQ entry

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?

Attachments:

signature.asc (0.19 KB)

david.lang at digitalinsight

Jul 19, 2007, 5:13 PM

Post #2 of 8 (1466 views)
Permalink

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

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

jacob at internet24

Jul 20, 2007, 12:41 AM

Post #3 of 8 (1472 views)
Permalink

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

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?

Attachments:

signature.asc (0.19 KB)

david.lang at digitalinsight

Jul 20, 2007, 10:44 AM

Post #4 of 8 (1460 views)
Permalink

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

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

kaber at trash

Jul 20, 2007, 10:50 AM

Post #5 of 8 (1461 views)
Permalink

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

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.

david.lang at digitalinsight

Jul 20, 2007, 11:08 AM

Post #6 of 8 (1461 views)
Permalink

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

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

kaber at trash

Jul 20, 2007, 8:44 PM

Post #7 of 8 (1479 views)
Permalink

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

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).

ged at jubileegroup

Jul 20, 2007, 11:41 PM

Post #8 of 8 (1473 views)
Permalink

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

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.

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads