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

2015-12-18 Thread HePeng 

> 在 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 misunderstood your decision. Will provide a 
patch passing style check soon. 

Another question is that last time you told me 
about moving cuckoo hash into the ODP/ not 
helper/. Is there any changes? if not, I am going to 
add this in ODP/. 

> 
> Maxim.
>> 
>>> 在 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 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 > 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 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 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.
>>> 
>>>But isn't the use case here SW centric?
>>> 
>>>Perhaps there's opportunity here for a new Queue type
>>>that would permit an implementation to implement the
>>>queue API as a ring for additional performance?
>>> 
>>>I think it is a bad idea to overload the ODP queue with
>>>another type of usage and implied implementation. Better to
>>>define a new ODP object.
>>> 
>>>What are the real requirements of the "ring" as used by the
>>>cuckoo hash design? Enqueue/dequeue operations. Fixed size
>>>is OK? Storing arbitrary objects (not just ODP events)?
>>The real requirement is use the ring as a sort of container.
>>Fixed Size is OK. And the ring should be used to
>>store any ODP events, since it is used as a container,
>>like vector in C++ STL.
>> 
>>What if I would like to store objects that are not ODP events in
>>the cuckoo hash table? E.g. arbitrary pointers (to memory that
>>is managed in some other way).
>> 
>Yes, that is currently ring’s implementation.
> 
> 
>> 
>>>  The scheduler itself could use this since its use of
>>>queues is subject to the same issues.
>>> 
>>>On Mon, Dec 7, 2015 at 11:39 PM,
>>>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 current
>>>ODP implementation, I found that
>>>the ODP queue is implemented more likely a facility
>>>for transmitting objects, not
>>>a container to store objects. Look at the ODP queue
>>>enqueue interface:
>>> 
>>>int odp_queue_enq(odp_queue_t queue,
>>>odp_event_t ev);
>>> 
>>>the *odp_event_t* is related to the events, but I
>>>only want to use odp_queue to
>>>storing and retrieving objects, any objects.
>>> 
>>> 
>>>So I use ODP buffer/pool interfaces instead
>>>of ODP queue
>>>for the new cuckoo hash implementation.
>>> 
>>>However, compared to the previous implementation
>>>based on ring, this version
>>>suffers a serious performance degradation. The
>>>evaluation is

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

2015-12-17 Thread 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.

Maxim.



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

But isn't the use case here SW centric?

Perhaps there's opportunity here for a new Queue type
that would permit an implementation to implement the
queue API as a ring for additional performance?

I think it is a bad idea to overload the ODP queue with
another type of usage and implied implementation. Better to
define a new ODP object.

What are the real requirements of the "ring" as used by the
cuckoo hash design? Enqueue/dequeue operations. Fixed size
is OK? Storing arbitrary objects (not just ODP events)?

The real requirement is use the ring as a sort of container.
Fixed Size is OK. And the ring should be used to
store any ODP events, since it is used as a container,
like vector in C++ STL.

What if I would like to store objects that are not ODP events in
the cuckoo hash table? E.g. arbitrary pointers (to memory that
is managed in some other way).


Yes, that is currently ring’s implementation.





  The scheduler itself could use this since its use of
queues is subject to the same issues.

On Mon, Dec 7, 2015 at 11:39 PM,
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 current
ODP implementation, I found that
the ODP queue is implemented more likely a facility
for transmitting objects, not
a container to store objects. Look at the ODP queue
enqueue interface:

int odp_queue_enq(odp_queue_t queue,
odp_event_t ev);

the *odp_event_t* is related to the events, but I
only want to use odp_queue to
storing and retrieving objects, any objects.


So I use ODP buffer/pool interfaces instead
of ODP queue
for the new cuckoo hash implementation.

However, compared to the previous implementation
based on ring, this version
suffers a serious performance degradation. The
evaluation is carried out on a Intel
servers. I test lookup time for 1000 lookups on a
table storing 1 million items.
The ODP buffer/pool version suffers at least a 2x
performance degradation.

This is the buffer/pool version, for 1M insert, and
1000 lookup time:

Average insert time = 2.383836, lookup time = 0.000353,

This is the ring version.

Average insert time = 1.629115, lookup time = 0.98

This performance degradation stems from the
heavy implementation of
 ODP buffer/pool. In the ring based one, all the
key is stored in a big array, and
the ring only stores the array indexes of each key.
Keys are retrieved using array indexes.
In the new one, I use ODP buffer to store the key
content. Keys are retrieved by

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

2015-12-16 Thread HePeng 
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 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 > > 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 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 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.
> 
>But isn't the use case here SW centric?
> 
>Perhaps there's opportunity here for a new Queue type
>that would permit an implementation to implement the
>queue API as a ring for additional performance?
> 
>I think it is a bad idea to overload the ODP queue with
>another type of usage and implied implementation. Better to
>define a new ODP object.
> 
>What are the real requirements of the "ring" as used by the
>cuckoo hash design? Enqueue/dequeue operations. Fixed size
>is OK? Storing arbitrary objects (not just ODP events)?
 
The real requirement is use the ring as a sort of container.
Fixed Size is OK. And the ring should be used to
store any ODP events, since it is used as a container,
like vector in C++ STL.
 
What if I would like to store objects that are not ODP events in
the cuckoo hash table? E.g. arbitrary pointers (to memory that
is managed in some other way).
 
>>>Yes, that is currently ring’s implementation.
>>> 
>>> 
 
 
> 
>  The scheduler itself could use this since its use of
>queues is subject to the same issues.
> 
>On Mon, Dec 7, 2015 at 11:39 PM,
>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 current
>ODP implementation, I found that
>the ODP queue is implemented more likely a facility
>for transmitting objects, not
>a container to store objects. Look at the ODP queue
>enqueue interface:
> 
>int odp_queue_enq(odp_queue_t queue,
>odp_event_t ev);
> 
>the *odp_event_t* is related to the events, but I
>only want to use odp_queue to
>storing and retrieving objects, any objects.
> 
> 
>So I use ODP buffer/pool interfaces instead
>of ODP queue
>for the new cuckoo hash implementation.
> 
>However, compared to the previous implementation
>based on ring, this version
>suffers a serious performance degradation. The
>evaluation is carried out on a Intel
>servers. I test lookup time for 1000 lookups on a
>table storing 1 million items.
>The ODP buffer/pool version suffers at least a 2x
>performance degradation.
> 
>This is the buffer/pool version, for 1M insert, and
>1000 lookup time:
> 
>Average insert time = 2.383836, lookup time = 0.000353,
> 
>This is the ring version.
> 
>Average insert time = 1.629115, lookup time = 0.98
> 
>

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

2015-12-16 Thread Maxim Uvarov 
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 > 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 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 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.

But isn't the use case here SW centric?

Perhaps there's opportunity here for a new Queue type
that would permit an implementation to implement the
queue API as a ring for additional performance?

I think it is a bad idea to overload the ODP queue with
another type of usage and implied implementation. Better to
define a new ODP object.

What are the real requirements of the "ring" as used by the
cuckoo hash design? Enqueue/dequeue operations. Fixed size
is OK? Storing arbitrary objects (not just ODP events)?


The real requirement is use the ring as a sort of container.
Fixed Size is OK. And the ring should be used to
store any ODP events, since it is used as a container,
like vector in C++ STL.

What if I would like to store objects that are not ODP events in
the cuckoo hash table? E.g. arbitrary pointers (to memory that
is managed in some other way).


Yes, that is currently ring’s implementation.







  The scheduler itself could use this since its use of
queues is subject to the same issues.

On Mon, Dec 7, 2015 at 11:39 PM,
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 current
ODP implementation, I found that
the ODP queue is implemented more likely a facility
for transmitting objects, not
a container to store objects. Look at the ODP queue
enqueue interface:

