xt_hashlimit : speedups hash_dst()
Subsystems (3)
1) Using jhash2() instead of jhash() is a litle bit faster if applicable.
2) Thanks to jhash, hash value uses full 32 bits. Instead of returning hash % size (implying a divide) we return the high 32 bits of the (hash * size) that will give results between [0 and size-1] and same hash distribution.
On most cpus, a multiply is less expensive than a divide, by an order of magnitude.
net/netfilter/xt_hashlimit.c +10 -1
@@ -105,7 +105,16 @@ static inline bool dst_cmp(const struct dsthash_ent *ent,static u_int32_t hash_dst (const struct xt_hashlimit_htable *ht,const struct dsthash_dst *dst) { -return jhash (dst,sizeof (*dst), ht->rnd) % ht->cfg.size; +u_int32_t hash =jhash2 ((const u32 *)dst, +sizeof (*dst)/sizeof (u32), + ht->rnd); +/* +* Instead of returning hash % ht->cfg.size (implying a divide) +* we return the high 32 bits of the (hash * ht->cfg.size) that will +* give results between [0 and cfg.size-1] and same hash distribution, +* but using a multiply, less expensive than a divide +*/ +return ((u64 )hash * ht->cfg.size) >>32 ; } static struct dsthash_ent *
Quoted 9 lines · Eric Dumazet
1) Using
jhash2()instead ofjhash()is a litle bit faster if applicable.2) Thanks to jhash, hash value uses full 32 bits. Instead of returning hash % size (implying a divide) we return the high 32 bits of the (hash * size) that will give results between [0 and size-1] and same hash distribution.
On most cpus, a multiply is less expensive than a divide, by an order of magnitude.
Clever :) Applied, thanks Eric.
David Miller
maintainerFrom: Eric Dumazet <[email protected]>
Date: Fri, 14 Dec 2007 12:09:31 +0100
Quoted 11 lines
1) Using
jhash2()instead ofjhash()is a litle bit faster if applicable.2) Thanks to jhash, hash value uses full 32 bits. Instead of returning hash % size (implying a divide) we return the high 32 bits of the (hash * size) that will give results between [0 and size-1] and same hash distribution.
On most cpus, a multiply is less expensive than a divide, by an order of magnitude.
Signed-off-by Eric Dumazet <[email protected]>
As a side note, Jenkins performs nearly optimally (unlike most traditional hash functions) with power of two hash table sizes.
Using a pow2 hash table size would completely obviate the issues solved by #2.
I don't know if that is feasible here in xt_hashlimit, but if it is that is how we should solve this expensive modulo.
Eric Dumazet wrote, On 12/14/2007 12:09 PM:
...
net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117
Quoted 7 lines
net/netfilter/xt_hashlimit.c +7
-0+/* +* Instead of returning hash % ht->cfg.size (implying a divide) +* we return the high 32 bits of the (hash * ht->cfg.size) that will +* give results between [0 and cfg.size-1] and same hash distribution, +* but using a multiply, less expensive than a divide +*/ +return ((u64 )hash * ht->cfg.size) >>32 ;
Are we sure of the same hash distribution? Probably I miss something,
but: if this 'hash' is well distributed on 32 bits, and ht->cfg.size is smaller than 32 bits, e.g. 256 (8 bits), then this multiplication moves to the higher 32 of u64 only max. 8 bits of the most significant byte, and the other three bytes are never used, while division is always affected by all four bytes...
Regards,
Jarek P.
Quoted 17 lines · Jarek Poplawski
Eric Dumazet wrote, On 12/14/2007 12:09 PM:
...net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117
Quoted 7 lines
net/netfilter/xt_hashlimit.c +7
-0+/* +* Instead of returning hash % ht->cfg.size (implying a divide) +* we return the high 32 bits of the (hash * ht->cfg.size) that will +* give results between [0 and cfg.size-1] and same hash distribution, +* but using a multiply, less expensive than a divide +*/ +return ((u64 )hash * ht->cfg.size) >>32 ;Are we sure of the same hash distribution? Probably I miss something,
but: if this 'hash' is well distributed on 32 bits, andht->cfg.sizeis smaller than 32 bits, e.g. 256 (8 bits), then this multiplication moves to the higher 32 of u64 only max. 8 bits of the most significant byte, and the other three bytes are never used, while division is always affected by all four bytes...
Not sure what you are saying... but if size=256, then, yes, we want a final result between 0 and 255, so three bytes are nul.
'size' is the size of hashtable, its not a random 32bits value :)
-
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Eric Dumazet wrote, On 12/14/2007 10:37 PM:
Quoted 18 lines
Quoted 16 lines · Jarek Poplawski
Eric Dumazet wrote, On 12/14/2007 12:09 PM:
...net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117
Quoted 7 lines
net/netfilter/xt_hashlimit.c +7
-0+/* +* Instead of returning hash % ht->cfg.size (implying a divide) +* we return the high 32 bits of the (hash * ht->cfg.size) that will +* give results between [0 and cfg.size-1] and same hash distribution, +* but using a multiply, less expensive than a divide +*/ +return ((u64 )hash * ht->cfg.size) >>32 ;Are we sure of the same hash distribution? Probably I miss something,
but: if this 'hash' is well distributed on 32 bits, andht->cfg.sizeis smaller than 32 bits, e.g. 256 (8 bits), then this multiplication moves to the higher 32 of u64 only max. 8 bits of the most significant byte, and the other three bytes are never used, while division is always affected by all four bytes...
Quoted 2 lines
Not sure what you are saying... but if size=256, then, yes, we want a final result between 0 and 255, so three bytes are nul.
Eric, it would be nice to acknowledge David's suggestion that this hash size is always power of two here, because otherwise at least your words about the same hash distribution according to the "%" variant could be wrong (but I don't say the final result would be wrong). Maybe I mix up these sizes, but it seems this could be set by a user, and I didn't find anything about this power of two necessity?
Regards,
Jarek P.
-
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 19 lines · Jarek Poplawski
Eric Dumazet wrote, On 12/14/2007 10:37 PM:
Quoted 17 lines
Quoted 16 lines · Jarek Poplawski
Eric Dumazet wrote, On 12/14/2007 12:09 PM:
...net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117
Quoted 7 lines
net/netfilter/xt_hashlimit.c +7
-0+/* +* Instead of returning hash % ht->cfg.size (implying a divide) +* we return the high 32 bits of the (hash * ht->cfg.size) that will +* give results between [0 and cfg.size-1] and same hash distribution, +* but using a multiply, less expensive than a divide +*/ +return ((u64 )hash * ht->cfg.size) >>32 ;Are we sure of the same hash distribution? Probably I miss something,
but: if this 'hash' is well distributed on 32 bits, andht->cfg.sizeis smaller than 32 bits, e.g. 256 (8 bits), then this multiplication moves to the higher 32 of u64 only max. 8 bits of the most significant byte, and the other three bytes are never used, while division is always affected by all four bytes...
Quoted 9 lines
Quoted 1 line
Not sure what you are saying... but if size=256, then, yes, we want a final result between 0 and 255, so three bytes are nul.
Eric, it would be nice to acknowledge David's suggestion that this hash size is always power of two here, because otherwise at least your words about the same hash distribution according to the "%" variant could be wrong (but I don't say the final result would be wrong). Maybe I mix up these sizes, but it seems this could be set by a user, and I didn't find anything about this power of two necessity?
size is not a power of two here.
I prefer to let admins chose their size, since it makes attacker life more difficult :)
For example, I can tell you I have a server, were size is between 2.000.000 and 3.500.000, I dont want to be forced to use 2097152
A multiply is cheap, at least on current hardware.
-
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
David Miller
maintainerFrom: Eric Dumazet <[email protected]>
Date: Sat, 15 Dec 2007 12:04:47 +0100
Quoted 7 lines
I prefer to let admins chose their size, since it makes attacker life more difficult :)
For example, I can tell you I have a server, were size is between 2.000.000 and 3.500.000, I dont want to be forced to use 2097152
A multiply is cheap, at least on current hardware.
I agree, and I see nothing wrong with Eric's patch and it should be merged ASAP.
Quoted 11 lines · David Miller
From: Eric Dumazet <[email protected]>
Date: Sat, 15 Dec 2007 12:04:47 +0100Quoted 5 lines
I prefer to let admins chose their size, since it makes attacker life more difficult :)
For example, I can tell you I have a server, were size is between 2.000.000 and 3.500.000, I dont want to be forced to use 2097152
A multiply is cheap, at least on current hardware.
I agree, and I see nothing wrong with Eric's patch and it should be merged ASAP.
I have it queued for 2.6.25 - would you like me to send it for 2.6.24?
Quoted 6 lines · David Miller
From: Eric Dumazet <[email protected]>
Date: Sat, 15 Dec 2007 12:04:47 +0100Quoted 3 lines
I prefer to let admins chose their size, since it makes attacker life more difficult :)
Quoted 7 lines
Quoted 4 lines
For example, I can tell you I have a server, were size is between 2.000.000 and 3.500.000, I dont want to be forced to use 2097152
A multiply is cheap, at least on current hardware.
I agree, and I see nothing wrong with Eric's patch and it should be merged ASAP.
You could do the same optimization for net/netfilter/nf_conntrack_core.c:__hash_conntrack() , too.
Signature · 1 line
Do what you love because life is too short for anything else.
Quoted 6 lines · Sami Farin
Quoted 5 lines · David Miller
From: Eric Dumazet <[email protected]>
Date: Sat, 15 Dec 2007 12:04:47 +0100Quoted 2 lines
I prefer to let admins chose their size, since it makes attacker life more difficult :)
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
For example, I can tell you I have a server, were size is between 2.000.000 and 3.500.000, I dont want to be forced to use 2097152
A multiply is cheap, at least on current hardware.
I agree, and I see nothing wrong with Eric's patch and it should be merged ASAP.
You could do the same optimization for net/netfilter/nf_conntrack_core.c:__hash_conntrack() , too.
Yes, I already took care of that for conntrack and other netfilter non-power-of-two hashes.
Jarek Poplawski wrote, On 12/14/2007 09:59 PM:
Quoted 17 lines
Eric Dumazet wrote, On 12/14/2007 12:09 PM:
...net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117
Quoted 7 lines
net/netfilter/xt_hashlimit.c +7
-0+/* +* Instead of returning hash % ht->cfg.size (implying a divide) +* we return the high 32 bits of the (hash * ht->cfg.size) that will +* give results between [0 and cfg.size-1] and same hash distribution, +* but using a multiply, less expensive than a divide +*/ +return ((u64 )hash * ht->cfg.size) >>32 ;Are we sure of the same hash distribution? Probably I miss something,
but: if this 'hash' is well distributed on 32 bits, andht->cfg.sizeis smaller than 32 bits, e.g. 256 (8 bits), then this multiplication moves to the higher 32 of u64 only max. 8 bits of the most significant byte, and the other three bytes are never used, while division is always affected by all four bytes...
OOPS! So, I've missed this division here is also affected by only one byte, but from the other side - so, almost the same... It seems this could have been replaced with masking from the beginning...
Sorry,
Jarek P.