From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id E4BDAA00C5; Wed, 31 Aug 2022 08:47:23 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 533294281B; Wed, 31 Aug 2022 08:47:18 +0200 (CEST) Received: from mga06.intel.com (mga06b.intel.com [134.134.136.31]) by mails.dpdk.org (Postfix) with ESMTP id 96C96400D6 for ; Wed, 31 Aug 2022 08:47:15 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1661928435; x=1693464435; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=Sp8zTI5NjyeuMRKcjdPK4lYENyBA2xuz/8jmLK59CAg=; b=OSEIc936UY/f5sZFnXjsWAh6npEpkdqc6CoFuSHT+43oLIbzhgeZ69OO SN5vDvC8MA9Ye+OW7ADoKgxlSb0V3KKpbZ123pEYrUPiwvcWmj5uBBmBZ f10bham+LNKjHvvH92aGMAHIvEnn8iheyVUWytba7NruLuNj86LAAI7rU kXKuf2kBCC8FIpND+o/djZWDR/r6WvKHeOqMNdPzdzznCxlySsUPiFQr7 tG0PBxcTkmK+2C8TMHWgPaNK9A//sOM3JaQi4BegUU7+c559gXNaus68b r0BrEyNg3BDzGvMBZkeC8lObcb+P8X7WioSHCaNTJciDWeocxOQWAQUpM w==; X-IronPort-AV: E=McAfee;i="6500,9779,10455"; a="357102914" X-IronPort-AV: E=Sophos;i="5.93,277,1654585200"; d="scan'208";a="357102914" Received: from orsmga005.jf.intel.com ([10.7.209.41]) by orsmga104.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 30 Aug 2022 23:46:53 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.93,277,1654585200"; d="scan'208";a="787774781" Received: from dpdk-lrong-icx-01.sh.intel.com ([10.67.119.18]) by orsmga005.jf.intel.com with ESMTP; 30 Aug 2022 23:46:50 -0700 From: Leyi Rong To: ferruh.yigit@xilinx.com, suanmingm@nvidia.com, yipeng1.wang@intel.com, zaoxingliu@gmail.com, sameh.gobriel@intel.com Cc: dev@dpdk.org, Leyi Rong Subject: [PATCH v2 2/2] test/member: add functional and perf tests for sketch Date: Wed, 31 Aug 2022 14:46:39 +0800 Message-Id: <20220831064639.4163765-3-leyi.rong@intel.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220831064639.4163765-1-leyi.rong@intel.com> References: <20220810074518.1695013-1-leyi.rong@intel.com> <20220831064639.4163765-1-leyi.rong@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org This patch adds functional and performance tests for sketch mode of membership library. Signed-off-by: Yipeng Wang Signed-off-by: Leyi Rong --- app/test/test_member.c | 272 ++++++++++++++++++++++++++++++++++++ app/test/test_member_perf.c | 153 +++++++++++++++++++- 2 files changed, 421 insertions(+), 4 deletions(-) diff --git a/app/test/test_member.c b/app/test/test_member.c index 26a712439f..8266e6437b 100644 --- a/app/test/test_member.c +++ b/app/test/test_member.c @@ -4,6 +4,7 @@ /* This test is for membership library's simple feature test */ +#include #include "test.h" #include @@ -28,6 +29,7 @@ test_member(void) struct rte_member_setsum *setsum_ht; struct rte_member_setsum *setsum_cache; struct rte_member_setsum *setsum_vbf; +struct rte_member_setsum *setsum_sketch; /* 5-tuple key type */ struct flow_key { @@ -108,6 +110,21 @@ static struct rte_member_parameters params = { .socket_id = 0 /* NUMA Socket ID for memory. */ }; +/* for sketch definitions */ +#define TOP_K 10 +#define HH_PKT_SIZE 16 +#define SKETCH_ERROR_RATE 0.05 +#define SKETCH_SAMPLE_RATE 0.001 +#define PRINT_OUT_COUNT 20 + +#define SKETCH_LARGEST_KEY_SIZE 1000000 +#define SKETCH_TOTAL_KEY 500 +#define NUM_OF_KEY(key) {\ + (unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (key + 1)) \ +} + +void *heavy_hitters[TOP_K]; + /* * Sequence of operations for find existing setsummary * @@ -684,6 +701,257 @@ perform_free(void) rte_member_free(setsum_vbf); } +static void +print_out_sketch_results(uint64_t *count_result, member_set_t *heavy_set, + uint32_t print_num, bool count_byte) +{ + uint32_t i; + + for (i = 0; i < print_num; i++) { + if (count_byte) + printf("key %2u, count %8"PRIu64", real count %8u, " + "heavy_set %u, deviation rate [%.04f]\n", + i, count_result[i], + (unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1)) * + HH_PKT_SIZE, + heavy_set[i], + fabs((float)count_result[i] - (float)NUM_OF_KEY(i) * HH_PKT_SIZE) / + ((float)NUM_OF_KEY(i) * HH_PKT_SIZE)); + else + printf("key %2u, count %8"PRIu64", real count %8u, " + "heavy_set %u, deviation rate [%.04f]\n", + i, count_result[i], + (unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1)), + heavy_set[i], + fabs((float)count_result[i] - (float)NUM_OF_KEY(i)) / + (float)NUM_OF_KEY(i)); + } +} + +static int +sketch_test(uint32_t *keys, uint32_t total_pkt, int count_byte, int reset_test) +{ + uint32_t i; + uint64_t result_count[SKETCH_TOTAL_KEY]; + member_set_t heavy_set[SKETCH_TOTAL_KEY]; + uint64_t count[TOP_K]; + int ret; + int hh_cnt; + + setsum_sketch = rte_member_create(¶ms); + if (setsum_sketch == NULL) { + printf("Creation of setsums fail\n"); + return -1; + } + + for (i = 0; i < total_pkt; i++) { + if (count_byte) + ret = rte_member_add_byte_count(setsum_sketch, &keys[i], HH_PKT_SIZE); + else + ret = rte_member_add(setsum_sketch, &keys[i], 1); + + if (ret < 0) { + printf("rte_member_add Failed! Error [%d]\n", ret); + rte_member_free(setsum_sketch); + + return -1; + } + } + + for (i = 0; i < SKETCH_TOTAL_KEY; i++) { + uint32_t tmp_key = i; + + rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]); + rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]); + } + + print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte); + + hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count); + if (hh_cnt < 0) { + printf("sketch report heavy hitter error!"); + rte_member_free(setsum_sketch); + + return -1; + } + + printf("Report heavy hitters:"); + for (i = 0; i < (unsigned int)hh_cnt; i++) { + printf("%u: %"PRIu64"\t", + *((uint32_t *)heavy_hitters[i]), count[i]); + } + printf("\n"); + + if (reset_test) { + printf("\nEntering Sketch Reset Test Process!\n"); + rte_member_reset(setsum_sketch); + + /* after reset, check some key's count */ + for (i = 0; i < SKETCH_TOTAL_KEY; i++) { + uint32_t tmp_key = i; + + rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]); + rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]); + } + + print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte); + + printf("\nReinsert keys after Sketch Reset!\n"); + for (i = 0; i < total_pkt; i++) { + if (count_byte) + ret = rte_member_add_byte_count + (setsum_sketch, &keys[i], HH_PKT_SIZE); + else + ret = rte_member_add(setsum_sketch, &keys[i], 1); + + if (ret < 0) { + printf("rte_member_add Failed! Error [%d]\n", ret); + rte_member_free(setsum_sketch); + + return -1; + } + } + + for (i = 0; i < SKETCH_TOTAL_KEY; i++) { + uint32_t tmp_key = i; + + rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]); + rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]); + } + + print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte); + + hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count); + if (hh_cnt < 0) { + printf("sketch report heavy hitter error!"); + rte_member_free(setsum_sketch); + + return -1; + } + printf("Report heavy hitters:"); + for (i = 0; i < (unsigned int)hh_cnt; i++) { + printf("%u: %"PRIu64"\t", + *((uint32_t *)heavy_hitters[i]), count[i]); + } + printf("\n"); + + printf("\nDelete some keys!\n"); + uint32_t tmp_key = 0; + + rte_member_delete(setsum_sketch, (void *)&tmp_key, 0); + tmp_key = 1; + rte_member_delete(setsum_sketch, (void *)&tmp_key, 0); + + for (i = 0; i < SKETCH_TOTAL_KEY; i++) { + uint32_t tmp_key = i; + + rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]); + rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]); + } + + print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte); + + hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count); + if (hh_cnt < 0) { + printf("sketch report heavy hitter error!"); + rte_member_free(setsum_sketch); + + return -1; + } + printf("Report heavy hitters:"); + for (i = 0; i < (unsigned int)hh_cnt; i++) { + printf("%u: %"PRIu64"\t", + *((uint32_t *)heavy_hitters[i]), count[i]); + } + printf("\n"); + } + + rte_member_free(setsum_sketch); + return 0; +} + +static int +test_member_sketch(void) +{ + unsigned int i, j, index; + uint32_t total_pkt = 0; + uint32_t *keys; + int count_byte = 0; + + for (i = 0; i < SKETCH_TOTAL_KEY; i++) + total_pkt += ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1)); + + printf("\nTotal key count [%u] in Sketch Autotest\n", total_pkt); + + keys = rte_zmalloc(NULL, sizeof(uint32_t) * total_pkt, 0); + + if (keys == NULL) { + printf("RTE_ZMALLOC failed\n"); + return -1; + } + + index = 0; + for (i = 0; i < SKETCH_TOTAL_KEY; i++) { + for (j = 0; j < ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1)); j++) + keys[index++] = i; + } + + /* shuffle the keys */ + for (i = index - 1; i > 0; i--) { + uint32_t swap_idx = rte_rand() % i; + uint32_t tmp_key = keys[i]; + + keys[i] = keys[swap_idx]; + keys[swap_idx] = tmp_key; + } + + params.key_len = 4; + params.name = "test_member_sketch"; + params.type = RTE_MEMBER_TYPE_SKETCH; + params.error_rate = SKETCH_ERROR_RATE; + params.sample_rate = SKETCH_SAMPLE_RATE; + params.extra_flag = 0; + params.top_k = TOP_K; + params.prim_hash_seed = rte_rdtsc(); + int reset_test = 0; + + printf("Default sketching params: Error Rate: [%f]\tSample Rate: [%f]\tTopK: [%d]\n", + SKETCH_ERROR_RATE, SKETCH_SAMPLE_RATE, TOP_K); + + printf("\n[Sketch with Fixed Sampling Rate Mode]\n"); + if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) { + rte_free(keys); + return -1; + } + + params.extra_flag |= RTE_MEMBER_SKETCH_ALWAYS_BOUNDED; + printf("\n[Sketch with Always Bounded Mode]\n"); + if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) { + rte_free(keys); + return -1; + } + + count_byte = 1; + params.extra_flag |= RTE_MEMBER_SKETCH_COUNT_BYTE; + printf("\n[Sketch with Packet Size Mode]\n"); + if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) { + rte_free(keys); + return -1; + } + + count_byte = 0; + params.extra_flag = 0; + reset_test = 1; + printf("\nreset sketch test\n"); + if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) { + rte_free(keys); + return -1; + } + + rte_free(keys); + return 0; +} + static int test_member(void) { @@ -719,6 +987,10 @@ test_member(void) return -1; } + if (test_member_sketch() < 0) { + perform_free(); + return -1; + } perform_free(); return 0; } diff --git a/app/test/test_member_perf.c b/app/test/test_member_perf.c index 978db0020a..b7eb3e4c66 100644 --- a/app/test/test_member_perf.c +++ b/app/test/test_member_perf.c @@ -13,6 +13,7 @@ #include #include #include +#include #ifdef RTE_EXEC_ENV_WINDOWS static int @@ -26,7 +27,7 @@ test_member_perf(void) #include -#define NUM_KEYSIZES 10 +#define NUM_KEYSIZES RTE_DIM(hashtest_key_lens) #define NUM_SHUFFLES 10 #define MAX_KEYSIZE 64 #define MAX_ENTRIES (1 << 19) @@ -36,12 +37,23 @@ test_member_perf(void) #define BURST_SIZE 64 #define VBF_FALSE_RATE 0.03 +/* for the heavy hitter detection */ +#define SKETCH_LARGEST_KEY_SIZE (1<<15) +#define SKETCH_PKT_SIZE 16 +#define TOP_K 100 +#define SKETCH_ERROR_RATE 0.05 +#define SKETCH_SAMPLE_RATE 0.001 +#define NUM_ADDS (KEYS_TO_ADD * 20) + static unsigned int test_socket_id; enum sstype { HT = 0, CACHE, VBF, + SKETCH, + SKETCH_BOUNDED, + SKETCH_BYTE, NUM_TYPE }; @@ -88,6 +100,7 @@ static member_set_t data[NUM_TYPE][/* Array to store the data */KEYS_TO_ADD]; /* Array to store all input keys */ static uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; +static uint8_t hh_keys[KEYS_TO_ADD][MAX_KEYSIZE]; /* Shuffle the keys that have been added, so lookups will be totally random */ static void @@ -136,6 +149,10 @@ setup_keys_and_data(struct member_perf_params *params, unsigned int cycle, { unsigned int i, j; int num_duplicates; + int distinct_key = 0; + int count_down = SKETCH_LARGEST_KEY_SIZE; + uint32_t swap_idx; + uint8_t temp_key[MAX_KEYSIZE]; params->key_size = hashtest_key_lens[cycle]; params->cycle = cycle; @@ -176,6 +193,22 @@ setup_keys_and_data(struct member_perf_params *params, unsigned int cycle, /* Shuffle the random values again */ shuffle_input_keys(params); + for (i = 0; i < KEYS_TO_ADD; i++) { + if (count_down == 0) { + distinct_key++; + count_down = ceil(SKETCH_LARGEST_KEY_SIZE / (distinct_key + 1)); + } + memcpy(hh_keys[i], keys[distinct_key], params->key_size); + count_down--; + } + + for (i = KEYS_TO_ADD - 1; i > 0; i--) { + swap_idx = rte_rand() % i; + memcpy(temp_key, hh_keys[i], params->key_size); + memcpy(hh_keys[i], hh_keys[swap_idx], params->key_size); + memcpy(hh_keys[swap_idx], temp_key, params->key_size); + } + /* For testing miss lookup, we insert half and lookup the other half */ unsigned int entry_cnt, bf_key_cnt; if (!miss) { @@ -208,6 +241,44 @@ setup_keys_and_data(struct member_perf_params *params, unsigned int cycle, params->setsum[VBF] = rte_member_create(&member_params); if (params->setsum[VBF] == NULL) fprintf(stderr, "VBF create fail\n"); + + member_params.name = "test_member_sketch"; + member_params.key_len = params->key_size; + member_params.type = RTE_MEMBER_TYPE_SKETCH; + member_params.error_rate = SKETCH_ERROR_RATE; + member_params.sample_rate = SKETCH_SAMPLE_RATE; + member_params.extra_flag = 0; + member_params.top_k = TOP_K; + member_params.prim_hash_seed = rte_rdtsc(); + params->setsum[SKETCH] = rte_member_create(&member_params); + if (params->setsum[SKETCH] == NULL) + fprintf(stderr, "sketch create fail\n"); + + member_params.name = "test_member_sketch_bounded"; + member_params.key_len = params->key_size; + member_params.type = RTE_MEMBER_TYPE_SKETCH; + member_params.error_rate = SKETCH_ERROR_RATE; + member_params.sample_rate = SKETCH_SAMPLE_RATE; + member_params.extra_flag |= RTE_MEMBER_SKETCH_ALWAYS_BOUNDED; + member_params.top_k = TOP_K; + member_params.prim_hash_seed = rte_rdtsc(); + params->setsum[SKETCH_BOUNDED] = rte_member_create(&member_params); + if (params->setsum[SKETCH_BOUNDED] == NULL) + fprintf(stderr, "sketch create fail\n"); + + member_params.name = "test_member_sketch_byte"; + member_params.key_len = params->key_size; + member_params.type = RTE_MEMBER_TYPE_SKETCH; + member_params.error_rate = SKETCH_ERROR_RATE; + member_params.sample_rate = SKETCH_SAMPLE_RATE; + member_params.extra_flag |= RTE_MEMBER_SKETCH_COUNT_BYTE; + member_params.top_k = TOP_K; + member_params.prim_hash_seed = rte_rdtsc(); + params->setsum[SKETCH_BYTE] = rte_member_create(&member_params); + if (params->setsum[SKETCH_BYTE] == NULL) + fprintf(stderr, "sketch create fail\n"); + + for (i = 0; i < NUM_TYPE; i++) { if (params->setsum[i] == NULL) return -1; @@ -243,6 +314,39 @@ timed_adds(struct member_perf_params *params, int type) return 0; } +static int +timed_adds_sketch(struct member_perf_params *params, int type) +{ + const uint64_t start_tsc = rte_rdtsc(); + unsigned int i, j, a; + int32_t ret; + + for (i = 0; i < NUM_ADDS / KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD; j++) { + if (type == SKETCH_BYTE) + ret = rte_member_add_byte_count(params->setsum[type], + &hh_keys[j], SKETCH_PKT_SIZE); + else + ret = rte_member_add(params->setsum[type], &hh_keys[j], 1); + if (ret < 0) { + printf("Error %d in rte_member_add - key=0x", ret); + for (a = 0; a < params->key_size; a++) + printf("%02x", hh_keys[j][a]); + printf("type: %d\n", type); + + return -1; + } + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[type][params->cycle][ADD] = time_taken / NUM_ADDS; + + return 0; +} + static int timed_lookups(struct member_perf_params *params, int type) { @@ -279,6 +383,36 @@ timed_lookups(struct member_perf_params *params, int type) return 0; } +static int +timed_lookups_sketch(struct member_perf_params *params, int type) +{ + unsigned int i, j; + + false_data[type][params->cycle] = 0; + + const uint64_t start_tsc = rte_rdtsc(); + member_set_t result; + int ret; + + for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD; j++) { + ret = rte_member_lookup(params->setsum[type], &hh_keys[j], + &result); + if (ret < 0) { + printf("lookup wrong internally"); + return -1; + } + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[type][params->cycle][LOOKUP] = time_taken / NUM_LOOKUPS; + + return 0; +} + static int timed_lookups_bulk(struct member_perf_params *params, int type) { @@ -531,7 +665,7 @@ run_all_tbl_perf_tests(void) printf("Could not create keys/data/table\n"); return -1; } - for (j = 0; j < NUM_TYPE; j++) { + for (j = 0; j < SKETCH; j++) { if (timed_adds(¶ms, j) < 0) return exit_with_fail("timed_adds", ¶ms, @@ -562,6 +696,17 @@ run_all_tbl_perf_tests(void) /* Print a dot to show progress on operations */ } + + for (j = SKETCH; j < NUM_TYPE; j++) { + if (timed_adds_sketch(¶ms, j) < 0) + return exit_with_fail + ("timed_adds_sketch", ¶ms, i, j); + + if (timed_lookups_sketch(¶ms, j) < 0) + return exit_with_fail + ("timed_lookups_sketch", ¶ms, i, j); + } + printf("."); fflush(stdout); @@ -574,7 +719,7 @@ run_all_tbl_perf_tests(void) printf("Could not create keys/data/table\n"); return -1; } - for (j = 0; j < NUM_TYPE; j++) { + for (j = 0; j < SKETCH; j++) { if (timed_miss_lookup(¶ms, j) < 0) return exit_with_fail("timed_miss_lookup", ¶ms, i, j); @@ -605,7 +750,7 @@ run_all_tbl_perf_tests(void) "fr_multi_bulk", "false_positive_rate"); /* Key size not influence False rate so just print out one key size */ for (i = 0; i < 1; i++) { - for (j = 0; j < NUM_TYPE; j++) { + for (j = 0; j < SKETCH; j++) { printf("%-18d", hashtest_key_lens[i]); printf("%-18d", j); printf("%-18f", (float)false_data[j][i] / NUM_LOOKUPS); -- 2.25.1