int odp_queue_enq(odp_queue_t queue,
odp_event_t ev);

the *odp_event_t* is related to the events, but I
only want to use odp_queue to
storing and retrieving objects, any objects.


So I use ODP buffer/pool interfaces instead
of ODP queue
for the new cuckoo hash implementation.

However, compared to the previous implementation
based on ring, this version
suffers a serious performance degradation. The
evaluation is carried out on a Intel
servers. I test lookup time for 1000 lookups on a
table storing 1 million items.
The ODP buffer/pool version suffers at least a 2x
performance degradation.

This is the buffer/pool version, for 1M insert, and
1000 lookup time:

Average insert time = 2.383836, lookup time = 0.000353,

This is the ring version.

Average insert time = 1.629115, lookup time = 0.98

This performance degradation stems from the
heavy implementation of
 ODP buffer/pool. In the ring based one, all the
key is stored in a big array, and
the ring only stores the array indexes of each key.
Keys are retrieved using array indexes.
In the new one, I use ODP buffer to store the key
content. Keys are retrieved by
dereferencing a *odp_buffer_t* handle.

With this high performance degradation, I
suggest moving ring into the odp/api
as a container implementation, and use the previous
implementation of cuckoo

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

2015-12-14 Thread Mike Holmes 
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 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
>>> 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.
>>>
>> But isn't the use case here SW centric?
>>
>>
>>> Perhaps there's opportunity here for a new Queue type that would permit
>>> an implementation to implement the queue API as a ring for additional
>>> performance?
>>>
>> I think it is a bad idea to overload the ODP queue with another type of
>> usage and implied implementation. Better to define a new ODP object.
>>
>> What are the real requirements of the "ring" as used by the cuckoo hash
>> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary
>> objects (not just ODP events)?
>>
>>
>> The real requirement is use the ring as a sort of container.
>> Fixed Size is OK. And the ring should be used to
>> store any ODP events, since it is used as a container,
>> like vector in C++ STL.
>>
> What if I would like to store objects that are not ODP events in the
> cuckoo hash table? E.g. arbitrary pointers (to memory that is managed in
> some other way).
>
> Yes, that is currently ring’s implementation.
>
>
>
>>
>>
>>
>>
>>>   The scheduler itself could use this since its use of queues is subject
>>> to the same issues.
>>>
>>> On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP implementation, I
 found that
 the ODP queue is implemented more likely a facility for transmitting
 objects, not
 a container to store objects. Look at the ODP queue enqueue interface:

 int odp_queue_enq(odp_queue_t queue, odp_event_t ev);

 the *odp_event_t* is related to the events, but I only want to use
 odp_queue to
 storing and retrieving objects, any objects.


 So I use ODP buffer/pool interfaces instead of ODP queue
 for the new cuckoo hash implementation.

 However, compared to the previous implementation based on ring,
 this version
 suffers a serious performance degradation. The evaluation is carried
 out on a Intel
 servers. I test lookup time for 1000 lookups on a table storing 1
 million items.
 The ODP buffer/pool version suffers at least a 2x performance
 degradation.

 This is the buffer/pool version, for 1M insert, and 1000 lookup time:

 Average insert time = 2.383836, lookup time = 0.000353,

 This is the ring version.

 Average insert time = 1.629115, lookup time = 0.98

 This performance degradation stems from the heavy
 implementation of
  ODP buffer/pool. In the ring based one, all the key is stored in a big
 array, and
 the ring only stores the array indexes of each key. Keys are retrieved
 using array indexes.
 In the new one, I use ODP buffer to store the key content. Keys are
 retrieved by
 dereferencing a *odp_buffer_t*  handle.

 With this high performance degradation, I suggest moving ring
 into the odp/api
 as a container implementation, and use the previous implementation of
 cuckoo hash.






 ___
 lng-odp mailing list
 lng-odp@lists.linaro.org
 https://lists.linaro.org/mailman/listinfo/lng-odp

>>>
>>>
>>> ___
>>> lng-odp mailing list
>>> lng-odp@lists.linaro.org
>>> https://lists.linaro.org/mailman/listinfo/lng-odp
>>>
>>>
>>
>>
>
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/lng-odp
>
>
>
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/lng-odp
>
>


-- 
Mike Holmes
Technical Manager - Linaro Networking Group
Linaro.org  *│ *Open source software for ARM SoCs
___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-12 Thread HePeng 
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 > > 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 
>>> 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.
>>> But isn't the use case here SW centric?
>>>  
>>> Perhaps there's opportunity here for a new Queue type that would permit an 
>>> implementation to implement the queue API as a ring for additional 
>>> performance?
>>> I think it is a bad idea to overload the ODP queue with another type of 
>>> usage and implied implementation. Better to define a new ODP object.
>>> 
>>> What are the real requirements of the "ring" as used by the cuckoo hash 
>>> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
>>> objects (not just ODP events)?
>> 
>> The real requirement is use the ring as a sort of container. 
>> Fixed Size is OK. And the ring should be used to 
>> store any ODP events, since it is used as a container, 
>> like vector in C++ STL. 
>> What if I would like to store objects that are not ODP events in the cuckoo 
>> hash table? E.g. arbitrary pointers (to memory that is managed in some other 
>> way).
>> 
>   Yes, that is currently ring’s implementation. 
> 
> 
>> 
>> 
>>> 
>>>  
>>>   The scheduler itself could use this since its use of queues is subject to 
>>> the same issues.
>>> 
>>> On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP implementation, I 
>>> found that
>>> the ODP queue is implemented more likely a facility for transmitting 
>>> objects, not
>>> a container to store objects. Look at the ODP queue enqueue interface:
>>> 
>>> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>>> 
>>> the *odp_event_t* is related to the events, but I only want to use 
>>> odp_queue to
>>> storing and retrieving objects, any objects.
>>> 
>>> 
>>> So I use ODP buffer/pool interfaces instead of ODP queue
>>> for the new cuckoo hash implementation.
>>> 
>>> However, compared to the previous implementation based on ring, 
>>> this version
>>> suffers a serious performance degradation. The evaluation is carried out on 
>>> a Intel
>>> servers. I test lookup time for 1000 lookups on a table storing 1 million 
>>> items.
>>> The ODP buffer/pool version suffers at least a 2x performance degradation.
>>> 
>>> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>>> 
>>> Average insert time = 2.383836, lookup time = 0.000353,
>>> 
>>> This is the ring version.
>>> 
>>> Average insert time = 1.629115, lookup time = 0.98
>>> 
>>> This performance degradation stems from the heavy implementation of
>>>  ODP buffer/pool. In the ring based one, all the key is stored in a big 
>>> array, and
>>> the ring only stores the array indexes of each key. Keys are retrieved 
>>> using array indexes.
>>> In the new one, I use ODP buffer to store the key content. Keys are 
>>> retrieved by
>>> dereferencing a *odp_buffer_t*  handle.
>>> 
>>> With this high performance degradation, I suggest moving ring into 
>>> the odp/api
>>> as a container implementation, and use the previous implementation of 
>>> cuckoo hash.
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> ___
>>> lng-odp mailing list
>>> lng-odp@lists.linaro.org 
>>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>>> 
>>> 
>>> 
>>> ___
>>> lng-odp mailing list
>>> lng-odp@lists.linaro.org 
>>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>>> 
>>> 
>>> 
>> 
>> 
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org 
> https://lists.linaro.org/mailman/listinfo/lng-odp 
> 
___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-09 Thread 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 size), a hash 
table needs to

calculate the hash value from the key, find the right bucket, and compare
the input key with the keys stored in the bucket. If the two keys are 
equal, then

return the value of the key.

So any hash table needs to manage some memory to store the keys.
In the previous implementation, the hash table will allocate a big
array for storing every keys, and the ring is used to store the index of
all the empty array slot. If you need to insert a new key, the hash 
table will

