Re: [dpdk-dev] cuckoo hash in dpdk

[Andriy Berestovskyy <aber@semihalf.com>]

Hey Pragash,
You can pass your own hash function to rte_hash_create() otherwise a
default one will be used, see
http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_cuckoo_hash.c#n281

The default hash function is rte_hash_crc() or in some cases rte_jhash(), see
http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_cuckoo_hash.h#n61

You can find the implementation of rte_hash_crc() over here:
http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_hash_crc.h#n588



Please note there is a separate mailing list for DPDK usage discussions:
http://dpdk.org/ml/listinfo/users

The dev@ list is mostly for patch reviews and RFCs...


Andriy

On Thu, Aug 24, 2017 at 8:54 PM, Pragash Vijayaragavan <pxv3620@rit.edu> wrote:
> Thats great, what about the hash functions.
>
> On 24 Aug 2017 10:54, "Andriy Berestovskyy" <aber@semihalf.com> wrote:
>>
>> Hey Pragash,
>> I am not the author of the code, but I guess it is done that way
>> because modern compilers do recognize power of two constants and do
>> substitute division and modulo operations with corresponding bit
>> manipulations.
>>
>> Just try to compile a small program like the following:
>>
>> volatile unsigned a = 123, b, c;
>> int main(int argc, char **argv)
>> {
>>     b = a / 4;
>>     c = a % 4;
>>     printf("%x %x %x\n", a, b, c);
>> }
>>
>>
>> and then disassemble it with gdb:
>>
>> (gdb) disassemble /s main
>> [...]
>> 13 b = a / 4;
>>    0x0000000000400464 <+20>: shr    $0x2,%eax
>>    0x0000000000400467 <+23>: mov    %eax,0x200bd3(%rip)        # 0x601040
>> <b>
>>
>> 14 c = a % 4;
>>    0x000000000040046d <+29>: mov    0x200bc5(%rip),%eax        # 0x601038
>> <a>
>>    0x0000000000400473 <+35>: and    $0x3,%eax
>>    0x0000000000400476 <+38>: mov    %eax,0x200bc8(%rip)        # 0x601044
>> <c>
>> [...]
>>
>> As you can see both division and modulo was substituted with "shr" and
>> "and".
>>
>> So basically nowadays there is no need to worry about that and
>> complicate code with explicit low-level optimizations. Hope that
>> answers your question.
>>
>> Regards,
>> Andriy
>>
>>
>> On Wed, Aug 23, 2017 at 4:15 PM, Pragash Vijayaragavan <pxv3620@rit.edu>
>> wrote:
>> > Hi,
>> >
>> > I got the chance to look at the cuckoo hash used in dpdk and have a
>> > query.
>> >
>> > would using division and modulo operations be slower than bitwise
>> > operations on RTE_HASH_BUCKET_ENTRIES, specially since
>> > RTE_HASH_BUCKET_ENTRIES is a power of 2.
>> > For example, to do a modulo we can do a "AND" operation on
>> > (RTE_HASH_BUCKET_ENTRIES - 1), which might be faster. We did a cuckoo
>> > filter for VPP and doing this gave a slight improvement in speed.
>> > Is there any particular reason its done this way.
>> >
>> > Sorry if i am being wrong in any way, i was just curious.
>> >
>> > Thanks,
>> >
>> > Pragash Vijayaragavan
>> > Grad Student at Rochester Institute of Technology
>> > email : pxv3620@rit.edu
>> > ph : 585 764 4662
>>
>>
>>
>> --
>> Andriy Berestovskyy



-- 
Andriy Berestovskyy