tot entries unbalance largest linear array (stat. approx.)
---------------------------------------------------------------------
-41 entries: 9 20.5+4.5=25 (target ~50/2=25)
-47 entries: 9 23.5+4.5=28 (target ~56/2=28)
+48 entries: 2 (98%) 24+1=25 (target ~50/2=25)
+54 entries: 2 (97%) 27+1=28 (target ~56/2=28)
Note: there exists rare worse cases where the unbalance is larger, but
it happens _very_ rarely. But need to provide a fallback if the subclass
tot entries unbalance largest linear array (stat. approx.)
---------------------------------------------------------------------
-80 entries: 20 20+5=25 (target: ~100/4=25)
-90 entries: 22 22.5+5.5=28 (target: ~112/4=28)
+92 entries: 8 (99%) 23+2=25 (target: ~100/4=25)
+104 entries: 8 (99%) 26+2=28 (target: ~112/4=28)
Note: there exists rare worse cases where the unbalance is larger, but
* The node the index within the following arrays is represented on 3
* bits. It identifies the node type, min/max number of children, and
* the size order.
+ * The max_child values for the RCU_JA_POOL below result from
+ * statistical approximation: over million populations, the max_child
+ * covers between 97% and 99% of the populations generated. Therefore, a
+ * fallback should exist to cover the rare extreme population unbalance
+ * cases, but it will not have a major impact on speed nor space
+ * consumption, since those are rare cases.
*/
#if (CAA_BITS_PER_LONG < 64)
{ .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = 25, .order = 7, },
/* Pools may fill sooner than max_child */
- { .type_class = RCU_JA_POOL, .min_child = 20, .max_child = 50, .order = 8, .nr_pool_order = 1, .pool_size_order = 7, },
- { .type_class = RCU_JA_POOL, .min_child = 42, .max_child = 100, .order = 9, .nr_pool_order = 2, .pool_size_order = 7, },
-
- /* TODO: Upon downsize, if at least one pool is filled, we need to keep pigeon */
- { .type_class = RCU_JA_PIGEON, .min_child = 90, .max_child = 256, .order = 10, },
+ { .type_class = RCU_JA_POOL, .min_child = 20, .max_child = 48, .order = 8, .nr_pool_order = 1, .pool_size_order = 7, },
+ { .type_class = RCU_JA_POOL, .min_child = 45, .max_child = 92, .order = 9, .nr_pool_order = 2, .pool_size_order = 7, },
+
+ /*
+ * TODO: Upon node removal below min_child, if child pool is
+ * filled beyond capacity, we need to roll back to pigeon.
+ */
+ { .type_class = RCU_JA_PIGEON, .min_child = 89, .max_child = 256, .order = 10, },
};
CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) > JA_TYPE_MAX_NR);
#else /* !(CAA_BITS_PER_LONG < 64) */
{ .type_class = RCU_JA_LINEAR, .min_child = 5, .max_child = 14, .order = 7, },
{ .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = 28, .order = 8, },
- /* Pools may fill sooner than max_child */
- { .type_class = RCU_JA_POOL, .min_child = 22, .max_child = 56, .order = 9, .nr_pool_order = 1, .pool_size_order = 8, },
- { .type_class = RCU_JA_POOL, .min_child = 44, .max_child = 112, .order = 10, .nr_pool_order = 2, .pool_size_order = 8, },
+ /* Pools may fill sooner than max_child. */
+ { .type_class = RCU_JA_POOL, .min_child = 22, .max_child = 54, .order = 9, .nr_pool_order = 1, .pool_size_order = 8, },
+ { .type_class = RCU_JA_POOL, .min_child = 51, .max_child = 104, .order = 10, .nr_pool_order = 2, .pool_size_order = 8, },
- /* TODO: Upon downsize, if at least one pool is filled, we need to keep pigeon */
- { .type_class = RCU_JA_PIGEON, .min_child = 100, .max_child = 256, .order = 11, },
+ /*
+ * TODO: Upon node removal below min_child, if child pool is
+ * filled beyond capacity, we need to roll back to pigeon.
+ */
+ { .type_class = RCU_JA_PIGEON, .min_child = 101, .max_child = 256, .order = 11, },
};
CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) > JA_TYPE_MAX_NR);
#endif /* !(BITS_PER_LONG < 64) */
assert(type->type_class == RCU_JA_POOL);
linear = (struct rcu_ja_node *)
- &node->data[(n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
+ &node->data[((unsigned long) n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
return ja_linear_node_get_nth(NULL, linear, n);
}
--- /dev/null
+/*
+ * rcuja/testpop.c
+ *
+ * Userspace RCU library - RCU Judy Array population size test
+ *
+ * Copyright 2012 - 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
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/*
+ * 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).
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <time.h>
+#include <string.h>
+#include <limits.h>
+
+static int sel_pool_len = 50; /* default */
+static int nr_distrib = 2; /* default */
+//#define SEL_POOL_LEN 100
+//#define NR_POOLS 10000000ULL
+
+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 unsigned int unbalance_distrib[256];
+
+static
+uint8_t random_char(void)
+{
+ return (uint8_t) random();
+}
+
+static
+void print_pool(void)
+{
+ int i;
+
+ printf("pool: ");
+ for (i = 0; i < sel_pool_len; i++) {
+ printf("%d ", (int) pool[i]);
+ }
+ printf("\n");
+}
+
+static
+void gen_pool(void)
+{
+ uint8_t src_pool[256];
+ int i;
+ int nr_left = 256;
+
+ memset(pool, 0, sizeof(pool));
+ for (i = 0; i < 256; i++)
+ src_pool[i] = (uint8_t) i;
+ for (i = 0; i < sel_pool_len; i++) {
+ int sel;
+
+ sel = random_char() % nr_left;
+ pool[i] = src_pool[sel];
+ src_pool[sel] = src_pool[nr_left - 1];
+ nr_left--;
+ }
+}
+
+static
+void count_pool(void)
+{
+ int i;
+
+ 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));
+ for (i = 0; i < sel_pool_len; i++) {
+ if (nr_distrib == 2) {
+ int j;
+
+ for (j = 0; j < 8; j++) {
+ if (pool[i] & (1U << j))
+ nr_one[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]++;
+ }
+ }
+ }
+ }
+ }
+}
+
+static
+void print_count(void)
+{
+ int i;
+
+ printf("pool distribution:\n");
+
+ if (nr_distrib == 2) {
+ printf(" 0 1\n");
+ printf("----------\n");
+ for (i = 0; i < 8; i++) {
+ printf("%3d %3d\n",
+ sel_pool_len - nr_one[i], nr_one[i]);
+ }
+ }
+
+ if (nr_distrib == 4) {
+ /* TODO */
+ }
+ printf("\n");
+}
+
+static
+void stat_count(void)
+{
+ int minunbalance = INT_MAX;
+
+ if (nr_distrib == 2) {
+ int i;
+
+ for (i = 0; i < 8; i++) {
+ int diff;
+
+ diff = (int) nr_one[i] * 2 - sel_pool_len;
+ if (diff < 0)
+ diff = -diff;
+ if (diff < minunbalance) {
+ minunbalance = diff;
+ }
+ }
+ }
+
+ 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];
+ }
+ }
+ }
+ }
+
+ if (minunbalance > global_max_minunbalance) {
+ global_max_minunbalance = minunbalance;
+ }
+ unbalance_distrib[minunbalance]++;
+}
+
+static
+void print_distrib(void)
+{
+ int i;
+ unsigned long long tot = 0;
+
+ for (i = 0; i < 256; i++) {
+ tot += unbalance_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);
+ }
+ 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);
+ print_distrib();
+}
+
+int main(int argc, char **argv)
+{
+ uint64_t i = 0;
+
+ srandom(time(NULL));
+
+ if (argc > 1) {
+ sel_pool_len = atoi(argv[1]);
+ if (sel_pool_len > 256 || sel_pool_len < 1) {
+ printf("Wrong pool len\n");
+ return -1;
+ }
+ }
+ printf("pool len: %d\n", sel_pool_len);
+
+ if (argc > 2) {
+ nr_distrib = atoi(argv[2]);
+ if (nr_distrib > 256 || nr_distrib < 1) {
+ printf("Wrong number of distributions\n");
+ return -1;
+ }
+ }
+ printf("pool distributions: %d\n", nr_distrib);
+
+ if (nr_distrib != 2 && nr_distrib != 4) {
+ printf("Wrong number of distributions. Only 2 and 4 supported.\n");
+ return -1;
+ }
+
+ //for (i = 0; i < NR_POOLS; i++) {
+ while (1) {
+ gen_pool();
+ count_pool();
+ //print_pool();
+ //print_count();
+ stat_count();
+ if (!(i % 100000ULL))
+ print_stat(i);
+ i++;
+ }
+ print_stat(i);
+ print_distrib();
+
+ return 0;
+}
projects / urcu.git / commitdiff