firstly dequeue an index from the ring, and then calculate the address
of the empty slot (base_ptr + index * key_size), and memcpy the key into
the array slot.

So this is why I say the ring is used as a container, it is just used 
as a container to
store key indices. It is quite similar to ODP buffer/pool. And this is 
the reason

I use ODP buffer/pool to store all the keys in the new implementation.


Thanks that description is clear.

For now we have pool for buffers and packets. Will but we do not have 
pool for objects.
That might be fixed size objects and FIFO and LIFO type of that pool 
(Petris idea).

What do you think about it?

Maxim.




在 2015年12月9日，下午1:31，HePeng > 写道：




在 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 think the issue is that while a ring is a very useful
implementation construct its semantics are very SW centric.

But isn't the use case here SW centric?

Perhaps there's opportunity here for a new Queue type that would
permit an implementation to implement the queue API as a ring
for additional performance?

I think it is a bad idea to overload the ODP queue with another type 
of usage and implied implementation. Better to define a new ODP object.


What are the real requirements of the "ring" as used by the cuckoo 
hash design? Enqueue/dequeue operations. Fixed size is OK? Storing 
arbitrary objects (not just ODP events)?


The real requirement is use the ring as a sort of container.
Fixed Size is OK. And the ring should be used to
store any ODP events, since it is used as a container,
like vector in C++ STL.




  The scheduler itself could use this since its use of queues is
subject to the same issues.

On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP
implementation, I found that
the ODP queue is implemented more likely a facility for
transmitting objects, not
a container to store objects. Look at the ODP queue enqueue
interface:

int odp_queue_enq(odp_queue_t queue, odp_event_t ev);

the *odp_event_t* is related to the events, but I only want
to use odp_queue to
storing and retrieving objects, any objects.


So I use ODP buffer/pool interfaces instead of ODP queue
for the new cuckoo hash implementation.

However, compared to the previous implementation
based on ring, this version
suffers a serious performance degradation. The evaluation is
carried out on a Intel
servers. I test lookup time for 1000 lookups on a table
storing 1 million items.
The ODP buffer/pool version suffers at least a 2x
performance degradation.

This is the buffer/pool version, for 1M insert, and 1000
lookup time:

Average insert time = 2.383836, lookup time = 0.000353,

This is the ring version.

Average insert time = 1.629115, lookup time = 0.98

This performance degradation stems from the heavy
implementation of
 ODP buffer/pool. In the ring based one, all the key is
stored in a big array, and
the ring only stores the array indexes of each key. Keys are
retrieved using array indexes.
In the new one, I use ODP buffer to store the key content.
Keys are retrieved by
dereferencing a *odp_buffer_t* handle.

With this high performance degradation, I suggest
moving ring into the odp/api
as a container implementation, and use the previous
implementation of cuckoo hash.

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

2015-12-09 Thread Ola Liljedahl 
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
>> 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.
>>
> But isn't the use case here SW centric?
>
>
>> Perhaps there's opportunity here for a new Queue type that would permit
>> an implementation to implement the queue API as a ring for additional
>> performance?
>>
> I think it is a bad idea to overload the ODP queue with another type of
> usage and implied implementation. Better to define a new ODP object.
>
> What are the real requirements of the "ring" as used by the cuckoo hash
> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary
> objects (not just ODP events)?
>
>
> The real requirement is use the ring as a sort of container.
> Fixed Size is OK. And the ring should be used to
> store any ODP events, since it is used as a container,
> like vector in C++ STL.
>
What if I would like to store objects that are not ODP events in the cuckoo
hash table? E.g. arbitrary pointers (to memory that is managed in some
other way).


>
>
>
>
>>   The scheduler itself could use this since its use of queues is subject
>> to the same issues.
>>
>> On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP implementation, I
>>> found that
>>> the ODP queue is implemented more likely a facility for transmitting
>>> objects, not
>>> a container to store objects. Look at the ODP queue enqueue interface:
>>>
>>> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>>>
>>> the *odp_event_t* is related to the events, but I only want to use
>>> odp_queue to
>>> storing and retrieving objects, any objects.
>>>
>>>
>>> So I use ODP buffer/pool interfaces instead of ODP queue
>>> for the new cuckoo hash implementation.
>>>
>>> However, compared to the previous implementation based on ring,
>>> this version
>>> suffers a serious performance degradation. The evaluation is carried out
>>> on a Intel
>>> servers. I test lookup time for 1000 lookups on a table storing 1
>>> million items.
>>> The ODP buffer/pool version suffers at least a 2x performance
>>> degradation.
>>>
>>> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>>>
>>> Average insert time = 2.383836, lookup time = 0.000353,
>>>
>>> This is the ring version.
>>>
>>> Average insert time = 1.629115, lookup time = 0.98
>>>
>>> This performance degradation stems from the heavy implementation
>>> of
>>>  ODP buffer/pool. In the ring based one, all the key is stored in a big
>>> array, and
>>> the ring only stores the array indexes of each key. Keys are retrieved
>>> using array indexes.
>>> In the new one, I use ODP buffer to store the key content. Keys are
>>> retrieved by
>>> dereferencing a *odp_buffer_t*  handle.
>>>
>>> With this high performance degradation, I suggest moving ring
>>> into the odp/api
>>> as a container implementation, and use the previous implementation of
>>> cuckoo hash.
>>>
>>>
>>>
>>>
>>>
>>>
>>> ___
>>> lng-odp mailing list
>>> lng-odp@lists.linaro.org
>>> https://lists.linaro.org/mailman/listinfo/lng-odp
>>>
>>
>>
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org
>> https://lists.linaro.org/mailman/listinfo/lng-odp
>>
>>
>
>
___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-09 Thread Ola Liljedahl 
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 some size), a hash table
>> needs to
>> calculate the hash value from the key, find the right bucket, and compare
>> the input key with the keys stored in the bucket. If the two keys are
>> equal, then
>> return the value of the key.
>>
>> So any hash table needs to manage some memory to store the keys.
>> In the previous implementation, the hash table will allocate a big
>> array for storing every keys, and the ring is used to store the index of
>> all the empty array slot. If you need to insert a new key, the hash table
>> will
>> firstly dequeue an index from the ring, and then calculate the address
>> of the empty slot (base_ptr + index * key_size), and memcpy the key into
>> the array slot.
>>
>> So this is why I say the ring is used as a container, it is just used as
>> a container to
>> store key indices. It is quite similar to ODP buffer/pool. And this is
>> the reason
>> I use ODP buffer/pool to store all the keys in the new implementation.
>>
>
> Thanks that description is clear.
>
> For now we have pool for buffers and packets. Will but we do not have pool
> for objects.
> That might be fixed size objects and FIFO and LIFO type of that pool
> (Petris idea).
>
ODP queues are FIFO by definition. ODP pools have unspecified free/alloc
order, LIFO just happens to be a common characteristic (e.g. what happens
when you use a single-linked list as a free list).



> What do you think about it?
>
> Maxim.
>
>
>>
>> 在 2015年12月9日，下午1:31，HePeng > xnhp0...@icloud.com>> 写道：
>>>
>>>
 在 2015年12月8日，下午9:34，Ola Liljedahl >> ola.liljed...@linaro.org>> 写道：

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

 But isn't the use case here SW centric?

 Perhaps there's opportunity here for a new Queue type that would
 permit an implementation to implement the queue API as a ring
 for additional performance?

 I think it is a bad idea to overload the ODP queue with another type of
 usage and implied implementation. Better to define a new ODP object.

 What are the real requirements of the "ring" as used by the cuckoo hash
 design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary
 objects (not just ODP events)?

