rcuja/testpop.c

   1 /*
   2  * rcuja/testpop.c
   3  *
   4  * Userspace RCU library - RCU Judy Array population size test
   5  *
   6  * Copyright 2012-2013 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   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.
  12  *
  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.
  17  *
  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
  21  */
  22
  23 /*
  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.
  27  */
  28
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <stdint.h>
  32 #include <time.h>
  33 #include <string.h>
  34 #include <limits.h>
  35 #include <assert.h>
  36
  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
  41
  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;
  49
  50 static unsigned int subclass_len_distrib[256];
  51
  52 static
  53 uint8_t random_char(void)
  54 {
  55         return (uint8_t) random();
  56 }
  57
  58 static
  59 void print_pool(void)
  60 {
  61         int i;
  62
  63         printf("pool: ");
  64         for (i = 0; i < sel_pool_len; i++) {
  65                 printf("%d ", (int) pool[i]);
  66         }
  67         printf("\n");
  68 }
  69
  70 static
  71 void gen_pool(void)
  72 {
  73         uint8_t src_pool[256];
  74         int i;
  75         int nr_left = 256;
  76
  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++) {
  81                 int sel;
  82
  83                 sel = random_char() % nr_left;
  84                 pool[i] = src_pool[sel];
  85                 src_pool[sel] = src_pool[nr_left - 1];
  86                 nr_left--;
  87         }
  88 }
  89
  90 static
  91 void count_pool(void)
  92 {
  93         int i;
  94
  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));
 100
 101         for (i = 0; i < sel_pool_len; i++) {
 102                 if (nr_distrib == 2) {
 103                         int j;
 104
 105                         for (j = 0; j < 8; j++) {
 106                                 if (pool[i] & (1U << j))
 107                                         nr_one[j]++;
 108                         }
 109                 }
 110
 111                 if (nr_distrib == 4) {
 112                         int bit_i, bit_j;
 113
 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]++;
 119                                                 } else {
 120                                                         nr_2d_10[bit_i][bit_j]++;
 121                                                 }
 122                                         } else {
 123                                                 if (pool[i] & (1U << bit_j)) {
 124                                                         nr_2d_01[bit_i][bit_j]++;
 125                                                 } else {
 126                                                         nr_2d_00[bit_i][bit_j]++;
 127                                                 }
 128                                         }
 129                                 }
 130                         }
 131                 }
 132         }
 133 }
 134
 135 static
 136 void print_count(void)
 137 {
 138         int i;
 139
 140         printf("pool distribution:\n");
 141
 142         if (nr_distrib == 2) {
 143                 printf("  0      1\n");
 144                 printf("----------\n");
 145                 for (i = 0; i < 8; i++) {
 146                         printf("%3d    %3d\n",
 147                                 sel_pool_len - nr_one[i], nr_one[i]);
 148                 }
 149         }
 150
 151         if (nr_distrib == 4) {
 152                 /* TODO */
 153         }
 154         printf("\n");
 155 }
 156
 157 static
 158 void stat_count_1d(void)
 159 {
 160         unsigned int overall_best_distance = UINT_MAX;
 161         unsigned int overall_minsubclass_len;
 162         int i;
 163
 164         for (i = 0; i < 8; i++) {
 165                 int distance_to_best;
 166
 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;
 172                 }
 173         }
 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;
 177         }
 178         subclass_len_distrib[overall_minsubclass_len]++;
 179 }
 180
 181 static
 182 void stat_count_2d(void)
 183 {
 184         int overall_best_distance = INT_MAX;
 185         unsigned int overall_minsubclass_len = 0;
 186         int bit_i, bit_j;
 187
 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];
 191
 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;
 196
 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];
 201
 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];
 206                         }
 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];
 210                         }
 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];
 214                         }
 215
 216                         /*
 217                          * If our worse distance is better than overall,
 218                          * we become new best candidate.
 219                          */
 220                         if (distance_to_best[0] < overall_best_distance) {
 221                                 overall_best_distance = distance_to_best[0];
 222                                 overall_minsubclass_len = subclass_len[0];
 223                         }
 224                 }
 225         }
 226         if (overall_minsubclass_len > global_max_minsubclass_len) {
 227                 global_max_minsubclass_len = overall_minsubclass_len;
 228         }
 229         subclass_len_distrib[overall_minsubclass_len]++;
 230 }
 231
 232 static
 233 void stat_count(void)
 234 {
 235         switch (nr_distrib) {
 236         case 2:
 237                 stat_count_1d();
 238                 break;
 239         case 4:
 240                 stat_count_2d();
 241                 break;
 242         default:
 243                 assert(0);
 244                 break;
 245         }
 246 }
 247
 248 static
 249 void print_distrib(void)
 250 {
 251         int i;
 252         unsigned long long tot = 0;
 253
 254         for (i = 0; i < 256; i++) {
 255                 tot += subclass_len_distrib[i];
 256         }
 257         if (tot == 0)
 258                 return;
 259         printf("Distribution:\n");
 260         for (i = 0; i < 256; i++) {
 261                 if (!subclass_len_distrib[i])
 262                         continue;
 263                 printf("(%u, %u, %llu%%) ",
 264                         i, subclass_len_distrib[i],
 265                         100 * (unsigned long long) subclass_len_distrib[i] / tot);
 266         }
 267         printf("\n");
 268 }
 269
 270 static
 271 void print_stat(uint64_t i)
 272 {
 273         printf("after %llu pools, global_max_minsubclass_len: %d\n",
 274                 (unsigned long long) i, global_max_minsubclass_len);
 275         print_distrib();
 276 }
 277
 278 int main(int argc, char **argv)
 279 {
 280         uint64_t i = 0;
 281
 282         srandom(time(NULL));
 283
 284         if (argc > 1) {
 285                 sel_pool_len = atoi(argv[1]);
 286                 if (sel_pool_len > 256 || sel_pool_len < 1) {
 287                         printf("Wrong pool len\n");
 288                         return -1;
 289                 }
 290         }
 291         printf("pool len: %d\n", sel_pool_len);
 292
 293         if (argc > 2) {
 294                 nr_distrib = atoi(argv[2]);
 295                 if (nr_distrib > 256 || nr_distrib < 1) {
 296                         printf("Wrong number of distributions\n");
 297                         return -1;
 298                 }
 299         }
 300         printf("pool distributions: %d\n", nr_distrib);
 301
 302         if (nr_distrib != 2 && nr_distrib != 4) {
 303                 printf("Wrong number of distributions. Only 2 and 4 supported.\n");
 304                 return -1;
 305         }
 306
 307         //for (i = 0; i < NR_POOLS; i++) {
 308         while (1) {
 309                 gen_pool();
 310                 count_pool();
 311                 //print_pool();
 312                 //print_count();
 313                 stat_count();
 314                 if (!(i % 100000ULL))
 315                         print_stat(i);
 316                 i++;
 317         }
 318         print_stat(i);
 319         print_distrib();
 320
 321         return 0;
 322 }