Hi Yipeng, Stephen, all,
On 17/03/2020 19:52, Wang, Yipeng1 wrote:
-----Original Message-----
From: Stephen Hemminger <step...@networkplumber.org>
Sent: Monday, March 16, 2020 12:33 PM
To: Medvedkin, Vladimir <vladimir.medved...@intel.com>
Cc: Morten Brørup <m...@smartsharesystems.com>; dev@dpdk.org;
Ananyev, Konstantin <konstantin.anan...@intel.com>; Wang, Yipeng1
<yipeng1.w...@intel.com>; Gobriel, Sameh <sameh.gobr...@intel.com>;
Richardson, Bruce <bruce.richard...@intel.com>; Suanming Mou
<suanmi...@mellanox.com>; Olivier Matz <olivier.m...@6wind.com>;
Xueming(Steven) Li <xuemi...@mellanox.com>; Andrew Rybchenko
<arybche...@solarflare.com>; Asaf Penso <as...@mellanox.com>; Ori Kam
<or...@mellanox.com>
Subject: Re: [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table
On Mon, 16 Mar 2020 18:27:40 +0000
"Medvedkin, Vladimir" <vladimir.medved...@intel.com> wrote:
Hi Morten,
On 16/03/2020 14:39, Morten Brørup wrote:
From: dev [mailto:dev-boun...@dpdk.org] On Behalf Of Vladimir
Medvedkin
Sent: Monday, March 16, 2020 2:38 PM
Currently DPDK has a special implementation of a hash table for
4 byte keys which is called FBK hash. Unfortunately its main
drawback is that it only supports 2 byte values.
The new implementation called DWK (double word key) hash supports 8
byte values, which is enough to store a pointer.
It would also be nice to get feedback on whether to leave the old
FBK and new DWK implementations, or whether to deprecate the old
one?
<rant on>
Who comes up with these names?!?
FBK (Four Byte Key) and DWK (Double Word Key) is supposed to mean
the same. Could you use 32 somewhere in the name instead, like in int32_t,
instead of using a growing list of creative synonyms for the same thing?
Pretty please, with a cherry on top!
That's true, at first I named it as fbk2, but then it was decided to
rename it "dwk", so that there was no confusion with the existing FBK
library. Naming suggestions are welcome!
And if the value size is fixed too, perhaps the name should also indicate
the value size.
<rant off>
It's a shame we don't have C++ class templates available in DPDK...
In other news, Mellanox has sent an RFC for an "indexed memory pool"
library [1] to conserve memory by using uintXX_t instead of pointers, so
perhaps a variant of a 32 bit key hash library with 32 bit values (in addition
to
16 bit values in FBK and 64 bit in DWK) would be nice combination with that
library.
[1]: http://mails.dpdk.org/archives/dev/2019-October/147513.html
Med venlig hilsen / kind regards
- Morten Brørup
Why is this different (or better) than existing rte_hash.
Having more flavors is not necessarily a good thing (except in Gelato)
[Wang, Yipeng]
Hi, Vladimir,
As Stephen mentioned, I think it is good idea to explain the benefit of this
new type of hash table more explicitly such as
Specific use cases, differences with current rte_hash, and performance numbers,
etc.
The main reason for this new hash library is performance. As I mentioned
earlier, the current rte_fbk implementation is pretty fast but it has a
number of drawbacks such as 2 byte values and limited collision
resolving capabilities. On the other hand, rte_hash (cuckoo hash)
doesn't have this drawbacks but at the cost of lower performance
comparing to rte_fbk.
If I understand correctly, performance penalty are due to :
1. Load two buckets
2. First compare signatures
3. If signature comparison hits get a key index and find memory location
with a key itself and get the key
4. Using indirect call to memcmp() to compare two uint32_t.
The new proposed 4 byte key hash table doesn't have rte_fbk drawbacks
while offers the same performance as rte_fbk.
Regarding use cases, in rte_ipsec_sad we are using rte_hash with 4 byte
key size. Replacing it with a new implementation gives about 30% in
performance.
The main disadvantage comparing to rte_hash is some performance
degradation with high average table utilization due to chain resolving
for 5th and subsequent collision.
--
Regards,
Vladimir
