From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga01.intel.com (mga01.intel.com [192.55.52.88]) by dpdk.org (Postfix) with ESMTP id 2D211C510 for ; Mon, 29 Jun 2015 00:25:34 +0200 (CEST) Received: from orsmga001.jf.intel.com ([10.7.209.18]) by fmsmga101.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="719249701" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by orsmga001.jf.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 t5SMPUtb030616; 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 t5SMPUoD010187; Sun, 28 Jun 2015 23:25:30 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t5SMPUVI010183; Sun, 28 Jun 2015 23:25:30 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Sun, 28 Jun 2015 23:25:22 +0100 Message-Id: <1435530330-10132-4-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 03/11] test/hash: enhance hash unit tests 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 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 --- app/test/Makefile | 2 +- app/test/test_hash.c | 59 ++++ app/test/test_hash_perf.c | 702 ------------------------------------------ app/test/test_hash_perf_new.c | 560 +++++++++++++++++++++++++++++++++ 4 files changed, 620 insertions(+), 703 deletions(-) delete mode 100644 app/test/test_hash_perf.c create mode 100644 app/test/test_hash_perf_new.c diff --git a/app/test/Makefile b/app/test/Makefile index 2e2758c..8624e95 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.c +SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_perf_new.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.c b/app/test/test_hash.c index 4300de9..46174db 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -1147,6 +1147,63 @@ 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_hash_crc; + 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 (-ENOENT != rte_hash_lookup(handle, simple_key)) + 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); + rte_hash_create(&ut_params); + } + + 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 +1462,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 deleted file mode 100644 index d0e5ce0..0000000 --- a/app/test/test_hash_perf.c +++ /dev/null @@ -1,702 +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 -#include -#include -#include -#include -#include - -#include "test.h" - -#include -#include -#include -#include - -/* 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 */ -}; - -/* 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; -}; - -#define ITERATIONS 10000 -#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15) - -/******************************************************************************* - * 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}, -}; - -/******************************************************************************/ - -/* - * 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) -{ - double sum = 0; - unsigned i; - for (i = 0; i < size; i++) - sum += array[i]; - return sum / (double)size; -} - -/* - * To help print out name of hash functions. - */ -static const char *get_hash_name(rte_hash_function f) -{ - if (f == rte_jhash) - return "jhash"; - - if (f == rte_hash_crc) - return "rte_hash_crc"; - - return "UnknownHash"; -} - -/* - * 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) -{ - 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; - - bucket_occupancies = rte_calloc("bucket occupancies", - num_buckets, sizeof(uint32_t), 16); - if (bucket_occupancies == NULL) { - rte_free(key); - return -1; - } - - ticks = 0; - *invalid_pos_count = 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(); - - /* Perform operation, and measure time it takes */ - begin = rte_rdtsc(); - pos = func(h, key); - end = rte_rdtsc(); - ticks += end - begin; - - /* Other work per iteration */ - if (pos < 0) - *invalid_pos_count += 1; - else - bucket_occupancies[pos / params->bucket_entries]++; - } - *avg_occupancy = get_avg(bucket_occupancies, num_buckets); - - rte_free(bucket_occupancies); - rte_free(key); - - return (double)ticks / params->num_iterations; -} - -/* - * To help print out what tests are being done. - */ -static const char * -get_tbl_perf_test_desc(enum hash_test_t type) -{ - 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"; - } -} - -/* - * Run a hash table performance test based on params. - */ -static int -run_tbl_perf_test(struct tbl_perf_test_params *params) -{ - 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; - } - - 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); - return 0; -} - -/* - * Run all hash table performance tests. - */ -static int run_all_tbl_perf_tests(void) -{ - unsigned i; - - 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"); - - /* Loop through every combination of test parameters */ - for (i = 0; - i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params); - i++) { - - /* Perform test */ - if (run_tbl_perf_test(&tbl_perf_params[i]) < 0) - return -1; - } - 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; - unsigned i, j; - - handle = rte_fbk_hash_create(¶ms); - RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed"); - - keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); - RETURN_IF_ERROR_FBK(keys == NULL, - "fbk hash: memory allocation for key store failed"); - - /* Generate random keys and values. */ - for (i = 0; i < ENTRIES; i++) { - uint32_t key = (uint32_t)rte_rand(); - key = ((uint64_t)key << 32) | (uint64_t)rte_rand(); - uint16_t 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; -} - -/* - * Do all unit and performance tests. - */ -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 new file mode 100644 index 0000000..1da1839 --- /dev/null +++ b/app/test/test_hash_perf_new.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_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