>>>
>>> The real requirement is use the ring as a sort of container.
>>> Fixed Size is OK. And the ring should be used to
>>> store any ODP events, since it is used as a container,
>>> like vector in C++ STL.
>>>
>>>
>>>
   The scheduler itself could use this since its use of queues is
 subject to the same issues.

 On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP
 implementation, I found that
 the ODP queue is implemented more likely a facility for
 transmitting objects, not
 a container to store objects. Look at the ODP queue enqueue
 interface:

 int odp_queue_enq(odp_queue_t queue, odp_event_t ev);

 the *odp_event_t* is related to the events, but I only want
 to use odp_queue to
 storing and retrieving objects, any objects.


 So I use ODP buffer/pool interfaces instead of ODP queue
 for the new cuckoo hash implementation.

 However, compared to the previous implementation
 based on ring, this version
 suffers a serious performance degradation. The evaluation is
 carried out on a Intel
 servers. I test lookup time for 1000 lookups on a table
 storing 1 million items.
 The ODP buffer/pool version suffers at least a 2x
 performance degradation.

 This is the buffer/pool version, for 1M insert, and 1000
 lookup time:

 Average insert time = 2.383836, lookup time = 0.000353,

 This is the ring version.

 Average insert

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

2015-12-09 Thread HePeng 


> 在 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 size), a hash table 
>> needs to
>> calculate the hash value from the key, find the right bucket, and compare
>> the input key with the keys stored in the bucket. If the two keys are equal, 
>> then
>> return the value of the key.
>> 
>> So any hash table needs to manage some memory to store the keys.
>> In the previous implementation, the hash table will allocate a big
>> array for storing every keys, and the ring is used to store the index of
>> all the empty array slot. If you need to insert a new key, the hash table 
>> will
>> firstly dequeue an index from the ring, and then calculate the address
>> of the empty slot (base_ptr + index * key_size), and memcpy the key into
>> the array slot.
>> 
>> So this is why I say the ring is used as a container, it is just used as a 
>> container to
>> store key indices. It is quite similar to ODP buffer/pool. And this is the 
>> reason
>> I use ODP buffer/pool to store all the keys in the new implementation.
> 
> Thanks that description is clear.
> 
> For now we have pool for buffers and packets. Will but we do not have pool 
> for objects.
> That might be fixed size objects and FIFO and LIFO type of that pool (Petris 
> idea).
> What do you think about it?

I think it is a good idea to have this data structure as a facility in ODP. 
We can use the ring code for the implementation. 


> 
> Maxim.
> 
>> 
>> 
>>> 在 2015年12月9日，下午1:31，HePeng >> > 写道：
>>> 
 
 在 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 think the issue is that while a ring is a very useful
implementation construct its semantics are very SW centric.
 
 But isn't the use case here SW centric?
 
Perhaps there's opportunity here for a new Queue type that would
permit an implementation to implement the queue API as a ring
for additional performance?
 
 I think it is a bad idea to overload the ODP queue with another type of 
 usage and implied implementation. Better to define a new ODP object.
 
 What are the real requirements of the "ring" as used by the cuckoo hash 
 design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
 objects (not just ODP events)?
>>> 
>>> The real requirement is use the ring as a sort of container.
>>> Fixed Size is OK. And the ring should be used to
>>> store any ODP events, since it is used as a container,
>>> like vector in C++ STL.
>>> 
>>> 
 
  The scheduler itself could use this since its use of queues is
subject to the same issues.
 
On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP
implementation, I found that
the ODP queue is implemented more likely a facility for
transmitting objects, not
a container to store objects. Look at the ODP queue enqueue
interface:
 
int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
 
the *odp_event_t* is related to the events, but I only want
to use odp_queue to
storing and retrieving objects, any objects.
 
 
So I use ODP buffer/pool interfaces instead of ODP queue
for the new cuckoo hash implementation.
 
However, compared to the previous implementation
based on ring, this version
suffers a serious performance degradation. The evaluation is
carried out on a Intel
servers. I test lookup time for 1000 lookups on a table
storing 1 million items.
The ODP buffer/pool version suffers at least a 2x
performance degradation.
 
This is the buffer/pool version, for 1M insert, and 1000
lookup time:
 
Average insert time = 2.383836, lookup time = 0.000353,
 
This is the ring version.
 
Average insert time = 1.629115, lookup time = 0.98

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

2015-12-09 Thread HePeng 

> 在 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 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 centric.
>> But isn't the use case here SW centric?
>>  
>> Perhaps there's opportunity here for a new Queue type that would permit an 
>> implementation to implement the queue API as a ring for additional 
>> performance?
>> I think it is a bad idea to overload the ODP queue with another type of 
>> usage and implied implementation. Better to define a new ODP object.
>> 
>> What are the real requirements of the "ring" as used by the cuckoo hash 
>> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
>> objects (not just ODP events)?
> 
> The real requirement is use the ring as a sort of container. 
> Fixed Size is OK. And the ring should be used to 
> store any ODP events, since it is used as a container, 
> like vector in C++ STL. 
> What if I would like to store objects that are not ODP events in the cuckoo 
> hash table? E.g. arbitrary pointers (to memory that is managed in some other 
> way).
> 
Yes, that is currently ring’s implementation. 


> 
> 
>> 
>>  
>>   The scheduler itself could use this since its use of queues is subject to 
>> the same issues.
>> 
>> On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP implementation, I 
>> found that
>> the ODP queue is implemented more likely a facility for transmitting 
>> objects, not
>> a container to store objects. Look at the ODP queue enqueue interface:
>> 
>> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>> 
>> the *odp_event_t* is related to the events, but I only want to use odp_queue 
>> to
>> storing and retrieving objects, any objects.
>> 
>> 
>> So I use ODP buffer/pool interfaces instead of ODP queue
>> for the new cuckoo hash implementation.
>> 
>> However, compared to the previous implementation based on ring, this 
>> version
>> suffers a serious performance degradation. The evaluation is carried out on 
>> a Intel
>> servers. I test lookup time for 1000 lookups on a table storing 1 million 
>> items.
>> The ODP buffer/pool version suffers at least a 2x performance degradation.
>> 
>> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>> 
>> Average insert time = 2.383836, lookup time = 0.000353,
>> 
>> This is the ring version.
>> 
>> Average insert time = 1.629115, lookup time = 0.98
>> 
>> This performance degradation stems from the heavy implementation of
>>  ODP buffer/pool. In the ring based one, all the key is stored in a big 
>> array, and
>> the ring only stores the array indexes of each key. Keys are retrieved using 
>> array indexes.
>> In the new one, I use ODP buffer to store the key content. Keys are 
>> retrieved by
>> dereferencing a *odp_buffer_t*  handle.
>> 
>> With this high performance degradation, I suggest moving ring into 
>> the odp/api
>> as a container implementation, and use the previous implementation of cuckoo 
>> hash.
>> 
>> 
>> 
>> 
>> 
>> 
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org 
>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>> 
>> 
>> 
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org 
>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>> 
>> 
>> 
> 
> 

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-08 Thread Maxim Uvarov 
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 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 
implementation to implement the queue API as a ring for additional 
performance?  The scheduler itself could use this since its use of 
queues is subject to the same issues.


On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP
implementation, I found that
the ODP queue is implemented more likely a facility for
transmitting objects, not
a container to store objects. Look at the ODP queue enqueue interface:

int odp_queue_enq(odp_queue_t queue, odp_event_t ev);

the *odp_event_t* is related to the events, but I only want to use
odp_queue to
storing and retrieving objects, any objects.


So I use ODP buffer/pool interfaces instead of ODP queue
for the new cuckoo hash implementation.

However, compared to the previous implementation based on
ring, this version
suffers a serious performance degradation. The evaluation is
carried out on a Intel
servers. I test lookup time for 1000 lookups on a table storing 1
million items.
The ODP buffer/pool version suffers at least a 2x performance
degradation.

