From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx03a-out01ag.rit.edu (mx03a-out01ag.rit.edu [129.21.3.134]) by dpdk.org (Postfix) with ESMTP id A236E7D42 for ; Wed, 23 Aug 2017 22:39:48 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=rit.edu; i=@rit.edu; q=dns/txt; s=rit1608; t=1503520789; x=1535056789; h=mime-version:in-reply-to:references:date:message-id: subject:to:cc:reply-to:from; bh=ET5c4fHU6O7oa5pOoJwSUIOKWiE66xBJnBogBAZGFqQ=; b=vifRytN5L5MB3KICht1IYiko3qf1tMlye2H5R74aAA0w1pfSDG3uP7Pp UkbkmNrnlB0xZ7BC9L5gMW6cbFeyp/E5/UriTq1AiUG2srwW+Lo5AeXX9 Jgh/1YvtCnmP5SXTVTUljni2LAbF+eFtLazatV6Dts7zrL1xfEiZFpAkY w=; From: Pragash Vijayaragavan X-IronPort-AV: E=Sophos;i="5.41,417,1498536000"; d="scan'208,217";a="141624647" Received: from mail-ua0-f198.google.com ([209.85.217.198]) by smtp-server.rit.edu with ESMTP/TLS/AES128-GCM-SHA256; 23 Aug 2017 16:39:48 -0400 Received: by mail-ua0-f198.google.com with SMTP id t47so817098uah.7 for ; Wed, 23 Aug 2017 13:39:48 -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=/CRDIgbzWJT4IdrRm4zia5bjjr2dTV3et11TBaBUd1g=; b=U3GRmC4ZKHnTBeKnvX9OIpbSqpASgmoD/vXA5K7MIrAaK+ieDFHnCHGQnOLXfNPVUZ Z5tZZnl6ljopE73wuoet5RZen5U854+KEUz6GrDSm1FCzvlVNy6ex5nOyHXEkZJgZEXa 0RqQKdSDpiJhdXjVWiow38pg0uRPpeO9XLCySsoiAvbjCLzsggRIa2oHYMnP+M8gyYl0 WU3fzfVzNEvMWXXYayVyhctvc07gHg6W612IzA5DN0F4yOVpiPJAiMB/nChqaTyl1Ri4 zJ3BlSDJ1wGH5yj2DHWUkLdosXsYWZAOo2Q4Ts4ZpRqgI5y6/qhIJ4x+x6AU4GYpv3hu vEIQ== X-Gm-Message-State: AHYfb5igompBvnULPmwA7aeYbEFpIo8sUOw5VZW5gig0Budaa7B8UqQa spuv9bEdSSc9hGMZFNJdthmAuxi2fqM8v/Bak30X5zlITt15MJdEae7fr1I4Ulp+YXkKXuTInkl RyVYaHR9tyuRjO0p2t7vK X-Received: by 10.176.0.102 with SMTP id 93mr179845uai.51.1503520787083; Wed, 23 Aug 2017 13:39:47 -0700 (PDT) X-Received: by 10.176.0.102 with SMTP id 93mr179840uai.51.1503520786874; Wed, 23 Aug 2017 13:39:46 -0700 (PDT) MIME-Version: 1.0 Received: by 10.159.53.111 with HTTP; Wed, 23 Aug 2017 13:39:46 -0700 (PDT) In-Reply-To: References: <3EB4FA525960D640B5BDFFD6A3D891267BA9E6FA@IRSMSX108.ger.corp.intel.com> Date: Wed, 23 Aug 2017 16:39:46 -0400 Message-ID: To: "Dumitrescu, Cristian" 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: Wed, 23 Aug 2017 20:39:49 -0000 And yea, mod will take only 1 Clock cycle that way :) Also if divisor is a power of 2, a / b can be done like ( Given a is unsigned, a > b and since our hash values are greater than 0, a is our hash value, b the power of 2) while(b != 1) { a >>= 1; b >>= 1; } which is less clock cycles than normal division i guess :) Thanks, Pragash Vijayaragavan Grad Student at Rochester Institute of Technology email : pxv3620@rit.edu ph : 585 764 4662 On Wed, Aug 23, 2017 at 4:20 PM, Pragash Vijayaragavan wrote: > Hi , > > The performance will depend on the time taken for calculating the hash1 > and hash2 values for each lookup. > > Can i know which hash functions are used to calculate the hash values for > each incoming key. We use CRC32 which uses xxhash i guess. > I could not find the implementation of the hash functions. > > > Thanks, > > Pragash Vijayaragavan > Grad Student at Rochester Institute of Technology > email : pxv3620@rit.edu > ph : 585 764 4662 <(585)%20764-4662> > > > On Wed, Aug 23, 2017 at 2:28 PM, Dumitrescu, Cristian < > cristian.dumitrescu@intel.com> wrote: > >> >> >> > -----Original Message----- >> > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Pragash >> > Vijayaragavan >> > Sent: Wednesday, August 23, 2017 3:16 PM >> > To: dev@dpdk.org >> > Cc: Minseok Kwon >> > Subject: [dpdk-dev] cuckoo hash in dpdk >> > >> > 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 >> >> Bitwise AND typically takes 1 cycle on any CPU, while modulo takes dozens >> of cycles. >> > >