Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

> 在 2015年12月17日，下午4:26，Maxim Uvarov 写道： > > On 12/17/2015 08:56, HePeng wrote: >> Hi, Maxim >> >> I will present a quick patch that will not pass the kernel style >> check as this one is just for evaluation. > ok, in that case you can add RFC to patch tag. Sorry, I

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

On 12/17/2015 08:56, HePeng wrote: Hi, Maxim I will present a quick patch that will not pass the kernel style check as this one is just for evaluation. ok, in that case you can add RFC to patch tag. Maxim. 在 2015年12月16日，下午8:22，Maxim Uvarov 写道： From meeting we

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Hi, Maxim I will present a quick patch that will not pass the kernel style check as this one is just for evaluation. > 在 2015年12月16日，下午8:22，Maxim Uvarov 写道： > > From meeting we decided that we want solution based on pool. Can you post that > patches? We will try to

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

From meeting we decided that we want solution based on pool. Can you post that patches? We will try to help how to improve performance. Maxim. On 12/14/2015 22:30, Mike Holmes wrote: Added to Tuesday agenda On 12 December 2015 at 22:18, HePeng

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Added to Tuesday agenda On 12 December 2015 at 22:18, HePeng wrote: > Ping. > > So what is your decision on this. > > 在 2015年12月10日，下午1:06，HePeng 写道： > > > 在 2015年12月9日，下午6:49，Ola Liljedahl 写道： > > On 9 December 2015 at

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Ping. So what is your decision on this. > 在 2015年12月10日，下午1:06，HePeng 写道： > >> >> 在 2015年12月9日，下午6:49，Ola Liljedahl > > 写道： >> >> On 9 December 2015 at 06:31, HePeng >

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

On 12/09/2015 08:54, HePeng wrote: Let me further explain this. Cuckoo hash is a hash table, and as a hash table, it needs to store the key-value paris. For any input, e.g. a key ( a byte string with some size), a hash table needs to calculate the hash value from the key, find the right

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

On 9 December 2015 at 06:31, HePeng wrote: > > 在 2015年12月8日，下午9:34，Ola Liljedahl 写道： > > On 8 December 2015 at 12:42, Bill Fischofer > wrote: > >> This is an interesting topic. I'd like to discuss this a bit during >>

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

On 9 December 2015 at 11:20, Maxim Uvarov wrote: > On 12/09/2015 08:54, HePeng wrote: > >> Let me further explain this. >> >> Cuckoo hash is a hash table, and as a hash table, it needs to store the >> key-value paris. >> For any input, e.g. a key ( a byte string with

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

> 在 2015年12月9日，下午6:20，Maxim Uvarov 写道： > > On 12/09/2015 08:54, HePeng wrote: >> Let me further explain this. >> >> Cuckoo hash is a hash table, and as a hash table, it needs to store the >> key-value paris. >> For any input, e.g. a key ( a byte string with some

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

> 在 2015年12月9日，下午6:49，Ola Liljedahl 写道： > > On 9 December 2015 at 06:31, HePeng > wrote: > >> 在 2015年12月8日，下午9:34，Ola Liljedahl > > 写道： >> >> On 8

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Peng, can you please send version with buffers pool to the list. Might be something wrong in implementation. Maxim. On 12/08/2015 14:42, Bill Fischofer wrote: This is an interesting topic. I'd like to discuss this a bit during today's ODP public call. I think the issue is that while a ring

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

This is an interesting topic. I'd like to discuss this a bit during today's ODP public call. I think the issue is that while a ring is a very useful implementation construct its semantics are very SW centric. Perhaps there's opportunity here for a new Queue type that would permit an

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

On 8 December 2015 at 06:39, HePeng wrote: > Hi Maxim, > I implement a new version of cuckoo hash based on the ODP > buffer/pool. > > As I’ve mentioned earlier, the use of ring in cuckoo hash is like > to the use of > a container, e.g. a queue in C++ STL. In

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

On 8 December 2015 at 12:42, Bill Fischofer wrote: > This is an interesting topic. I'd like to discuss this a bit during > today's ODP public call. > > I think the issue is that while a ring is a very useful implementation > construct its semantics are very SW

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

> 在 2015年12月8日，下午9:34，Ola Liljedahl 写道： > > On 8 December 2015 at 12:42, Bill Fischofer > wrote: > This is an interesting topic. I'd like to discuss this a bit during today's > ODP public call. > > I

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Let me further explain this. Cuckoo hash is a hash table, and as a hash table, it needs to store the key-value paris. For any input, e.g. a key ( a byte string with some size), a hash table needs to calculate the hash value from the key, find the right bucket, and compare the input key with

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Hi Maxim, I implement a new version of cuckoo hash based on the ODP buffer/pool. As I’ve mentioned earlier, the use of ring in cuckoo hash is like to the use of a container, e.g. a queue in C++ STL. In current ODP implementation, I found that the ODP queue is implemented

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

> 在 2015年12月2日，下午5:30，Maxim Uvarov 写道： > > On 12/02/2015 10:26, HePeng wrote: >>> 在 2015年11月30日，下午11:04，Maxim Uvarov 写道： >>> >>> On 11/30/2015 11:18, HePeng wrote: Hi, Maxim, How is everything going, about the ring? >>> >>> Hello

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

> 在 2015年11月30日，下午11:04，Maxim Uvarov 写道： > > On 11/30/2015 11:18, HePeng wrote: >> Hi, Maxim, >> How is everything going, about the ring? > > > Hello Peng, > > We need to take a look it it's possible to rewrite your hash implementation > to odp queues api instead of

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Cuckoo Hash Table is an efficient hash table variant which has a very high utilization (load/total entries > 90%). In our tests, the utilization is around 94%. Here is a brief introduction on cuckoo hash: https://en.wikipedia.org/wiki/Cuckoo_hashing

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Peng, please find quick review bellow. The main comment is you need to split this patch on 3 patches: - "api:" patch with proposal api change; - implementation patch - validation test patch. I just wanted to move code from helper to linux-generic and reuse it for shm ipc. But now it looks

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Please ignore this patch, it contains a silly mistake on hash.h which modifies its comments causing a typo. sorry. > 在 2015年11月26日，上午10:20，Peng 写道： > > Signed-off-by: Peng > --- > helper/Makefile.am |2 + >

[lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Signed-off-by: Peng --- helper/Makefile.am |2 + helper/cuckoo_hash.c| 1117 +++ helper/include/odp/helper/cuckoo_hash.h | 435 helper/include/odp/helper/ring.h| 43 ++

[lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

Signed-off-by: Peng --- helper/Makefile.am |2 + helper/cuckoo_hash.c| 1117 +++ helper/include/odp/helper/cuckoo_hash.h | 435 helper/include/odp/helper/ring.h| 43 ++