This is the buffer/pool version, for 1M insert, and 1000 lookup time:

Average insert time = 2.383836, lookup time = 0.000353,

This is the ring version.

Average insert time = 1.629115, lookup time = 0.98

This performance degradation stems from the heavy
implementation of
 ODP buffer/pool. In the ring based one, all the key is stored in
a big array, and
the ring only stores the array indexes of each key. Keys are
retrieved using array indexes.
In the new one, I use ODP buffer to store the key content. Keys
are retrieved by
dereferencing a *odp_buffer_t*  handle.

With this high performance degradation, I suggest moving
ring into the odp/api
as a container implementation, and use the previous implementation
of cuckoo hash.






___
lng-odp mailing list
lng-odp@lists.linaro.org 
https://lists.linaro.org/mailman/listinfo/lng-odp




___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-08 Thread Bill Fischofer 
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 implementation to implement
the queue API as a ring for additional performance?  The scheduler itself
could use this since its use of queues is subject to the same issues.

On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP implementation, I
> found that
> the ODP queue is implemented more likely a facility for transmitting
> objects, not
> a container to store objects. Look at the ODP queue enqueue interface:
>
> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>
> the *odp_event_t* is related to the events, but I only want to use
> odp_queue to
> storing and retrieving objects, any objects.
>
>
> So I use ODP buffer/pool interfaces instead of ODP queue
> for the new cuckoo hash implementation.
>
> However, compared to the previous implementation based on ring,
> this version
> suffers a serious performance degradation. The evaluation is carried out
> on a Intel
> servers. I test lookup time for 1000 lookups on a table storing 1 million
> items.
> The ODP buffer/pool version suffers at least a 2x performance degradation.
>
> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>
> Average insert time = 2.383836, lookup time = 0.000353,
>
> This is the ring version.
>
> Average insert time = 1.629115, lookup time = 0.98
>
> This performance degradation stems from the heavy implementation of
>  ODP buffer/pool. In the ring based one, all the key is stored in a big
> array, and
> the ring only stores the array indexes of each key. Keys are retrieved
> using array indexes.
> In the new one, I use ODP buffer to store the key content. Keys are
> retrieved by
> dereferencing a *odp_buffer_t*  handle.
>
> With this high performance degradation, I suggest moving ring into
> the odp/api
> as a container implementation, and use the previous implementation of
> cuckoo hash.
>
>
>
>
>
>
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/lng-odp
>
___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-08 Thread Ola Liljedahl 
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 current ODP implementation, I
> found that
> the ODP queue is implemented more likely a facility for transmitting
> objects, not
>
ODP queues are for storing ODP events and passing them from producer to
consumer (which may be SW threads and also HW blocks).


> a container to store objects. Look at the ODP queue enqueue interface:
>
> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>
> the *odp_event_t* is related to the events, but I only want to use
> odp_queue to
> storing and retrieving objects, any objects.
>
Using ODP HW abstractions (e.g. ODP queues, ODP pools) doesn't seem optimal
for storing any type of SW objects.


>
>
> So I use ODP buffer/pool interfaces instead of ODP queue
> for the new cuckoo hash implementation.
>
> However, compared to the previous implementation based on ring,
> this version
> suffers a serious performance degradation. The evaluation is carried out
> on a Intel
> servers. I test lookup time for 1000 lookups on a table storing 1 million
> items.
> The ODP buffer/pool version suffers at least a 2x performance degradation.
>
Which ODP implementation are you using? ODP/DPDK or linux-generic?


> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>
> Average insert time = 2.383836, lookup time = 0.000353,
>
> This is the ring version.
>
> Average insert time = 1.629115, lookup time = 0.98
>
> This performance degradation stems from the heavy implementation of
>  ODP buffer/pool. In the ring based one, all the key is stored in a big
> array, and
> the ring only stores the array indexes of each key. Keys are retrieved
> using array indexes.
> In the new one, I use ODP buffer to store the key content. Keys are
> retrieved by
> dereferencing a *odp_buffer_t*  handle.
>
> With this high performance degradation, I suggest moving ring into
> the odp/api
> as a container implementation, and use the previous implementation of
> cuckoo hash.
>
Is the ODP (I think the heritage goes back to BSD) ring optimal for this?


>
>
>
>
>
>
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/lng-odp
>
___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-08 Thread 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 think the issue is that while a ring is a very useful implementation
> construct its semantics are very SW centric.
>
But isn't the use case here SW centric?


> Perhaps there's opportunity here for a new Queue type that would permit an
> implementation to implement the queue API as a ring for additional
> performance?
>
I think it is a bad idea to overload the ODP queue with another type of
usage and implied implementation. Better to define a new ODP object.

What are the real requirements of the "ring" as used by the cuckoo hash
design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary
objects (not just ODP events)?



>   The scheduler itself could use this since its use of queues is subject
> to the same issues.
>
> On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP implementation, I
>> found that
>> the ODP queue is implemented more likely a facility for transmitting
>> objects, not
>> a container to store objects. Look at the ODP queue enqueue interface:
>>
>> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>>
>> the *odp_event_t* is related to the events, but I only want to use
>> odp_queue to
>> storing and retrieving objects, any objects.
>>
>>
>> So I use ODP buffer/pool interfaces instead of ODP queue
>> for the new cuckoo hash implementation.
>>
>> However, compared to the previous implementation based on ring,
>> this version
>> suffers a serious performance degradation. The evaluation is carried out
>> on a Intel
>> servers. I test lookup time for 1000 lookups on a table storing 1 million
>> items.
>> The ODP buffer/pool version suffers at least a 2x performance degradation.
>>
>> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>>
>> Average insert time = 2.383836, lookup time = 0.000353,
>>
>> This is the ring version.
>>
>> Average insert time = 1.629115, lookup time = 0.98
>>
>> This performance degradation stems from the heavy implementation
>> of
>>  ODP buffer/pool. In the ring based one, all the key is stored in a big
>> array, and
>> the ring only stores the array indexes of each key. Keys are retrieved
>> using array indexes.
>> In the new one, I use ODP buffer to store the key content. Keys are
>> retrieved by
>> dereferencing a *odp_buffer_t*  handle.
>>
>> With this high performance degradation, I suggest moving ring
>> into the odp/api
>> as a container implementation, and use the previous implementation of
>> cuckoo hash.
>>
>>
>>
>>
>>
>>
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org
>> https://lists.linaro.org/mailman/listinfo/lng-odp
>>
>
>
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/lng-odp
>
>
___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-08 Thread HePeng 

> 在 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 think the issue is that while a ring is a very useful implementation 
> construct its semantics are very SW centric.
> But isn't the use case here SW centric?
>  
> Perhaps there's opportunity here for a new Queue type that would permit an 
> implementation to implement the queue API as a ring for additional 
> performance?
> I think it is a bad idea to overload the ODP queue with another type of usage 
> and implied implementation. Better to define a new ODP object.
> 
> What are the real requirements of the "ring" as used by the cuckoo hash 
> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
> objects (not just ODP events)?

The real requirement is use the ring as a sort of container. 
Fixed Size is OK. And the ring should be used to 
store any ODP events, since it is used as a container, 
like vector in C++ STL. 


