[dpdk-dev] [PATCH] test/hash: improve hash unit tests

[Bruce Richardson]

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 at 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