* [PATCH] Improve hash unit tests - Cuckoo hash part 2 @ 2015-07-08 13:12 Pablo de Lara 2015-07-08 13:12 ` [PATCH] test/hash: improve hash unit tests Pablo de Lara 2015-07-08 16:30 ` [PATCH v2] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 0 siblings, 2 replies; 13+ messages in thread From: Pablo de Lara @ 2015-07-08 13:12 UTC (permalink / raw) To: dev This patch improves the unit tests for the hash library, showing more readable results, in preparation for the new hash implementation to show performance differences. Pablo de Lara (1): test/hash: improve hash unit tests app/test/test_hash.c | 61 ++++ app/test/test_hash_perf.c | 906 +++++++++++++++++++--------------------------- 2 files changed, 439 insertions(+), 528 deletions(-) -- 2.4.2 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH] test/hash: improve hash unit tests 2015-07-08 13:12 [PATCH] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara @ 2015-07-08 13:12 ` Pablo de Lara 2015-07-08 13:39 ` Bruce Richardson 2015-07-08 15:04 ` Bruce Richardson 2015-07-08 16:30 ` [PATCH v2] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 1 sibling, 2 replies; 13+ messages in thread From: Pablo de Lara @ 2015-07-08 13:12 UTC (permalink / raw) To: dev Add new unit test for calculating the average table utilization, using random keys, based on number of entries that can be added until we encounter one that cannot be added (bucket if full) Also, replace current hash_perf unit test to see performance more clear. The current hash_perf unit test takes too long and add keys that may or may not fit in the table and look up/delete that may not be in the table. This new unit test gets a set of keys that we know that fits in the table, and then measure the time to add/look up/delete them. Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com> --- app/test/test_hash.c | 61 ++++ app/test/test_hash_perf.c | 906 +++++++++++++++++++--------------------------- 2 files changed, 439 insertions(+), 528 deletions(-) diff --git a/app/test/test_hash.c b/app/test/test_hash.c index 4300de9..4d538b2 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -1147,6 +1147,65 @@ test_hash_creation_with_good_parameters(void) return 0; } +#define ITERATIONS 50 +/* + * Test to see the average table utilization (entries added/max entries) + * before hitting a random entry that cannot be added + */ +static int test_average_table_utilization(void) +{ + struct rte_hash *handle; + void *simple_key; + unsigned i, j, no_space = 0; + double added_keys_until_no_space = 0; + int ret; + + ut_params.entries = 1 << 20; + ut_params.name = "test_average_utilization"; + ut_params.hash_func = rte_jhash; + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + simple_key = rte_zmalloc(NULL, ut_params.key_len, 0); + + for (j = 0; j < ITERATIONS; j++) { + while (!no_space) { + for (i = 0; i < ut_params.key_len; i++) + ((uint8_t *) simple_key)[i] = rte_rand() % 255; + + ret = rte_hash_add_key(handle, simple_key); + print_key_info("Add", simple_key, ret); + + if (ret == -ENOSPC) { + if (rte_hash_lookup(handle, simple_key) != -ENOENT) + printf("Found key that should not be present\n"); + no_space = 1; + } else { + if (ret < 0) + rte_free(simple_key); + RETURN_IF_ERROR(ret < 0, + "failed to add key (ret=%d)", ret); + added_keys_until_no_space++; + } + } + no_space = 0; + + /* Reset the table */ + rte_hash_free(handle); + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + } + + const unsigned average_keys_added = added_keys_until_no_space / ITERATIONS; + + printf("Average table utilization = %.2f%% (%u/%u)\n", + ((double) average_keys_added / ut_params.entries * 100), + average_keys_added, ut_params.entries); + rte_hash_free(handle); + + return 0; +} + static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, @@ -1405,6 +1464,8 @@ test_hash(void) return -1; if (test_hash_creation_with_good_parameters() < 0) return -1; + if (test_average_table_utilization() < 0) + return -1; run_hash_func_tests(); diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c index d0e5ce0..67dbdd0 100644 --- a/app/test/test_hash_perf.c +++ b/app/test/test_hash_perf.c @@ -32,574 +32,421 @@ */ #include <stdio.h> -#include <stdint.h> -#include <string.h> -#include <stdlib.h> -#include <stdarg.h> -#include <errno.h> -#include <sys/queue.h> - -#include <rte_common.h> +#include <inttypes.h> + #include <rte_lcore.h> -#include <rte_malloc.h> #include <rte_cycles.h> +#include <rte_malloc.h> +#include <rte_hash.h> +#include <rte_hash_crc.h> +#include <rte_jhash.h> +#include <rte_fbk_hash.h> #include <rte_random.h> -#include <rte_memory.h> -#include <rte_memzone.h> -#include <rte_eal.h> -#include <rte_ip.h> #include <rte_string_fns.h> #include "test.h" -#include <rte_hash.h> -#include <rte_fbk_hash.h> -#include <rte_jhash.h> -#include <rte_hash_crc.h> - -/* Types of hash table performance test that can be performed */ -enum hash_test_t { - ADD_ON_EMPTY, /*< Add keys to empty table */ - DELETE_ON_EMPTY, /*< Attempt to delete keys from empty table */ - LOOKUP_ON_EMPTY, /*< Attempt to find keys in an empty table */ - ADD_UPDATE, /*< Add/update keys in a full table */ - DELETE, /*< Delete keys from a full table */ - LOOKUP /*< Find keys in a full table */ +#define KEYS_TO_ADD (1 << 18) +#define MAX_ENTRIES (KEYS_TO_ADD * 4) /* 25% table utilization */ +#define NUM_LOOKUPS (KEYS_TO_ADD * 10) /* Loop among keys added, several times */ +#define BUCKET_SIZE 4 +#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE) +#define MAX_KEYSIZE 64 +#define NUM_KEYSIZES 10 +#define NUM_SHUFFLES 10 +#define BURST_SIZE 16 + +enum operations { + ADD = 0, + LOOKUP, + LOOKUP_MULTI, + DELETE, + NUM_OPERATIONS }; -/* Function type for hash table operations. */ -typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key); - -/* Structure to hold parameters used to run a hash table performance test */ -struct tbl_perf_test_params { - enum hash_test_t test_type; - uint32_t num_iterations; - uint32_t entries; - uint32_t bucket_entries; - uint32_t key_len; - rte_hash_function hash_func; - uint32_t hash_func_init_val; +static uint32_t hashtest_key_lens[] = { + /* standard key sizes */ + 4, 8, 16, 32, 48, 64, + /* IPv4 SRC + DST + protocol, unpadded */ + 9, + /* IPv4 5-tuple, unpadded */ + 13, + /* IPv6 5-tuple, unpadded */ + 37, + /* IPv6 5-tuple, padded to 8-byte boundary */ + 40 }; -#define ITERATIONS 10000 -#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15) +struct rte_hash *h[NUM_KEYSIZES]; +/* Array that stores if a slot is full */ +uint8_t slot_taken[MAX_ENTRIES]; +/* Array to store number of cycles per operation */ +uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2]; +/* Array to store all input keys */ +uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; +/* Array to store the precomputed hash for 'keys' */ +hash_sig_t signatures[KEYS_TO_ADD]; +/* Array to store how many busy entries have each bucket */ +uint8_t buckets[NUM_BUCKETS]; +/* Array to store the positions where keys are added */ +int32_t positions[KEYS_TO_ADD]; + +/* Parameters used for hash table in unit test functions. */ +static struct rte_hash_parameters ut_params = { + .entries = MAX_ENTRIES, + .bucket_entries = BUCKET_SIZE, + .hash_func = rte_jhash, + .hash_func_init_val = 0, +}; -/******************************************************************************* - * Hash table performance test configuration section. - */ -struct tbl_perf_test_params tbl_perf_params[] = +static int +create_table(unsigned table_index) { -/* Small table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_jhash, 0}, -/* Small table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, -/* Small table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, -/* Big table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_jhash, 0}, -/* Big table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, -/* Big table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, -/* Small table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_hash_crc, 0}, -/* Small table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, -/* Small table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, -/* Big table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_hash_crc, 0}, -/* Big table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, -/* Big table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, -}; + char name[RTE_HASH_NAMESIZE]; -/******************************************************************************/ + sprintf(name, "test_hash%d", hashtest_key_lens[table_index]); + ut_params.name = name; + ut_params.key_len = hashtest_key_lens[table_index]; + ut_params.socket_id = rte_socket_id(); + h[table_index] = rte_hash_find_existing(name); + if (h[table_index] != NULL) + /* + * If table was already created, free it to create it again, + * so we force it is empty + */ + rte_hash_free(h[table_index]); + h[table_index] = rte_hash_create(&ut_params); + if (h[table_index] == NULL) { + printf("Error creating table\n"); + return -1; + } + return 0; -/* - * Check condition and return an error if true. Assumes that "handle" is the - * name of the hash structure pointer to be freed. - */ -#define RETURN_IF_ERROR(cond, str, ...) do { \ - if (cond) { \ - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ - if (handle) rte_hash_free(handle); \ - return -1; \ - } \ -} while(0) - -#define RETURN_IF_ERROR_FBK(cond, str, ...) do { \ - if (cond) { \ - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ - if (handle) rte_fbk_hash_free(handle); \ - rte_free(keys); \ - return -1; \ - } \ -} while(0) +} -/* - * Find average of array of numbers. - */ -static double -get_avg(const uint32_t *array, uint32_t size) +/* Shuffle the keys that have been added, so lookups will be totally random */ +static void +shuffle_input_keys(unsigned table_index) { - double sum = 0; unsigned i; - for (i = 0; i < size; i++) - sum += array[i]; - return sum / (double)size; + uint32_t swap_idx; + uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX]; + hash_sig_t temp_signature; + int32_t temp_position; + + for (i = KEYS_TO_ADD - 1; i > 0; i--) { + swap_idx = rte_rand() % i; + + memcpy(temp_key, keys[i], hashtest_key_lens[table_index]); + temp_signature = signatures[i]; + temp_position = positions[i]; + + memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]); + signatures[i] = signatures[swap_idx]; + positions[i] = positions[swap_idx]; + + memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]); + signatures[swap_idx] = temp_signature; + positions[swap_idx] = temp_position; + } } /* - * To help print out name of hash functions. + * Looks for random keys which + * ALL can fit in hash table (no errors) */ -static const char *get_hash_name(rte_hash_function f) +static int +get_input_keys(unsigned table_index) { - if (f == rte_jhash) - return "jhash"; + unsigned i, j; + unsigned bucket_idx, incr, success = 1; + uint8_t k = 0; + int32_t ret; + const uint32_t bucket_bitmask = NUM_BUCKETS - 1; + + /* Reset all arrays */ + for (i = 0; i < MAX_ENTRIES; i++) + slot_taken[i] = 0; - if (f == rte_hash_crc) - return "rte_hash_crc"; + for (i = 0; i < NUM_BUCKETS; i++) + buckets[i] = 0; - return "UnknownHash"; + for (j = 0; j < hashtest_key_lens[table_index]; j++) + keys[0][j] = 0; + + /* + * Add only entries that are not duplicated and that fits in the table + * (cannot store more than BUCKET_SIZE entries in a bucket). + * Regardless a key has been added correctly or not (success), + * the next one to try will be increased by 1. + */ + for (i = 0; i < KEYS_TO_ADD;) { + incr = 0; + if (i != 0) { + keys[i][0] = ++k; + /* Overflow, need to increment the next byte */ + if (keys[i][0] == 0) + incr = 1; + for (j = 1; j < hashtest_key_lens[table_index]; j++) { + /* Do not increase next byte */ + if (incr == 0) + if (success == 1) + keys[i][j] = keys[i - 1][j]; + else + keys[i][j] = keys[i][j]; + /* Increase next byte by one */ + else { + if (success == 1) + keys[i][j] = keys[i-1][j] + 1; + else + keys[i][j] = keys[i][j] + 1; + if (keys[i][j] == 0) + incr = 1; + else + incr = 0; + } + } + } + success = 0; + signatures[i] = rte_hash_hash(h[table_index], keys[i]); + bucket_idx = signatures[i] & bucket_bitmask; + /* If bucket is full, do not try to insert the key */ + if (buckets[bucket_idx] == BUCKET_SIZE) + continue; + /* If key can be added, leave in successful key arrays "keys" */ + ret = rte_hash_add_key_with_hash(h[table_index], keys[i], + signatures[i]); + if (ret >= 0) { + /* If key is already added, ignore the entry and do not store */ + if (slot_taken[ret]) + continue; + else { + /* Store the returned position and mark slot as taken */ + slot_taken[ret] = 1; + buckets[bucket_idx]++; + success = 1; + i++; + } + } + } + + /* Reset the table, so we can measure the time to add all the entries */ + rte_hash_free(h[table_index]); + h[table_index] = rte_hash_create(&ut_params); + + return 0; } -/* - * Do a single performance test, of one type of operation. - * - * @param h - * hash table to run test on - * @param func - * function to call (add, delete or lookup function) - * @param avg_occupancy - * The average number of entries in each bucket of the hash table - * @param invalid_pos_count - * The amount of errors (e.g. due to a full bucket). - * @return - * The average number of ticks per hash function call. A negative number - * signifies failure. - */ -static double -run_single_tbl_perf_test(const struct rte_hash *h, hash_operation func, - const struct tbl_perf_test_params *params, double *avg_occupancy, - uint32_t *invalid_pos_count) +static int +timed_adds(unsigned with_hash, unsigned table_index) { - uint64_t begin, end, ticks = 0; - uint8_t *key = NULL; - uint32_t *bucket_occupancies = NULL; - uint32_t num_buckets, i, j; - int32_t pos; - - /* Initialise */ - num_buckets = params->entries / params->bucket_entries; - key = rte_zmalloc("hash key", - params->key_len * sizeof(uint8_t), 16); - if (key == NULL) - return -1; + unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + ret = rte_hash_add_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); + else + ret = rte_hash_add_key(h[table_index], keys[i]); - bucket_occupancies = rte_calloc("bucket occupancies", - num_buckets, sizeof(uint32_t), 16); - if (bucket_occupancies == NULL) { - rte_free(key); - return -1; + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } } - ticks = 0; - *invalid_pos_count = 0; + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; - for (i = 0; i < params->num_iterations; i++) { - /* Prepare inputs for the current iteration */ - for (j = 0; j < params->key_len; j++) - key[j] = (uint8_t) rte_rand(); + cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD; - /* Perform operation, and measure time it takes */ - begin = rte_rdtsc(); - pos = func(h, key); - end = rte_rdtsc(); - ticks += end - begin; + return 0; +} - /* Other work per iteration */ - if (pos < 0) - *invalid_pos_count += 1; - else - bucket_occupancies[pos / params->bucket_entries]++; +static int +timed_lookups(unsigned with_hash, unsigned table_index) +{ + unsigned i, j; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD; j++) { + if (with_hash) + ret = rte_hash_lookup_with_hash(h[table_index], + (const void *) keys[j], + signatures[j]); + else + ret = rte_hash_lookup(h[table_index], keys[j]); + if (ret < 0 || ret != positions[j]) { + printf("Key looked up in %d, should be in %d\n", + ret, positions[j]); + return -1; + } + } } - *avg_occupancy = get_avg(bucket_occupancies, num_buckets); - rte_free(bucket_occupancies); - rte_free(key); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; - return (double)ticks / params->num_iterations; + cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS; + + return 0; } -/* - * To help print out what tests are being done. - */ -static const char * -get_tbl_perf_test_desc(enum hash_test_t type) +static int +timed_lookups_multi(unsigned table_index) { - switch (type){ - case ADD_ON_EMPTY: return "Add on Empty"; - case DELETE_ON_EMPTY: return "Delete on Empty"; - case LOOKUP_ON_EMPTY: return "Lookup on Empty"; - case ADD_UPDATE: return "Add Update"; - case DELETE: return "Delete"; - case LOOKUP: return "Lookup"; - default: return "UNKNOWN"; + unsigned i, j, k; + int32_t positions_burst[BURST_SIZE]; + const void *keys_burst[BURST_SIZE]; + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) { + for (k = 0; k < BURST_SIZE; k++) + keys_burst[k] = keys[j * BURST_SIZE + k]; + + rte_hash_lookup_bulk(h[table_index], + (const void **) keys_burst, + BURST_SIZE, + positions_burst); + for (k = 0; k < BURST_SIZE; k++) { + if (positions_burst[k] != positions[j * BURST_SIZE + k]) { + printf("Key looked up in %d, should be in %d\n", + positions_burst[k], + positions[j * BURST_SIZE + k]); + return -1; + } + } + } } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS; + + return 0; } -/* - * Run a hash table performance test based on params. - */ static int -run_tbl_perf_test(struct tbl_perf_test_params *params) +timed_deletes(unsigned with_hash, unsigned table_index) { - static unsigned calledCount = 5; - struct rte_hash_parameters hash_params = { - .entries = params->entries, - .bucket_entries = params->bucket_entries, - .key_len = params->key_len, - .hash_func = params->hash_func, - .hash_func_init_val = params->hash_func_init_val, - .socket_id = rte_socket_id(), - }; - struct rte_hash *handle; - double avg_occupancy = 0, ticks = 0; - uint32_t num_iterations, invalid_pos; - char name[RTE_HASH_NAMESIZE]; - char hashname[RTE_HASH_NAMESIZE]; - - snprintf(name, 32, "test%u", calledCount++); - hash_params.name = name; - - handle = rte_hash_create(&hash_params); - RETURN_IF_ERROR(handle == NULL, "hash creation failed"); - - switch (params->test_type){ - case ADD_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, - params, &avg_occupancy, &invalid_pos); - break; - case DELETE_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, - params, &avg_occupancy, &invalid_pos); - break; - case LOOKUP_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, - params, &avg_occupancy, &invalid_pos); - break; - case ADD_UPDATE: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, - params, &avg_occupancy, &invalid_pos); - break; - case DELETE: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, - params, &avg_occupancy, &invalid_pos); - break; - case LOOKUP: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, - params, &avg_occupancy, &invalid_pos); - break; - default: return -1; + unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + ret = rte_hash_del_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); + else + ret = rte_hash_del_key(h[table_index], + (const void *) keys[i]); + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } } - snprintf(hashname, RTE_HASH_NAMESIZE, "%s", get_hash_name(params->hash_func)); - - printf("%-12s, %-15s, %-16u, %-7u, %-18u, %-8u, %-19.2f, %.2f\n", - hashname, - get_tbl_perf_test_desc(params->test_type), - (unsigned) params->key_len, - (unsigned) params->entries, - (unsigned) params->bucket_entries, - (unsigned) invalid_pos, - avg_occupancy, - ticks - ); - - /* Free */ - rte_hash_free(handle); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD; + return 0; } -/* - * Run all hash table performance tests. - */ -static int run_all_tbl_perf_tests(void) +static void +free_table(unsigned table_index) { - unsigned i; + rte_hash_free(h[table_index]); +} + +static int +reset_table(unsigned table_index) +{ + free_table(table_index); + if (create_table(table_index) != 0) + return -1; - printf(" *** Hash table performance test results ***\n"); - printf("Hash Func. , Operation , Key size (bytes), Entries, " - "Entries per bucket, Errors , Avg. bucket entries, Ticks/Op.\n"); + return 0; +} + +static int +run_all_tbl_perf_tests(void) +{ + unsigned i, j; - /* Loop through every combination of test parameters */ - for (i = 0; - i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params); - i++) { + for (i = 0; i < NUM_KEYSIZES; i++) { + if (create_table(i) < 0) + return -1; - /* Perform test */ - if (run_tbl_perf_test(&tbl_perf_params[i]) < 0) + if (get_input_keys(i) < 0) return -1; + + if (timed_adds(0, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + if (timed_lookups(0, i) < 0) + return -1; + + if (timed_lookups_multi(i) < 0) + return -1; + + if (timed_deletes(0, i) < 0) + return -1; + + if (reset_table(i) < 0) + return -1; + + if (timed_adds(1, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + if (timed_lookups(1, i) < 0) + return -1; + + if (timed_deletes(1, i) < 0) + return -1; + + free_table(i); + } + printf("\nResults (in CPU cycles/operation)\n"); + printf("---------------------------------\n"); + printf("\nWith just keys\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); + for (i = 0; i < NUM_KEYSIZES; i++) { + printf("%-18d", hashtest_key_lens[i]); + for (j = 0; j < NUM_OPERATIONS; j++) + printf("%-18"PRIu64, cycles[i][j][0]); + printf("\n"); + } + printf("\nWith precomputed hash\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); + for (i = 0; i < NUM_KEYSIZES; i++) { + printf("%-18d", hashtest_key_lens[i]); + for (j = 0; j < NUM_OPERATIONS; j++) + printf("%-18"PRIu64, cycles[i][j][1]); + printf("\n"); } + return 0; } @@ -624,28 +471,34 @@ fbk_hash_perf_test(void) uint64_t lookup_time = 0; unsigned added = 0; unsigned value = 0; + uint32_t key; + uint16_t val; unsigned i, j; handle = rte_fbk_hash_create(¶ms); - RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed"); + if (handle == NULL) { + printf("Error creating table\n"); + return -1; + } keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); - RETURN_IF_ERROR_FBK(keys == NULL, - "fbk hash: memory allocation for key store failed"); + if (keys == NULL) { + printf("fbk hash: memory allocation for key store failed\n"); + return -1; + } /* Generate random keys and values. */ for (i = 0; i < ENTRIES; i++) { - uint32_t key = (uint32_t)rte_rand(); + key = (uint32_t)rte_rand(); key = ((uint64_t)key << 32) | (uint64_t)rte_rand(); - uint16_t val = (uint16_t)rte_rand(); + val = (uint16_t)rte_rand(); if (rte_fbk_hash_add_key(handle, key, val) == 0) { keys[added] = key; added++; } - if (added > (LOAD_FACTOR * ENTRIES)) { + if (added > (LOAD_FACTOR * ENTRIES)) break; - } } for (i = 0; i < TEST_ITERATIONS; i++) { @@ -653,15 +506,14 @@ fbk_hash_perf_test(void) uint64_t end; /* Generate random indexes into keys[] array. */ - for (j = 0; j < TEST_SIZE; j++) { + for (j = 0; j < TEST_SIZE; j++) indexes[j] = rte_rand() % added; - } begin = rte_rdtsc(); /* Do lookups */ - for (j = 0; j < TEST_SIZE; j++) { + for (j = 0; j < TEST_SIZE; j++) value += rte_fbk_hash_lookup(handle, keys[indexes[j]]); - } + end = rte_rdtsc(); lookup_time += (double)(end - begin); } @@ -681,9 +533,6 @@ fbk_hash_perf_test(void) return 0; } -/* - * Do all unit and performance tests. - */ static int test_hash_perf(void) { @@ -692,11 +541,12 @@ test_hash_perf(void) if (fbk_hash_perf_test() < 0) return -1; + return 0; } static struct test_command hash_perf_cmd = { - .command = "hash_perf_autotest", - .callback = test_hash_perf, + .command = "hash_perf_autotest", + .callback = test_hash_perf, }; REGISTER_TEST_COMMAND(hash_perf_cmd); -- 2.4.2 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH] test/hash: improve hash unit tests 2015-07-08 13:12 ` [PATCH] test/hash: improve hash unit tests Pablo de Lara @ 2015-07-08 13:39 ` Bruce Richardson 2015-07-08 15:04 ` Bruce Richardson 1 sibling, 0 replies; 13+ messages in thread From: Bruce Richardson @ 2015-07-08 13:39 UTC (permalink / raw) To: Pablo de Lara; +Cc: dev On Wed, Jul 08, 2015 at 02:12:06PM +0100, Pablo de Lara wrote: > Add new unit test for calculating the average table utilization, > using random keys, based on number of entries that can be added > until we encounter one that cannot be added (bucket if full) > > Also, replace current hash_perf unit test to see performance more clear. > The current hash_perf unit test takes too long and add keys that > may or may not fit in the table and look up/delete that may not be > in the table. This new unit test gets a set of keys that we know > that fits in the table, and then measure the time to add/look up/delete > them. > > Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com> Looks a good change to me - especially for the perf test. The output is much more usable since it doesn't try to cover every possibility and give pages and pages of output. Some comments inline below. /Bruce > --- > app/test/test_hash.c | 61 ++++ > app/test/test_hash_perf.c | 906 +++++++++++++++++++--------------------------- > 2 files changed, 439 insertions(+), 528 deletions(-) > > diff --git a/app/test/test_hash.c b/app/test/test_hash.c > index 4300de9..4d538b2 100644 > --- a/app/test/test_hash.c > +++ b/app/test/test_hash.c > @@ -1147,6 +1147,65 @@ test_hash_creation_with_good_parameters(void) > return 0; > } > > +#define ITERATIONS 50 > +/* > + * Test to see the average table utilization (entries added/max entries) > + * before hitting a random entry that cannot be added > + */ > +static int test_average_table_utilization(void) > +{ > + struct rte_hash *handle; > + void *simple_key; > + unsigned i, j, no_space = 0; > + double added_keys_until_no_space = 0; > + int ret; > + > + ut_params.entries = 1 << 20; > + ut_params.name = "test_average_utilization"; > + ut_params.hash_func = rte_jhash; > + handle = rte_hash_create(&ut_params); > + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); > + > + simple_key = rte_zmalloc(NULL, ut_params.key_len, 0); > + > + for (j = 0; j < ITERATIONS; j++) { > + while (!no_space) { > + for (i = 0; i < ut_params.key_len; i++) > + ((uint8_t *) simple_key)[i] = rte_rand() % 255; > + > + ret = rte_hash_add_key(handle, simple_key); > + print_key_info("Add", simple_key, ret); > + > + if (ret == -ENOSPC) { > + if (rte_hash_lookup(handle, simple_key) != -ENOENT) > + printf("Found key that should not be present\n"); > + no_space = 1; > + } else { > + if (ret < 0) > + rte_free(simple_key); > + RETURN_IF_ERROR(ret < 0, > + "failed to add key (ret=%d)", ret); > + added_keys_until_no_space++; > + } > + } > + no_space = 0; > + > + /* Reset the table */ > + rte_hash_free(handle); > + handle = rte_hash_create(&ut_params); > + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); > + } > + > + const unsigned average_keys_added = added_keys_until_no_space / ITERATIONS; > + > + printf("Average table utilization = %.2f%% (%u/%u)\n", > + ((double) average_keys_added / ut_params.entries * 100), > + average_keys_added, ut_params.entries); The output is unclear for someone running the test. I think you need a longer explanatory message. Perhaps at the start of the test print out: "Running test to determine average utilitization before adding elements beings to fail". That would make it clear what the "Average table utilization" refers to. Also, unrelated directly to your patch, but when the test is run the first line output is: "# Testing hash creation with invalid parameters - expert error msgs" Presumably "expert" should really be "expect". Could you maybe fix this if you do a V2 of this patch. Also, at the end of that test run - we should indicate test successful to make it clear that additional errors are *not* expected from that point onwards. > + rte_hash_free(handle); > + > + return 0; > +} > + > static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, > 0x04, 0x05, 0x06, 0x07, > 0x08, 0x09, 0x0a, 0x0b, > @@ -1405,6 +1464,8 @@ test_hash(void) > return -1; > if (test_hash_creation_with_good_parameters() < 0) > return -1; > + if (test_average_table_utilization() < 0) > + return -1; > > run_hash_func_tests(); > > diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c > index d0e5ce0..67dbdd0 100644 > --- a/app/test/test_hash_perf.c > +++ b/app/test/test_hash_perf.c > @@ -32,574 +32,421 @@ > */ > > #include <stdio.h> > -#include <stdint.h> > -#include <string.h> > -#include <stdlib.h> > -#include <stdarg.h> > -#include <errno.h> > -#include <sys/queue.h> > - > -#include <rte_common.h> > +#include <inttypes.h> > + > #include <rte_lcore.h> > -#include <rte_malloc.h> > #include <rte_cycles.h> > +#include <rte_malloc.h> > +#include <rte_hash.h> > +#include <rte_hash_crc.h> > +#include <rte_jhash.h> > +#include <rte_fbk_hash.h> > #include <rte_random.h> > -#include <rte_memory.h> > -#include <rte_memzone.h> > -#include <rte_eal.h> > -#include <rte_ip.h> > #include <rte_string_fns.h> > > #include "test.h" > > -#include <rte_hash.h> > -#include <rte_fbk_hash.h> > -#include <rte_jhash.h> > -#include <rte_hash_crc.h> > - > -/* Types of hash table performance test that can be performed */ > -enum hash_test_t { > - ADD_ON_EMPTY, /*< Add keys to empty table */ > - DELETE_ON_EMPTY, /*< Attempt to delete keys from empty table */ > - LOOKUP_ON_EMPTY, /*< Attempt to find keys in an empty table */ > - ADD_UPDATE, /*< Add/update keys in a full table */ > - DELETE, /*< Delete keys from a full table */ > - LOOKUP /*< Find keys in a full table */ > +#define KEYS_TO_ADD (1 << 18) > +#define MAX_ENTRIES (KEYS_TO_ADD * 4) /* 25% table utilization */ > +#define NUM_LOOKUPS (KEYS_TO_ADD * 10) /* Loop among keys added, several times */ > +#define BUCKET_SIZE 4 > +#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE) > +#define MAX_KEYSIZE 64 > +#define NUM_KEYSIZES 10 > +#define NUM_SHUFFLES 10 > +#define BURST_SIZE 16 > + > +enum operations { > + ADD = 0, > + LOOKUP, > + LOOKUP_MULTI, > + DELETE, > + NUM_OPERATIONS > }; > > -/* Function type for hash table operations. */ > -typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key); > - > -/* Structure to hold parameters used to run a hash table performance test */ > -struct tbl_perf_test_params { > - enum hash_test_t test_type; > - uint32_t num_iterations; > - uint32_t entries; > - uint32_t bucket_entries; > - uint32_t key_len; > - rte_hash_function hash_func; > - uint32_t hash_func_init_val; > +static uint32_t hashtest_key_lens[] = { > + /* standard key sizes */ > + 4, 8, 16, 32, 48, 64, > + /* IPv4 SRC + DST + protocol, unpadded */ > + 9, > + /* IPv4 5-tuple, unpadded */ > + 13, > + /* IPv6 5-tuple, unpadded */ > + 37, > + /* IPv6 5-tuple, padded to 8-byte boundary */ > + 40 > }; > > -#define ITERATIONS 10000 > -#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15) > +struct rte_hash *h[NUM_KEYSIZES]; > +/* Array that stores if a slot is full */ > +uint8_t slot_taken[MAX_ENTRIES]; > +/* Array to store number of cycles per operation */ > +uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2]; > +/* Array to store all input keys */ > +uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; > +/* Array to store the precomputed hash for 'keys' */ > +hash_sig_t signatures[KEYS_TO_ADD]; > +/* Array to store how many busy entries have each bucket */ > +uint8_t buckets[NUM_BUCKETS]; > +/* Array to store the positions where keys are added */ > +int32_t positions[KEYS_TO_ADD]; Please put the comments above at the end of the lines, or else put a blank line between the definitions, so that it's clear at a glance what comment goes with what definition. <snip> > + printf("\nResults (in CPU cycles/operation)\n"); > + printf("---------------------------------\n"); > + printf("\nWith just keys\n"); "With just keys" is unclear. "Without pre-computed hash values" is better. > + printf("\n%-18s%-18s%-18s%-18s%-18s\n", > + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); > + for (i = 0; i < NUM_KEYSIZES; i++) { > + printf("%-18d", hashtest_key_lens[i]); > + for (j = 0; j < NUM_OPERATIONS; j++) > + printf("%-18"PRIu64, cycles[i][j][0]); > + printf("\n"); > + } > + printf("\nWith precomputed hash\n"); > + printf("\n%-18s%-18s%-18s%-18s%-18s\n", > + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); > + for (i = 0; i < NUM_KEYSIZES; i++) { > + printf("%-18d", hashtest_key_lens[i]); > + for (j = 0; j < NUM_OPERATIONS; j++) > + printf("%-18"PRIu64, cycles[i][j][1]); > + printf("\n"); > } > + > return 0; > } When you run the perf unit test, it takes some time while the test is run and all the output is then printed. Can you add a printout at the start of the test to say something like "Measuring performance, please wait...", so that the user knows that there is a delay and that the app has not hung. Even better, you could put a print-out at the end of every stage of the process - either a single line stating what has just been done, or if you like brevity, just an additional dot on the screen to show that the process is not hung. Regards, /Bruce ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH] test/hash: improve hash unit tests 2015-07-08 13:12 ` [PATCH] test/hash: improve hash unit tests Pablo de Lara 2015-07-08 13:39 ` Bruce Richardson @ 2015-07-08 15:04 ` Bruce Richardson 2015-07-08 15:14 ` De Lara Guarch, Pablo 1 sibling, 1 reply; 13+ messages in thread From: Bruce Richardson @ 2015-07-08 15:04 UTC (permalink / raw) To: Pablo de Lara; +Cc: dev On Wed, Jul 08, 2015 at 02:12:06PM +0100, Pablo de Lara wrote: > Add new unit test for calculating the average table utilization, > using random keys, based on number of entries that can be added > until we encounter one that cannot be added (bucket if full) > > Also, replace current hash_perf unit test to see performance more clear. > The current hash_perf unit test takes too long and add keys that > may or may not fit in the table and look up/delete that may not be > in the table. This new unit test gets a set of keys that we know > that fits in the table, and then measure the time to add/look up/delete > them. > > Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com> Few more comments on the change to test_hash.c /Bruce > --- > app/test/test_hash.c | 61 ++++ > app/test/test_hash_perf.c | 906 +++++++++++++++++++--------------------------- > 2 files changed, 439 insertions(+), 528 deletions(-) > > diff --git a/app/test/test_hash.c b/app/test/test_hash.c > index 4300de9..4d538b2 100644 > --- a/app/test/test_hash.c > +++ b/app/test/test_hash.c > @@ -1147,6 +1147,65 @@ test_hash_creation_with_good_parameters(void) > return 0; > } > > +#define ITERATIONS 50 > +/* > + * Test to see the average table utilization (entries added/max entries) > + * before hitting a random entry that cannot be added > + */ > +static int test_average_table_utilization(void) > +{ > + struct rte_hash *handle; > + void *simple_key; > + unsigned i, j, no_space = 0; > + double added_keys_until_no_space = 0; > + int ret; > + > + ut_params.entries = 1 << 20; > + ut_params.name = "test_average_utilization"; > + ut_params.hash_func = rte_jhash; > + handle = rte_hash_create(&ut_params); > + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); > + > + simple_key = rte_zmalloc(NULL, ut_params.key_len, 0); > + > + for (j = 0; j < ITERATIONS; j++) { > + while (!no_space) { > + for (i = 0; i < ut_params.key_len; i++) > + ((uint8_t *) simple_key)[i] = rte_rand() % 255; > + > + ret = rte_hash_add_key(handle, simple_key); > + print_key_info("Add", simple_key, ret); > + > + if (ret == -ENOSPC) { > + if (rte_hash_lookup(handle, simple_key) != -ENOENT) > + printf("Found key that should not be present\n"); Should this not be an immediate test failure? In fact, is it really worth testing, for this condition. Why not just have the loop and test as: do { /*set up simple key */ } while ((ret = rte_hash_add_key(...)) >= 0); if (ret != -ENOSPC) { /* print error */ return -1; } > + no_space = 1; > + } else { > + if (ret < 0) > + rte_free(simple_key); Rather than using malloc free, why not just make simple_key a local array of size MAX_KEY_SIZE. > + RETURN_IF_ERROR(ret < 0, > + "failed to add key (ret=%d)", ret); > + added_keys_until_no_space++; > + } > + } > + no_space = 0; > + > + /* Reset the table */ > + rte_hash_free(handle); > + handle = rte_hash_create(&ut_params); > + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); Would a reset call work better than a free/recreate? > + } > + > + const unsigned average_keys_added = added_keys_until_no_space / ITERATIONS; > + > + printf("Average table utilization = %.2f%% (%u/%u)\n", > + ((double) average_keys_added / ut_params.entries * 100), > + average_keys_added, ut_params.entries); > + rte_hash_free(handle); > + > + return 0; > +} > + > static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, > 0x04, 0x05, 0x06, 0x07, > 0x08, 0x09, 0x0a, 0x0b, > @@ -1405,6 +1464,8 @@ test_hash(void) > return -1; > if (test_hash_creation_with_good_parameters() < 0) > return -1; > + if (test_average_table_utilization() < 0) > + return -1; > > run_hash_func_tests(); > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH] test/hash: improve hash unit tests 2015-07-08 15:04 ` Bruce Richardson @ 2015-07-08 15:14 ` De Lara Guarch, Pablo 0 siblings, 0 replies; 13+ messages in thread From: De Lara Guarch, Pablo @ 2015-07-08 15:14 UTC (permalink / raw) To: Richardson, Bruce; +Cc: dev Hi Bruce, > -----Original Message----- > From: Richardson, Bruce > Sent: Wednesday, July 08, 2015 4:04 PM > To: De Lara Guarch, Pablo > Cc: dev@dpdk.org > Subject: Re: [dpdk-dev] [PATCH] test/hash: improve hash unit tests > > On Wed, Jul 08, 2015 at 02:12:06PM +0100, Pablo de Lara wrote: > > Add new unit test for calculating the average table utilization, > > using random keys, based on number of entries that can be added > > until we encounter one that cannot be added (bucket if full) > > > > Also, replace current hash_perf unit test to see performance more clear. > > The current hash_perf unit test takes too long and add keys that > > may or may not fit in the table and look up/delete that may not be > > in the table. This new unit test gets a set of keys that we know > > that fits in the table, and then measure the time to add/look up/delete > > them. > > > > Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com> > > Few more comments on the change to test_hash.c > > /Bruce > > --- > > app/test/test_hash.c | 61 ++++ > > app/test/test_hash_perf.c | 906 +++++++++++++++++++-------------------- > ------- > > 2 files changed, 439 insertions(+), 528 deletions(-) > > > > diff --git a/app/test/test_hash.c b/app/test/test_hash.c > > index 4300de9..4d538b2 100644 > > --- a/app/test/test_hash.c > > +++ b/app/test/test_hash.c > > @@ -1147,6 +1147,65 @@ > test_hash_creation_with_good_parameters(void) > > return 0; > > } > > > > +#define ITERATIONS 50 > > +/* > > + * Test to see the average table utilization (entries added/max entries) > > + * before hitting a random entry that cannot be added > > + */ > > +static int test_average_table_utilization(void) > > +{ > > + struct rte_hash *handle; > > + void *simple_key; > > + unsigned i, j, no_space = 0; > > + double added_keys_until_no_space = 0; > > + int ret; > > + > > + ut_params.entries = 1 << 20; > > + ut_params.name = "test_average_utilization"; > > + ut_params.hash_func = rte_jhash; > > + handle = rte_hash_create(&ut_params); > > + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); > > + > > + simple_key = rte_zmalloc(NULL, ut_params.key_len, 0); > > + > > + for (j = 0; j < ITERATIONS; j++) { > > + while (!no_space) { > > + for (i = 0; i < ut_params.key_len; i++) > > + ((uint8_t *) simple_key)[i] = rte_rand() % > 255; > > + > > + ret = rte_hash_add_key(handle, simple_key); > > + print_key_info("Add", simple_key, ret); > > + > > + if (ret == -ENOSPC) { > > + if (rte_hash_lookup(handle, simple_key) != - > ENOENT) > > + printf("Found key that should not be > present\n"); > Should this not be an immediate test failure? > In fact, is it really worth testing, for this condition. Why not just have > the loop and test as: > > do { > /*set up simple key */ > } while ((ret = rte_hash_add_key(...)) >= 0); > if (ret != -ENOSPC) { > /* print error */ > return -1; > } > Sure, I forgot to return an error in this case. And yes, you are right, that's more elegant. Only thing missing there is freeing the hash table. > > + no_space = 1; > > + } else { > > + if (ret < 0) > > + rte_free(simple_key); > > Rather than using malloc free, why not just make simple_key a local array of > size MAX_KEY_SIZE. Will do. > > > + RETURN_IF_ERROR(ret < 0, > > + "failed to add key (ret=%d)", > ret); > > + added_keys_until_no_space++; > > + } > > + } > > + no_space = 0; > > + > > + /* Reset the table */ > > + rte_hash_free(handle); > > + handle = rte_hash_create(&ut_params); > > + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); > > Would a reset call work better than a free/recreate? It would, but that function was not present in the current implementation. I have added it in the new implementation, so I changed this as soon as I implement it. > > > + } > > + > > + const unsigned average_keys_added = added_keys_until_no_space > / ITERATIONS; > > + > > + printf("Average table utilization = %.2f%% (%u/%u)\n", > > + ((double) average_keys_added / ut_params.entries * 100), > > + average_keys_added, ut_params.entries); > > + rte_hash_free(handle); > > + > > + return 0; > > +} > > + > > static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, > > 0x04, 0x05, 0x06, 0x07, > > 0x08, 0x09, 0x0a, 0x0b, > > @@ -1405,6 +1464,8 @@ test_hash(void) > > return -1; > > if (test_hash_creation_with_good_parameters() < 0) > > return -1; > > + if (test_average_table_utilization() < 0) > > + return -1; > > > > run_hash_func_tests(); > > ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2] Improve hash unit tests - Cuckoo hash part 2 2015-07-08 13:12 [PATCH] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 2015-07-08 13:12 ` [PATCH] test/hash: improve hash unit tests Pablo de Lara @ 2015-07-08 16:30 ` Pablo de Lara 2015-07-08 16:30 ` [PATCH v2] test/hash: improve hash unit tests Pablo de Lara 2015-07-09 12:19 ` [PATCH v3] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 1 sibling, 2 replies; 13+ messages in thread From: Pablo de Lara @ 2015-07-08 16:30 UTC (permalink / raw) To: dev This patch improves the unit tests for the hash library, showing more readable results, in preparation for the new hash implementation to show performance differences. Changes in v2: - Add missing error check - Simplify average table utilization test - Improve outputs - Fix some typos Pablo de Lara (1): test/hash: improve hash unit tests app/test/test_hash.c | 66 +++- app/test/test_hash_perf.c | 927 ++++++++++++++++++++-------------------------- 2 files changed, 462 insertions(+), 531 deletions(-) -- 2.4.2 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2] test/hash: improve hash unit tests 2015-07-08 16:30 ` [PATCH v2] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara @ 2015-07-08 16:30 ` Pablo de Lara 2015-07-09 12:19 ` [PATCH v3] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 1 sibling, 0 replies; 13+ messages in thread From: Pablo de Lara @ 2015-07-08 16:30 UTC (permalink / raw) To: dev Add new unit test for calculating the average table utilization, using random keys, based on number of entries that can be added until we encounter one that cannot be added (bucket if full) Also, replace current hash_perf unit test to see performance more clear. The current hash_perf unit test takes too long and add keys that may or may not fit in the table and look up/delete that may not be in the table. This new unit test gets a set of keys that we know that fits in the table, and then measure the time to add/look up/delete them. Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com> --- app/test/test_hash.c | 66 +++- app/test/test_hash_perf.c | 927 ++++++++++++++++++++-------------------------- 2 files changed, 462 insertions(+), 531 deletions(-) diff --git a/app/test/test_hash.c b/app/test/test_hash.c index 4300de9..7c71ed6 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -190,7 +190,7 @@ test_crc32_hash_alg_equiv(void) unsigned i, j; size_t data_len; - printf("# CRC32 implementations equivalence test\n"); + printf("\n# CRC32 implementations equivalence test\n"); for (i = 0; i < CRC32_ITERATIONS; i++) { /* Randomizing data_len of data set */ data_len = (size_t) ((rte_rand() % sizeof(data64)) + 1); @@ -785,7 +785,7 @@ fbk_hash_unit_test(void) /* Try creating hashes with invalid parameters */ printf("# Testing hash creation with invalid parameters " - "- expert error msgs\n"); + "- expect error msgs\n"); handle = rte_fbk_hash_create(&invalid_params_1); RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); @@ -1087,6 +1087,7 @@ static int test_hash_creation_with_bad_parameters(void) } rte_hash_free(handle); + printf("# Test successful. No more errors expected\n"); return 0; } @@ -1147,6 +1148,65 @@ test_hash_creation_with_good_parameters(void) return 0; } +#define ITERATIONS 50 +/* + * Test to see the average table utilization (entries added/max entries) + * before hitting a random entry that cannot be added + */ +static int test_average_table_utilization(void) +{ + struct rte_hash *handle; + uint8_t simple_key[RTE_HASH_KEY_LENGTH_MAX]; + unsigned i, j; + unsigned added_keys, average_keys_added = 0; + int ret; + + printf("\n# Running test to determine average utilization" + "\n before adding elements begins to fail\n"); + printf("Measuring performance, please wait"); + fflush(stdout); + ut_params.entries = 1 << 20; + ut_params.name = "test_average_utilization"; + ut_params.hash_func = rte_jhash; + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + for (j = 0; j < ITERATIONS; j++) { + ret = 0; + /* Add random entries until key cannot be added */ + for (added_keys = 0; ret >= 0; added_keys++) { + for (i = 0; i < ut_params.key_len; i++) + simple_key[i] = rte_rand() % 255; + ret = rte_hash_add_key(handle, simple_key); + } + if (ret != -ENOSPC) { + printf("Unexpected error when adding keys\n"); + rte_hash_free(handle); + return -1; + } + + average_keys_added += added_keys; + + /* Reset the table */ + rte_hash_free(handle); + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + } + + average_keys_added /= ITERATIONS; + + printf("\nAverage table utilization = %.2f%% (%u/%u)\n", + ((double) average_keys_added / ut_params.entries * 100), + average_keys_added, ut_params.entries); + rte_hash_free(handle); + + return 0; +} + static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, @@ -1405,6 +1465,8 @@ test_hash(void) return -1; if (test_hash_creation_with_good_parameters() < 0) return -1; + if (test_average_table_utilization() < 0) + return -1; run_hash_func_tests(); diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c index d0e5ce0..1597fa7 100644 --- a/app/test/test_hash_perf.c +++ b/app/test/test_hash_perf.c @@ -32,574 +32,440 @@ */ #include <stdio.h> -#include <stdint.h> -#include <string.h> -#include <stdlib.h> -#include <stdarg.h> -#include <errno.h> -#include <sys/queue.h> - -#include <rte_common.h> +#include <inttypes.h> + #include <rte_lcore.h> -#include <rte_malloc.h> #include <rte_cycles.h> +#include <rte_malloc.h> +#include <rte_hash.h> +#include <rte_hash_crc.h> +#include <rte_jhash.h> +#include <rte_fbk_hash.h> #include <rte_random.h> -#include <rte_memory.h> -#include <rte_memzone.h> -#include <rte_eal.h> -#include <rte_ip.h> #include <rte_string_fns.h> #include "test.h" -#include <rte_hash.h> -#include <rte_fbk_hash.h> -#include <rte_jhash.h> -#include <rte_hash_crc.h> - -/* Types of hash table performance test that can be performed */ -enum hash_test_t { - ADD_ON_EMPTY, /*< Add keys to empty table */ - DELETE_ON_EMPTY, /*< Attempt to delete keys from empty table */ - LOOKUP_ON_EMPTY, /*< Attempt to find keys in an empty table */ - ADD_UPDATE, /*< Add/update keys in a full table */ - DELETE, /*< Delete keys from a full table */ - LOOKUP /*< Find keys in a full table */ +#define KEYS_TO_ADD (1 << 18) +#define MAX_ENTRIES (KEYS_TO_ADD * 4) /* 25% table utilization */ +#define NUM_LOOKUPS (KEYS_TO_ADD * 10) /* Loop among keys added, several times */ +#define BUCKET_SIZE 4 +#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE) +#define MAX_KEYSIZE 64 +#define NUM_KEYSIZES 10 +#define NUM_SHUFFLES 10 +#define BURST_SIZE 16 + +enum operations { + ADD = 0, + LOOKUP, + LOOKUP_MULTI, + DELETE, + NUM_OPERATIONS }; -/* Function type for hash table operations. */ -typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key); - -/* Structure to hold parameters used to run a hash table performance test */ -struct tbl_perf_test_params { - enum hash_test_t test_type; - uint32_t num_iterations; - uint32_t entries; - uint32_t bucket_entries; - uint32_t key_len; - rte_hash_function hash_func; - uint32_t hash_func_init_val; +static uint32_t hashtest_key_lens[] = { + /* standard key sizes */ + 4, 8, 16, 32, 48, 64, + /* IPv4 SRC + DST + protocol, unpadded */ + 9, + /* IPv4 5-tuple, unpadded */ + 13, + /* IPv6 5-tuple, unpadded */ + 37, + /* IPv6 5-tuple, padded to 8-byte boundary */ + 40 }; -#define ITERATIONS 10000 -#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15) +struct rte_hash *h[NUM_KEYSIZES]; -/******************************************************************************* - * Hash table performance test configuration section. - */ -struct tbl_perf_test_params tbl_perf_params[] = -{ -/* Small table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_jhash, 0}, -/* Small table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, -/* Small table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, -/* Big table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_jhash, 0}, -/* Big table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, -/* Big table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, -/* Small table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_hash_crc, 0}, -/* Small table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, -/* Small table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, -/* Big table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_hash_crc, 0}, -/* Big table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, -/* Big table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, -}; +/* Array that stores if a slot is full */ +uint8_t slot_taken[MAX_ENTRIES]; -/******************************************************************************/ +/* Array to store number of cycles per operation */ +uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2]; -/* - * Check condition and return an error if true. Assumes that "handle" is the - * name of the hash structure pointer to be freed. - */ -#define RETURN_IF_ERROR(cond, str, ...) do { \ - if (cond) { \ - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ - if (handle) rte_hash_free(handle); \ - return -1; \ - } \ -} while(0) - -#define RETURN_IF_ERROR_FBK(cond, str, ...) do { \ - if (cond) { \ - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ - if (handle) rte_fbk_hash_free(handle); \ - rte_free(keys); \ - return -1; \ - } \ -} while(0) +/* Array to store all input keys */ +uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; -/* - * Find average of array of numbers. - */ -static double -get_avg(const uint32_t *array, uint32_t size) +/* Array to store the precomputed hash for 'keys' */ +hash_sig_t signatures[KEYS_TO_ADD]; + +/* Array to store how many busy entries have each bucket */ +uint8_t buckets[NUM_BUCKETS]; + +/* Array to store the positions where keys are added */ +int32_t positions[KEYS_TO_ADD]; + +/* Parameters used for hash table in unit test functions. */ +static struct rte_hash_parameters ut_params = { + .entries = MAX_ENTRIES, + .bucket_entries = BUCKET_SIZE, + .hash_func = rte_jhash, + .hash_func_init_val = 0, +}; + +static int +create_table(unsigned table_index) { - double sum = 0; - unsigned i; - for (i = 0; i < size; i++) - sum += array[i]; - return sum / (double)size; + char name[RTE_HASH_NAMESIZE]; + + sprintf(name, "test_hash%d", hashtest_key_lens[table_index]); + ut_params.name = name; + ut_params.key_len = hashtest_key_lens[table_index]; + ut_params.socket_id = rte_socket_id(); + h[table_index] = rte_hash_find_existing(name); + if (h[table_index] != NULL) + /* + * If table was already created, free it to create it again, + * so we force it is empty + */ + rte_hash_free(h[table_index]); + h[table_index] = rte_hash_create(&ut_params); + if (h[table_index] == NULL) { + printf("Error creating table\n"); + return -1; + } + return 0; + } -/* - * To help print out name of hash functions. - */ -static const char *get_hash_name(rte_hash_function f) +/* Shuffle the keys that have been added, so lookups will be totally random */ +static void +shuffle_input_keys(unsigned table_index) { - if (f == rte_jhash) - return "jhash"; + unsigned i; + uint32_t swap_idx; + uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX]; + hash_sig_t temp_signature; + int32_t temp_position; - if (f == rte_hash_crc) - return "rte_hash_crc"; + for (i = KEYS_TO_ADD - 1; i > 0; i--) { + swap_idx = rte_rand() % i; - return "UnknownHash"; + memcpy(temp_key, keys[i], hashtest_key_lens[table_index]); + temp_signature = signatures[i]; + temp_position = positions[i]; + + memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]); + signatures[i] = signatures[swap_idx]; + positions[i] = positions[swap_idx]; + + memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]); + signatures[swap_idx] = temp_signature; + positions[swap_idx] = temp_position; + } } /* - * Do a single performance test, of one type of operation. - * - * @param h - * hash table to run test on - * @param func - * function to call (add, delete or lookup function) - * @param avg_occupancy - * The average number of entries in each bucket of the hash table - * @param invalid_pos_count - * The amount of errors (e.g. due to a full bucket). - * @return - * The average number of ticks per hash function call. A negative number - * signifies failure. + * Looks for random keys which + * ALL can fit in hash table (no errors) */ -static double -run_single_tbl_perf_test(const struct rte_hash *h, hash_operation func, - const struct tbl_perf_test_params *params, double *avg_occupancy, - uint32_t *invalid_pos_count) +static int +get_input_keys(unsigned table_index) { - uint64_t begin, end, ticks = 0; - uint8_t *key = NULL; - uint32_t *bucket_occupancies = NULL; - uint32_t num_buckets, i, j; - int32_t pos; - - /* Initialise */ - num_buckets = params->entries / params->bucket_entries; - key = rte_zmalloc("hash key", - params->key_len * sizeof(uint8_t), 16); - if (key == NULL) - return -1; + unsigned i, j; + unsigned bucket_idx, incr, success = 1; + uint8_t k = 0; + int32_t ret; + const uint32_t bucket_bitmask = NUM_BUCKETS - 1; - bucket_occupancies = rte_calloc("bucket occupancies", - num_buckets, sizeof(uint32_t), 16); - if (bucket_occupancies == NULL) { - rte_free(key); - return -1; - } + /* Reset all arrays */ + for (i = 0; i < MAX_ENTRIES; i++) + slot_taken[i] = 0; - ticks = 0; - *invalid_pos_count = 0; + for (i = 0; i < NUM_BUCKETS; i++) + buckets[i] = 0; - for (i = 0; i < params->num_iterations; i++) { - /* Prepare inputs for the current iteration */ - for (j = 0; j < params->key_len; j++) - key[j] = (uint8_t) rte_rand(); + for (j = 0; j < hashtest_key_lens[table_index]; j++) + keys[0][j] = 0; - /* Perform operation, and measure time it takes */ - begin = rte_rdtsc(); - pos = func(h, key); - end = rte_rdtsc(); - ticks += end - begin; + /* + * Add only entries that are not duplicated and that fits in the table + * (cannot store more than BUCKET_SIZE entries in a bucket). + * Regardless a key has been added correctly or not (success), + * the next one to try will be increased by 1. + */ + for (i = 0; i < KEYS_TO_ADD;) { + incr = 0; + if (i != 0) { + keys[i][0] = ++k; + /* Overflow, need to increment the next byte */ + if (keys[i][0] == 0) + incr = 1; + for (j = 1; j < hashtest_key_lens[table_index]; j++) { + /* Do not increase next byte */ + if (incr == 0) + if (success == 1) + keys[i][j] = keys[i - 1][j]; + else + keys[i][j] = keys[i][j]; + /* Increase next byte by one */ + else { + if (success == 1) + keys[i][j] = keys[i-1][j] + 1; + else + keys[i][j] = keys[i][j] + 1; + if (keys[i][j] == 0) + incr = 1; + else + incr = 0; + } + } + } + success = 0; + signatures[i] = rte_hash_hash(h[table_index], keys[i]); + bucket_idx = signatures[i] & bucket_bitmask; + /* If bucket is full, do not try to insert the key */ + if (buckets[bucket_idx] == BUCKET_SIZE) + continue; + /* If key can be added, leave in successful key arrays "keys" */ + ret = rte_hash_add_key_with_hash(h[table_index], keys[i], + signatures[i]); + if (ret >= 0) { + /* If key is already added, ignore the entry and do not store */ + if (slot_taken[ret]) + continue; + else { + /* Store the returned position and mark slot as taken */ + slot_taken[ret] = 1; + buckets[bucket_idx]++; + success = 1; + i++; + } + } + } + + /* Reset the table, so we can measure the time to add all the entries */ + rte_hash_free(h[table_index]); + h[table_index] = rte_hash_create(&ut_params); - /* Other work per iteration */ - if (pos < 0) - *invalid_pos_count += 1; + return 0; +} + +static int +timed_adds(unsigned with_hash, unsigned table_index) +{ + unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + ret = rte_hash_add_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); else - bucket_occupancies[pos / params->bucket_entries]++; + ret = rte_hash_add_key(h[table_index], keys[i]); + + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } } - *avg_occupancy = get_avg(bucket_occupancies, num_buckets); - rte_free(bucket_occupancies); - rte_free(key); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; - return (double)ticks / params->num_iterations; + cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD; + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + return 0; } -/* - * To help print out what tests are being done. - */ -static const char * -get_tbl_perf_test_desc(enum hash_test_t type) +static int +timed_lookups(unsigned with_hash, unsigned table_index) { - switch (type){ - case ADD_ON_EMPTY: return "Add on Empty"; - case DELETE_ON_EMPTY: return "Delete on Empty"; - case LOOKUP_ON_EMPTY: return "Lookup on Empty"; - case ADD_UPDATE: return "Add Update"; - case DELETE: return "Delete"; - case LOOKUP: return "Lookup"; - default: return "UNKNOWN"; + unsigned i, j; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD; j++) { + if (with_hash) + ret = rte_hash_lookup_with_hash(h[table_index], + (const void *) keys[j], + signatures[j]); + else + ret = rte_hash_lookup(h[table_index], keys[j]); + if (ret < 0 || ret != positions[j]) { + printf("Key looked up in %d, should be in %d\n", + ret, positions[j]); + return -1; + } + } } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS; + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + + return 0; } -/* - * Run a hash table performance test based on params. - */ static int -run_tbl_perf_test(struct tbl_perf_test_params *params) +timed_lookups_multi(unsigned table_index) { - static unsigned calledCount = 5; - struct rte_hash_parameters hash_params = { - .entries = params->entries, - .bucket_entries = params->bucket_entries, - .key_len = params->key_len, - .hash_func = params->hash_func, - .hash_func_init_val = params->hash_func_init_val, - .socket_id = rte_socket_id(), - }; - struct rte_hash *handle; - double avg_occupancy = 0, ticks = 0; - uint32_t num_iterations, invalid_pos; - char name[RTE_HASH_NAMESIZE]; - char hashname[RTE_HASH_NAMESIZE]; - - snprintf(name, 32, "test%u", calledCount++); - hash_params.name = name; - - handle = rte_hash_create(&hash_params); - RETURN_IF_ERROR(handle == NULL, "hash creation failed"); - - switch (params->test_type){ - case ADD_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, - params, &avg_occupancy, &invalid_pos); - break; - case DELETE_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, - params, &avg_occupancy, &invalid_pos); - break; - case LOOKUP_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, - params, &avg_occupancy, &invalid_pos); - break; - case ADD_UPDATE: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, - params, &avg_occupancy, &invalid_pos); - break; - case DELETE: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, - params, &avg_occupancy, &invalid_pos); - break; - case LOOKUP: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, - params, &avg_occupancy, &invalid_pos); - break; - default: return -1; + unsigned i, j, k; + int32_t positions_burst[BURST_SIZE]; + const void *keys_burst[BURST_SIZE]; + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) { + for (k = 0; k < BURST_SIZE; k++) + keys_burst[k] = keys[j * BURST_SIZE + k]; + + rte_hash_lookup_bulk(h[table_index], + (const void **) keys_burst, + BURST_SIZE, + positions_burst); + for (k = 0; k < BURST_SIZE; k++) { + if (positions_burst[k] != positions[j * BURST_SIZE + k]) { + printf("Key looked up in %d, should be in %d\n", + positions_burst[k], + positions[j * BURST_SIZE + k]); + return -1; + } + } + } } - snprintf(hashname, RTE_HASH_NAMESIZE, "%s", get_hash_name(params->hash_func)); - - printf("%-12s, %-15s, %-16u, %-7u, %-18u, %-8u, %-19.2f, %.2f\n", - hashname, - get_tbl_perf_test_desc(params->test_type), - (unsigned) params->key_len, - (unsigned) params->entries, - (unsigned) params->bucket_entries, - (unsigned) invalid_pos, - avg_occupancy, - ticks - ); - - /* Free */ - rte_hash_free(handle); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS; + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + return 0; } -/* - * Run all hash table performance tests. - */ -static int run_all_tbl_perf_tests(void) +static int +timed_deletes(unsigned with_hash, unsigned table_index) { unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + ret = rte_hash_del_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); + else + ret = rte_hash_del_key(h[table_index], + (const void *) keys[i]); + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } + } - printf(" *** Hash table performance test results ***\n"); - printf("Hash Func. , Operation , Key size (bytes), Entries, " - "Entries per bucket, Errors , Avg. bucket entries, Ticks/Op.\n"); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; - /* Loop through every combination of test parameters */ - for (i = 0; - i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params); - i++) { + cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD; + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); - /* Perform test */ - if (run_tbl_perf_test(&tbl_perf_params[i]) < 0) + return 0; +} + +static void +free_table(unsigned table_index) +{ + rte_hash_free(h[table_index]); +} + +static int +reset_table(unsigned table_index) +{ + free_table(table_index); + if (create_table(table_index) != 0) + return -1; + + return 0; +} + +static int +run_all_tbl_perf_tests(void) +{ + unsigned i, j; + + printf("Measuring performance, please wait"); + fflush(stdout); + for (i = 0; i < NUM_KEYSIZES; i++) { + if (create_table(i) < 0) return -1; + + if (get_input_keys(i) < 0) + return -1; + + if (timed_adds(0, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + if (timed_lookups(0, i) < 0) + return -1; + + if (timed_lookups_multi(i) < 0) + return -1; + + if (timed_deletes(0, i) < 0) + return -1; + + if (reset_table(i) < 0) + return -1; + + if (timed_adds(1, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + if (timed_lookups(1, i) < 0) + return -1; + + if (timed_deletes(1, i) < 0) + return -1; + + free_table(i); + } + printf("\nResults (in CPU cycles/operation)\n"); + printf("---------------------------------\n"); + printf("\nWithout pre-computed hash values\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); + for (i = 0; i < NUM_KEYSIZES; i++) { + printf("%-18d", hashtest_key_lens[i]); + for (j = 0; j < NUM_OPERATIONS; j++) + printf("%-18"PRIu64, cycles[i][j][0]); + printf("\n"); + } + printf("\nWith pre-computed hash values\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); + for (i = 0; i < NUM_KEYSIZES; i++) { + printf("%-18d", hashtest_key_lens[i]); + for (j = 0; j < NUM_OPERATIONS; j++) + printf("%-18"PRIu64, cycles[i][j][1]); + printf("\n"); } + return 0; } @@ -624,28 +490,34 @@ fbk_hash_perf_test(void) uint64_t lookup_time = 0; unsigned added = 0; unsigned value = 0; + uint32_t key; + uint16_t val; unsigned i, j; handle = rte_fbk_hash_create(¶ms); - RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed"); + if (handle == NULL) { + printf("Error creating table\n"); + return -1; + } keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); - RETURN_IF_ERROR_FBK(keys == NULL, - "fbk hash: memory allocation for key store failed"); + if (keys == NULL) { + printf("fbk hash: memory allocation for key store failed\n"); + return -1; + } /* Generate random keys and values. */ for (i = 0; i < ENTRIES; i++) { - uint32_t key = (uint32_t)rte_rand(); + key = (uint32_t)rte_rand(); key = ((uint64_t)key << 32) | (uint64_t)rte_rand(); - uint16_t val = (uint16_t)rte_rand(); + val = (uint16_t)rte_rand(); if (rte_fbk_hash_add_key(handle, key, val) == 0) { keys[added] = key; added++; } - if (added > (LOAD_FACTOR * ENTRIES)) { + if (added > (LOAD_FACTOR * ENTRIES)) break; - } } for (i = 0; i < TEST_ITERATIONS; i++) { @@ -653,15 +525,14 @@ fbk_hash_perf_test(void) uint64_t end; /* Generate random indexes into keys[] array. */ - for (j = 0; j < TEST_SIZE; j++) { + for (j = 0; j < TEST_SIZE; j++) indexes[j] = rte_rand() % added; - } begin = rte_rdtsc(); /* Do lookups */ - for (j = 0; j < TEST_SIZE; j++) { + for (j = 0; j < TEST_SIZE; j++) value += rte_fbk_hash_lookup(handle, keys[indexes[j]]); - } + end = rte_rdtsc(); lookup_time += (double)(end - begin); } @@ -681,9 +552,6 @@ fbk_hash_perf_test(void) return 0; } -/* - * Do all unit and performance tests. - */ static int test_hash_perf(void) { @@ -692,11 +560,12 @@ test_hash_perf(void) if (fbk_hash_perf_test() < 0) return -1; + return 0; } static struct test_command hash_perf_cmd = { - .command = "hash_perf_autotest", - .callback = test_hash_perf, + .command = "hash_perf_autotest", + .callback = test_hash_perf, }; REGISTER_TEST_COMMAND(hash_perf_cmd); -- 2.4.2 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v3] Improve hash unit tests - Cuckoo hash part 2 2015-07-08 16:30 ` [PATCH v2] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 2015-07-08 16:30 ` [PATCH v2] test/hash: improve hash unit tests Pablo de Lara @ 2015-07-09 12:19 ` Pablo de Lara 2015-07-09 12:19 ` [PATCH v3] test/hash: improve hash unit tests Pablo de Lara 1 sibling, 1 reply; 13+ messages in thread From: Pablo de Lara @ 2015-07-09 12:19 UTC (permalink / raw) To: dev This patch improves the unit tests for the hash library, showing more readable results, in preparation for the new hash implementation to show performance differences. Changes in v3: - Increase table utilization in performance unit tests Changes in v2: - Add missing error check - Simplify average table utilization test - Improve outputs - Fix some typos Pablo de Lara (1): test/hash: improve hash unit tests app/test/test_hash.c | 66 +++- app/test/test_hash_perf.c | 927 ++++++++++++++++++++-------------------------- 2 files changed, 462 insertions(+), 531 deletions(-) -- 2.4.2 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v3] test/hash: improve hash unit tests 2015-07-09 12:19 ` [PATCH v3] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara @ 2015-07-09 12:19 ` Pablo de Lara 2015-07-09 16:54 ` [PATCH v4] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 0 siblings, 1 reply; 13+ messages in thread From: Pablo de Lara @ 2015-07-09 12:19 UTC (permalink / raw) To: dev Add new unit test for calculating the average table utilization, using random keys, based on number of entries that can be added until we encounter one that cannot be added (bucket if full) Also, replace current hash_perf unit test to see performance more clear. The current hash_perf unit test takes too long and add keys that may or may not fit in the table and look up/delete that may not be in the table. This new unit test gets a set of keys that we know that fits in the table, and then measure the time to add/look up/delete them. Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com> --- app/test/test_hash.c | 66 +++- app/test/test_hash_perf.c | 927 ++++++++++++++++++++-------------------------- 2 files changed, 462 insertions(+), 531 deletions(-) diff --git a/app/test/test_hash.c b/app/test/test_hash.c index 4300de9..7c71ed6 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -190,7 +190,7 @@ test_crc32_hash_alg_equiv(void) unsigned i, j; size_t data_len; - printf("# CRC32 implementations equivalence test\n"); + printf("\n# CRC32 implementations equivalence test\n"); for (i = 0; i < CRC32_ITERATIONS; i++) { /* Randomizing data_len of data set */ data_len = (size_t) ((rte_rand() % sizeof(data64)) + 1); @@ -785,7 +785,7 @@ fbk_hash_unit_test(void) /* Try creating hashes with invalid parameters */ printf("# Testing hash creation with invalid parameters " - "- expert error msgs\n"); + "- expect error msgs\n"); handle = rte_fbk_hash_create(&invalid_params_1); RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); @@ -1087,6 +1087,7 @@ static int test_hash_creation_with_bad_parameters(void) } rte_hash_free(handle); + printf("# Test successful. No more errors expected\n"); return 0; } @@ -1147,6 +1148,65 @@ test_hash_creation_with_good_parameters(void) return 0; } +#define ITERATIONS 50 +/* + * Test to see the average table utilization (entries added/max entries) + * before hitting a random entry that cannot be added + */ +static int test_average_table_utilization(void) +{ + struct rte_hash *handle; + uint8_t simple_key[RTE_HASH_KEY_LENGTH_MAX]; + unsigned i, j; + unsigned added_keys, average_keys_added = 0; + int ret; + + printf("\n# Running test to determine average utilization" + "\n before adding elements begins to fail\n"); + printf("Measuring performance, please wait"); + fflush(stdout); + ut_params.entries = 1 << 20; + ut_params.name = "test_average_utilization"; + ut_params.hash_func = rte_jhash; + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + for (j = 0; j < ITERATIONS; j++) { + ret = 0; + /* Add random entries until key cannot be added */ + for (added_keys = 0; ret >= 0; added_keys++) { + for (i = 0; i < ut_params.key_len; i++) + simple_key[i] = rte_rand() % 255; + ret = rte_hash_add_key(handle, simple_key); + } + if (ret != -ENOSPC) { + printf("Unexpected error when adding keys\n"); + rte_hash_free(handle); + return -1; + } + + average_keys_added += added_keys; + + /* Reset the table */ + rte_hash_free(handle); + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + } + + average_keys_added /= ITERATIONS; + + printf("\nAverage table utilization = %.2f%% (%u/%u)\n", + ((double) average_keys_added / ut_params.entries * 100), + average_keys_added, ut_params.entries); + rte_hash_free(handle); + + return 0; +} + static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, @@ -1405,6 +1465,8 @@ test_hash(void) return -1; if (test_hash_creation_with_good_parameters() < 0) return -1; + if (test_average_table_utilization() < 0) + return -1; run_hash_func_tests(); diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c index d0e5ce0..7acba59 100644 --- a/app/test/test_hash_perf.c +++ b/app/test/test_hash_perf.c @@ -32,574 +32,440 @@ */ #include <stdio.h> -#include <stdint.h> -#include <string.h> -#include <stdlib.h> -#include <stdarg.h> -#include <errno.h> -#include <sys/queue.h> - -#include <rte_common.h> +#include <inttypes.h> + #include <rte_lcore.h> -#include <rte_malloc.h> #include <rte_cycles.h> +#include <rte_malloc.h> +#include <rte_hash.h> +#include <rte_hash_crc.h> +#include <rte_jhash.h> +#include <rte_fbk_hash.h> #include <rte_random.h> -#include <rte_memory.h> -#include <rte_memzone.h> -#include <rte_eal.h> -#include <rte_ip.h> #include <rte_string_fns.h> #include "test.h" -#include <rte_hash.h> -#include <rte_fbk_hash.h> -#include <rte_jhash.h> -#include <rte_hash_crc.h> - -/* Types of hash table performance test that can be performed */ -enum hash_test_t { - ADD_ON_EMPTY, /*< Add keys to empty table */ - DELETE_ON_EMPTY, /*< Attempt to delete keys from empty table */ - LOOKUP_ON_EMPTY, /*< Attempt to find keys in an empty table */ - ADD_UPDATE, /*< Add/update keys in a full table */ - DELETE, /*< Delete keys from a full table */ - LOOKUP /*< Find keys in a full table */ +#define MAX_ENTRIES (1 << 20) +#define KEYS_TO_ADD (MAX_ENTRIES * 3 / 4) /* 75% table utilization */ +#define NUM_LOOKUPS (KEYS_TO_ADD * 10) /* Loop among keys added, several times */ +#define BUCKET_SIZE 4 +#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE) +#define MAX_KEYSIZE 64 +#define NUM_KEYSIZES 10 +#define NUM_SHUFFLES 10 +#define BURST_SIZE 16 + +enum operations { + ADD = 0, + LOOKUP, + LOOKUP_MULTI, + DELETE, + NUM_OPERATIONS }; -/* Function type for hash table operations. */ -typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key); - -/* Structure to hold parameters used to run a hash table performance test */ -struct tbl_perf_test_params { - enum hash_test_t test_type; - uint32_t num_iterations; - uint32_t entries; - uint32_t bucket_entries; - uint32_t key_len; - rte_hash_function hash_func; - uint32_t hash_func_init_val; +static uint32_t hashtest_key_lens[] = { + /* standard key sizes */ + 4, 8, 16, 32, 48, 64, + /* IPv4 SRC + DST + protocol, unpadded */ + 9, + /* IPv4 5-tuple, unpadded */ + 13, + /* IPv6 5-tuple, unpadded */ + 37, + /* IPv6 5-tuple, padded to 8-byte boundary */ + 40 }; -#define ITERATIONS 10000 -#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15) +struct rte_hash *h[NUM_KEYSIZES]; -/******************************************************************************* - * Hash table performance test configuration section. - */ -struct tbl_perf_test_params tbl_perf_params[] = -{ -/* Small table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_jhash, 0}, -/* Small table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, -/* Small table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, -/* Big table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_jhash, 0}, -/* Big table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, -/* Big table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, -/* Small table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_hash_crc, 0}, -/* Small table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, -/* Small table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, -/* Big table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_hash_crc, 0}, -/* Big table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, -/* Big table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, -}; +/* Array that stores if a slot is full */ +uint8_t slot_taken[MAX_ENTRIES]; -/******************************************************************************/ +/* Array to store number of cycles per operation */ +uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2]; -/* - * Check condition and return an error if true. Assumes that "handle" is the - * name of the hash structure pointer to be freed. - */ -#define RETURN_IF_ERROR(cond, str, ...) do { \ - if (cond) { \ - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ - if (handle) rte_hash_free(handle); \ - return -1; \ - } \ -} while(0) - -#define RETURN_IF_ERROR_FBK(cond, str, ...) do { \ - if (cond) { \ - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ - if (handle) rte_fbk_hash_free(handle); \ - rte_free(keys); \ - return -1; \ - } \ -} while(0) +/* Array to store all input keys */ +uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; -/* - * Find average of array of numbers. - */ -static double -get_avg(const uint32_t *array, uint32_t size) +/* Array to store the precomputed hash for 'keys' */ +hash_sig_t signatures[KEYS_TO_ADD]; + +/* Array to store how many busy entries have each bucket */ +uint8_t buckets[NUM_BUCKETS]; + +/* Array to store the positions where keys are added */ +int32_t positions[KEYS_TO_ADD]; + +/* Parameters used for hash table in unit test functions. */ +static struct rte_hash_parameters ut_params = { + .entries = MAX_ENTRIES, + .bucket_entries = BUCKET_SIZE, + .hash_func = rte_jhash, + .hash_func_init_val = 0, +}; + +static int +create_table(unsigned table_index) { - double sum = 0; - unsigned i; - for (i = 0; i < size; i++) - sum += array[i]; - return sum / (double)size; + char name[RTE_HASH_NAMESIZE]; + + sprintf(name, "test_hash%d", hashtest_key_lens[table_index]); + ut_params.name = name; + ut_params.key_len = hashtest_key_lens[table_index]; + ut_params.socket_id = rte_socket_id(); + h[table_index] = rte_hash_find_existing(name); + if (h[table_index] != NULL) + /* + * If table was already created, free it to create it again, + * so we force it is empty + */ + rte_hash_free(h[table_index]); + h[table_index] = rte_hash_create(&ut_params); + if (h[table_index] == NULL) { + printf("Error creating table\n"); + return -1; + } + return 0; + } -/* - * To help print out name of hash functions. - */ -static const char *get_hash_name(rte_hash_function f) +/* Shuffle the keys that have been added, so lookups will be totally random */ +static void +shuffle_input_keys(unsigned table_index) { - if (f == rte_jhash) - return "jhash"; + unsigned i; + uint32_t swap_idx; + uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX]; + hash_sig_t temp_signature; + int32_t temp_position; - if (f == rte_hash_crc) - return "rte_hash_crc"; + for (i = KEYS_TO_ADD - 1; i > 0; i--) { + swap_idx = rte_rand() % i; - return "UnknownHash"; + memcpy(temp_key, keys[i], hashtest_key_lens[table_index]); + temp_signature = signatures[i]; + temp_position = positions[i]; + + memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]); + signatures[i] = signatures[swap_idx]; + positions[i] = positions[swap_idx]; + + memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]); + signatures[swap_idx] = temp_signature; + positions[swap_idx] = temp_position; + } } /* - * Do a single performance test, of one type of operation. - * - * @param h - * hash table to run test on - * @param func - * function to call (add, delete or lookup function) - * @param avg_occupancy - * The average number of entries in each bucket of the hash table - * @param invalid_pos_count - * The amount of errors (e.g. due to a full bucket). - * @return - * The average number of ticks per hash function call. A negative number - * signifies failure. + * Looks for random keys which + * ALL can fit in hash table (no errors) */ -static double -run_single_tbl_perf_test(const struct rte_hash *h, hash_operation func, - const struct tbl_perf_test_params *params, double *avg_occupancy, - uint32_t *invalid_pos_count) +static int +get_input_keys(unsigned table_index) { - uint64_t begin, end, ticks = 0; - uint8_t *key = NULL; - uint32_t *bucket_occupancies = NULL; - uint32_t num_buckets, i, j; - int32_t pos; - - /* Initialise */ - num_buckets = params->entries / params->bucket_entries; - key = rte_zmalloc("hash key", - params->key_len * sizeof(uint8_t), 16); - if (key == NULL) - return -1; + unsigned i, j; + unsigned bucket_idx, incr, success = 1; + uint8_t k = 0; + int32_t ret; + const uint32_t bucket_bitmask = NUM_BUCKETS - 1; - bucket_occupancies = rte_calloc("bucket occupancies", - num_buckets, sizeof(uint32_t), 16); - if (bucket_occupancies == NULL) { - rte_free(key); - return -1; - } + /* Reset all arrays */ + for (i = 0; i < MAX_ENTRIES; i++) + slot_taken[i] = 0; - ticks = 0; - *invalid_pos_count = 0; + for (i = 0; i < NUM_BUCKETS; i++) + buckets[i] = 0; - for (i = 0; i < params->num_iterations; i++) { - /* Prepare inputs for the current iteration */ - for (j = 0; j < params->key_len; j++) - key[j] = (uint8_t) rte_rand(); + for (j = 0; j < hashtest_key_lens[table_index]; j++) + keys[0][j] = 0; - /* Perform operation, and measure time it takes */ - begin = rte_rdtsc(); - pos = func(h, key); - end = rte_rdtsc(); - ticks += end - begin; + /* + * Add only entries that are not duplicated and that fits in the table + * (cannot store more than BUCKET_SIZE entries in a bucket). + * Regardless a key has been added correctly or not (success), + * the next one to try will be increased by 1. + */ + for (i = 0; i < KEYS_TO_ADD;) { + incr = 0; + if (i != 0) { + keys[i][0] = ++k; + /* Overflow, need to increment the next byte */ + if (keys[i][0] == 0) + incr = 1; + for (j = 1; j < hashtest_key_lens[table_index]; j++) { + /* Do not increase next byte */ + if (incr == 0) + if (success == 1) + keys[i][j] = keys[i - 1][j]; + else + keys[i][j] = keys[i][j]; + /* Increase next byte by one */ + else { + if (success == 1) + keys[i][j] = keys[i-1][j] + 1; + else + keys[i][j] = keys[i][j] + 1; + if (keys[i][j] == 0) + incr = 1; + else + incr = 0; + } + } + } + success = 0; + signatures[i] = rte_hash_hash(h[table_index], keys[i]); + bucket_idx = signatures[i] & bucket_bitmask; + /* If bucket is full, do not try to insert the key */ + if (buckets[bucket_idx] == BUCKET_SIZE) + continue; + /* If key can be added, leave in successful key arrays "keys" */ + ret = rte_hash_add_key_with_hash(h[table_index], keys[i], + signatures[i]); + if (ret >= 0) { + /* If key is already added, ignore the entry and do not store */ + if (slot_taken[ret]) + continue; + else { + /* Store the returned position and mark slot as taken */ + slot_taken[ret] = 1; + buckets[bucket_idx]++; + success = 1; + i++; + } + } + } + + /* Reset the table, so we can measure the time to add all the entries */ + rte_hash_free(h[table_index]); + h[table_index] = rte_hash_create(&ut_params); - /* Other work per iteration */ - if (pos < 0) - *invalid_pos_count += 1; + return 0; +} + +static int +timed_adds(unsigned with_hash, unsigned table_index) +{ + unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + ret = rte_hash_add_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); else - bucket_occupancies[pos / params->bucket_entries]++; + ret = rte_hash_add_key(h[table_index], keys[i]); + + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } } - *avg_occupancy = get_avg(bucket_occupancies, num_buckets); - rte_free(bucket_occupancies); - rte_free(key); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; - return (double)ticks / params->num_iterations; + cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD; + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + return 0; } -/* - * To help print out what tests are being done. - */ -static const char * -get_tbl_perf_test_desc(enum hash_test_t type) +static int +timed_lookups(unsigned with_hash, unsigned table_index) { - switch (type){ - case ADD_ON_EMPTY: return "Add on Empty"; - case DELETE_ON_EMPTY: return "Delete on Empty"; - case LOOKUP_ON_EMPTY: return "Lookup on Empty"; - case ADD_UPDATE: return "Add Update"; - case DELETE: return "Delete"; - case LOOKUP: return "Lookup"; - default: return "UNKNOWN"; + unsigned i, j; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD; j++) { + if (with_hash) + ret = rte_hash_lookup_with_hash(h[table_index], + (const void *) keys[j], + signatures[j]); + else + ret = rte_hash_lookup(h[table_index], keys[j]); + if (ret < 0 || ret != positions[j]) { + printf("Key looked up in %d, should be in %d\n", + ret, positions[j]); + return -1; + } + } } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS; + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + + return 0; } -/* - * Run a hash table performance test based on params. - */ static int -run_tbl_perf_test(struct tbl_perf_test_params *params) +timed_lookups_multi(unsigned table_index) { - static unsigned calledCount = 5; - struct rte_hash_parameters hash_params = { - .entries = params->entries, - .bucket_entries = params->bucket_entries, - .key_len = params->key_len, - .hash_func = params->hash_func, - .hash_func_init_val = params->hash_func_init_val, - .socket_id = rte_socket_id(), - }; - struct rte_hash *handle; - double avg_occupancy = 0, ticks = 0; - uint32_t num_iterations, invalid_pos; - char name[RTE_HASH_NAMESIZE]; - char hashname[RTE_HASH_NAMESIZE]; - - snprintf(name, 32, "test%u", calledCount++); - hash_params.name = name; - - handle = rte_hash_create(&hash_params); - RETURN_IF_ERROR(handle == NULL, "hash creation failed"); - - switch (params->test_type){ - case ADD_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, - params, &avg_occupancy, &invalid_pos); - break; - case DELETE_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, - params, &avg_occupancy, &invalid_pos); - break; - case LOOKUP_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, - params, &avg_occupancy, &invalid_pos); - break; - case ADD_UPDATE: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, - params, &avg_occupancy, &invalid_pos); - break; - case DELETE: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, - params, &avg_occupancy, &invalid_pos); - break; - case LOOKUP: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, - params, &avg_occupancy, &invalid_pos); - break; - default: return -1; + unsigned i, j, k; + int32_t positions_burst[BURST_SIZE]; + const void *keys_burst[BURST_SIZE]; + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) { + for (k = 0; k < BURST_SIZE; k++) + keys_burst[k] = keys[j * BURST_SIZE + k]; + + rte_hash_lookup_bulk(h[table_index], + (const void **) keys_burst, + BURST_SIZE, + positions_burst); + for (k = 0; k < BURST_SIZE; k++) { + if (positions_burst[k] != positions[j * BURST_SIZE + k]) { + printf("Key looked up in %d, should be in %d\n", + positions_burst[k], + positions[j * BURST_SIZE + k]); + return -1; + } + } + } } - snprintf(hashname, RTE_HASH_NAMESIZE, "%s", get_hash_name(params->hash_func)); - - printf("%-12s, %-15s, %-16u, %-7u, %-18u, %-8u, %-19.2f, %.2f\n", - hashname, - get_tbl_perf_test_desc(params->test_type), - (unsigned) params->key_len, - (unsigned) params->entries, - (unsigned) params->bucket_entries, - (unsigned) invalid_pos, - avg_occupancy, - ticks - ); - - /* Free */ - rte_hash_free(handle); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS; + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + return 0; } -/* - * Run all hash table performance tests. - */ -static int run_all_tbl_perf_tests(void) +static int +timed_deletes(unsigned with_hash, unsigned table_index) { unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + ret = rte_hash_del_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); + else + ret = rte_hash_del_key(h[table_index], + (const void *) keys[i]); + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } + } - printf(" *** Hash table performance test results ***\n"); - printf("Hash Func. , Operation , Key size (bytes), Entries, " - "Entries per bucket, Errors , Avg. bucket entries, Ticks/Op.\n"); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; - /* Loop through every combination of test parameters */ - for (i = 0; - i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params); - i++) { + cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD; + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); - /* Perform test */ - if (run_tbl_perf_test(&tbl_perf_params[i]) < 0) + return 0; +} + +static void +free_table(unsigned table_index) +{ + rte_hash_free(h[table_index]); +} + +static int +reset_table(unsigned table_index) +{ + free_table(table_index); + if (create_table(table_index) != 0) + return -1; + + return 0; +} + +static int +run_all_tbl_perf_tests(void) +{ + unsigned i, j; + + printf("Measuring performance, please wait"); + fflush(stdout); + for (i = 0; i < NUM_KEYSIZES; i++) { + if (create_table(i) < 0) return -1; + + if (get_input_keys(i) < 0) + return -1; + + if (timed_adds(0, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + if (timed_lookups(0, i) < 0) + return -1; + + if (timed_lookups_multi(i) < 0) + return -1; + + if (timed_deletes(0, i) < 0) + return -1; + + if (reset_table(i) < 0) + return -1; + + if (timed_adds(1, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + if (timed_lookups(1, i) < 0) + return -1; + + if (timed_deletes(1, i) < 0) + return -1; + + free_table(i); + } + printf("\nResults (in CPU cycles/operation)\n"); + printf("---------------------------------\n"); + printf("\nWithout pre-computed hash values\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); + for (i = 0; i < NUM_KEYSIZES; i++) { + printf("%-18d", hashtest_key_lens[i]); + for (j = 0; j < NUM_OPERATIONS; j++) + printf("%-18"PRIu64, cycles[i][j][0]); + printf("\n"); + } + printf("\nWith pre-computed hash values\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); + for (i = 0; i < NUM_KEYSIZES; i++) { + printf("%-18d", hashtest_key_lens[i]); + for (j = 0; j < NUM_OPERATIONS; j++) + printf("%-18"PRIu64, cycles[i][j][1]); + printf("\n"); } + return 0; } @@ -624,28 +490,34 @@ fbk_hash_perf_test(void) uint64_t lookup_time = 0; unsigned added = 0; unsigned value = 0; + uint32_t key; + uint16_t val; unsigned i, j; handle = rte_fbk_hash_create(¶ms); - RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed"); + if (handle == NULL) { + printf("Error creating table\n"); + return -1; + } keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); - RETURN_IF_ERROR_FBK(keys == NULL, - "fbk hash: memory allocation for key store failed"); + if (keys == NULL) { + printf("fbk hash: memory allocation for key store failed\n"); + return -1; + } /* Generate random keys and values. */ for (i = 0; i < ENTRIES; i++) { - uint32_t key = (uint32_t)rte_rand(); + key = (uint32_t)rte_rand(); key = ((uint64_t)key << 32) | (uint64_t)rte_rand(); - uint16_t val = (uint16_t)rte_rand(); + val = (uint16_t)rte_rand(); if (rte_fbk_hash_add_key(handle, key, val) == 0) { keys[added] = key; added++; } - if (added > (LOAD_FACTOR * ENTRIES)) { + if (added > (LOAD_FACTOR * ENTRIES)) break; - } } for (i = 0; i < TEST_ITERATIONS; i++) { @@ -653,15 +525,14 @@ fbk_hash_perf_test(void) uint64_t end; /* Generate random indexes into keys[] array. */ - for (j = 0; j < TEST_SIZE; j++) { + for (j = 0; j < TEST_SIZE; j++) indexes[j] = rte_rand() % added; - } begin = rte_rdtsc(); /* Do lookups */ - for (j = 0; j < TEST_SIZE; j++) { + for (j = 0; j < TEST_SIZE; j++) value += rte_fbk_hash_lookup(handle, keys[indexes[j]]); - } + end = rte_rdtsc(); lookup_time += (double)(end - begin); } @@ -681,9 +552,6 @@ fbk_hash_perf_test(void) return 0; } -/* - * Do all unit and performance tests. - */ static int test_hash_perf(void) { @@ -692,11 +560,12 @@ test_hash_perf(void) if (fbk_hash_perf_test() < 0) return -1; + return 0; } static struct test_command hash_perf_cmd = { - .command = "hash_perf_autotest", - .callback = test_hash_perf, + .command = "hash_perf_autotest", + .callback = test_hash_perf, }; REGISTER_TEST_COMMAND(hash_perf_cmd); -- 2.4.2 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v4] Improve hash unit tests - Cuckoo hash part 2 2015-07-09 12:19 ` [PATCH v3] test/hash: improve hash unit tests Pablo de Lara @ 2015-07-09 16:54 ` Pablo de Lara 2015-07-09 16:54 ` [PATCH v4] test/hash: improve hash unit tests Pablo de Lara 0 siblings, 1 reply; 13+ messages in thread From: Pablo de Lara @ 2015-07-09 16:54 UTC (permalink / raw) To: dev This patch improves the unit tests for the hash library, showing more readable results, in preparation for the new hash implementation to show performance differences. Changes in v4: - Reduce test time, by reducing number of added keys/iterations, as test was taking too long. - Reduce number of dots indicating progress (there were too many) - Add additional information in commit message. Changes in v3: - Increase table utilization in performance unit tests Changes in v2: - Add missing error check - Simplify average table utilization test - Improve outputs - Fix some typos Pablo de Lara (1): test/hash: improve hash unit tests app/test/test_hash.c | 66 +++- app/test/test_hash_perf.c | 923 ++++++++++++++++++++-------------------------- 2 files changed, 458 insertions(+), 531 deletions(-) -- 2.4.2 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v4] test/hash: improve hash unit tests 2015-07-09 16:54 ` [PATCH v4] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara @ 2015-07-09 16:54 ` Pablo de Lara 2015-07-10 9:11 ` Bruce Richardson 0 siblings, 1 reply; 13+ messages in thread From: Pablo de Lara @ 2015-07-09 16:54 UTC (permalink / raw) To: dev Add new unit test for calculating the average table utilization, using random keys, based on number of entries that can be added until we encounter one that cannot be added (bucket if full). Also, replace current hash_perf unit test to see performance more clear. The current hash_perf unit test takes too long and add keys that may or may not fit in the table and look up/delete that may not be in the table. This new unit test gets a set of keys that we know that fits in the table, and then measure the time to add/look up/delete them. Mind that performance numbers include time to take a random key from a pre-made array of keys, plus a quick check of return value. Also, as stated above, expect higher numbers, as all operations in the new unit tests will be successful, which means that it will take more time, than mixing both successful and unsuccesful operations. Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com> --- app/test/test_hash.c | 66 +++- app/test/test_hash_perf.c | 923 ++++++++++++++++++++-------------------------- 2 files changed, 458 insertions(+), 531 deletions(-) diff --git a/app/test/test_hash.c b/app/test/test_hash.c index 4300de9..7c71ed6 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -190,7 +190,7 @@ test_crc32_hash_alg_equiv(void) unsigned i, j; size_t data_len; - printf("# CRC32 implementations equivalence test\n"); + printf("\n# CRC32 implementations equivalence test\n"); for (i = 0; i < CRC32_ITERATIONS; i++) { /* Randomizing data_len of data set */ data_len = (size_t) ((rte_rand() % sizeof(data64)) + 1); @@ -785,7 +785,7 @@ fbk_hash_unit_test(void) /* Try creating hashes with invalid parameters */ printf("# Testing hash creation with invalid parameters " - "- expert error msgs\n"); + "- expect error msgs\n"); handle = rte_fbk_hash_create(&invalid_params_1); RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); @@ -1087,6 +1087,7 @@ static int test_hash_creation_with_bad_parameters(void) } rte_hash_free(handle); + printf("# Test successful. No more errors expected\n"); return 0; } @@ -1147,6 +1148,65 @@ test_hash_creation_with_good_parameters(void) return 0; } +#define ITERATIONS 50 +/* + * Test to see the average table utilization (entries added/max entries) + * before hitting a random entry that cannot be added + */ +static int test_average_table_utilization(void) +{ + struct rte_hash *handle; + uint8_t simple_key[RTE_HASH_KEY_LENGTH_MAX]; + unsigned i, j; + unsigned added_keys, average_keys_added = 0; + int ret; + + printf("\n# Running test to determine average utilization" + "\n before adding elements begins to fail\n"); + printf("Measuring performance, please wait"); + fflush(stdout); + ut_params.entries = 1 << 20; + ut_params.name = "test_average_utilization"; + ut_params.hash_func = rte_jhash; + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + for (j = 0; j < ITERATIONS; j++) { + ret = 0; + /* Add random entries until key cannot be added */ + for (added_keys = 0; ret >= 0; added_keys++) { + for (i = 0; i < ut_params.key_len; i++) + simple_key[i] = rte_rand() % 255; + ret = rte_hash_add_key(handle, simple_key); + } + if (ret != -ENOSPC) { + printf("Unexpected error when adding keys\n"); + rte_hash_free(handle); + return -1; + } + + average_keys_added += added_keys; + + /* Reset the table */ + rte_hash_free(handle); + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + } + + average_keys_added /= ITERATIONS; + + printf("\nAverage table utilization = %.2f%% (%u/%u)\n", + ((double) average_keys_added / ut_params.entries * 100), + average_keys_added, ut_params.entries); + rte_hash_free(handle); + + return 0; +} + static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, @@ -1405,6 +1465,8 @@ test_hash(void) return -1; if (test_hash_creation_with_good_parameters() < 0) return -1; + if (test_average_table_utilization() < 0) + return -1; run_hash_func_tests(); diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c index d0e5ce0..a3876c1 100644 --- a/app/test/test_hash_perf.c +++ b/app/test/test_hash_perf.c @@ -32,574 +32,436 @@ */ #include <stdio.h> -#include <stdint.h> -#include <string.h> -#include <stdlib.h> -#include <stdarg.h> -#include <errno.h> -#include <sys/queue.h> - -#include <rte_common.h> +#include <inttypes.h> + #include <rte_lcore.h> -#include <rte_malloc.h> #include <rte_cycles.h> +#include <rte_malloc.h> +#include <rte_hash.h> +#include <rte_hash_crc.h> +#include <rte_jhash.h> +#include <rte_fbk_hash.h> #include <rte_random.h> -#include <rte_memory.h> -#include <rte_memzone.h> -#include <rte_eal.h> -#include <rte_ip.h> #include <rte_string_fns.h> #include "test.h" -#include <rte_hash.h> -#include <rte_fbk_hash.h> -#include <rte_jhash.h> -#include <rte_hash_crc.h> - -/* Types of hash table performance test that can be performed */ -enum hash_test_t { - ADD_ON_EMPTY, /*< Add keys to empty table */ - DELETE_ON_EMPTY, /*< Attempt to delete keys from empty table */ - LOOKUP_ON_EMPTY, /*< Attempt to find keys in an empty table */ - ADD_UPDATE, /*< Add/update keys in a full table */ - DELETE, /*< Delete keys from a full table */ - LOOKUP /*< Find keys in a full table */ +#define MAX_ENTRIES (1 << 19) +#define KEYS_TO_ADD (MAX_ENTRIES * 3 / 4) /* 75% table utilization */ +#define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */ +#define BUCKET_SIZE 4 +#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE) +#define MAX_KEYSIZE 64 +#define NUM_KEYSIZES 10 +#define NUM_SHUFFLES 10 +#define BURST_SIZE 16 + +enum operations { + ADD = 0, + LOOKUP, + LOOKUP_MULTI, + DELETE, + NUM_OPERATIONS }; -/* Function type for hash table operations. */ -typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key); - -/* Structure to hold parameters used to run a hash table performance test */ -struct tbl_perf_test_params { - enum hash_test_t test_type; - uint32_t num_iterations; - uint32_t entries; - uint32_t bucket_entries; - uint32_t key_len; - rte_hash_function hash_func; - uint32_t hash_func_init_val; +static uint32_t hashtest_key_lens[] = { + /* standard key sizes */ + 4, 8, 16, 32, 48, 64, + /* IPv4 SRC + DST + protocol, unpadded */ + 9, + /* IPv4 5-tuple, unpadded */ + 13, + /* IPv6 5-tuple, unpadded */ + 37, + /* IPv6 5-tuple, padded to 8-byte boundary */ + 40 }; -#define ITERATIONS 10000 -#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15) +struct rte_hash *h[NUM_KEYSIZES]; -/******************************************************************************* - * Hash table performance test configuration section. - */ -struct tbl_perf_test_params tbl_perf_params[] = -{ -/* Small table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_jhash, 0}, -/* Small table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, -/* Small table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, -/* Big table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_jhash, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_jhash, 0}, -/* Big table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, -/* Big table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, -/* Small table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_hash_crc, 0}, -/* Small table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, -/* Small table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, -/* Big table, add */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_hash_crc, 0}, -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_hash_crc, 0}, -/* Big table, update */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, -/* Big table, lookup */ -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, -}; +/* Array that stores if a slot is full */ +uint8_t slot_taken[MAX_ENTRIES]; -/******************************************************************************/ +/* Array to store number of cycles per operation */ +uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2]; -/* - * Check condition and return an error if true. Assumes that "handle" is the - * name of the hash structure pointer to be freed. - */ -#define RETURN_IF_ERROR(cond, str, ...) do { \ - if (cond) { \ - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ - if (handle) rte_hash_free(handle); \ - return -1; \ - } \ -} while(0) - -#define RETURN_IF_ERROR_FBK(cond, str, ...) do { \ - if (cond) { \ - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ - if (handle) rte_fbk_hash_free(handle); \ - rte_free(keys); \ - return -1; \ - } \ -} while(0) +/* Array to store all input keys */ +uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; -/* - * Find average of array of numbers. - */ -static double -get_avg(const uint32_t *array, uint32_t size) +/* Array to store the precomputed hash for 'keys' */ +hash_sig_t signatures[KEYS_TO_ADD]; + +/* Array to store how many busy entries have each bucket */ +uint8_t buckets[NUM_BUCKETS]; + +/* Array to store the positions where keys are added */ +int32_t positions[KEYS_TO_ADD]; + +/* Parameters used for hash table in unit test functions. */ +static struct rte_hash_parameters ut_params = { + .entries = MAX_ENTRIES, + .bucket_entries = BUCKET_SIZE, + .hash_func = rte_jhash, + .hash_func_init_val = 0, +}; + +static int +create_table(unsigned table_index) { - double sum = 0; - unsigned i; - for (i = 0; i < size; i++) - sum += array[i]; - return sum / (double)size; + char name[RTE_HASH_NAMESIZE]; + + sprintf(name, "test_hash%d", hashtest_key_lens[table_index]); + ut_params.name = name; + ut_params.key_len = hashtest_key_lens[table_index]; + ut_params.socket_id = rte_socket_id(); + h[table_index] = rte_hash_find_existing(name); + if (h[table_index] != NULL) + /* + * If table was already created, free it to create it again, + * so we force it is empty + */ + rte_hash_free(h[table_index]); + h[table_index] = rte_hash_create(&ut_params); + if (h[table_index] == NULL) { + printf("Error creating table\n"); + return -1; + } + return 0; + } -/* - * To help print out name of hash functions. - */ -static const char *get_hash_name(rte_hash_function f) +/* Shuffle the keys that have been added, so lookups will be totally random */ +static void +shuffle_input_keys(unsigned table_index) { - if (f == rte_jhash) - return "jhash"; + unsigned i; + uint32_t swap_idx; + uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX]; + hash_sig_t temp_signature; + int32_t temp_position; - if (f == rte_hash_crc) - return "rte_hash_crc"; + for (i = KEYS_TO_ADD - 1; i > 0; i--) { + swap_idx = rte_rand() % i; - return "UnknownHash"; + memcpy(temp_key, keys[i], hashtest_key_lens[table_index]); + temp_signature = signatures[i]; + temp_position = positions[i]; + + memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]); + signatures[i] = signatures[swap_idx]; + positions[i] = positions[swap_idx]; + + memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]); + signatures[swap_idx] = temp_signature; + positions[swap_idx] = temp_position; + } } /* - * Do a single performance test, of one type of operation. - * - * @param h - * hash table to run test on - * @param func - * function to call (add, delete or lookup function) - * @param avg_occupancy - * The average number of entries in each bucket of the hash table - * @param invalid_pos_count - * The amount of errors (e.g. due to a full bucket). - * @return - * The average number of ticks per hash function call. A negative number - * signifies failure. + * Looks for random keys which + * ALL can fit in hash table (no errors) */ -static double -run_single_tbl_perf_test(const struct rte_hash *h, hash_operation func, - const struct tbl_perf_test_params *params, double *avg_occupancy, - uint32_t *invalid_pos_count) +static int +get_input_keys(unsigned table_index) { - uint64_t begin, end, ticks = 0; - uint8_t *key = NULL; - uint32_t *bucket_occupancies = NULL; - uint32_t num_buckets, i, j; - int32_t pos; - - /* Initialise */ - num_buckets = params->entries / params->bucket_entries; - key = rte_zmalloc("hash key", - params->key_len * sizeof(uint8_t), 16); - if (key == NULL) - return -1; + unsigned i, j; + unsigned bucket_idx, incr, success = 1; + uint8_t k = 0; + int32_t ret; + const uint32_t bucket_bitmask = NUM_BUCKETS - 1; - bucket_occupancies = rte_calloc("bucket occupancies", - num_buckets, sizeof(uint32_t), 16); - if (bucket_occupancies == NULL) { - rte_free(key); - return -1; - } + /* Reset all arrays */ + for (i = 0; i < MAX_ENTRIES; i++) + slot_taken[i] = 0; - ticks = 0; - *invalid_pos_count = 0; + for (i = 0; i < NUM_BUCKETS; i++) + buckets[i] = 0; - for (i = 0; i < params->num_iterations; i++) { - /* Prepare inputs for the current iteration */ - for (j = 0; j < params->key_len; j++) - key[j] = (uint8_t) rte_rand(); + for (j = 0; j < hashtest_key_lens[table_index]; j++) + keys[0][j] = 0; - /* Perform operation, and measure time it takes */ - begin = rte_rdtsc(); - pos = func(h, key); - end = rte_rdtsc(); - ticks += end - begin; + /* + * Add only entries that are not duplicated and that fits in the table + * (cannot store more than BUCKET_SIZE entries in a bucket). + * Regardless a key has been added correctly or not (success), + * the next one to try will be increased by 1. + */ + for (i = 0; i < KEYS_TO_ADD;) { + incr = 0; + if (i != 0) { + keys[i][0] = ++k; + /* Overflow, need to increment the next byte */ + if (keys[i][0] == 0) + incr = 1; + for (j = 1; j < hashtest_key_lens[table_index]; j++) { + /* Do not increase next byte */ + if (incr == 0) + if (success == 1) + keys[i][j] = keys[i - 1][j]; + else + keys[i][j] = keys[i][j]; + /* Increase next byte by one */ + else { + if (success == 1) + keys[i][j] = keys[i-1][j] + 1; + else + keys[i][j] = keys[i][j] + 1; + if (keys[i][j] == 0) + incr = 1; + else + incr = 0; + } + } + } + success = 0; + signatures[i] = rte_hash_hash(h[table_index], keys[i]); + bucket_idx = signatures[i] & bucket_bitmask; + /* If bucket is full, do not try to insert the key */ + if (buckets[bucket_idx] == BUCKET_SIZE) + continue; + /* If key can be added, leave in successful key arrays "keys" */ + ret = rte_hash_add_key_with_hash(h[table_index], keys[i], + signatures[i]); + if (ret >= 0) { + /* If key is already added, ignore the entry and do not store */ + if (slot_taken[ret]) + continue; + else { + /* Store the returned position and mark slot as taken */ + slot_taken[ret] = 1; + buckets[bucket_idx]++; + success = 1; + i++; + } + } + } - /* Other work per iteration */ - if (pos < 0) - *invalid_pos_count += 1; + /* Reset the table, so we can measure the time to add all the entries */ + rte_hash_free(h[table_index]); + h[table_index] = rte_hash_create(&ut_params); + + return 0; +} + +static int +timed_adds(unsigned with_hash, unsigned table_index) +{ + unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + ret = rte_hash_add_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); else - bucket_occupancies[pos / params->bucket_entries]++; + ret = rte_hash_add_key(h[table_index], keys[i]); + + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } } - *avg_occupancy = get_avg(bucket_occupancies, num_buckets); - rte_free(bucket_occupancies); - rte_free(key); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; - return (double)ticks / params->num_iterations; + cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD; + return 0; } -/* - * To help print out what tests are being done. - */ -static const char * -get_tbl_perf_test_desc(enum hash_test_t type) +static int +timed_lookups(unsigned with_hash, unsigned table_index) { - switch (type){ - case ADD_ON_EMPTY: return "Add on Empty"; - case DELETE_ON_EMPTY: return "Delete on Empty"; - case LOOKUP_ON_EMPTY: return "Lookup on Empty"; - case ADD_UPDATE: return "Add Update"; - case DELETE: return "Delete"; - case LOOKUP: return "Lookup"; - default: return "UNKNOWN"; + unsigned i, j; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD; j++) { + if (with_hash) + ret = rte_hash_lookup_with_hash(h[table_index], + (const void *) keys[j], + signatures[j]); + else + ret = rte_hash_lookup(h[table_index], keys[j]); + if (ret < 0 || ret != positions[j]) { + printf("Key looked up in %d, should be in %d\n", + ret, positions[j]); + return -1; + } + } } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS; + + return 0; } -/* - * Run a hash table performance test based on params. - */ static int -run_tbl_perf_test(struct tbl_perf_test_params *params) +timed_lookups_multi(unsigned table_index) { - static unsigned calledCount = 5; - struct rte_hash_parameters hash_params = { - .entries = params->entries, - .bucket_entries = params->bucket_entries, - .key_len = params->key_len, - .hash_func = params->hash_func, - .hash_func_init_val = params->hash_func_init_val, - .socket_id = rte_socket_id(), - }; - struct rte_hash *handle; - double avg_occupancy = 0, ticks = 0; - uint32_t num_iterations, invalid_pos; - char name[RTE_HASH_NAMESIZE]; - char hashname[RTE_HASH_NAMESIZE]; - - snprintf(name, 32, "test%u", calledCount++); - hash_params.name = name; - - handle = rte_hash_create(&hash_params); - RETURN_IF_ERROR(handle == NULL, "hash creation failed"); - - switch (params->test_type){ - case ADD_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, - params, &avg_occupancy, &invalid_pos); - break; - case DELETE_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, - params, &avg_occupancy, &invalid_pos); - break; - case LOOKUP_ON_EMPTY: - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, - params, &avg_occupancy, &invalid_pos); - break; - case ADD_UPDATE: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, - params, &avg_occupancy, &invalid_pos); - break; - case DELETE: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, - params, &avg_occupancy, &invalid_pos); - break; - case LOOKUP: - num_iterations = params->num_iterations; - params->num_iterations = params->entries; - run_single_tbl_perf_test(handle, rte_hash_add_key, params, - &avg_occupancy, &invalid_pos); - - params->num_iterations = num_iterations; - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, - params, &avg_occupancy, &invalid_pos); - break; - default: return -1; + unsigned i, j, k; + int32_t positions_burst[BURST_SIZE]; + const void *keys_burst[BURST_SIZE]; + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) { + for (k = 0; k < BURST_SIZE; k++) + keys_burst[k] = keys[j * BURST_SIZE + k]; + + rte_hash_lookup_bulk(h[table_index], + (const void **) keys_burst, + BURST_SIZE, + positions_burst); + for (k = 0; k < BURST_SIZE; k++) { + if (positions_burst[k] != positions[j * BURST_SIZE + k]) { + printf("Key looked up in %d, should be in %d\n", + positions_burst[k], + positions[j * BURST_SIZE + k]); + return -1; + } + } + } } - snprintf(hashname, RTE_HASH_NAMESIZE, "%s", get_hash_name(params->hash_func)); - - printf("%-12s, %-15s, %-16u, %-7u, %-18u, %-8u, %-19.2f, %.2f\n", - hashname, - get_tbl_perf_test_desc(params->test_type), - (unsigned) params->key_len, - (unsigned) params->entries, - (unsigned) params->bucket_entries, - (unsigned) invalid_pos, - avg_occupancy, - ticks - ); - - /* Free */ - rte_hash_free(handle); + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS; + return 0; } -/* - * Run all hash table performance tests. - */ -static int run_all_tbl_perf_tests(void) +static int +timed_deletes(unsigned with_hash, unsigned table_index) { unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + int32_t ret; + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + ret = rte_hash_del_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); + else + ret = rte_hash_del_key(h[table_index], + (const void *) keys[i]); + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD; + + return 0; +} + +static void +free_table(unsigned table_index) +{ + rte_hash_free(h[table_index]); +} + +static int +reset_table(unsigned table_index) +{ + free_table(table_index); + if (create_table(table_index) != 0) + return -1; + + return 0; +} + +static int +run_all_tbl_perf_tests(void) +{ + unsigned i, j; - printf(" *** Hash table performance test results ***\n"); - printf("Hash Func. , Operation , Key size (bytes), Entries, " - "Entries per bucket, Errors , Avg. bucket entries, Ticks/Op.\n"); + printf("Measuring performance, please wait"); + fflush(stdout); + for (i = 0; i < NUM_KEYSIZES; i++) { + if (create_table(i) < 0) + return -1; + + if (get_input_keys(i) < 0) + return -1; + + if (timed_adds(0, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + if (timed_lookups(0, i) < 0) + return -1; + + if (timed_lookups_multi(i) < 0) + return -1; + + if (timed_deletes(0, i) < 0) + return -1; - /* Loop through every combination of test parameters */ - for (i = 0; - i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params); - i++) { + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + + if (reset_table(i) < 0) + return -1; - /* Perform test */ - if (run_tbl_perf_test(&tbl_perf_params[i]) < 0) + if (timed_adds(1, i) < 0) return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + if (timed_lookups(1, i) < 0) + return -1; + + if (timed_deletes(1, i) < 0) + return -1; + + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + + free_table(i); + } + printf("\nResults (in CPU cycles/operation)\n"); + printf("---------------------------------\n"); + printf("\nWithout pre-computed hash values\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); + for (i = 0; i < NUM_KEYSIZES; i++) { + printf("%-18d", hashtest_key_lens[i]); + for (j = 0; j < NUM_OPERATIONS; j++) + printf("%-18"PRIu64, cycles[i][j][0]); + printf("\n"); + } + printf("\nWith pre-computed hash values\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); + for (i = 0; i < NUM_KEYSIZES; i++) { + printf("%-18d", hashtest_key_lens[i]); + for (j = 0; j < NUM_OPERATIONS; j++) + printf("%-18"PRIu64, cycles[i][j][1]); + printf("\n"); } + return 0; } @@ -624,28 +486,34 @@ fbk_hash_perf_test(void) uint64_t lookup_time = 0; unsigned added = 0; unsigned value = 0; + uint32_t key; + uint16_t val; unsigned i, j; handle = rte_fbk_hash_create(¶ms); - RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed"); + if (handle == NULL) { + printf("Error creating table\n"); + return -1; + } keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); - RETURN_IF_ERROR_FBK(keys == NULL, - "fbk hash: memory allocation for key store failed"); + if (keys == NULL) { + printf("fbk hash: memory allocation for key store failed\n"); + return -1; + } /* Generate random keys and values. */ for (i = 0; i < ENTRIES; i++) { - uint32_t key = (uint32_t)rte_rand(); + key = (uint32_t)rte_rand(); key = ((uint64_t)key << 32) | (uint64_t)rte_rand(); - uint16_t val = (uint16_t)rte_rand(); + val = (uint16_t)rte_rand(); if (rte_fbk_hash_add_key(handle, key, val) == 0) { keys[added] = key; added++; } - if (added > (LOAD_FACTOR * ENTRIES)) { + if (added > (LOAD_FACTOR * ENTRIES)) break; - } } for (i = 0; i < TEST_ITERATIONS; i++) { @@ -653,15 +521,14 @@ fbk_hash_perf_test(void) uint64_t end; /* Generate random indexes into keys[] array. */ - for (j = 0; j < TEST_SIZE; j++) { + for (j = 0; j < TEST_SIZE; j++) indexes[j] = rte_rand() % added; - } begin = rte_rdtsc(); /* Do lookups */ - for (j = 0; j < TEST_SIZE; j++) { + for (j = 0; j < TEST_SIZE; j++) value += rte_fbk_hash_lookup(handle, keys[indexes[j]]); - } + end = rte_rdtsc(); lookup_time += (double)(end - begin); } @@ -681,9 +548,6 @@ fbk_hash_perf_test(void) return 0; } -/* - * Do all unit and performance tests. - */ static int test_hash_perf(void) { @@ -692,11 +556,12 @@ test_hash_perf(void) if (fbk_hash_perf_test() < 0) return -1; + return 0; } static struct test_command hash_perf_cmd = { - .command = "hash_perf_autotest", - .callback = test_hash_perf, + .command = "hash_perf_autotest", + .callback = test_hash_perf, }; REGISTER_TEST_COMMAND(hash_perf_cmd); -- 2.4.2 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH v4] test/hash: improve hash unit tests 2015-07-09 16:54 ` [PATCH v4] test/hash: improve hash unit tests Pablo de Lara @ 2015-07-10 9:11 ` Bruce Richardson 2015-07-10 10:35 ` Thomas Monjalon 0 siblings, 1 reply; 13+ messages in thread From: Bruce Richardson @ 2015-07-10 9:11 UTC (permalink / raw) To: Pablo de Lara; +Cc: dev On Thu, Jul 09, 2015 at 05:54:30PM +0100, Pablo de Lara wrote: > Add new unit test for calculating the average table utilization, > using random keys, based on number of entries that can be added > until we encounter one that cannot be added (bucket if full). > > Also, replace current hash_perf unit test to see performance more clear. s/clear/clearly/ > The current hash_perf unit test takes too long and add keys that > may or may not fit in the table and look up/delete that may not be > in the table. This new unit test gets a set of keys that we know > that fits in the table, and then measure the time to add/look up/delete > them. > > Mind that performance numbers include time to take a random key s/Mind/Note/ > from a pre-made array of keys, plus a quick check of return value. > Also, as stated above, expect higher numbers, as all operations > in the new unit tests will be successful, which means that > it will take more time, than mixing both successful and unsuccesful > operations. > > Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com> Looks good, Pablo. Thomas, perhaps you could make the above minor changes to the commit log when applying the patch. Acked-by: Bruce Richardson <bruce.richardson@intel.com> > --- > app/test/test_hash.c | 66 +++- > app/test/test_hash_perf.c | 923 ++++++++++++++++++++-------------------------- > 2 files changed, 458 insertions(+), 531 deletions(-) > > diff --git a/app/test/test_hash.c b/app/test/test_hash.c > index 4300de9..7c71ed6 100644 > --- a/app/test/test_hash.c > +++ b/app/test/test_hash.c > @@ -190,7 +190,7 @@ test_crc32_hash_alg_equiv(void) > unsigned i, j; > size_t data_len; > > - printf("# CRC32 implementations equivalence test\n"); > + printf("\n# CRC32 implementations equivalence test\n"); > for (i = 0; i < CRC32_ITERATIONS; i++) { > /* Randomizing data_len of data set */ > data_len = (size_t) ((rte_rand() % sizeof(data64)) + 1); > @@ -785,7 +785,7 @@ fbk_hash_unit_test(void) > > /* Try creating hashes with invalid parameters */ > printf("# Testing hash creation with invalid parameters " > - "- expert error msgs\n"); > + "- expect error msgs\n"); > handle = rte_fbk_hash_create(&invalid_params_1); > RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); > > @@ -1087,6 +1087,7 @@ static int test_hash_creation_with_bad_parameters(void) > } > > rte_hash_free(handle); > + printf("# Test successful. No more errors expected\n"); > > return 0; > } > @@ -1147,6 +1148,65 @@ test_hash_creation_with_good_parameters(void) > return 0; > } > > +#define ITERATIONS 50 > +/* > + * Test to see the average table utilization (entries added/max entries) > + * before hitting a random entry that cannot be added > + */ > +static int test_average_table_utilization(void) > +{ > + struct rte_hash *handle; > + uint8_t simple_key[RTE_HASH_KEY_LENGTH_MAX]; > + unsigned i, j; > + unsigned added_keys, average_keys_added = 0; > + int ret; > + > + printf("\n# Running test to determine average utilization" > + "\n before adding elements begins to fail\n"); > + printf("Measuring performance, please wait"); > + fflush(stdout); > + ut_params.entries = 1 << 20; > + ut_params.name = "test_average_utilization"; > + ut_params.hash_func = rte_jhash; > + handle = rte_hash_create(&ut_params); > + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); > + > + for (j = 0; j < ITERATIONS; j++) { > + ret = 0; > + /* Add random entries until key cannot be added */ > + for (added_keys = 0; ret >= 0; added_keys++) { > + for (i = 0; i < ut_params.key_len; i++) > + simple_key[i] = rte_rand() % 255; > + ret = rte_hash_add_key(handle, simple_key); > + } > + if (ret != -ENOSPC) { > + printf("Unexpected error when adding keys\n"); > + rte_hash_free(handle); > + return -1; > + } > + > + average_keys_added += added_keys; > + > + /* Reset the table */ > + rte_hash_free(handle); > + handle = rte_hash_create(&ut_params); > + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); > + > + /* Print a dot to show progress on operations */ > + printf("."); > + fflush(stdout); > + } > + > + average_keys_added /= ITERATIONS; > + > + printf("\nAverage table utilization = %.2f%% (%u/%u)\n", > + ((double) average_keys_added / ut_params.entries * 100), > + average_keys_added, ut_params.entries); > + rte_hash_free(handle); > + > + return 0; > +} > + > static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, > 0x04, 0x05, 0x06, 0x07, > 0x08, 0x09, 0x0a, 0x0b, > @@ -1405,6 +1465,8 @@ test_hash(void) > return -1; > if (test_hash_creation_with_good_parameters() < 0) > return -1; > + if (test_average_table_utilization() < 0) > + return -1; > > run_hash_func_tests(); > > diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c > index d0e5ce0..a3876c1 100644 > --- a/app/test/test_hash_perf.c > +++ b/app/test/test_hash_perf.c > @@ -32,574 +32,436 @@ > */ > > #include <stdio.h> > -#include <stdint.h> > -#include <string.h> > -#include <stdlib.h> > -#include <stdarg.h> > -#include <errno.h> > -#include <sys/queue.h> > - > -#include <rte_common.h> > +#include <inttypes.h> > + > #include <rte_lcore.h> > -#include <rte_malloc.h> > #include <rte_cycles.h> > +#include <rte_malloc.h> > +#include <rte_hash.h> > +#include <rte_hash_crc.h> > +#include <rte_jhash.h> > +#include <rte_fbk_hash.h> > #include <rte_random.h> > -#include <rte_memory.h> > -#include <rte_memzone.h> > -#include <rte_eal.h> > -#include <rte_ip.h> > #include <rte_string_fns.h> > > #include "test.h" > > -#include <rte_hash.h> > -#include <rte_fbk_hash.h> > -#include <rte_jhash.h> > -#include <rte_hash_crc.h> > - > -/* Types of hash table performance test that can be performed */ > -enum hash_test_t { > - ADD_ON_EMPTY, /*< Add keys to empty table */ > - DELETE_ON_EMPTY, /*< Attempt to delete keys from empty table */ > - LOOKUP_ON_EMPTY, /*< Attempt to find keys in an empty table */ > - ADD_UPDATE, /*< Add/update keys in a full table */ > - DELETE, /*< Delete keys from a full table */ > - LOOKUP /*< Find keys in a full table */ > +#define MAX_ENTRIES (1 << 19) > +#define KEYS_TO_ADD (MAX_ENTRIES * 3 / 4) /* 75% table utilization */ > +#define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */ > +#define BUCKET_SIZE 4 > +#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE) > +#define MAX_KEYSIZE 64 > +#define NUM_KEYSIZES 10 > +#define NUM_SHUFFLES 10 > +#define BURST_SIZE 16 > + > +enum operations { > + ADD = 0, > + LOOKUP, > + LOOKUP_MULTI, > + DELETE, > + NUM_OPERATIONS > }; > > -/* Function type for hash table operations. */ > -typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key); > - > -/* Structure to hold parameters used to run a hash table performance test */ > -struct tbl_perf_test_params { > - enum hash_test_t test_type; > - uint32_t num_iterations; > - uint32_t entries; > - uint32_t bucket_entries; > - uint32_t key_len; > - rte_hash_function hash_func; > - uint32_t hash_func_init_val; > +static uint32_t hashtest_key_lens[] = { > + /* standard key sizes */ > + 4, 8, 16, 32, 48, 64, > + /* IPv4 SRC + DST + protocol, unpadded */ > + 9, > + /* IPv4 5-tuple, unpadded */ > + 13, > + /* IPv6 5-tuple, unpadded */ > + 37, > + /* IPv6 5-tuple, padded to 8-byte boundary */ > + 40 > }; > > -#define ITERATIONS 10000 > -#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15) > +struct rte_hash *h[NUM_KEYSIZES]; > > -/******************************************************************************* > - * Hash table performance test configuration section. > - */ > -struct tbl_perf_test_params tbl_perf_params[] = > -{ > -/* Small table, add */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_jhash, 0}, > -/* Small table, update */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, > -/* Small table, lookup */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_jhash, 0}, > -/* Big table, add */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_jhash, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_jhash, 0}, > -/* Big table, update */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, > -/* Big table, lookup */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_jhash, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_jhash, 0}, > -/* Small table, add */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_hash_crc, 0}, > -/* Small table, update */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, > -/* Small table, lookup */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0}, > -/* Big table, add */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_hash_crc, 0}, > -{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_hash_crc, 0}, > -/* Big table, update */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, > -{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, > -/* Big table, lookup */ > -/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */ > -{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0}, > -{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0}, > -}; > +/* Array that stores if a slot is full */ > +uint8_t slot_taken[MAX_ENTRIES]; > > -/******************************************************************************/ > +/* Array to store number of cycles per operation */ > +uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2]; > > -/* > - * Check condition and return an error if true. Assumes that "handle" is the > - * name of the hash structure pointer to be freed. > - */ > -#define RETURN_IF_ERROR(cond, str, ...) do { \ > - if (cond) { \ > - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ > - if (handle) rte_hash_free(handle); \ > - return -1; \ > - } \ > -} while(0) > - > -#define RETURN_IF_ERROR_FBK(cond, str, ...) do { \ > - if (cond) { \ > - printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ > - if (handle) rte_fbk_hash_free(handle); \ > - rte_free(keys); \ > - return -1; \ > - } \ > -} while(0) > +/* Array to store all input keys */ > +uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; > > -/* > - * Find average of array of numbers. > - */ > -static double > -get_avg(const uint32_t *array, uint32_t size) > +/* Array to store the precomputed hash for 'keys' */ > +hash_sig_t signatures[KEYS_TO_ADD]; > + > +/* Array to store how many busy entries have each bucket */ > +uint8_t buckets[NUM_BUCKETS]; > + > +/* Array to store the positions where keys are added */ > +int32_t positions[KEYS_TO_ADD]; > + > +/* Parameters used for hash table in unit test functions. */ > +static struct rte_hash_parameters ut_params = { > + .entries = MAX_ENTRIES, > + .bucket_entries = BUCKET_SIZE, > + .hash_func = rte_jhash, > + .hash_func_init_val = 0, > +}; > + > +static int > +create_table(unsigned table_index) > { > - double sum = 0; > - unsigned i; > - for (i = 0; i < size; i++) > - sum += array[i]; > - return sum / (double)size; > + char name[RTE_HASH_NAMESIZE]; > + > + sprintf(name, "test_hash%d", hashtest_key_lens[table_index]); > + ut_params.name = name; > + ut_params.key_len = hashtest_key_lens[table_index]; > + ut_params.socket_id = rte_socket_id(); > + h[table_index] = rte_hash_find_existing(name); > + if (h[table_index] != NULL) > + /* > + * If table was already created, free it to create it again, > + * so we force it is empty > + */ > + rte_hash_free(h[table_index]); > + h[table_index] = rte_hash_create(&ut_params); > + if (h[table_index] == NULL) { > + printf("Error creating table\n"); > + return -1; > + } > + return 0; > + > } > > -/* > - * To help print out name of hash functions. > - */ > -static const char *get_hash_name(rte_hash_function f) > +/* Shuffle the keys that have been added, so lookups will be totally random */ > +static void > +shuffle_input_keys(unsigned table_index) > { > - if (f == rte_jhash) > - return "jhash"; > + unsigned i; > + uint32_t swap_idx; > + uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX]; > + hash_sig_t temp_signature; > + int32_t temp_position; > > - if (f == rte_hash_crc) > - return "rte_hash_crc"; > + for (i = KEYS_TO_ADD - 1; i > 0; i--) { > + swap_idx = rte_rand() % i; > > - return "UnknownHash"; > + memcpy(temp_key, keys[i], hashtest_key_lens[table_index]); > + temp_signature = signatures[i]; > + temp_position = positions[i]; > + > + memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]); > + signatures[i] = signatures[swap_idx]; > + positions[i] = positions[swap_idx]; > + > + memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]); > + signatures[swap_idx] = temp_signature; > + positions[swap_idx] = temp_position; > + } > } > > /* > - * Do a single performance test, of one type of operation. > - * > - * @param h > - * hash table to run test on > - * @param func > - * function to call (add, delete or lookup function) > - * @param avg_occupancy > - * The average number of entries in each bucket of the hash table > - * @param invalid_pos_count > - * The amount of errors (e.g. due to a full bucket). > - * @return > - * The average number of ticks per hash function call. A negative number > - * signifies failure. > + * Looks for random keys which > + * ALL can fit in hash table (no errors) > */ > -static double > -run_single_tbl_perf_test(const struct rte_hash *h, hash_operation func, > - const struct tbl_perf_test_params *params, double *avg_occupancy, > - uint32_t *invalid_pos_count) > +static int > +get_input_keys(unsigned table_index) > { > - uint64_t begin, end, ticks = 0; > - uint8_t *key = NULL; > - uint32_t *bucket_occupancies = NULL; > - uint32_t num_buckets, i, j; > - int32_t pos; > - > - /* Initialise */ > - num_buckets = params->entries / params->bucket_entries; > - key = rte_zmalloc("hash key", > - params->key_len * sizeof(uint8_t), 16); > - if (key == NULL) > - return -1; > + unsigned i, j; > + unsigned bucket_idx, incr, success = 1; > + uint8_t k = 0; > + int32_t ret; > + const uint32_t bucket_bitmask = NUM_BUCKETS - 1; > > - bucket_occupancies = rte_calloc("bucket occupancies", > - num_buckets, sizeof(uint32_t), 16); > - if (bucket_occupancies == NULL) { > - rte_free(key); > - return -1; > - } > + /* Reset all arrays */ > + for (i = 0; i < MAX_ENTRIES; i++) > + slot_taken[i] = 0; > > - ticks = 0; > - *invalid_pos_count = 0; > + for (i = 0; i < NUM_BUCKETS; i++) > + buckets[i] = 0; > > - for (i = 0; i < params->num_iterations; i++) { > - /* Prepare inputs for the current iteration */ > - for (j = 0; j < params->key_len; j++) > - key[j] = (uint8_t) rte_rand(); > + for (j = 0; j < hashtest_key_lens[table_index]; j++) > + keys[0][j] = 0; > > - /* Perform operation, and measure time it takes */ > - begin = rte_rdtsc(); > - pos = func(h, key); > - end = rte_rdtsc(); > - ticks += end - begin; > + /* > + * Add only entries that are not duplicated and that fits in the table > + * (cannot store more than BUCKET_SIZE entries in a bucket). > + * Regardless a key has been added correctly or not (success), > + * the next one to try will be increased by 1. > + */ > + for (i = 0; i < KEYS_TO_ADD;) { > + incr = 0; > + if (i != 0) { > + keys[i][0] = ++k; > + /* Overflow, need to increment the next byte */ > + if (keys[i][0] == 0) > + incr = 1; > + for (j = 1; j < hashtest_key_lens[table_index]; j++) { > + /* Do not increase next byte */ > + if (incr == 0) > + if (success == 1) > + keys[i][j] = keys[i - 1][j]; > + else > + keys[i][j] = keys[i][j]; > + /* Increase next byte by one */ > + else { > + if (success == 1) > + keys[i][j] = keys[i-1][j] + 1; > + else > + keys[i][j] = keys[i][j] + 1; > + if (keys[i][j] == 0) > + incr = 1; > + else > + incr = 0; > + } > + } > + } > + success = 0; > + signatures[i] = rte_hash_hash(h[table_index], keys[i]); > + bucket_idx = signatures[i] & bucket_bitmask; > + /* If bucket is full, do not try to insert the key */ > + if (buckets[bucket_idx] == BUCKET_SIZE) > + continue; > + /* If key can be added, leave in successful key arrays "keys" */ > + ret = rte_hash_add_key_with_hash(h[table_index], keys[i], > + signatures[i]); > + if (ret >= 0) { > + /* If key is already added, ignore the entry and do not store */ > + if (slot_taken[ret]) > + continue; > + else { > + /* Store the returned position and mark slot as taken */ > + slot_taken[ret] = 1; > + buckets[bucket_idx]++; > + success = 1; > + i++; > + } > + } > + } > > - /* Other work per iteration */ > - if (pos < 0) > - *invalid_pos_count += 1; > + /* Reset the table, so we can measure the time to add all the entries */ > + rte_hash_free(h[table_index]); > + h[table_index] = rte_hash_create(&ut_params); > + > + return 0; > +} > + > +static int > +timed_adds(unsigned with_hash, unsigned table_index) > +{ > + unsigned i; > + const uint64_t start_tsc = rte_rdtsc(); > + int32_t ret; > + > + for (i = 0; i < KEYS_TO_ADD; i++) { > + if (with_hash) > + ret = rte_hash_add_key_with_hash(h[table_index], > + (const void *) keys[i], > + signatures[i]); > else > - bucket_occupancies[pos / params->bucket_entries]++; > + ret = rte_hash_add_key(h[table_index], keys[i]); > + > + if (ret >= 0) > + positions[i] = ret; > + else { > + printf("Failed to add key number %u\n", ret); > + return -1; > + } > } > - *avg_occupancy = get_avg(bucket_occupancies, num_buckets); > > - rte_free(bucket_occupancies); > - rte_free(key); > + const uint64_t end_tsc = rte_rdtsc(); > + const uint64_t time_taken = end_tsc - start_tsc; > > - return (double)ticks / params->num_iterations; > + cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD; > + return 0; > } > > -/* > - * To help print out what tests are being done. > - */ > -static const char * > -get_tbl_perf_test_desc(enum hash_test_t type) > +static int > +timed_lookups(unsigned with_hash, unsigned table_index) > { > - switch (type){ > - case ADD_ON_EMPTY: return "Add on Empty"; > - case DELETE_ON_EMPTY: return "Delete on Empty"; > - case LOOKUP_ON_EMPTY: return "Lookup on Empty"; > - case ADD_UPDATE: return "Add Update"; > - case DELETE: return "Delete"; > - case LOOKUP: return "Lookup"; > - default: return "UNKNOWN"; > + unsigned i, j; > + const uint64_t start_tsc = rte_rdtsc(); > + int32_t ret; > + > + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { > + for (j = 0; j < KEYS_TO_ADD; j++) { > + if (with_hash) > + ret = rte_hash_lookup_with_hash(h[table_index], > + (const void *) keys[j], > + signatures[j]); > + else > + ret = rte_hash_lookup(h[table_index], keys[j]); > + if (ret < 0 || ret != positions[j]) { > + printf("Key looked up in %d, should be in %d\n", > + ret, positions[j]); > + return -1; > + } > + } > } > + > + const uint64_t end_tsc = rte_rdtsc(); > + const uint64_t time_taken = end_tsc - start_tsc; > + > + cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS; > + > + return 0; > } > > -/* > - * Run a hash table performance test based on params. > - */ > static int > -run_tbl_perf_test(struct tbl_perf_test_params *params) > +timed_lookups_multi(unsigned table_index) > { > - static unsigned calledCount = 5; > - struct rte_hash_parameters hash_params = { > - .entries = params->entries, > - .bucket_entries = params->bucket_entries, > - .key_len = params->key_len, > - .hash_func = params->hash_func, > - .hash_func_init_val = params->hash_func_init_val, > - .socket_id = rte_socket_id(), > - }; > - struct rte_hash *handle; > - double avg_occupancy = 0, ticks = 0; > - uint32_t num_iterations, invalid_pos; > - char name[RTE_HASH_NAMESIZE]; > - char hashname[RTE_HASH_NAMESIZE]; > - > - snprintf(name, 32, "test%u", calledCount++); > - hash_params.name = name; > - > - handle = rte_hash_create(&hash_params); > - RETURN_IF_ERROR(handle == NULL, "hash creation failed"); > - > - switch (params->test_type){ > - case ADD_ON_EMPTY: > - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, > - params, &avg_occupancy, &invalid_pos); > - break; > - case DELETE_ON_EMPTY: > - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, > - params, &avg_occupancy, &invalid_pos); > - break; > - case LOOKUP_ON_EMPTY: > - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, > - params, &avg_occupancy, &invalid_pos); > - break; > - case ADD_UPDATE: > - num_iterations = params->num_iterations; > - params->num_iterations = params->entries; > - run_single_tbl_perf_test(handle, rte_hash_add_key, params, > - &avg_occupancy, &invalid_pos); > - params->num_iterations = num_iterations; > - ticks = run_single_tbl_perf_test(handle, rte_hash_add_key, > - params, &avg_occupancy, &invalid_pos); > - break; > - case DELETE: > - num_iterations = params->num_iterations; > - params->num_iterations = params->entries; > - run_single_tbl_perf_test(handle, rte_hash_add_key, params, > - &avg_occupancy, &invalid_pos); > - > - params->num_iterations = num_iterations; > - ticks = run_single_tbl_perf_test(handle, rte_hash_del_key, > - params, &avg_occupancy, &invalid_pos); > - break; > - case LOOKUP: > - num_iterations = params->num_iterations; > - params->num_iterations = params->entries; > - run_single_tbl_perf_test(handle, rte_hash_add_key, params, > - &avg_occupancy, &invalid_pos); > - > - params->num_iterations = num_iterations; > - ticks = run_single_tbl_perf_test(handle, rte_hash_lookup, > - params, &avg_occupancy, &invalid_pos); > - break; > - default: return -1; > + unsigned i, j, k; > + int32_t positions_burst[BURST_SIZE]; > + const void *keys_burst[BURST_SIZE]; > + const uint64_t start_tsc = rte_rdtsc(); > + > + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { > + for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) { > + for (k = 0; k < BURST_SIZE; k++) > + keys_burst[k] = keys[j * BURST_SIZE + k]; > + > + rte_hash_lookup_bulk(h[table_index], > + (const void **) keys_burst, > + BURST_SIZE, > + positions_burst); > + for (k = 0; k < BURST_SIZE; k++) { > + if (positions_burst[k] != positions[j * BURST_SIZE + k]) { > + printf("Key looked up in %d, should be in %d\n", > + positions_burst[k], > + positions[j * BURST_SIZE + k]); > + return -1; > + } > + } > + } > } > > - snprintf(hashname, RTE_HASH_NAMESIZE, "%s", get_hash_name(params->hash_func)); > - > - printf("%-12s, %-15s, %-16u, %-7u, %-18u, %-8u, %-19.2f, %.2f\n", > - hashname, > - get_tbl_perf_test_desc(params->test_type), > - (unsigned) params->key_len, > - (unsigned) params->entries, > - (unsigned) params->bucket_entries, > - (unsigned) invalid_pos, > - avg_occupancy, > - ticks > - ); > - > - /* Free */ > - rte_hash_free(handle); > + const uint64_t end_tsc = rte_rdtsc(); > + const uint64_t time_taken = end_tsc - start_tsc; > + > + cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS; > + > return 0; > } > > -/* > - * Run all hash table performance tests. > - */ > -static int run_all_tbl_perf_tests(void) > +static int > +timed_deletes(unsigned with_hash, unsigned table_index) > { > unsigned i; > + const uint64_t start_tsc = rte_rdtsc(); > + int32_t ret; > + > + for (i = 0; i < KEYS_TO_ADD; i++) { > + if (with_hash) > + ret = rte_hash_del_key_with_hash(h[table_index], > + (const void *) keys[i], > + signatures[i]); > + else > + ret = rte_hash_del_key(h[table_index], > + (const void *) keys[i]); > + if (ret >= 0) > + positions[i] = ret; > + else { > + printf("Failed to add key number %u\n", ret); > + return -1; > + } > + } > + > + const uint64_t end_tsc = rte_rdtsc(); > + const uint64_t time_taken = end_tsc - start_tsc; > + > + cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD; > + > + return 0; > +} > + > +static void > +free_table(unsigned table_index) > +{ > + rte_hash_free(h[table_index]); > +} > + > +static int > +reset_table(unsigned table_index) > +{ > + free_table(table_index); > + if (create_table(table_index) != 0) > + return -1; > + > + return 0; > +} > + > +static int > +run_all_tbl_perf_tests(void) > +{ > + unsigned i, j; > > - printf(" *** Hash table performance test results ***\n"); > - printf("Hash Func. , Operation , Key size (bytes), Entries, " > - "Entries per bucket, Errors , Avg. bucket entries, Ticks/Op.\n"); > + printf("Measuring performance, please wait"); > + fflush(stdout); > + for (i = 0; i < NUM_KEYSIZES; i++) { > + if (create_table(i) < 0) > + return -1; > + > + if (get_input_keys(i) < 0) > + return -1; > + > + if (timed_adds(0, i) < 0) > + return -1; > + > + for (j = 0; j < NUM_SHUFFLES; j++) > + shuffle_input_keys(i); > + > + if (timed_lookups(0, i) < 0) > + return -1; > + > + if (timed_lookups_multi(i) < 0) > + return -1; > + > + if (timed_deletes(0, i) < 0) > + return -1; > > - /* Loop through every combination of test parameters */ > - for (i = 0; > - i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params); > - i++) { > + /* Print a dot to show progress on operations */ > + printf("."); > + fflush(stdout); > + > + if (reset_table(i) < 0) > + return -1; > > - /* Perform test */ > - if (run_tbl_perf_test(&tbl_perf_params[i]) < 0) > + if (timed_adds(1, i) < 0) > return -1; > + > + for (j = 0; j < NUM_SHUFFLES; j++) > + shuffle_input_keys(i); > + > + if (timed_lookups(1, i) < 0) > + return -1; > + > + if (timed_deletes(1, i) < 0) > + return -1; > + > + /* Print a dot to show progress on operations */ > + printf("."); > + fflush(stdout); > + > + free_table(i); > + } > + printf("\nResults (in CPU cycles/operation)\n"); > + printf("---------------------------------\n"); > + printf("\nWithout pre-computed hash values\n"); > + printf("\n%-18s%-18s%-18s%-18s%-18s\n", > + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); > + for (i = 0; i < NUM_KEYSIZES; i++) { > + printf("%-18d", hashtest_key_lens[i]); > + for (j = 0; j < NUM_OPERATIONS; j++) > + printf("%-18"PRIu64, cycles[i][j][0]); > + printf("\n"); > + } > + printf("\nWith pre-computed hash values\n"); > + printf("\n%-18s%-18s%-18s%-18s%-18s\n", > + "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); > + for (i = 0; i < NUM_KEYSIZES; i++) { > + printf("%-18d", hashtest_key_lens[i]); > + for (j = 0; j < NUM_OPERATIONS; j++) > + printf("%-18"PRIu64, cycles[i][j][1]); > + printf("\n"); > } > + > return 0; > } > > @@ -624,28 +486,34 @@ fbk_hash_perf_test(void) > uint64_t lookup_time = 0; > unsigned added = 0; > unsigned value = 0; > + uint32_t key; > + uint16_t val; > unsigned i, j; > > handle = rte_fbk_hash_create(¶ms); > - RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed"); > + if (handle == NULL) { > + printf("Error creating table\n"); > + return -1; > + } > > keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); > - RETURN_IF_ERROR_FBK(keys == NULL, > - "fbk hash: memory allocation for key store failed"); > + if (keys == NULL) { > + printf("fbk hash: memory allocation for key store failed\n"); > + return -1; > + } > > /* Generate random keys and values. */ > for (i = 0; i < ENTRIES; i++) { > - uint32_t key = (uint32_t)rte_rand(); > + key = (uint32_t)rte_rand(); > key = ((uint64_t)key << 32) | (uint64_t)rte_rand(); > - uint16_t val = (uint16_t)rte_rand(); > + val = (uint16_t)rte_rand(); > > if (rte_fbk_hash_add_key(handle, key, val) == 0) { > keys[added] = key; > added++; > } > - if (added > (LOAD_FACTOR * ENTRIES)) { > + if (added > (LOAD_FACTOR * ENTRIES)) > break; > - } > } > > for (i = 0; i < TEST_ITERATIONS; i++) { > @@ -653,15 +521,14 @@ fbk_hash_perf_test(void) > uint64_t end; > > /* Generate random indexes into keys[] array. */ > - for (j = 0; j < TEST_SIZE; j++) { > + for (j = 0; j < TEST_SIZE; j++) > indexes[j] = rte_rand() % added; > - } > > begin = rte_rdtsc(); > /* Do lookups */ > - for (j = 0; j < TEST_SIZE; j++) { > + for (j = 0; j < TEST_SIZE; j++) > value += rte_fbk_hash_lookup(handle, keys[indexes[j]]); > - } > + > end = rte_rdtsc(); > lookup_time += (double)(end - begin); > } > @@ -681,9 +548,6 @@ fbk_hash_perf_test(void) > return 0; > } > > -/* > - * Do all unit and performance tests. > - */ > static int > test_hash_perf(void) > { > @@ -692,11 +556,12 @@ test_hash_perf(void) > > if (fbk_hash_perf_test() < 0) > return -1; > + > return 0; > } > > static struct test_command hash_perf_cmd = { > - .command = "hash_perf_autotest", > - .callback = test_hash_perf, > + .command = "hash_perf_autotest", > + .callback = test_hash_perf, > }; > REGISTER_TEST_COMMAND(hash_perf_cmd); > -- > 2.4.2 > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v4] test/hash: improve hash unit tests 2015-07-10 9:11 ` Bruce Richardson @ 2015-07-10 10:35 ` Thomas Monjalon 0 siblings, 0 replies; 13+ messages in thread From: Thomas Monjalon @ 2015-07-10 10:35 UTC (permalink / raw) To: Pablo de Lara; +Cc: dev 2015-07-10 10:11, Bruce Richardson: > On Thu, Jul 09, 2015 at 05:54:30PM +0100, Pablo de Lara wrote: > > Add new unit test for calculating the average table utilization, > > using random keys, based on number of entries that can be added > > until we encounter one that cannot be added (bucket if full). > > > > Also, replace current hash_perf unit test to see performance more clear. > s/clear/clearly/ > > > The current hash_perf unit test takes too long and add keys that > > may or may not fit in the table and look up/delete that may not be > > in the table. This new unit test gets a set of keys that we know > > that fits in the table, and then measure the time to add/look up/delete > > them. > > > > Mind that performance numbers include time to take a random key > s/Mind/Note/ > > > from a pre-made array of keys, plus a quick check of return value. > > Also, as stated above, expect higher numbers, as all operations > > in the new unit tests will be successful, which means that > > it will take more time, than mixing both successful and unsuccesful > > operations. > > > > Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com> > > Looks good, Pablo. > Thomas, perhaps you could make the above minor changes to > the commit log when applying the patch. > > Acked-by: Bruce Richardson <bruce.richardson@intel.com> Applied with above comments, thanks ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2015-07-10 10:36 UTC | newest] Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2015-07-08 13:12 [PATCH] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 2015-07-08 13:12 ` [PATCH] test/hash: improve hash unit tests Pablo de Lara 2015-07-08 13:39 ` Bruce Richardson 2015-07-08 15:04 ` Bruce Richardson 2015-07-08 15:14 ` De Lara Guarch, Pablo 2015-07-08 16:30 ` [PATCH v2] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 2015-07-08 16:30 ` [PATCH v2] test/hash: improve hash unit tests Pablo de Lara 2015-07-09 12:19 ` [PATCH v3] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 2015-07-09 12:19 ` [PATCH v3] test/hash: improve hash unit tests Pablo de Lara 2015-07-09 16:54 ` [PATCH v4] Improve hash unit tests - Cuckoo hash part 2 Pablo de Lara 2015-07-09 16:54 ` [PATCH v4] test/hash: improve hash unit tests Pablo de Lara 2015-07-10 9:11 ` Bruce Richardson 2015-07-10 10:35 ` Thomas Monjalon
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.