From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <thomas.monjalon@6wind.com> Received: from mail-wm0-f42.google.com (mail-wm0-f42.google.com [74.125.82.42]) by dpdk.org (Postfix) with ESMTP id B3BF11094 for <dev@dpdk.org>; Tue, 17 Jan 2017 21:29:46 +0100 (CET) Received: by mail-wm0-f42.google.com with SMTP id r144so241340842wme.1 for <dev@dpdk.org>; Tue, 17 Jan 2017 12:29:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=6wind-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:user-agent:in-reply-to :references:mime-version:content-transfer-encoding; bh=/vLluQoqtmEEh2Zzi4SUS7O53Jb1RdFP1IVgwy0N9Kk=; b=Zcix1uApoC5fw/VNOKPcXaQxA5YXOldYI2a9avjf1Zz5oPDBM5j8Ab7jg1KnU3bBje sxIBNKdM67jYXkEb4NKKwmgVaNe4kACQFGDa8OJvA9/hAfyF47Qu2WjtfcvyaTRFgLnr NVP7wtpkq9dQyStSysr8nvwXB1UdurQdY8Xyeu+K1H0jnJFy3LM4Hg7OGBIQUl5Xbi58 67hbcPIFZE3idguykCFN9JeUMeZ2Wwo/dEI1w5t9XFnUnqXzo4iWv+qYhf6GBsS6mYkw dRXzNpW+s+H9MFE5IIUcg4hHg76n94/yg1GVGItel/Z0zZ5IQyvPJMGQ9p59Qum5FTh6 pGPg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:user-agent :in-reply-to:references:mime-version:content-transfer-encoding; bh=/vLluQoqtmEEh2Zzi4SUS7O53Jb1RdFP1IVgwy0N9Kk=; b=nH1LEkw5qIeoJ3TdFV5BzeLSU+gvNuv9cvleUYYJE4/sS4zm4uWox3D6+GIKGY++bi DE/7pI/9v7ssQdvljhLytHBv+KiBRzesOek3eSbW3WozCt7VQLB2fZ7NCiNAxi6Q4RQQ P84rjk7dARA+A7d9SGGNZbx9/N7jjgmsRRAn/P6MynhV5S8bG4eI+XpsD97JfY8zuyjD L09H9VqMbaJecUQwdfyIMGL8REKwElef+D8bn9Mch/Gak2EfoLvFh+TdIAeT4pMK4B3Q 9f52P8j1QgSqYk+OoxK7yqdxH2weCHZg7+V9gaJM25EdmpNW+2oZncRPvjXxpcXOmSZk e9cQ== X-Gm-Message-State: AIkVDXIm7bqirRz1nJxx3E75PkSNMFx8HD8SL5vFIdT8s0bmSnG8mqQhON81/TqyXQJMkhNB X-Received: by 10.28.170.213 with SMTP id t204mr16696429wme.29.1484684986330; Tue, 17 Jan 2017 12:29:46 -0800 (PST) Received: from xps13.localnet (184.203.134.77.rev.sfr.net. [77.134.203.184]) by smtp.gmail.com with ESMTPSA id m78sm39465091wmd.8.2017.01.17.12.29.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 17 Jan 2017 12:29:45 -0800 (PST) From: Thomas Monjalon <thomas.monjalon@6wind.com> To: Pablo de Lara <pablo.de.lara.guarch@intel.com> Cc: dev@dpdk.org Date: Tue, 17 Jan 2017 21:29:44 +0100 Message-ID: <2025228.QPsT3Dr00a@xps13> User-Agent: KMail/4.14.10 (Linux/4.5.4-1-ARCH; KDE/4.14.11; x86_64; ; ) In-Reply-To: <1484594519-227376-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1484559804-133610-1-git-send-email-pablo.de.lara.guarch@intel.com> <1484594519-227376-1-git-send-email-pablo.de.lara.guarch@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Subject: Re: [dpdk-dev] [PATCH v6 0/5] Elastic Flow Distributor X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions <dev.dpdk.org> List-Unsubscribe: <http://dpdk.org/ml/options/dev>, <mailto:dev-request@dpdk.org?subject=unsubscribe> List-Archive: <http://dpdk.org/ml/archives/dev/> List-Post: <mailto:dev@dpdk.org> List-Help: <mailto:dev-request@dpdk.org?subject=help> List-Subscribe: <http://dpdk.org/ml/listinfo/dev>, <mailto:dev-request@dpdk.org?subject=subscribe> X-List-Received-Date: Tue, 17 Jan 2017 20:29:46 -0000 2017-01-16 19:21, Pablo de Lara: > EFD is a distributor library that uses perfect hashing to determine a= > target/value for a given incoming flow key. It has the following adva= ntages: > first, because it uses perfect hashing it does not store the key itse= lf and > hence lookup performance is not dependent on the key size. Second, th= e > target/value can be any arbitrary value hence the system designer and= /or > operator can better optimize service rates and inter-cluster network = traffic > locating. Third, since the storage requirement is much smaller than = a > hash-based flow table (i.e. better fit for CPU cache), EFD can scale = to millions > of flow keys. Finally, with current optimized library implementation = performance > is fully scalable with number of CPU cores. >=20 > The basic idea of EFD is when a given key is to be inserted, a family= of hash > functions is searched until the correct hash function that maps the i= nput key to > the correct value is found. However, rather than explicitly storing a= ll keys and > their associated values, EFD stores only indices of hash functions th= at map keys > to values, and thereby consumes much less space than conventional fl= ow-based > tables. The lookup operation is very simple, similar to computational= -based > scheme, given an input key the lookup operation is reduced to hashing= that key > with the correct hash function. >=20 > Intuitively, finding a hash function that maps each of a large number= (millions) > of input keys to the correct output value is effectively impossible, = as a result > EFD, breaks the problem into smaller pieces (divide and conquer). EFD= divides > the entire input key set into many small groups. Each group consists = of > approximately 20-28 keys (a configurable parameter for the library), = then, for > each small group, a brute force search to find a hash function that p= roduces the > correct outputs for each key in the group. > It should be mentioned that since in the online lookup table for EFD = doesn=E2=80=99t > store the key itself, the size of the EFD table is independent of the= key size > and hence EFD lookup performance which is almost constant irrespectiv= e of the > length of the key which is a highly desirable feature especially for = longer > keys. >=20 > Library code is included in the patch, plus an sample application tha= t shows > how the library can be used. >=20 > RFC for this library was already sent: > http://dpdk.org/ml/archives/dev/2016-October/049238.html >=20 > Changes in v6: >=20 > - Separated x86 SIMD code in different file It would have been nice to make a separate patch for x86. > - Fixed shared library compilation > - Fixed figure reference in documentation > - Added missing parameter documentation Unfortunately, there is another compilation error on ARM: lib/librte_efd/rte_efd.c:39:23: fatal error: immintrin.h: No such file or directory