> 
>  
>   The scheduler itself could use this since its use of queues is subject to 
> the same issues.
> 
> On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP implementation, I found 
> that
> the ODP queue is implemented more likely a facility for transmitting objects, 
> not
> a container to store objects. Look at the ODP queue enqueue interface:
> 
> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
> 
> the *odp_event_t* is related to the events, but I only want to use odp_queue 
> to
> storing and retrieving objects, any objects.
> 
> 
> So I use ODP buffer/pool interfaces instead of ODP queue
> for the new cuckoo hash implementation.
> 
> However, compared to the previous implementation based on ring, this 
> version
> suffers a serious performance degradation. The evaluation is carried out on a 
> Intel
> servers. I test lookup time for 1000 lookups on a table storing 1 million 
> items.
> The ODP buffer/pool version suffers at least a 2x performance degradation.
> 
> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
> 
> Average insert time = 2.383836, lookup time = 0.000353,
> 
> This is the ring version.
> 
> Average insert time = 1.629115, lookup time = 0.98
> 
> This performance degradation stems from the heavy implementation of
>  ODP buffer/pool. In the ring based one, all the key is stored in a big 
> array, and
> the ring only stores the array indexes of each key. Keys are retrieved using 
> array indexes.
> In the new one, I use ODP buffer to store the key content. Keys are retrieved 
> by
> dereferencing a *odp_buffer_t*  handle.
> 
> With this high performance degradation, I suggest moving ring into 
> the odp/api
> as a container implementation, and use the previous implementation of cuckoo 
> hash.
> 
> 
> 
> 
> 
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org 
> https://lists.linaro.org/mailman/listinfo/lng-odp 
> 
> 
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org 
> https://lists.linaro.org/mailman/listinfo/lng-odp 
> 
> 
> 

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-08 Thread HePeng 
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 the keys stored in the bucket. If the two keys are equal, 
then 
return the value of the key. 

So any hash table needs to manage some memory to store the keys. 
In the previous implementation, the hash table will allocate a big 
array for storing every keys, and the ring is used to store the index of 
all the empty array slot. If you need to insert a new key, the hash table will
firstly dequeue an index from the ring, and then calculate the address 
of the empty slot (base_ptr + index * key_size), and memcpy the key into 
the array slot. 

So this is why I say the ring is used as a container, it is just used as a 
container to 
store key indices. It is quite similar to ODP buffer/pool. And this is the 
reason 
I use ODP buffer/pool to store all the keys in the new implementation.   


> 在 2015年12月9日，下午1:31，HePeng  写道：
> 
>> 
>> 在 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 think the issue is that while a ring is a very useful implementation 
>> construct its semantics are very SW centric.
>> But isn't the use case here SW centric?
>>  
>> Perhaps there's opportunity here for a new Queue type that would permit an 
>> implementation to implement the queue API as a ring for additional 
>> performance?
>> I think it is a bad idea to overload the ODP queue with another type of 
>> usage and implied implementation. Better to define a new ODP object.
>> 
>> What are the real requirements of the "ring" as used by the cuckoo hash 
>> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
>> objects (not just ODP events)?
> 
> The real requirement is use the ring as a sort of container. 
> Fixed Size is OK. And the ring should be used to 
> store any ODP events, since it is used as a container, 
> like vector in C++ STL. 
> 
> 
>> 
>>  
>>   The scheduler itself could use this since its use of queues is subject to 
>> the same issues.
>> 
>> On Mon, Dec 7, 2015 at 11:39 PM, 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 current ODP implementation, I 
>> found that
>> the ODP queue is implemented more likely a facility for transmitting 
>> objects, not
>> a container to store objects. Look at the ODP queue enqueue interface:
>> 
>> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>> 
>> the *odp_event_t* is related to the events, but I only want to use odp_queue 
>> to
>> storing and retrieving objects, any objects.
>> 
>> 
>> So I use ODP buffer/pool interfaces instead of ODP queue
>> for the new cuckoo hash implementation.
>> 
>> However, compared to the previous implementation based on ring, this 
>> version
>> suffers a serious performance degradation. The evaluation is carried out on 
>> a Intel
>> servers. I test lookup time for 1000 lookups on a table storing 1 million 
>> items.
>> The ODP buffer/pool version suffers at least a 2x performance degradation.
>> 
>> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>> 
>> Average insert time = 2.383836, lookup time = 0.000353,
>> 
>> This is the ring version.
>> 
>> Average insert time = 1.629115, lookup time = 0.98
>> 
>> This performance degradation stems from the heavy implementation of
>>  ODP buffer/pool. In the ring based one, all the key is stored in a big 
>> array, and
>> the ring only stores the array indexes of each key. Keys are retrieved using 
>> array indexes.
>> In the new one, I use ODP buffer to store the key content. Keys are 
>> retrieved by
>> dereferencing a *odp_buffer_t*  handle.
>> 
>> With this high performance degradation, I suggest moving ring into 
>> the odp/api
>> as a container implementation, and use the previous implementation of cuckoo 
>> hash.
>> 
>> 
>> 
>> 
>> 
>> 
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org 
>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>> 
>> 
>> 
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org 
>>

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

2015-12-07 Thread HePeng 
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 more likely a facility for transmitting objects, 
not 
a container to store objects. Look at the ODP queue enqueue interface:

int odp_queue_enq(odp_queue_t queue, odp_event_t ev);

the *odp_event_t* is related to the events, but I only want to use odp_queue to 
storing and retrieving objects, any objects. 


So I use ODP buffer/pool interfaces instead of ODP queue 
for the new cuckoo hash implementation. 

However, compared to the previous implementation based on ring, this 
version 
suffers a serious performance degradation. The evaluation is carried out on a 
Intel 
servers. I test lookup time for 1000 lookups on a table storing 1 million 
items. 
The ODP buffer/pool version suffers at least a 2x performance degradation. 

This is the buffer/pool version, for 1M insert, and 1000 lookup time:

Average insert time = 2.383836, lookup time = 0.000353,

This is the ring version. 

Average insert time = 1.629115, lookup time = 0.98

This performance degradation stems from the heavy implementation of
 ODP buffer/pool. In the ring based one, all the key is stored in a big array, 
and 
the ring only stores the array indexes of each key. Keys are retrieved using 
array indexes. 
In the new one, I use ODP buffer to store the key content. Keys are retrieved 
by 
dereferencing a *odp_buffer_t*  handle. 

With this high performance degradation, I suggest moving ring into the 
odp/api 
as a container implementation, and use the previous implementation of cuckoo 
hash. 






___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-02 Thread HePeng 

> 在 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 Peng,
>>> 
>>> We need to take a look it it's possible to rewrite your hash implementation 
>>> to odp queues api instead of odp ring.
>>> That will allow to use hw queues accelerators for hash.
>>> 
>>> Maxim.
>> Hi Maxim,
>>  
>>  The ring structure in cuckoo hash is just a buffer storing the “key” 
>> address.
>> 
>>  The hash table stores all the keys. In this implementation,  it is the 
>> hash table itself which maintains the memory of all the keys.
>> When add a new key, the hash table will firstly allocate an“index” of the 
>> key using the ring, and when delete a key, the
>> hash table will recycle the “index” of the key into the ring. All in all, 
>> this ring is like a free slots buffer storing all the free indexes.
>> 
>>  In my opinion, (while I did not do this in hardware), the ring is not a 
>> critical data structure in the scenario of hash table matching,
>> because only when table update happens,  the hash table will need to use the 
>> ring. Unless you use the hash table in a write-heavy
>> scenario, and this hardware queue can help you to ease the lock contention 
>> in multi-core.
>> 
>>  So my opinion is that, 1) yes, we can use the queue to replace the 
>> ring, as long as the queue can be large enough to hold
>> all the hash entries. 2) But I do not think it is a critical optimization.
> On the latest Tuesday call we have long discussion about that.  And the final 
> agreement was that cuckoo has is needed but it needs to
> use native odp interface. I.e. use of odp_queue instead of helper odph_ring. 
> The other deal is how that odp_queue is implemented.
> If needed we can extend current implementation of odp_queue or add some 
> parameter to api. I.e. if needed we can put ring code
> inside implementation and make external interface as odp_queue.  In that case 
> platform which can work with queues in hardware
> can accelerate it as other poll queues, other platform will have it in 
> software. You might seen that interface of the ring and
> queue is about the same, i.e. it puts and gets patches to object. So it might 
> be not so hard to rewrite code to current queues api,
> but in that form odp community will be happy to accept that patch. If there 
> will be some performance degradation, than we can work
> on queues implementation and fix it.
> 
> So plan is:
> 1) have this code with queues api;
> 2) remove ring code completely from helper
> 3) move ring code inside linux-generic (I will reuse it for shm pktio ipc);
> 4) test performance of cuckoo hash
> 5) move it to odp hash API when it will be ready (to do that code should not 
> use other helper code, just native odp apis).
Glad to see this. I will begin to shape the code using odp_queue API. 



