From mboxrd@z Thu Jan 1 00:00:00 1970 From: Thomas Monjalon Subject: Re: [PATCH v6 0/5] Elastic Flow Distributor Date: Tue, 17 Jan 2017 21:29:44 +0100 Message-ID: <2025228.QPsT3Dr00a@xps13> 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-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Cc: dev@dpdk.org To: Pablo de Lara Return-path: 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 ; Tue, 17 Jan 2017 21:29:46 +0100 (CET) Received: by mail-wm0-f42.google.com with SMTP id r144so241340842wme.1 for ; Tue, 17 Jan 2017 12:29:46 -0800 (PST) In-Reply-To: <1484594519-227376-1-git-send-email-pablo.de.lara.guarch@intel.com> List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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