From: Bruce Richardson <bruce.richardson@intel.com>
To: Pablo de Lara <pablo.de.lara.guarch@intel.com>
Cc: dev@dpdk.org
Subject: Re: [PATCH 2/6] hash: replace existing hash library with cuckoo hash implementation
Date: Wed, 17 Jun 2015 16:31:35 +0100 [thread overview]
Message-ID: <20150617153135.GD8208@bricha3-MOBL3> (raw)
In-Reply-To: <1433514804-7075-3-git-send-email-pablo.de.lara.guarch@intel.com>
On Fri, Jun 05, 2015 at 03:33:20PM +0100, Pablo de Lara wrote:
> This patch replaces the existing hash library with another approach,
> using the Cuckoo Hash method to resolve collisions (open addressing),
> which pushes items from a full bucket when a new entry tries
> to be added in it, storing the evicted entry in an alternative location,
> using a secondary hash function.
>
> This gives the user the ability to store more entries when a bucket
> is full, in comparison with the previous implementation.
> Therefore, the unit test has been updated, as some scenarios have changed
> (such as the previous removed restriction).
>
> Also note that the API has not been changed, although new fields
> have been added in the rte_hash structure.
> The main change when creating a new table is that the number of entries
> per bucket is fixed now, so its parameter is ignored now
> (still there to maintain the same parameters structure).
>
> As a last note, the maximum burst size in lookup_burst function
> hash been increased to 64, to improve performance.
>
> Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
I'm getting compile errors with icc and clang with this patch. Something to
fix in your V2.
/home/bruce/dpdk.org/app/test/test_hash.c:567:2: fatal error: array index 5 is past the end of the array (which contains 5 elements) [-Warray-bounds]
expected_pos[5] = pos[5];
^ ~
/home/bruce/dpdk.org/app/test/test_hash.c:548:2: note: array 'expected_pos' declared here
int expected_pos[5];
^
1 error generated.
Further review comments to follow.
/Bruce
next prev parent reply other threads:[~2015-06-17 15:31 UTC|newest]
Thread overview: 92+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-06-05 14:33 [PATCH 0/6] Cuckoo hash Pablo de Lara
2015-06-05 14:33 ` [PATCH 1/6] eal: add const in prefetch functions Pablo de Lara
2015-06-16 15:10 ` Bruce Richardson
2015-06-05 14:33 ` [PATCH 2/6] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-17 15:31 ` Bruce Richardson [this message]
2015-06-18 9:50 ` Bruce Richardson
2015-06-05 14:33 ` [PATCH 3/6] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-05 14:33 ` [PATCH 4/6] hash: add new functions rte_hash_rehash and rte_hash_reset Pablo de Lara
2015-06-05 14:33 ` [PATCH 5/6] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-05 14:33 ` [PATCH 6/6] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-16 13:44 ` [PATCH 0/6] Cuckoo hash Thomas Monjalon
2015-06-16 21:44 ` De Lara Guarch, Pablo
2015-06-25 22:05 ` [PATCH v2 00/11] " Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 08/11] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-26 16:49 ` Stephen Hemminger
2015-06-28 22:23 ` De Lara Guarch, Pablo
2015-06-30 7:36 ` Stephen Hemminger
2015-07-10 10:39 ` Bruce Richardson
2015-06-25 22:05 ` [PATCH v2 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 11/11] doc: update hash documentation Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 00/11] Cuckoo hash Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 08/11] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 11/11] doc: update hash documentation Pablo de Lara
2015-07-08 23:23 ` [PATCH v3 00/11] Cuckoo hash Thomas Monjalon
2015-07-09 8:02 ` Bruce Richardson
2015-07-10 17:24 ` [PATCH v4 0/7] Cuckoo hash - part 3 of " Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 4/7] hash: add iterate function Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 20:52 ` [PATCH v4 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 21:57 ` [PATCH v5 " Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 4/7] hash: add iterate function Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 22:52 ` [PATCH v5 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 23:30 ` [PATCH v6 " Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 4/7] hash: add iterate function Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 7/7] doc: update hash documentation Pablo de Lara
2015-07-11 0:18 ` [PATCH v7 0/7] Cuckoo hash - part 3 of Cuckoo hash Pablo de Lara
2015-07-11 0:18 ` [PATCH v7 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-12 22:29 ` Thomas Monjalon
2015-07-13 16:11 ` Bruce Richardson
2015-07-13 16:14 ` Bruce Richardson
2015-07-13 16:20 ` Thomas Monjalon
2015-07-13 16:26 ` Bruce Richardson
2015-07-16 9:39 ` Tony Lu
2015-07-16 20:42 ` De Lara Guarch, Pablo
2015-07-17 3:34 ` Tony Lu
2015-07-17 7:34 ` De Lara Guarch, Pablo
2015-07-17 7:58 ` Tony Lu
2015-07-17 9:06 ` De Lara Guarch, Pablo
2015-07-17 14:39 ` Tony Lu
2015-07-11 0:18 ` [PATCH v7 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-12 22:16 ` Thomas Monjalon
2015-07-11 0:18 ` [PATCH v7 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-12 22:00 ` Thomas Monjalon
2015-07-11 0:18 ` [PATCH v7 4/7] hash: add iterate function Pablo de Lara
2015-07-11 0:18 ` [PATCH v7 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-11 0:18 ` [PATCH v7 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-12 22:38 ` Thomas Monjalon
2015-07-11 0:18 ` [PATCH v7 7/7] doc: update hash documentation Pablo de Lara
2015-07-12 22:46 ` [PATCH v7 0/7] Cuckoo hash - part 3 of Cuckoo hash Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20150617153135.GD8208@bricha3-MOBL3 \
--to=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=pablo.de.lara.guarch@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.