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.
36 static int sel_pool_len
= 50; /* default */
37 static int nr_distrib
= 2; /* default */
38 //#define SEL_POOL_LEN 100
39 //#define NR_POOLS 10000000ULL
41 static uint8_t pool
[256];
42 static uint8_t nr_one
[8];
43 static uint8_t nr_2d_11
[8][8];
44 static uint8_t nr_2d_10
[8][8];
45 static uint8_t nr_2d_01
[8][8];
46 static uint8_t nr_2d_00
[8][8];
47 static int global_max_minsubclass_len
= 0;
48 static int global_max_best_distance
= 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(void)
160 int minsubclass_len
= INT_MAX
;
161 int overall_best_distance
= INT_MAX
;
163 if (nr_distrib
== 2) {
166 for (i
= 0; i
< 8; i
++) {
169 diff
= (int) nr_one
[i
] * 2 - sel_pool_len
;
172 if ((diff
>> 1) < minsubclass_len
) {
173 minsubclass_len
= diff
>> 1;
176 if (minsubclass_len
> global_max_minsubclass_len
) {
177 global_max_minsubclass_len
= minsubclass_len
;
179 subclass_len_distrib
[minsubclass_len
]++;
182 if (nr_distrib
== 4) {
185 for (bit_i
= 0; bit_i
< 8; bit_i
++) {
186 for (bit_j
= 0; bit_j
< bit_i
; bit_j
++) {
187 int distance_to_best
[4], subclass_len
[4];
189 distance_to_best
[0] = (nr_2d_11
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
190 distance_to_best
[1] = (nr_2d_10
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
191 distance_to_best
[2] = (nr_2d_01
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
192 distance_to_best
[3] = (nr_2d_00
[bit_i
][bit_j
] << 2U) - sel_pool_len
;
194 subclass_len
[0] = nr_2d_11
[bit_i
][bit_j
];
195 subclass_len
[1] = nr_2d_10
[bit_i
][bit_j
];
196 subclass_len
[2] = nr_2d_01
[bit_i
][bit_j
];
197 subclass_len
[3] = nr_2d_00
[bit_i
][bit_j
];
199 /* Consider worse distance above best */
200 if (distance_to_best
[1] > 0 && distance_to_best
[1] > distance_to_best
[0]) {
201 distance_to_best
[0] = distance_to_best
[1];
202 subclass_len
[0] = subclass_len
[1];
204 if (distance_to_best
[2] > 0 && distance_to_best
[2] > distance_to_best
[0]) {
205 distance_to_best
[0] = distance_to_best
[2];
206 subclass_len
[0] = subclass_len
[2];
208 if (distance_to_best
[3] > 0 && distance_to_best
[3] > distance_to_best
[0]) {
209 distance_to_best
[0] = distance_to_best
[3];
210 subclass_len
[0] = subclass_len
[3];
214 * If our worse distance is better than overall,
215 * we become new best candidate.
217 if (distance_to_best
[0] < overall_best_distance
) {
218 overall_best_distance
= distance_to_best
[0];
219 minsubclass_len
= subclass_len
[0];
223 if (overall_best_distance
> global_max_best_distance
) {
224 global_max_best_distance
= overall_best_distance
;
226 subclass_len_distrib
[minsubclass_len
]++;
231 void print_distrib(void)
234 unsigned long long tot
= 0;
236 for (i
= 0; i
< 256; i
++) {
237 tot
+= subclass_len_distrib
[i
];
241 printf("Distribution:\n");
242 for (i
= 0; i
< 256; i
++) {
243 printf("(%u, %u, %llu%%) ",
244 i
, subclass_len_distrib
[i
],
245 100 * (unsigned long long) subclass_len_distrib
[i
] / tot
);
251 void print_stat(uint64_t i
)
253 printf("after %llu pools, global_max_minsubclass_len extra: %d global_max_best_distance %d\n",
254 (unsigned long long) i
, global_max_minsubclass_len
,
255 global_max_best_distance
);
259 int main(int argc
, char **argv
)
266 sel_pool_len
= atoi(argv
[1]);
267 if (sel_pool_len
> 256 || sel_pool_len
< 1) {
268 printf("Wrong pool len\n");
272 printf("pool len: %d\n", sel_pool_len
);
275 nr_distrib
= atoi(argv
[2]);
276 if (nr_distrib
> 256 || nr_distrib
< 1) {
277 printf("Wrong number of distributions\n");
281 printf("pool distributions: %d\n", nr_distrib
);
283 if (nr_distrib
!= 2 && nr_distrib
!= 4) {
284 printf("Wrong number of distributions. Only 2 and 4 supported.\n");
288 //for (i = 0; i < NR_POOLS; i++) {
295 if (!(i
% 100000ULL))