From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf0-f50.google.com (mail-lf0-f50.google.com [209.85.215.50]) by dpdk.org (Postfix) with ESMTP id 32BBE7CFC for ; Fri, 25 Aug 2017 11:00:21 +0200 (CEST) Received: by mail-lf0-f50.google.com with SMTP id d202so7296527lfd.5 for ; Fri, 25 Aug 2017 02:00:21 -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=EhdoFZEEPbK2x4TqeAVIPVOz3w6IV8Np5H2Ot5jAZh8=; b=z08EEjHUk4sfKDaEs54NoPY4jBY/niTEJKAA/uWit0MP4vjiq1LGf3IC2G9/iFFBEV HTq1bHplhSbVq7fAGoaUqjBWVZEjONc/Fu06ZhAOGj7S9EJgr6Z+0MWXuyScaKbOyeht dupp7YV/YIoil8tMQWBoPrWp/g26iJkA1LBQPT5uVdMEzUMRFd/wcNQuQdqfKzll+Lfx +4S0YFaCqrQSSQ1eCT+kpKYv9Ag9UYcjxJG2s3riCP8fNz9IHicHng8oiJqnLVN+0xg5 /MKUjgDUkcpFHbGx8us68kBgxN9CslHyDpGbC5OTLlTIYUkzXG1a+lXwxrAGx3D8Izy6 Zx7A== 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=EhdoFZEEPbK2x4TqeAVIPVOz3w6IV8Np5H2Ot5jAZh8=; b=Jz5bjaNYR9XxxYyBRe5zq6YPT9ikUn2Gwem/VArgUGertp2pfzeiFvHjMXaOxuQAbr u3mVyz4gJ0xwZl7mf0TOGY43NiHI77dvJOfAWQX2vRPcQrajKq3o4cCzXEPwJWf8BWbf 0RZZVKCBCTQ1URno6wCHQqkA0JA9CXslL5Ccrj5qFhhsKdT+0pWAbukL9HLqtG80lkNd zk+/Cnd1gT5CJv0smVvU0ri1ballXvJZ6t+RIYDBFDScqBY/yDFab9DZ8tvVq75J7pRI CEpvhtQ5pczfknEl/G5Wt1Xu4mhh8DE+Gljh7C/yylXklCEwGuIzML20A35U3mIV4a3m DwJw== X-Gm-Message-State: AHYfb5i4wBtDgiI6UWoMGRP+JzD3O0JeGjl1IgsfG0cV0DEuJWW9XBdR //DaxbMp10GXCso9xvAF4fUz5f74nUlM X-Received: by 10.46.4.132 with SMTP id a4mr1843342ljf.34.1503651621292; Fri, 25 Aug 2017 02:00:21 -0700 (PDT) MIME-Version: 1.0 Received: by 10.179.0.8 with HTTP; Fri, 25 Aug 2017 02:00:00 -0700 (PDT) In-Reply-To: References: From: Andriy Berestovskyy Date: Fri, 25 Aug 2017 11:00:00 +0200 Message-ID: To: pxv3620@rit.edu Cc: DPDK , users 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: Fri, 25 Aug 2017 09:00:22 -0000 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 wrote: > 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 -- Andriy Berestovskyy