netdev
[Top] [All Lists]

Re: [PATCH] improvement on net/sched/cls_fw.c's hash function

To: Thomas Graf <tgraf@xxxxxxx>
Subject: Re: [PATCH] improvement on net/sched/cls_fw.c's hash function
From: "David S. Miller" <davem@xxxxxxxxxxxxx>
Date: Wed, 6 Apr 2005 11:15:09 -0700
Cc: hadi@xxxxxxxxxx, lark@xxxxxxxxxxxx, netdev@xxxxxxxxxxx
In-reply-to: <20050406141020.GQ26731@xxxxxxxxxxxxxx>
References: <20050405213023.0256.LARK@xxxxxxxxxxxx> <1112717495.1076.22.camel@xxxxxxxxxxxxxxxx> <20050406143842.026B.LARK@xxxxxxxxxxxx> <20050406123036.GO26731@xxxxxxxxxxxxxx> <1112794459.1096.61.camel@xxxxxxxxxxxxxxxx> <20050406134502.GP26731@xxxxxxxxxxxxxx> <20050406141020.GQ26731@xxxxxxxxxxxxxx>
Sender: netdev-bounce@xxxxxxxxxxx
On Wed, 6 Apr 2005 16:10:20 +0200
Thomas Graf <tgraf@xxxxxxx> wrote:

> The thing I'm worrying about is that I don't want to break the perfect
> alignment of fw_head to good slab obj sizes but I guess there is no
> way around. I'd really like to make hash size and hash function
> configureable. For example a hash size of 1024 would perform much
> better and would still fit into a single page on most systems.

I think a hash xor'ing in the high bits into the low 8 bits, as has
been suggested a few times already, meets your criteria and solves
Lark's problem.

The hash table size, if still an issue, can be dynamically sized based
upon some criteria with some reasonable default initial selection
(such as the current 256).

I think dynamic hash function selection is madness.  You have a key
that needs to be hashed, you are aware of one very common usage
(the one that perfectly hashes currently) and you are also aware of
a method by which the cases that don't fit into that mold can be made
to perform acceptably too (xor'ing in the upper bits).  We can thus
do this with one single hash function.


<Prev in Thread] Current Thread [Next in Thread>