Re: [dpdk-dev] cuckoo hash in dpdk

[Pragash Vijayaragavan <pxv3620@rit.edu>]

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
>