From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx03b-out01ag.rit.edu (mx03b-out01ag.rit.edu [129.21.3.135]) by dpdk.org (Postfix) with ESMTP id ADE262B91 for ; Thu, 24 Aug 2017 20:55:03 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=rit.edu; i=@rit.edu; q=dns/txt; s=rit1608; t=1503600903; x=1535136903; h=mime-version:in-reply-to:references:date:message-id: subject:to:cc:reply-to:from; bh=0JLVpK7UwruqsdRBRnewLcLYC9zdLQpQtemR2SPuGgM=; b=qHY3v/wZ48QcQFFqPahyyHOGhVqb1VBJIcu6e4aDzYlRJ9CTCJdR18F3 Lf8VIZh6XBSUk0aciUMadnfQXL9uMQ0Tc9O58CKVBHkv7zejg1L79Cjel AMZPEyK4W4TT5NY0t2vTkwycKWx2thpbGwEdpRGvMrV0TWFQlCOZ1PnVu s=; From: Pragash Vijayaragavan X-IronPort-AV: E=Sophos;i="5.41,422,1498536000"; d="scan'208,217";a="145126970" Received: from mail-vk0-f69.google.com ([209.85.213.69]) by smtp-server.rit.edu with ESMTP/TLS/AES128-GCM-SHA256; 24 Aug 2017 14:55:00 -0400 Received: by mail-vk0-f69.google.com with SMTP id u135so202353vkd.8 for ; Thu, 24 Aug 2017 11:55:00 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:reply-to:in-reply-to:references :from:date:message-id:subject:to:cc; bh=a/hBZuBLWdfHjMQfPl+2nbteLehZSJYfMLclVzWXbsI=; b=JyumQRUIYILW/m06Nw8dHIn/0unu8/jdwRMYc0OqQ7AueVedKrqCfFNnTw/IhTjj3m BwyjnxCY1MLBz1gi/CNc4JL/VHPB34Pqcwfvocq5z1xn53tnfhHar3aOenv3PP/UvdKk m/UlqKlg7UGjisRtGDZCPx1X184EUBswE6eiJ/fJoSOBx5whdD6ZVgZE8k6ijzKwAUDp cTumeDGafPkrOAugLQ2orGUDFp6Qel+nJjvti4Iuy4bPyX54MwqgRB/lsyzoLlLw+NEe P7cppvTJDqMqZnU6GUPSCxNnEfj5An7Sbt5RfdgG8qlz/xbc9ttd1YLvNP7Lkgpj7DYc YaBA== X-Gm-Message-State: AHYfb5jEeVCemiDgbObatTkrwdGZViFmTZszESVPiIvIZWY3tFa/Zazg cuwXmcZ3PPLqpwv9U7F8V3PzE8jTsZOQjEiDp/Y1qmwtudV1deZ1QJum6C8PhVTKGFtuUHR8CCN eYvsROgC7AuLZmgWw4lk9 X-Received: by 10.176.0.99 with SMTP id 90mr2139207uai.51.1503600899435; Thu, 24 Aug 2017 11:54:59 -0700 (PDT) X-Received: by 10.176.0.99 with SMTP id 90mr2139200uai.51.1503600899215; Thu, 24 Aug 2017 11:54:59 -0700 (PDT) MIME-Version: 1.0 Received: by 10.159.53.111 with HTTP; Thu, 24 Aug 2017 11:54:58 -0700 (PDT) Received: by 10.159.53.111 with HTTP; Thu, 24 Aug 2017 11:54:58 -0700 (PDT) In-Reply-To: References: Date: Thu, 24 Aug 2017 14:54:58 -0400 Message-ID: To: Andriy Berestovskyy Cc: dev@dpdk.org, Minseok Kwon Content-Type: text/plain; charset="UTF-8" X-Content-Filtered-By: Mailman/MimeDel 2.1.15 Subject: Re: [dpdk-dev] cuckoo hash in dpdk X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: pxv3620@rit.edu List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 24 Aug 2017 18:55:04 -0000 Thats great, what about the hash functions. On 24 Aug 2017 10:54, "Andriy Berestovskyy" 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 > > > 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 >