X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Ftestpop.c;h=76dbb03f7ac86572a736a97c83c886a0a7f569da;hb=refs%2Fheads%2Furcu%2Frcuja-range;hp=50d7a21d2dbfea554f8a9ee70b2f03f48651a6f5;hpb=3d45251f76e14c611c1e2d393f605900a20409a6;p=userspace-rcu.git diff --git a/rcuja/testpop.c b/rcuja/testpop.c index 50d7a21..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 @@ -21,12 +21,9 @@ */ /* - * This program generates random populations, and shows the worse-case - * unbalance, as well as the distribution of unbalance encountered. - * Remember that the unbalance is the delta between the lowest and - * largest population. Therefore, to get the delta between the subclass - * size and the actual number of items, we need to divide the unbalance - * by the number of subclasses (by hand). + * This program generates random populations, and shows the largest + * sub-class generated, as well as the distribution of sub-class size + * for the largest sub-class of each population. */ #include @@ -35,6 +32,7 @@ #include #include #include +#include static int sel_pool_len = 50; /* default */ static int nr_distrib = 2; /* default */ @@ -45,9 +43,13 @@ 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 int global_max_minunbalance = 0; +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 unbalance_distrib[256]; +static unsigned int subclass_len_distrib[256]; + +static int verbose; static uint8_t random_char(void) @@ -95,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; @@ -106,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]++; + } } } } @@ -145,53 +157,94 @@ void print_count(void) } static -void stat_count(void) +void stat_count_1d(void) { - int minunbalance = 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 < minunbalance) { - minunbalance = diff; - } + 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] < minunbalance) { - minunbalance = diff[0]; - } +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 (minunbalance > global_max_minunbalance) { - global_max_minunbalance = minunbalance; +static +void stat_count(void) +{ + switch (nr_distrib) { + case 2: + stat_count_1d(); + break; + case 4: + stat_count_2d(); + break; + default: + assert(0); + break; } - unbalance_distrib[minunbalance]++; } static @@ -201,15 +254,17 @@ void print_distrib(void) unsigned long long tot = 0; for (i = 0; i < 256; i++) { - tot += unbalance_distrib[i]; + tot += subclass_len_distrib[i]; } if (tot == 0) return; printf("Distribution:\n"); for (i = 0; i < 256; i++) { + if (!subclass_len_distrib[i]) + continue; printf("(%u, %u, %llu%%) ", - i, unbalance_distrib[i], - 100 * (unsigned long long) unbalance_distrib[i] / tot); + i, subclass_len_distrib[i], + 100 * (unsigned long long) subclass_len_distrib[i] / tot); } printf("\n"); } @@ -217,8 +272,8 @@ void print_distrib(void) static void print_stat(uint64_t i) { - printf("after %llu pools, global_max_minunbalance: %d\n", - (unsigned long long) i, global_max_minunbalance); + printf("after %llu pools, global_max_minsubclass_len: %d\n", + (unsigned long long) i, global_max_minsubclass_len); print_distrib(); } @@ -244,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) { @@ -255,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);