> 
> Best regards,
> Maxim.

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-12-01 Thread HePeng 

> 在 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 odp ring.
> That will allow to use hw queues accelerators for hash.
> 
> Maxim.

Hi Maxim,

The ring structure in cuckoo hash is just a buffer storing the “key” 
address. 

The hash table stores all the keys. In this implementation,  it is the 
hash table itself which maintains the memory of all the keys. 
When add a new key, the hash table will firstly allocate an“index” of the key 
using the ring, and when delete a key, the 
hash table will recycle the “index” of the key into the ring. All in all, this 
ring is like a free slots buffer storing all the free indexes. 

In my opinion, (while I did not do this in hardware), the ring is not a 
critical data structure in the scenario of hash table matching, 
because only when table update happens,  the hash table will need to use the 
ring. Unless you use the hash table in a write-heavy 
scenario, and this hardware queue can help you to ease the lock contention in 
multi-core. 

So my opinion is that, 1) yes, we can use the queue to replace the 
ring, as long as the queue can be large enough to hold 
all the hash entries. 2) But I do not think it is a critical optimization. 



___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-11-26 Thread HePeng 
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 


This implementation is a port from DPDK. I convert it into ODP conventions, 
based on ODP facilities. I think it will be nice for ODP developer to use this 
data structure for many dataplane functions. 

Thanks. 

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

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

2015-11-26 Thread Maxim Uvarov 

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 like it's needed to move ring code to main odp api.


  CC   cuckoo_hash.lo
cuckoo_hash.c:248:10: warning: Function call argument is an 
uninitialized value

