4 * Userspace RCU library - RCU Judy Array population size test
6 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 * This program generates random populations, and shows the worse-case
25 * unbalance, as well as the distribution of unbalance encountered.
26 * Remember that the unbalance is the delta between the lowest and
27 * largest population. Therefore, to get the delta between the subclass
28 * size and the actual number of items, we need to divide the unbalance
29 * by the number of subclasses (by hand).
39 static int sel_pool_len
= 50; /* default */
40 static int nr_distrib
= 2; /* default */
41 //#define SEL_POOL_LEN 100
42 //#define NR_POOLS 10000000ULL
44 static uint8_t pool
[256];
45 static uint8_t nr_one
[8];
46 static uint8_t nr_2d_11
[8][8];
47 static uint8_t nr_2d_10
[8][8];
48 static int global_max_minunbalance
= 0;
50 static unsigned int unbalance_distrib
[256];
53 uint8_t random_char(void)
55 return (uint8_t) random();
64 for (i
= 0; i
< sel_pool_len
; i
++) {
65 printf("%d ", (int) pool
[i
]);
73 uint8_t src_pool
[256];
77 memset(pool
, 0, sizeof(pool
));
78 for (i
= 0; i
< 256; i
++)
79 src_pool
[i
] = (uint8_t) i
;
80 for (i
= 0; i
< sel_pool_len
; i
++) {
83 sel
= random_char() % nr_left
;
84 pool
[i
] = src_pool
[sel
];
85 src_pool
[sel
] = src_pool
[nr_left
- 1];
95 memset(nr_one
, 0, sizeof(nr_one
));
96 memset(nr_2d_11
, 0, sizeof(nr_2d_11
));
97 memset(nr_2d_10
, 0, sizeof(nr_2d_10
));
98 for (i
= 0; i
< sel_pool_len
; i
++) {
99 if (nr_distrib
== 2) {
102 for (j
= 0; j
< 8; j
++) {
103 if (pool
[i
] & (1U << j
))
108 if (nr_distrib
== 4) {
111 for (j
= 0; j
< 8; j
++) {
112 for (k
= 0; k
< j
; k
++) {
113 if ((pool
[i
] & (1U << j
)) && (pool
[i
] & (1U << k
))) {
116 if ((pool
[i
] & (1U << j
)) && !(pool
[i
] & (1U << k
))) {
126 void print_count(void)
130 printf("pool distribution:\n");
132 if (nr_distrib
== 2) {
134 printf("----------\n");
135 for (i
= 0; i
< 8; i
++) {
137 sel_pool_len
- nr_one
[i
], nr_one
[i
]);
141 if (nr_distrib
== 4) {
148 void stat_count(void)
150 int minunbalance
= INT_MAX
;
152 if (nr_distrib
== 2) {
155 for (i
= 0; i
< 8; i
++) {
158 diff
= (int) nr_one
[i
] * 2 - sel_pool_len
;
161 if (diff
< minunbalance
) {
167 if (nr_distrib
== 4) {
170 for (j
= 0; j
< 8; j
++) {
171 for (k
= 0; k
< j
; k
++) {
174 diff
[0] = (int) nr_2d_11
[j
][k
] * 4 - sel_pool_len
;
178 diff
[1] = (int) nr_2d_10
[j
][k
] * 4 - sel_pool_len
;
181 /* Get max linear array size */
182 if (diff
[1] > diff
[0])
184 if (diff
[0] < minunbalance
) {
185 minunbalance
= diff
[0];
191 if (minunbalance
> global_max_minunbalance
) {
192 global_max_minunbalance
= minunbalance
;
194 unbalance_distrib
[minunbalance
]++;
198 void print_distrib(void)
201 unsigned long long tot
= 0;
203 for (i
= 0; i
< 256; i
++) {
204 tot
+= unbalance_distrib
[i
];
208 printf("Distribution:\n");
209 for (i
= 0; i
< 256; i
++) {
210 printf("(%u, %u, %llu%%) ",
211 i
, unbalance_distrib
[i
],
212 100 * (unsigned long long) unbalance_distrib
[i
] / tot
);
218 void print_stat(uint64_t i
)
220 printf("after %llu pools, global_max_minunbalance: %d\n",
221 (unsigned long long) i
, global_max_minunbalance
);
225 int main(int argc
, char **argv
)
232 sel_pool_len
= atoi(argv
[1]);
233 if (sel_pool_len
> 256 || sel_pool_len
< 1) {
234 printf("Wrong pool len\n");
238 printf("pool len: %d\n", sel_pool_len
);
241 nr_distrib
= atoi(argv
[2]);
242 if (nr_distrib
> 256 || nr_distrib
< 1) {
243 printf("Wrong number of distributions\n");
247 printf("pool distributions: %d\n", nr_distrib
);
249 if (nr_distrib
!= 2 && nr_distrib
!= 4) {
250 printf("Wrong number of distributions. Only 2 and 4 supported.\n");
254 //for (i = 0; i < NR_POOLS; i++) {
261 if (!(i
% 100000ULL))
This page took 0.04174 seconds and 4 git commands to generate.