X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Ftestpop.c;h=67bde86ca01889ce07e8663a744f41c8717f6aa4;hb=600eddfdc1cd8444544bfb1e04a56f886b949250;hp=50d7a21d2dbfea554f8a9ee70b2f03f48651a6f5;hpb=3d45251f76e14c611c1e2d393f605900a20409a6;p=userspace-rcu.git diff --git a/rcuja/testpop.c b/rcuja/testpop.c index 50d7a21..67bde86 100644 --- a/rcuja/testpop.c +++ b/rcuja/testpop.c @@ -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 @@ -45,9 +42,12 @@ 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 int global_max_best_distance = 0; -static unsigned int unbalance_distrib[256]; +static unsigned int subclass_len_distrib[256]; static uint8_t random_char(void) @@ -95,6 +95,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 +109,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]++; + } } } } @@ -147,7 +157,8 @@ void print_count(void) static void stat_count(void) { - int minunbalance = INT_MAX; + int minsubclass_len = INT_MAX; + int overall_best_distance = INT_MAX; if (nr_distrib == 2) { int i; @@ -158,40 +169,62 @@ void stat_count(void) diff = (int) nr_one[i] * 2 - sel_pool_len; if (diff < 0) diff = -diff; - if (diff < minunbalance) { - minunbalance = diff; + if ((diff >> 1) < minsubclass_len) { + minsubclass_len = diff >> 1; } } + if (minsubclass_len > global_max_minsubclass_len) { + global_max_minsubclass_len = minsubclass_len; + } + subclass_len_distrib[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]; + 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] = (nr_2d_11[bit_i][bit_j] << 2U) - sel_pool_len; + distance_to_best[1] = (nr_2d_10[bit_i][bit_j] << 2U) - sel_pool_len; + distance_to_best[2] = (nr_2d_01[bit_i][bit_j] << 2U) - sel_pool_len; + distance_to_best[3] = (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]; + minsubclass_len = subclass_len[0]; } } } + if (overall_best_distance > global_max_best_distance) { + global_max_best_distance = overall_best_distance; + } + subclass_len_distrib[minsubclass_len]++; } - - if (minunbalance > global_max_minunbalance) { - global_max_minunbalance = minunbalance; - } - unbalance_distrib[minunbalance]++; } static @@ -201,15 +234,15 @@ 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++) { 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 +250,9 @@ 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 extra: %d global_max_best_distance %d\n", + (unsigned long long) i, global_max_minsubclass_len, + global_max_best_distance); print_distrib(); }