Re: [dpdk-dev] [RFC] hash: introduce resizable hash list

["Wang, Yipeng1" <yipeng1.wang@intel.com>]

Hi, Bing,  I am sorry for the late reply:

>> >1.8.3.1
>>
>> [Wang, Yipeng]
>>
>> Hi, Bing,
>>
>> Table resizing is very important and I think it is a critical feature to have
>> in DPDK's hash library. Thanks a lot for putting effort on this and I hope
>> we could work out a solution based on your patch.
>>
>
>Thanks. To my understanding, yes it is very important. Especially, there is
>some case that the maximum capacity is quite large but elements could
>be just a few during one run time life cycle.
>
>> My major concern of the current implementation is as following:
>>
>> Although we still have the fbk hash table implementation, I think the
>> goal here is to have the users to move to the main hash table
>> implementation (the cuckoo algorithm), since it is the better one in
>> most use cases. There have been many optimizations done on the
>> current code base since the cuckoo hash was introduced, we do not
>> want to reinvent the wheel such as the multi-threading support, non-
>> TSO machine support, SIMD optimizations, etc. Also, comparing to
>> linked list, the current bucketized table should provide better lookup
>> performance. Last but not least, we probably don't want fragmented
>> hash table APIs.
>>
>
>Yes, I see and I agree. I have some basic study of the cuckoo and it is
>quite a nice implementation from the paper to the engineering. And a
>lot of optimizations both on X86_64 and aarch64 were done. And unique
>solution will be much easier and less problematic for the users and
>maintainers.
>
>> I would suggest to see if we could add resizing feature to the current
>> hash table implementation first.
>> For example, we can use the current bucketized design to do the
>> resizing rather than the new linked list-based data structure.
>> We do need some modifications such as having a local  bucket_shift
>> variable each bucket, but I think it is feasible. We could also turn off
>> the cuckoo path/extendable linked list of the current implementation
>> when resizing is needed, so that it would be simpler for the
>> implementation.
>> In such way, we keep the current API and also reuse many of the
>> existing code.
>>
>
>That will be quite great if the resize with cuckoo hash could be realized.
>I am not quite familiar with the current status of the researching. Is there
>any paper or ideas these years for the cuckoo hash algorithm already?
>
[Wang, Yipeng] 
I am not aware of new papers focusing on hash table resizing, but I encountered
one resizing algorithm from this paper: "Elastic Sketch: Adaptive and Fast Network-wide
Measurements". If you look at section 3.4, the authors first duplicates the hash table
and gradually remove the duplicates. But I think the duplication would still be too costly.

I guess what I suggested is to disable cuckoo path while we resize. Just treat
it as a regular hash table, then the resizing would be similar to your linked list algorithm right?
You just redistribute the contents in the buckets rather than breaking down the linked list.

>> Also, I wonder if you have a specific use case that benefit from the
>> gradually break-down approach? Since we could always stop the world
>> and resize the table at once.
>
>Do you mean the on-demand (when being accessed) split? Theoretically,
>no for the total time, or even more because of the calculation and extra
>checking. And this is only to smoothen the rate when there is already a
>lot of elements in the table, e.g. 1M. Traversing 1M elements and relocate
>them into the right position will be very time consuming. Especially the
>memory is dynamically allocated but not continuous, the cache may be
>also a problem with the linked list. I tested with a simple case and the
>rate seemed to be smooth (no big jitter) - there is also some other actions
>in the case and the hash action occupy about 15% of the CPU.
>And this is only for the list case. I think when using cuckoo hash, maybe
>there is no need of such trick 😊
[Wang, Yipeng] 
I guess I was thinking that If you have a specific use case,
we could design the algorithm with the use case in mind.

Thank you !
Yipeng