X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Ftestpop.c;h=76dbb03f7ac86572a736a97c83c886a0a7f569da;hb=refs%2Fheads%2Furcu%2Frcuja-range;hp=002ebaccf6ae62bed72f4ba17777a1ae2bee04d4;hpb=c7b5bcc325eeb21c655403563b1526814ab05bf3;p=userspace-rcu.git diff --git a/rcuja/testpop.c b/rcuja/testpop.c index 002ebac..76dbb03 100644 --- a/rcuja/testpop.c +++ b/rcuja/testpop.c @@ -3,7 +3,7 @@ * * Userspace RCU library - RCU Judy Array population size test * - * Copyright 2012 - Mathieu Desnoyers + * Copyright 2012-2013 - Mathieu Desnoyers * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -32,6 +32,7 @@ #include #include #include +#include static int sel_pool_len = 50; /* default */ static int nr_distrib = 2; /* default */ @@ -42,10 +43,14 @@ static uint8_t pool[256]; static uint8_t nr_one[8]; static uint8_t nr_2d_11[8][8]; static uint8_t nr_2d_10[8][8]; +static uint8_t nr_2d_01[8][8]; +static uint8_t nr_2d_00[8][8]; static int global_max_minsubclass_len = 0; static unsigned int subclass_len_distrib[256]; +static int verbose; + static uint8_t random_char(void) { @@ -92,6 +97,9 @@ void count_pool(void) memset(nr_one, 0, sizeof(nr_one)); memset(nr_2d_11, 0, sizeof(nr_2d_11)); memset(nr_2d_10, 0, sizeof(nr_2d_10)); + memset(nr_2d_01, 0, sizeof(nr_2d_01)); + memset(nr_2d_00, 0, sizeof(nr_2d_00)); + for (i = 0; i < sel_pool_len; i++) { if (nr_distrib == 2) { int j; @@ -103,15 +111,22 @@ void count_pool(void) } if (nr_distrib == 4) { - int j, k; - - for (j = 0; j < 8; j++) { - for (k = 0; k < j; k++) { - if ((pool[i] & (1U << j)) && (pool[i] & (1U << k))) { - nr_2d_11[j][k]++; - } - if ((pool[i] & (1U << j)) && !(pool[i] & (1U << k))) { - nr_2d_10[j][k]++; + int bit_i, bit_j; + + for (bit_i = 0; bit_i < 8; bit_i++) { + for (bit_j = 0; bit_j < bit_i; bit_j++) { + if (pool[i] & (1U << bit_i)) { + if (pool[i] & (1U << bit_j)) { + nr_2d_11[bit_i][bit_j]++; + } else { + nr_2d_10[bit_i][bit_j]++; + } + } else { + if (pool[i] & (1U << bit_j)) { + nr_2d_01[bit_i][bit_j]++; + } else { + nr_2d_00[bit_i][bit_j]++; + } } } } @@ -142,53 +157,94 @@ void print_count(void) } static -void stat_count(void) +void stat_count_1d(void) { - int minsubclass_len = INT_MAX; - - if (nr_distrib == 2) { - int i; + unsigned int overall_best_distance = UINT_MAX; + unsigned int overall_minsubclass_len; + int i; - for (i = 0; i < 8; i++) { - int diff; + for (i = 0; i < 8; i++) { + int distance_to_best; - diff = (int) nr_one[i] * 2 - sel_pool_len; - if (diff < 0) - diff = -diff; - if ((diff >> 1) < minsubclass_len) { - minsubclass_len = diff >> 1; - } + distance_to_best = ((unsigned int) nr_one[i] << 1U) - sel_pool_len; + if (distance_to_best < 0) + distance_to_best = -distance_to_best; + if (distance_to_best < overall_best_distance) { + overall_best_distance = distance_to_best; } } + overall_minsubclass_len = (overall_best_distance + sel_pool_len) >> 1UL; + if (overall_minsubclass_len > global_max_minsubclass_len) { + global_max_minsubclass_len = overall_minsubclass_len; + } + subclass_len_distrib[overall_minsubclass_len]++; +} - if (nr_distrib == 4) { - int j, k; - - for (j = 0; j < 8; j++) { - for (k = 0; k < j; k++) { - int diff[2]; - - diff[0] = (int) nr_2d_11[j][k] * 4 - sel_pool_len; - if (diff[0] < 0) - diff[0] = -diff[0]; - - diff[1] = (int) nr_2d_10[j][k] * 4 - sel_pool_len; - if (diff[1] < 0) - diff[1] = -diff[1]; - /* Get max linear array size */ - if (diff[1] > diff[0]) - diff[0] = diff[1]; - if ((diff[0] >> 2) < minsubclass_len) { - minsubclass_len = diff[0] >> 2; - } +static +void stat_count_2d(void) +{ + int overall_best_distance = INT_MAX; + unsigned int overall_minsubclass_len = 0; + int bit_i, bit_j; + + for (bit_i = 0; bit_i < 8; bit_i++) { + for (bit_j = 0; bit_j < bit_i; bit_j++) { + int distance_to_best[4], subclass_len[4]; + + distance_to_best[0] = ((unsigned int) nr_2d_11[bit_i][bit_j] << 2U) - sel_pool_len; + distance_to_best[1] = ((unsigned int) nr_2d_10[bit_i][bit_j] << 2U) - sel_pool_len; + distance_to_best[2] = ((unsigned int) nr_2d_01[bit_i][bit_j] << 2U) - sel_pool_len; + distance_to_best[3] = ((unsigned int) nr_2d_00[bit_i][bit_j] << 2U) - sel_pool_len; + + subclass_len[0] = nr_2d_11[bit_i][bit_j]; + subclass_len[1] = nr_2d_10[bit_i][bit_j]; + subclass_len[2] = nr_2d_01[bit_i][bit_j]; + subclass_len[3] = nr_2d_00[bit_i][bit_j]; + + /* Consider worse distance above best */ + if (distance_to_best[1] > 0 && distance_to_best[1] > distance_to_best[0]) { + distance_to_best[0] = distance_to_best[1]; + subclass_len[0] = subclass_len[1]; + } + if (distance_to_best[2] > 0 && distance_to_best[2] > distance_to_best[0]) { + distance_to_best[0] = distance_to_best[2]; + subclass_len[0] = subclass_len[2]; + } + if (distance_to_best[3] > 0 && distance_to_best[3] > distance_to_best[0]) { + distance_to_best[0] = distance_to_best[3]; + subclass_len[0] = subclass_len[3]; + } + + /* + * If our worse distance is better than overall, + * we become new best candidate. + */ + if (distance_to_best[0] < overall_best_distance) { + overall_best_distance = distance_to_best[0]; + overall_minsubclass_len = subclass_len[0]; } } } + if (overall_minsubclass_len > global_max_minsubclass_len) { + global_max_minsubclass_len = overall_minsubclass_len; + } + subclass_len_distrib[overall_minsubclass_len]++; +} - if (minsubclass_len > global_max_minsubclass_len) { - global_max_minsubclass_len = minsubclass_len; +static +void stat_count(void) +{ + switch (nr_distrib) { + case 2: + stat_count_1d(); + break; + case 4: + stat_count_2d(); + break; + default: + assert(0); + break; } - subclass_len_distrib[minsubclass_len]++; } static @@ -204,6 +260,8 @@ void print_distrib(void) return; printf("Distribution:\n"); for (i = 0; i < 256; i++) { + if (!subclass_len_distrib[i]) + continue; printf("(%u, %u, %llu%%) ", i, subclass_len_distrib[i], 100 * (unsigned long long) subclass_len_distrib[i] / tot); @@ -214,7 +272,7 @@ void print_distrib(void) static void print_stat(uint64_t i) { - printf("after %llu pools, global_max_minsubclass_len extra: %d\n", + printf("after %llu pools, global_max_minsubclass_len: %d\n", (unsigned long long) i, global_max_minsubclass_len); print_distrib(); } @@ -241,6 +299,13 @@ int main(int argc, char **argv) return -1; } } + + if (argc > 3) { + if (!strcmp(argv[3], "-v")) { + verbose = 1; + } + } + printf("pool distributions: %d\n", nr_distrib); if (nr_distrib != 2 && nr_distrib != 4) { @@ -252,8 +317,10 @@ int main(int argc, char **argv) while (1) { gen_pool(); count_pool(); - //print_pool(); - //print_count(); + if (verbose) { + print_pool(); + print_count(); + } stat_count(); if (!(i % 100000ULL)) print_stat(i);