4 * Userspace RCU library - RCU Judy Array population size test
6 * Copyright 2012-2013 - 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 largest
25 * sub-class generated, as well as the distribution of sub-class size
26 * for the largest sub-class of each population.
37 static int sel_pool_len
= 50; /* default */
38 static int nr_distrib
= 2; /* default */
39 //#define SEL_POOL_LEN 100
40 //#define NR_POOLS 10000000ULL
42 static uint8_t pool
[256];
43 static uint8_t nr_one
[8];
44 static uint8_t nr_2d_11
[8][8];
45 static uint8_t nr_2d_10
[8][8];
46 static uint8_t nr_2d_01
[8][8];
47 static uint8_t nr_2d_00
[8][8];
48 static int global_max_minsubclass_len
= 0;
50 static unsigned int subclass_len_distrib
[256];
55 uint8_t random_char(void)
57 return (uint8_t) random();
66 for (i
= 0; i
< sel_pool_len
; i
++) {
67 printf("%d ", (int) pool
[i
]);
75 uint8_t src_pool
[256];
79 memset(pool
, 0, sizeof(pool
));
80 for (i
= 0; i
< 256; i
++)
81 src_pool
[i
] = (uint8_t) i
;
82 for (i
= 0; i
< sel_pool_len
; i
++) {
85 sel
= random_char() % nr_left
;
86 pool
[i
] = src_pool
[sel
];
87 src_pool
[sel
] = src_pool
[nr_left
- 1];
97 memset(nr_one
, 0, sizeof(nr_one
));
98 memset(nr_2d_11
, 0, sizeof(nr_2d_11
));
99 memset(nr_2d_10
, 0, sizeof(nr_2d_10
));
100 memset(nr_2d_01
, 0, sizeof(nr_2d_01
));
101 memset(nr_2d_00
, 0, sizeof(nr_2d_00
));
103 for (i
= 0; i
< sel_pool_len
; i
++) {
104 if (nr_distrib
== 2) {
107 for (j
= 0; j
< 8; j
++) {
108 if (pool
[i
] & (1U << j
))
113 if (nr_distrib
== 4) {
116 for (bit_i
= 0; bit_i
< 8; bit_i
++) {
117 for (bit_j
= 0; bit_j
< bit_i
; bit_j
++) {
118 if (pool
[i
] & (1U << bit_i
)) {
119 if (pool
[i
] & (1U << bit_j
)) {
120 nr_2d_11
[bit_i
][bit_j
]++;
122 nr_2d_10
[bit_i
][bit_j
]++;
125 if (pool
[i
] & (1U << bit_j
)) {
126 nr_2d_01
[bit_i
][bit_j
]++;
128 nr_2d_00
[bit_i
][bit_j
]++;
138 void print_count(void)
142 printf("pool distribution:\n");
144 if (nr_distrib
== 2) {
146 printf("----------\n");
147 for (i
= 0; i
< 8; i
++) {
149 sel_pool_len
- nr_one
[i
], nr_one
[i
]);
153 if (nr_distrib
== 4) {
160 void stat_count_1d(void)
162 unsigned int overall_best_distance
= UINT_MAX
;
163 unsigned int overall_minsubclass_len
;
166 for (i
= 0; i
< 8; i
++) {
167 int distance_to_best
;
169 distance_to_best
= ((unsigned int) nr_one
[i
] << 1U) - sel_pool_len
;
170 if (distance_to_best
< 0)
171 distance_to_best
= -distance_to_best
;
172 if (distance_to_best
< overall_best_distance
) {
173 overall_best_distance
= distance_to_best
;
176 overall_minsubclass_len
= (overall_best_distance
+ sel_pool_len
) >> 1UL;
177 if (overall_minsubclass_len
> global_max_minsubclass_len
) {
178 global_max_minsubclass_len
= overall_minsubclass_len
;
180 subclass_len_distrib
[overall_minsubclass_len
]++;
184 void stat_count_2d(void)
186 int overall_best_distance
= INT_MAX
;
187 unsigned int overall_minsubclass_len
= 0;
190 for (bit_i
= 0; bit_i
< 8; bit_i
++) {
191 for (bit_j
= 0; bit_j
< bit_i
; bit_j
++) {
192 int distance_to_best
[4], subclass_len
[4];
194 distance_to_best
[0] = ((unsigned int) nr_2d_11
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
195 distance_to_best
[1] = ((unsigned int) nr_2d_10
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
196 distance_to_best
[2] = ((unsigned int) nr_2d_01
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
197 distance_to_best
[3] = ((unsigned int) nr_2d_00
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
199 subclass_len
[0] = nr_2d_11
[bit_i
][bit_j
];
200 subclass_len
[1] = nr_2d_10
[bit_i
][bit_j
];
201 subclass_len
[2] = nr_2d_01
[bit_i
][bit_j
];
202 subclass_len
[3] = nr_2d_00
[bit_i
][bit_j
];
204 /* Consider worse distance above best */
205 if (distance_to_best
[1] > 0 && distance_to_best
[1] > distance_to_best
[0]) {
206 distance_to_best
[0] = distance_to_best
[1];
207 subclass_len
[0] = subclass_len
[1];
209 if (distance_to_best
[2] > 0 && distance_to_best
[2] > distance_to_best
[0]) {
210 distance_to_best
[0] = distance_to_best
[2];
211 subclass_len
[0] = subclass_len
[2];
213 if (distance_to_best
[3] > 0 && distance_to_best
[3] > distance_to_best
[0]) {
214 distance_to_best
[0] = distance_to_best
[3];
215 subclass_len
[0] = subclass_len
[3];
219 * If our worse distance is better than overall,
220 * we become new best candidate.
222 if (distance_to_best
[0] < overall_best_distance
) {
223 overall_best_distance
= distance_to_best
[0];
224 overall_minsubclass_len
= subclass_len
[0];
228 if (overall_minsubclass_len
> global_max_minsubclass_len
) {
229 global_max_minsubclass_len
= overall_minsubclass_len
;
231 subclass_len_distrib
[overall_minsubclass_len
]++;
235 void stat_count(void)
237 switch (nr_distrib
) {
251 void print_distrib(void)
254 unsigned long long tot
= 0;
256 for (i
= 0; i
< 256; i
++) {
257 tot
+= subclass_len_distrib
[i
];
261 printf("Distribution:\n");
262 for (i
= 0; i
< 256; i
++) {
263 if (!subclass_len_distrib
[i
])
265 printf("(%u, %u, %llu%%) ",
266 i
, subclass_len_distrib
[i
],
267 100 * (unsigned long long) subclass_len_distrib
[i
] / tot
);
273 void print_stat(uint64_t i
)
275 printf("after %llu pools, global_max_minsubclass_len: %d\n",
276 (unsigned long long) i
, global_max_minsubclass_len
);
280 int main(int argc
, char **argv
)
287 sel_pool_len
= atoi(argv
[1]);
288 if (sel_pool_len
> 256 || sel_pool_len
< 1) {
289 printf("Wrong pool len\n");
293 printf("pool len: %d\n", sel_pool_len
);
296 nr_distrib
= atoi(argv
[2]);
297 if (nr_distrib
> 256 || nr_distrib
< 1) {
298 printf("Wrong number of distributions\n");
304 if (!strcmp(argv
[3], "-v")) {
309 printf("pool distributions: %d\n", nr_distrib
);
311 if (nr_distrib
!= 2 && nr_distrib
!= 4) {
312 printf("Wrong number of distributions. Only 2 and 4 supported.\n");
316 //for (i = 0; i < NR_POOLS; i++) {
325 if (!(i
% 100000ULL))