while (odph_ring_sc_dequeue(r, ptr) == 0) {
   ^~~~
cuckoo_hash.c:339:9: warning: Function call argument is an uninitialized 
value

while (odph_ring_sc_dequeue(h->free_slots, ptr) == 0) {
   ^~~~

  CC   odp_cuckoo_hash.o
odp_cuckoo_hash.c:217:2: warning: Value stored to 'ret' is never read
ret = odph_cuckoo_hash_create(, _params);
^ 
odp_cuckoo_hash.c:453:2: warning: Value stored to 'ret' is never read
ret = odph_cuckoo_hash_create(, NULL);
^ ~~
odp_cuckoo_hash.c:463:2: warning: Value stored to 'ret' is never read
ret =  odph_cuckoo_hash_create(, );
^  ~
odp_cuckoo_hash.c:483:2: warning: Value stored to 'ret' is never read
ret = odph_cuckoo_hash_create(, );
^ ~
odp_cuckoo_hash.c:525:2: warning: Value stored to 'ret' is never read
ret = odph_cuckoo_hash_create(, );
^ ~~
odp_cuckoo_hash.c:543:2: warning: Value stored to 'ret' is never read
ret = odph_cuckoo_hash_create(, );
^ ~~
odp_cuckoo_hash.c:575:2: warning: Value stored to 'ret' is never read
ret = odph_cuckoo_hash_create(, _params);
^ 
odp_cuckoo_hash.c:595:19: warning: The right operand of '!=' is a 
garbage value

if (next_data != data[i]) {
  ^  ~~~
odp_cuckoo_hash.c:649:2: warning: Value stored to 'ret' is never read
ret = odph_cuckoo_hash_create(, _params);
^ 

On 11/26/2015 05:26, Peng wrote:

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 ++
  helper/ring.c   |   28 +
  helper/test/Makefile.am |4 +-
  helper/test/odp_cuckoo_hash.c   |  779 +
  include/odp/api/hash.h  |   14 +
  8 files changed, 2421 insertions(+), 1 deletion(-)
  create mode 100644 helper/cuckoo_hash.c
  create mode 100644 helper/include/odp/helper/cuckoo_hash.h
  create mode 100644 helper/test/odp_cuckoo_hash.c

diff --git a/helper/Makefile.am b/helper/Makefile.am
index e72507e..e923aa8 100644
--- a/helper/Makefile.am
+++ b/helper/Makefile.am
@@ -18,6 +18,7 @@ helperinclude_HEADERS = \
  $(srcdir)/include/odp/helper/ipsec.h\
  $(srcdir)/include/odp/helper/tcp.h\
  $(srcdir)/include/odp/helper/table.h\

alphabetic order

+ $(srcdir)/include/odp/helper/cuckoo_hash.h\
  $(srcdir)/include/odp/helper/udp.h
  
  noinst_HEADERS = \

@@ -30,6 +31,7 @@ noinst_HEADERS = \
  __LIB__libodphelper_la_SOURCES = \
linux.c \
ring.c \
+   cuckoo_hash.c \

alphabetic order here also

hashtable.c \
lineartable.c
  
diff --git a/helper/cuckoo_hash.c b/helper/cuckoo_hash.c

new file mode 100644
index 000..4a4b56b
--- /dev/null
+++ b/helper/cuckoo_hash.c
@@ -0,0 +1,1117 @@
+/* Copyright (c) 2015, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
+ *   All rights reserved.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name

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

2015-11-25 Thread HePeng 
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 +
> helper/cuckoo_hash.c| 1117 +++
> helper/include/odp/helper/cuckoo_hash.h |  435 
> helper/include/odp/helper/ring.h|   43 ++
> helper/ring.c   |   28 +
> helper/test/Makefile.am |4 +-
> helper/test/odp_cuckoo_hash.c   |  779 +
> include/odp/api/hash.h  |   16 +-
> 8 files changed, 2422 insertions(+), 2 deletions(-)
> create mode 100644 helper/cuckoo_hash.c
> create mode 100644 helper/include/odp/helper/cuckoo_hash.h
> create mode 100644 helper/test/odp_cuckoo_hash.c
> 
> diff --git a/helper/Makefile.am b/helper/Makefile.am
> index e72507e..e923aa8 100644
> --- a/helper/Makefile.am
> +++ b/helper/Makefile.am
> @@ -18,6 +18,7 @@ helperinclude_HEADERS = \
> $(srcdir)/include/odp/helper/ipsec.h\
> $(srcdir)/include/odp/helper/tcp.h\
> $(srcdir)/include/odp/helper/table.h\
> +   $(srcdir)/include/odp/helper/cuckoo_hash.h\
> $(srcdir)/include/odp/helper/udp.h
> 
> noinst_HEADERS = \
> @@ -30,6 +31,7 @@ noinst_HEADERS = \
> __LIB__libodphelper_la_SOURCES = \
>   linux.c \
>   ring.c \
> + cuckoo_hash.c \
>   hashtable.c \
>   lineartable.c
> 
> diff --git a/helper/cuckoo_hash.c b/helper/cuckoo_hash.c
> new file mode 100644
> index 000..4a4b56b
> --- /dev/null
> +++ b/helper/cuckoo_hash.c
> @@ -0,0 +1,1117 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +/*-
> + *   BSD LICENSE
> + *
> + *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
> + *   All rights reserved.
> + *
> + *   Redistribution and use in source and binary forms, with or without
> + *   modification, are permitted provided that the following conditions
> + *   are met:
> + *
> + * * Redistributions of source code must retain the above copyright
> + *   notice, this list of conditions and the following disclaimer.
> + * * Redistributions in binary form must reproduce the above copyright
> + *   notice, this list of conditions and the following disclaimer in
> + *   the documentation and/or other materials provided with the
> + *   distribution.
> + * * Neither the name of Intel Corporation nor the names of its
> + *   contributors may be used to endorse or promote products derived
> + *   from this software without specific prior written permission.
> + *
> + *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
> + *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
> + *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
> + *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
> + *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
> + *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
> + *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
> + *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
> + *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
> + *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
> + *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
> + */
> +
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include "odph_debug.h"
> +
> +/* Macro to enable/disable run-time checking of function parameters */
> +#define RETURN_IF_TRUE(cond, retval) do { \
> + if (cond) \
> + return retval; \
> +} while (0)
> +
> +/* Hash function used if none is specified */
> +#include 
> +
> +/** Number of items per bucket. */
> +#define HASH_BUCKET_ENTRIES  4
> +#define NULL_SIGNATURE   0
> +#define KEY_ALIGNMENT16
> +
> +/** Maximum size of hash table that can be created. */
> +#define HASH_ENTRIES_MAX1048576
> +
> +/** Maximum number of keys that can be
> + *  searched for using odph_hash_lookup_bulk. */
> +#define HASH_LOOKUP_BULK_MAX 64
> +#define HASH_LOOKUP_MULTI_MAXHASH_LOOKUP_BULK_MAX
> +
> +/* Structure storing both primary and secondary hashes */
> +struct cuckoo_hash_signatures {
> + union {
> + struct {
> + uint32_t current;
> +

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

2015-11-25 Thread Peng 
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 ++
 helper/ring.c   |   28 +
 helper/test/Makefile.am |4 +-
 helper/test/odp_cuckoo_hash.c   |  779 +
 include/odp/api/hash.h  |   14 +
 8 files changed, 2421 insertions(+), 1 deletion(-)
 create mode 100644 helper/cuckoo_hash.c
 create mode 100644 helper/include/odp/helper/cuckoo_hash.h
 create mode 100644 helper/test/odp_cuckoo_hash.c

diff --git a/helper/Makefile.am b/helper/Makefile.am
index e72507e..e923aa8 100644
--- a/helper/Makefile.am
+++ b/helper/Makefile.am
@@ -18,6 +18,7 @@ helperinclude_HEADERS = \
  $(srcdir)/include/odp/helper/ipsec.h\
  $(srcdir)/include/odp/helper/tcp.h\
  $(srcdir)/include/odp/helper/table.h\
+ $(srcdir)/include/odp/helper/cuckoo_hash.h\
  $(srcdir)/include/odp/helper/udp.h
 
 noinst_HEADERS = \
@@ -30,6 +31,7 @@ noinst_HEADERS = \
 __LIB__libodphelper_la_SOURCES = \
linux.c \
ring.c \
+   cuckoo_hash.c \
hashtable.c \
lineartable.c
 
diff --git a/helper/cuckoo_hash.c b/helper/cuckoo_hash.c
new file mode 100644
index 000..4a4b56b
--- /dev/null
+++ b/helper/cuckoo_hash.c
@@ -0,0 +1,1117 @@
+/* Copyright (c) 2015, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
+ *   All rights reserved.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of Intel Corporation nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include "odph_debug.h"
+
+/* Macro to enable/disable run-time checking of function parameters */
+#define RETURN_IF_TRUE(cond, retval) do { \
+   if (cond) \
+   return retval; \
+} while (0)
+
+/* Hash function used if none is specified */
+#include 
+
+/** Number of items per bucket. */
+#define HASH_BUCKET_ENTRIES4
+#define NULL_SIGNATURE 0
+#define KEY_ALIGNMENT  16
+
+/** Maximum size of hash table that can be created. */
+#define HASH_ENTRIES_MAX1048576
+
+/** Maximum number of keys that can be
+ *  searched for using odph_hash_lookup_bulk. */
+#define HASH_LOOKUP_BULK_MAX   64
+#define HASH_LOOKUP_MULTI_MAX  HASH_LOOKUP_BULK_MAX
+
+/* Structure storing both primary and secondary hashes */
+struct cuckoo_hash_signatures {
+   union {
+   struct {
+   uint32_t current;
+   uint32_t alt;
+   };
+   uint64_t sig;
+   };
+};
+
+/* Structure that stores key-value pair */
+struct cuckoo_hash_key {
+   union {
+   uintptr_t idata;
+   void *pdata;
+   };
+   /* Variable key size */
+   char key[0];
+} ODP_ALIGNED(KEY_ALIGNMENT);
+
+/** Bucket structure */
+struct cuckoo_hash_bucket {
+

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

2015-11-25 Thread Peng 
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 ++
 helper/ring.c   |   28 +
 helper/test/Makefile.am |4 +-
 helper/test/odp_cuckoo_hash.c   |  779 +
 include/odp/api/hash.h  |   16 +-
 8 files changed, 2422 insertions(+), 2 deletions(-)
 create mode 100644 helper/cuckoo_hash.c
 create mode 100644 helper/include/odp/helper/cuckoo_hash.h
 create mode 100644 helper/test/odp_cuckoo_hash.c

diff --git a/helper/Makefile.am b/helper/Makefile.am
index e72507e..e923aa8 100644
--- a/helper/Makefile.am
+++ b/helper/Makefile.am
@@ -18,6 +18,7 @@ helperinclude_HEADERS = \
  $(srcdir)/include/odp/helper/ipsec.h\
  $(srcdir)/include/odp/helper/tcp.h\
  $(srcdir)/include/odp/helper/table.h\
+ $(srcdir)/include/odp/helper/cuckoo_hash.h\
  $(srcdir)/include/odp/helper/udp.h
 
 noinst_HEADERS = \
@@ -30,6 +31,7 @@ noinst_HEADERS = \
 __LIB__libodphelper_la_SOURCES = \
linux.c \
ring.c \
+   cuckoo_hash.c \
hashtable.c \
lineartable.c
 
diff --git a/helper/cuckoo_hash.c b/helper/cuckoo_hash.c
new file mode 100644
index 000..4a4b56b
--- /dev/null
+++ b/helper/cuckoo_hash.c
@@ -0,0 +1,1117 @@
+/* Copyright (c) 2015, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
+ *   All rights reserved.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of Intel Corporation nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include "odph_debug.h"
+
+/* Macro to enable/disable run-time checking of function parameters */
+#define RETURN_IF_TRUE(cond, retval) do { \
+   if (cond) \
+   return retval; \
+} while (0)
+
+/* Hash function used if none is specified */
+#include 
+
+/** Number of items per bucket. */
+#define HASH_BUCKET_ENTRIES4
+#define NULL_SIGNATURE 0
+#define KEY_ALIGNMENT  16
+
+/** Maximum size of hash table that can be created. */
+#define HASH_ENTRIES_MAX1048576
+
+/** Maximum number of keys that can be
+ *  searched for using odph_hash_lookup_bulk. */
+#define HASH_LOOKUP_BULK_MAX   64
+#define HASH_LOOKUP_MULTI_MAX  HASH_LOOKUP_BULK_MAX
+
+/* Structure storing both primary and secondary hashes */
+struct cuckoo_hash_signatures {
+   union {
+   struct {
+   uint32_t current;
+   uint32_t alt;
+   };
+   uint64_t sig;
+   };
+};
+
+/* Structure that stores key-value pair */
+struct cuckoo_hash_key {
+   union {
+   uintptr_t idata;
+   void *pdata;
+   };
+   /* Variable key size */
+   char key[0];
+} ODP_ALIGNED(KEY_ALIGNMENT);
+
+/** Bucket structure */
+struct cuckoo_hash_bucket {
+