From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 185D2C55C for ; Mon, 29 Jun 2015 00:25:33 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga102.fm.intel.com with ESMTP; 28 Jun 2015 15:25:32 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,695,1427785200"; d="scan'208";a="515624874" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by FMSMGA003.fm.intel.com with ESMTP; 28 Jun 2015 15:25:31 -0700 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t5SMPUIU030617; Sun, 28 Jun 2015 23:25:30 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t5SMPUFN010194; Sun, 28 Jun 2015 23:25:30 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t5SMPU7a010190; Sun, 28 Jun 2015 23:25:30 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Sun, 28 Jun 2015 23:25:23 +0100 Message-Id: <1435530330-10132-5-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v3 04/11] test/hash: rename new hash perf unit test back to original name X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 28 Jun 2015 22:25:35 -0000 To be able to see the diff more clear, new performance unit test was named differently from the old unit test. This patch renames the new unit test as the old one. Signed-off-by: Pablo de Lara --- app/test/Makefile | 2 +- app/test/test_hash_perf.c | 560 ++++++++++++++++++++++++++++++++++++++++++ app/test/test_hash_perf_new.c | 560 ------------------------------------------ 3 files changed, 561 insertions(+), 561 deletions(-) create mode 100644 app/test/test_hash_perf.c delete mode 100644 app/test/test_hash_perf_new.c diff --git a/app/test/Makefile b/app/test/Makefile index 8624e95..2e2758c 100644 --- a/app/test/Makefile +++ b/app/test/Makefile @@ -82,7 +82,7 @@ SRCS-y += test_memcpy.c SRCS-y += test_memcpy_perf.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash.c -SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_perf_new.c +SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_perf.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_functions.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_scaling.c diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c new file mode 100644 index 0000000..978731c --- /dev/null +++ b/app/test/test_hash_perf.c @@ -0,0 +1,560 @@ +/*- + * BSD LICENSE + * + * Copyright(c) 2010-2015 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "test.h" + +#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 +}; + +static uint32_t hashtest_key_lens[] = { + 4, 8, 16, 32, 48, 64, /* standard key sizes */ + 9, /* IPv4 SRC + DST + protocol, unpadded */ + 13, /* IPv4 5-tuple, unpadded */ + 37, /* IPv6 5-tuple, unpadded */ + 40 /* IPv6 5-tuple, padded to 8-byte boundary */ +}; +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]; + +/* 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) +{ + 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; + +} + +/* Shuffle the keys that have been added, so lookups will be totally random */ +static void +shuffle_input_keys(unsigned table_index) +{ + unsigned i; + uint32_t swap_idx; + uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX]; + hash_sig_t temp_signature; + + for (i = 0; i < KEYS_TO_ADD; i++) { + do + swap_idx = rte_rand() % KEYS_TO_ADD; + while (swap_idx == i); + + memcpy(temp_key, keys[i], hashtest_key_lens[table_index]); + temp_signature = signatures[i]; + + memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]); + signatures[i] = signatures[swap_idx]; + + memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]); + signatures[swap_idx] = temp_signature; + } +} + +/* + * Creates the table and looks for random keys which + * ALL can fit in hash table (no errors) + */ +static int +get_input_keys(unsigned table_index) +{ + 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; + + for (i = 0; i < NUM_BUCKETS; i++) + buckets[i] = 0; + + 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; +} + +static int +timed_adds(unsigned with_hash, unsigned table_index) { + unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + rte_hash_add_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); + else + rte_hash_add_key(h[table_index], keys[i]); + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); + + cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD; + + printf("\n%"PRIu64" adds in %f seconds\n", (uint64_t)KEYS_TO_ADD, + seconds_taken); + printf("Average %"PRIu64" tsc ticks per add\n", + cycles[table_index][ADD][with_hash]); + printf("Average %"PRIu64" adds per second\n", + (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken); + return 0; +} + +static int +timed_lookups(unsigned with_hash, unsigned table_index) +{ + unsigned i, j; + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD; j++) { + if (with_hash) + rte_hash_lookup_with_hash(h[table_index], + (const void *) keys[j], + signatures[j]); + else + rte_hash_lookup(h[table_index], keys[j]); + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); + + cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS; + + printf("%"PRIu64" lookups in %f seconds\n", (uint64_t) NUM_LOOKUPS, + seconds_taken); + printf("Average %"PRIu64" tsc ticks per lookup\n", + cycles[table_index][LOOKUP][with_hash]); + printf("Average %"PRIu64" lookups per second\n", + (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken); + return 0; +} + +static int +timed_lookups_multi(unsigned table_index) +{ + 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); + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); + + cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS; + + printf("%"PRIu64" lookups in %f seconds\n", (uint64_t)NUM_LOOKUPS, + seconds_taken); + printf("Average %"PRIu64" tsc ticks per lookup\n", + cycles[table_index][LOOKUP_MULTI][0]); + printf("Average %"PRIu64" lookups per second\n", + (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken); + return 0; +} + +static int +timed_deletes(unsigned with_hash, unsigned table_index) +{ + unsigned i; + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < KEYS_TO_ADD; i++) { + if (with_hash) + rte_hash_del_key_with_hash(h[table_index], + (const void *) keys[i], + signatures[i]); + else + rte_hash_del_key(h[table_index], + (const void *) keys[i]); + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); + + cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD; + + printf("\n%"PRIu64" deletions in %f seconds\n", (uint64_t) KEYS_TO_ADD, + seconds_taken); + printf("Average %"PRIu64" tsc ticks per deletion\n", + cycles[table_index][DELETE][with_hash]); + printf("Average %"PRIu64" deletions per second\n", + (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken); + 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; + + for (i = 0; i < NUM_KEYSIZES; i++) { + if (create_table(i) < 0) + return -1; + + if (get_input_keys(i) < 0) + return -1; + + printf("\n------ KEY SIZE = %u ----------\n\n", + hashtest_key_lens[i]); + printf("\n ----- WITH PRECOMPUTED HASH VALUES -----\n\n"); + + printf("\nTimed additions\n"); + printf("------------------\n"); + if (timed_adds(1, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + printf("\nTimed lookups\n"); + printf("------------------\n"); + if (timed_lookups(1, i) < 0) + return -1; + + printf("\nTimed deletions\n"); + printf("------------------\n"); + if (timed_deletes(1, i) < 0) + return -1; + + if (reset_table(i) < 0) + return -1; + + printf("\n ----- WITH JUST KEYS -----\n\n"); + + printf("\nTimed additions\n"); + printf("------------------\n"); + if (timed_adds(0, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + printf("\nTimed lookups\n"); + printf("------------------\n"); + if (timed_lookups(0, i) < 0) + return -1; + + printf("\nTimed lookups multi\n"); + printf("------------------\n"); + if (timed_lookups_multi(i) < 0) + return -1; + + printf("\nTimed deletions\n"); + printf("------------------\n"); + if (timed_deletes(0, i) < 0) + return -1; + + free_table(i); + + } + printf("\nResults (in CPU cycles/operation)\n"); + 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"); + } + 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"); + } + + return 0; +} + +/* Control operation of performance testing of fbk hash. */ +#define LOAD_FACTOR 0.667 /* How full to make the hash table. */ +#define TEST_SIZE 1000000 /* How many operations to time. */ +#define TEST_ITERATIONS 30 /* How many measurements to take. */ +#define ENTRIES (1 << 15) /* How many entries. */ + +static int +fbk_hash_perf_test(void) +{ + struct rte_fbk_hash_params params = { + .name = "fbk_hash_test", + .entries = ENTRIES, + .entries_per_bucket = 4, + .socket_id = rte_socket_id(), + }; + struct rte_fbk_hash_table *handle = NULL; + uint32_t *keys = NULL; + unsigned indexes[TEST_SIZE]; + 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); + if (handle == NULL) { + printf("Error creating table\n"); + return -1; + } + + keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); + 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++) { + key = (uint32_t)rte_rand(); + key = ((uint64_t)key << 32) | (uint64_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)) + break; + } + + for (i = 0; i < TEST_ITERATIONS; i++) { + uint64_t begin; + uint64_t end; + + /* Generate random indexes into keys[] array. */ + for (j = 0; j < TEST_SIZE; j++) + indexes[j] = rte_rand() % added; + + begin = rte_rdtsc(); + /* Do lookups */ + for (j = 0; j < TEST_SIZE; j++) + value += rte_fbk_hash_lookup(handle, keys[indexes[j]]); + + end = rte_rdtsc(); + lookup_time += (double)(end - begin); + } + + printf("\n\n *** FBK Hash function performance test results ***\n"); + /* + * The use of the 'value' variable ensures that the hash lookup is not + * being optimised out by the compiler. + */ + if (value != 0) + printf("Number of ticks per lookup = %g\n", + (double)lookup_time / + ((double)TEST_ITERATIONS * (double)TEST_SIZE)); + + rte_fbk_hash_free(handle); + + return 0; +} + +static int +test_hash_perf(void) +{ + if (run_all_tbl_perf_tests() < 0) + return -1; + + 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, +}; +REGISTER_TEST_COMMAND(hash_perf_cmd); diff --git a/app/test/test_hash_perf_new.c b/app/test/test_hash_perf_new.c deleted file mode 100644 index 1da1839..0000000 --- a/app/test/test_hash_perf_new.c +++ /dev/null @@ -1,560 +0,0 @@ -/*- - * BSD LICENSE - * - * Copyright(c) 2010-2015 Intel Corporation. All rights reserved. - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in - * the documentation and/or other materials provided with the - * distribution. - * * Neither the name of Intel Corporation nor the names of its - * contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#include -#include - -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include "test.h" - -#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 -}; - -static uint32_t hashtest_key_lens[] = { - 4, 8, 16, 32, 48, 64, /* standard key sizes */ - 9, /* IPv4 SRC + DST + protocol, unpadded */ - 13, /* IPv4 5-tuple, unpadded */ - 37, /* IPv6 5-tuple, unpadded */ - 40 /* IPv6 5-tuple, padded to 8-byte boundary */ -}; -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]; - -/* 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) -{ - 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; - -} - -/* Shuffle the keys that have been added, so lookups will be totally random */ -static void -shuffle_input_keys(unsigned table_index) -{ - unsigned i; - uint32_t swap_idx; - uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX]; - hash_sig_t temp_signature; - - for (i = 0; i < KEYS_TO_ADD; i++) { - do - swap_idx = rte_rand() % KEYS_TO_ADD; - while (swap_idx == i); - - memcpy(temp_key, keys[i], hashtest_key_lens[table_index]); - temp_signature = signatures[i]; - - memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]); - signatures[i] = signatures[swap_idx]; - - memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]); - signatures[swap_idx] = temp_signature; - } -} - -/* - * Creates the table and looks for random keys which - * ALL can fit in hash table (no errors) - */ -static int -get_input_keys(unsigned table_index) -{ - 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; - - for (i = 0; i < NUM_BUCKETS; i++) - buckets[i] = 0; - - 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; -} - -static int -timed_adds(unsigned with_hash, unsigned table_index) { - unsigned i; - const uint64_t start_tsc = rte_rdtsc(); - - for (i = 0; i < KEYS_TO_ADD; i++) { - if (with_hash) - rte_hash_add_key_with_hash(h[table_index], - (const void *) keys[i], - signatures[i]); - else - rte_hash_add_key(h[table_index], keys[i]); - } - - const uint64_t end_tsc = rte_rdtsc(); - const uint64_t time_taken = end_tsc - start_tsc; - const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); - - cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD; - - printf("\n%"PRIu64" adds in %f seconds\n", (uint64_t)KEYS_TO_ADD, - seconds_taken); - printf("Average %"PRIu64" tsc ticks per add\n", - cycles[table_index][ADD][with_hash]); - printf("Average %"PRIu64" adds per second\n", - (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken); - return 0; -} - -static int -timed_lookups(unsigned with_hash, unsigned table_index) -{ - unsigned i, j; - const uint64_t start_tsc = rte_rdtsc(); - - for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { - for (j = 0; j < KEYS_TO_ADD; j++) { - if (with_hash) - rte_hash_lookup_with_hash(h[table_index], - (const void *) keys[j], - signatures[j]); - else - rte_hash_lookup(h[table_index], keys[j]); - } - } - - const uint64_t end_tsc = rte_rdtsc(); - const uint64_t time_taken = end_tsc - start_tsc; - const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); - - cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS; - - printf("%"PRIu64" lookups in %f seconds\n", (uint64_t) NUM_LOOKUPS, - seconds_taken); - printf("Average %"PRIu64" tsc ticks per lookup\n", - cycles[table_index][LOOKUP][with_hash]); - printf("Average %"PRIu64" lookups per second\n", - (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken); - return 0; -} - -static int -timed_lookups_multi(unsigned table_index) -{ - 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); - } - } - - const uint64_t end_tsc = rte_rdtsc(); - const uint64_t time_taken = end_tsc - start_tsc; - const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); - - cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS; - - printf("%"PRIu64" lookups in %f seconds\n", (uint64_t)NUM_LOOKUPS, - seconds_taken); - printf("Average %"PRIu64" tsc ticks per lookup\n", - cycles[table_index][LOOKUP_MULTI][0]); - printf("Average %"PRIu64" lookups per second\n", - (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken); - return 0; -} - -static int -timed_deletes(unsigned with_hash, unsigned table_index) -{ - unsigned i; - const uint64_t start_tsc = rte_rdtsc(); - - for (i = 0; i < KEYS_TO_ADD; i++) { - if (with_hash) - rte_hash_del_key_with_hash(h[table_index], - (const void *) keys[i], - signatures[i]); - else - rte_hash_del_key(h[table_index], - (const void *) keys[i]); - } - - const uint64_t end_tsc = rte_rdtsc(); - const uint64_t time_taken = end_tsc - start_tsc; - const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); - - cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD; - - printf("\n%"PRIu64" deletions in %f seconds\n", (uint64_t) KEYS_TO_ADD, - seconds_taken); - printf("Average %"PRIu64" tsc ticks per deletion\n", - cycles[table_index][DELETE][with_hash]); - printf("Average %"PRIu64" deletions per second\n", - (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken); - 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; - - for (i = 0; i < NUM_KEYSIZES; i++) { - if (create_table(i) < 0) - return -1; - - if (get_input_keys(i) < 0) - return -1; - - printf("\n------ KEY SIZE = %u ----------\n\n", - hashtest_key_lens[i]); - printf("\n ----- WITH PRECOMPUTED HASH VALUES -----\n\n"); - - printf("\nTimed additions\n"); - printf("------------------\n"); - if (timed_adds(1, i) < 0) - return -1; - - for (j = 0; j < NUM_SHUFFLES; j++) - shuffle_input_keys(i); - - printf("\nTimed lookups\n"); - printf("------------------\n"); - if (timed_lookups(1, i) < 0) - return -1; - - printf("\nTimed deletions\n"); - printf("------------------\n"); - if (timed_deletes(1, i) < 0) - return -1; - - if (reset_table(i) < 0) - return -1; - - printf("\n ----- WITH JUST KEYS -----\n\n"); - - printf("\nTimed additions\n"); - printf("------------------\n"); - if (timed_adds(0, i) < 0) - return -1; - - for (j = 0; j < NUM_SHUFFLES; j++) - shuffle_input_keys(i); - - printf("\nTimed lookups\n"); - printf("------------------\n"); - if (timed_lookups(0, i) < 0) - return -1; - - printf("\nTimed lookups multi\n"); - printf("------------------\n"); - if (timed_lookups_multi(i) < 0) - return -1; - - printf("\nTimed deletions\n"); - printf("------------------\n"); - if (timed_deletes(0, i) < 0) - return -1; - - free_table(i); - - } - printf("\nResults (in CPU cycles/operation)\n"); - 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"); - } - 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"); - } - - return 0; -} - -/* Control operation of performance testing of fbk hash. */ -#define LOAD_FACTOR 0.667 /* How full to make the hash table. */ -#define TEST_SIZE 1000000 /* How many operations to time. */ -#define TEST_ITERATIONS 30 /* How many measurements to take. */ -#define ENTRIES (1 << 15) /* How many entries. */ - -static int -fbk_hash_perf_test(void) -{ - struct rte_fbk_hash_params params = { - .name = "fbk_hash_test", - .entries = ENTRIES, - .entries_per_bucket = 4, - .socket_id = rte_socket_id(), - }; - struct rte_fbk_hash_table *handle = NULL; - uint32_t *keys = NULL; - unsigned indexes[TEST_SIZE]; - 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); - if (handle == NULL) { - printf("Error creating table\n"); - return -1; - } - - keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); - 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++) { - key = (uint32_t)rte_rand(); - key = ((uint64_t)key << 32) | (uint64_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)) - break; - } - - for (i = 0; i < TEST_ITERATIONS; i++) { - uint64_t begin; - uint64_t end; - - /* Generate random indexes into keys[] array. */ - for (j = 0; j < TEST_SIZE; j++) - indexes[j] = rte_rand() % added; - - begin = rte_rdtsc(); - /* Do lookups */ - for (j = 0; j < TEST_SIZE; j++) - value += rte_fbk_hash_lookup(handle, keys[indexes[j]]); - - end = rte_rdtsc(); - lookup_time += (double)(end - begin); - } - - printf("\n\n *** FBK Hash function performance test results ***\n"); - /* - * The use of the 'value' variable ensures that the hash lookup is not - * being optimised out by the compiler. - */ - if (value != 0) - printf("Number of ticks per lookup = %g\n", - (double)lookup_time / - ((double)TEST_ITERATIONS * (double)TEST_SIZE)); - - rte_fbk_hash_free(handle); - - return 0; -} - -static int -test_hash_perf_new(void) -{ - if (run_all_tbl_perf_tests() < 0) - return -1; - - if (fbk_hash_perf_test() < 0) - return -1; - - return 0; -} - -static struct test_command hash_perf_new_cmd = { - .command = "hash_perf_new_autotest", - .callback = test_hash_perf_new, -}; -REGISTER_TEST_COMMAND(hash_perf_new_cmd); -- 2.4.2