From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf0-f49.google.com (mail-lf0-f49.google.com [209.85.215.49]) by dpdk.org (Postfix) with ESMTP id D97DC7D05 for ; Thu, 24 Aug 2017 16:53:57 +0200 (CEST) Received: by mail-lf0-f49.google.com with SMTP id a9so3923090lfh.4 for ; Thu, 24 Aug 2017 07:53:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=semihalf-com.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=Yczs01yZQiIbDmGFFAOSvXJDHU9HxZgpqiHTAznaF9c=; b=JbbBeBMbtWttK8ujMjmrW8Q6iFaUkpTbs4/0mY/CfdFPZAgOagRcROpfOFJAJzKDY/ +RKnZ5osHyhn/jbV88zW8k/PvFHzWran19zjYiQRgY1JQIBVVAkl7s8kxz26ShVO23ua 0ni6AydQu7QDFHEz6ZuSq/3KJ5iKIG4J+R2CfmIMnJ3ZNqB3hW54FxpGft91MUGuB8Pb q/YXd2ZHzUs5n3Kq9PVGF5kpIxSOjiIBxWZYzpoGsTHROc5HZpyEqQFIt5lQyzMDvqnH I9RgTDlTTCJIrWwi7iBxWjQwYr8KgFn4WN94igBCjGBaeG9Ydb3qbEcpzZVRxGNdtLGQ /SCQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=Yczs01yZQiIbDmGFFAOSvXJDHU9HxZgpqiHTAznaF9c=; b=bJc9YkTPReW8qkbWlM9BjyZgJcx62Oyt+YM6HXpDk67zNX+n2tbW1ZiJvCLru1F6Oy 3Tqvbdqz8c88lm6SZZt+Hj1b0Rld7y9BaUx8IWlZibmRzzQFALeKVamzWFHpUnaJWGD8 +sOUTBkdSy1vOSDZgY+YzpQZaiwfShP9JINtjNLkKQIRgNX5qDTZOAYxdU3q0Wk0KBGw Arr2EmXI0HmXWgA49CnKWMOG8V2vlxjnYfwPqMwwmXXpg1WptZNjxjcWe9HqXHHN8j3L HCZPLWqSWB31RMGMTBvcgOxTXbobLJu9xqi8lOw6vlJ8k2vDInNRUr2tXXygZC+N8xkY G8hg== X-Gm-Message-State: AHYfb5j9bLWbiMN2dc3LesLQTe0rz2mDchXYH3+FUKhusboR4YjQSVMl YdoqNsxxW4hpX48hTLbKO12LIBC2L8z8 X-Received: by 10.46.83.2 with SMTP id h2mr2612339ljb.22.1503586437343; Thu, 24 Aug 2017 07:53:57 -0700 (PDT) MIME-Version: 1.0 Received: by 10.179.0.8 with HTTP; Thu, 24 Aug 2017 07:53:36 -0700 (PDT) In-Reply-To: References: From: Andriy Berestovskyy Date: Thu, 24 Aug 2017 16:53:36 +0200 Message-ID: To: pxv3620@rit.edu Cc: DPDK , Minseok Kwon Content-Type: text/plain; charset="UTF-8" Subject: Re: [dpdk-dev] cuckoo hash in dpdk X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 24 Aug 2017 14:53:58 -0000 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 14 c = a % 4; 0x000000000040046d <+29>: mov 0x200bc5(%rip),%eax # 0x601038 0x0000000000400473 <+35>: and $0x3,%eax 0x0000000000400476 <+38>: mov %eax,0x200bc8(%rip) # 0x601044 [...] 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 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