*
* Userspace RCU library - RCU Judy Array population size test
*
- * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ * Copyright 2012-2013 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
*/
/*
- * 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 <stdio.h>
#include <time.h>
#include <string.h>
#include <limits.h>
+#include <assert.h>
static int sel_pool_len = 50; /* default */
static int nr_distrib = 2; /* default */
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)
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;
}
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]++;
+ }
}
}
}
}
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
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");
}
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();
}
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) {
while (1) {
gen_pool();
count_pool();
- //print_pool();
- //print_count();
+ if (verbose) {
+ print_pool();
+ print_count();
+ }
stat_count();
if (!(i % 100000ULL))
print_stat(i);
projects / userspace-rcu.git / blobdiff