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 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];
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 memset(nr_2d_01
, 0, sizeof(nr_2d_01
));
99 memset(nr_2d_00
, 0, sizeof(nr_2d_00
));
101 for (i
= 0; i
< sel_pool_len
; i
++) {
102 if (nr_distrib
== 2) {
105 for (j
= 0; j
< 8; j
++) {
106 if (pool
[i
] & (1U << j
))
111 if (nr_distrib
== 4) {
114 for (bit_i
= 0; bit_i
< 8; bit_i
++) {
115 for (bit_j
= 0; bit_j
< bit_i
; bit_j
++) {
116 if (pool
[i
] & (1U << bit_i
)) {
117 if (pool
[i
] & (1U << bit_j
)) {
118 nr_2d_11
[bit_i
][bit_j
]++;
120 nr_2d_10
[bit_i
][bit_j
]++;
123 if (pool
[i
] & (1U << bit_j
)) {
124 nr_2d_01
[bit_i
][bit_j
]++;
126 nr_2d_00
[bit_i
][bit_j
]++;
136 void print_count(void)
140 printf("pool distribution:\n");
142 if (nr_distrib
== 2) {
144 printf("----------\n");
145 for (i
= 0; i
< 8; i
++) {
147 sel_pool_len
- nr_one
[i
], nr_one
[i
]);
151 if (nr_distrib
== 4) {
158 void stat_count_1d(void)
160 unsigned int overall_best_distance
= UINT_MAX
;
161 unsigned int overall_minsubclass_len
;
164 for (i
= 0; i
< 8; i
++) {
165 int distance_to_best
;
167 distance_to_best
= ((unsigned int) nr_one
[i
] << 1U) - sel_pool_len
;
168 if (distance_to_best
< 0)
169 distance_to_best
= -distance_to_best
;
170 if (distance_to_best
< overall_best_distance
) {
171 overall_best_distance
= distance_to_best
;
174 overall_minsubclass_len
= (overall_best_distance
+ sel_pool_len
) >> 1UL;
175 if (overall_minsubclass_len
> global_max_minsubclass_len
) {
176 global_max_minsubclass_len
= overall_minsubclass_len
;
178 subclass_len_distrib
[overall_minsubclass_len
]++;
182 void stat_count_2d(void)
184 int overall_best_distance
= INT_MAX
;
185 unsigned int overall_minsubclass_len
= 0;
188 for (bit_i
= 0; bit_i
< 8; bit_i
++) {
189 for (bit_j
= 0; bit_j
< bit_i
; bit_j
++) {
190 int distance_to_best
[4], subclass_len
[4];
192 distance_to_best
[0] = ((unsigned int) nr_2d_11
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
193 distance_to_best
[1] = ((unsigned int) nr_2d_10
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
194 distance_to_best
[2] = ((unsigned int) nr_2d_01
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
195 distance_to_best
[3] = ((unsigned int) nr_2d_00
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
197 subclass_len
[0] = nr_2d_11
[bit_i
][bit_j
];
198 subclass_len
[1] = nr_2d_10
[bit_i
][bit_j
];
199 subclass_len
[2] = nr_2d_01
[bit_i
][bit_j
];
200 subclass_len
[3] = nr_2d_00
[bit_i
][bit_j
];
202 /* Consider worse distance above best */
203 if (distance_to_best
[1] > 0 && distance_to_best
[1] > distance_to_best
[0]) {
204 distance_to_best
[0] = distance_to_best
[1];
205 subclass_len
[0] = subclass_len
[1];
207 if (distance_to_best
[2] > 0 && distance_to_best
[2] > distance_to_best
[0]) {
208 distance_to_best
[0] = distance_to_best
[2];
209 subclass_len
[0] = subclass_len
[2];
211 if (distance_to_best
[3] > 0 && distance_to_best
[3] > distance_to_best
[0]) {
212 distance_to_best
[0] = distance_to_best
[3];
213 subclass_len
[0] = subclass_len
[3];
217 * If our worse distance is better than overall,
218 * we become new best candidate.
220 if (distance_to_best
[0] < overall_best_distance
) {
221 overall_best_distance
= distance_to_best
[0];
222 overall_minsubclass_len
= subclass_len
[0];
226 if (overall_minsubclass_len
> global_max_minsubclass_len
) {
227 global_max_minsubclass_len
= overall_minsubclass_len
;
229 subclass_len_distrib
[overall_minsubclass_len
]++;
233 void stat_count(void)
235 switch (nr_distrib
) {
249 void print_distrib(void)
252 unsigned long long tot
= 0;
254 for (i
= 0; i
< 256; i
++) {
255 tot
+= subclass_len_distrib
[i
];
259 printf("Distribution:\n");
260 for (i
= 0; i
< 256; i
++) {
261 if (!subclass_len_distrib
[i
])
263 printf("(%u, %u, %llu%%) ",
264 i
, subclass_len_distrib
[i
],
265 100 * (unsigned long long) subclass_len_distrib
[i
] / tot
);
271 void print_stat(uint64_t i
)
273 printf("after %llu pools, global_max_minsubclass_len: %d\n",
274 (unsigned long long) i
, global_max_minsubclass_len
);
278 int main(int argc
, char **argv
)
285 sel_pool_len
= atoi(argv
[1]);
286 if (sel_pool_len
> 256 || sel_pool_len
< 1) {
287 printf("Wrong pool len\n");
291 printf("pool len: %d\n", sel_pool_len
);
294 nr_distrib
= atoi(argv
[2]);
295 if (nr_distrib
> 256 || nr_distrib
< 1) {
296 printf("Wrong number of distributions\n");
300 printf("pool distributions: %d\n", nr_distrib
);
302 if (nr_distrib
!= 2 && nr_distrib
!= 4) {
303 printf("Wrong number of distributions. Only 2 and 4 supported.\n");
307 //for (i = 0; i < NR_POOLS; i++) {
314 if (!(i
% 100000ULL))