lib/bitset_stats.c

   1 /* Bitset statistics.
   2    Copyright (C) 2002 Free Software Foundation, Inc.
   3    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18 */
  19
  20 /* This file is a wrapper bitset implementation for the other bitset
  21    implementations.  It provides bitset compatibility checking and
  22    statistics gathering without having to instrument the bitset
  23    implementations.  When statistics gathering is enabled, the bitset
  24    operations get vectored through here and we then call the appropriate
  25    routines.
  26 */
  27
  28 #ifdef HAVE_CONFIG_H
  29 #include "config.h"
  30 #endif
  31
  32 #include "bbitset.h"
  33 #include "abitset.h"
  34 #include "ebitset.h"
  35 #include "lbitset.h"
  36 #include "bitset_stats.h"
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include <stdio.h>
  40
  41
  42 /* Configuration macros.  */
  43 #define BITSET_STATS_FILE "bitset.dat"
  44 #define BITSET_LOG_COUNT_BINS 10
  45 #define BITSET_LOG_SIZE_BINS  16
  46 #define BITSET_DENSITY_BINS  20
  47
  48
  49 /* Accessor macros.  */
  50 #define BITSET_STATS_ALLOCS_INC(TYPE)                   \
  51     bitset_stats_info->types[(TYPE)].allocs++
  52 #define BITSET_STATS_FREES_INC(BSET)                    \
  53     bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++
  54 #define BITSET_STATS_SETS_INC(BSET)                     \
  55     bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++
  56 #define BITSET_STATS_CACHE_SETS_INC(BSET)               \
  57     bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++
  58 #define BITSET_STATS_RESETS_INC(BSET)                   \
  59     bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++
  60 #define BITSET_STATS_CACHE_RESETS_INC(BSET)             \
  61     bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++
  62 #define BITSET_STATS_TESTS_INC(BSET)                    \
  63     bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++
  64 #define BITSET_STATS_CACHE_TESTS_INC(BSET)              \
  65     bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++
  66 #define BITSET_STATS_LISTS_INC(BSET)                    \
  67     bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++
  68 #define BITSET_STATS_LIST_COUNTS_INC(BSET, I)           \
  69     bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++
  70 #define BITSET_STATS_LIST_SIZES_INC(BSET, I)            \
  71     bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++
  72 #define BITSET_STATS_LIST_DENSITY_INC(BSET, I)          \
  73     bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++
  74
  75
  76 typedef struct bitset_stats_struct
  77 {
  78   bitset bset;
  79 } *bitset_stats;
  80
  81
  82 struct bitset_struct
  83 {
  84   struct bbitset_struct b;
  85   struct bitset_stats_struct s;
  86 };
  87
  88
  89 struct bitset_type_info_struct
  90 {
  91   unsigned int allocs;
  92   unsigned int frees;
  93   unsigned int lists;
  94   unsigned int sets;
  95   unsigned int cache_sets;
  96   unsigned int resets;
  97   unsigned int cache_resets;
  98   unsigned int tests;
  99   unsigned int cache_tests;
 100   unsigned int list_counts[BITSET_LOG_COUNT_BINS];
 101   unsigned int list_sizes[BITSET_LOG_SIZE_BINS];
 102   unsigned int list_density[BITSET_DENSITY_BINS];
 103 };
 104
 105 struct bitset_stats_info_struct
 106 {
 107   unsigned int runs;
 108   struct bitset_type_info_struct types[BITSET_TYPE_NUM];
 109 };
 110
 111
 112 struct bitset_stats_info_struct bitset_stats_info_data;
 113 struct bitset_stats_info_struct *bitset_stats_info;
 114 int bitset_stats_enabled = 0;
 115
 116
 117 static void bitset_stats_set PARAMS ((bitset, bitset_bindex));
 118 static void bitset_stats_reset PARAMS ((bitset, bitset_bindex));
 119 static int bitset_stats_test PARAMS ((bitset, bitset_bindex));
 120 static int bitset_stats_size PARAMS ((bitset));
 121 static int bitset_stats_op1 PARAMS ((bitset, enum bitset_ops));
 122 static int bitset_stats_op2 PARAMS ((bitset, bitset, enum bitset_ops));
 123 static int bitset_stats_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
 124 static int bitset_stats_op4 PARAMS ((bitset, bitset, bitset, bitset,
 125                                      enum bitset_ops));
 126 static int bitset_stats_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
 127                                       bitset_bindex *));
 128 static int bitset_stats_reverse_list
 129 PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
 130 static void bitset_stats_free PARAMS ((bitset));
 131 static void bitset_percent_histogram_print PARAMS ((FILE *, const char *,
 132                                                     const char *,
 133                                                     unsigned int,
 134                                                     unsigned int *));
 135 static void bitset_log_histogram_print PARAMS ((FILE *, const char *,
 136                                                 const char *,
 137                                                 unsigned int,
 138                                                 unsigned int *));
 139 static void bitset_stats_print_1
 140 PARAMS ((FILE *, const char *, struct bitset_type_info_struct *));
 141 static void bitset_stats_print PARAMS ((FILE *, int));
 142
 143
 144 /* Print a percentage histogram with message MSG to FILE.  */
 145 static void
 146 bitset_percent_histogram_print (file, name, msg, n_bins, bins)
 147      FILE *file;
 148      const char *name;
 149      const char *msg;
 150      unsigned int n_bins;
 151      unsigned int *bins;
 152 {
 153   unsigned int i;
 154   unsigned int total;
 155
 156   total = 0;
 157   for (i = 0; i < n_bins; i++)
 158     total += bins[i];
 159
 160   if (!total)
 161     return;
 162
 163   fprintf (file, "%s %s", name, msg);
 164   for (i = 0; i < n_bins; i++)
 165     fprintf (file, "%.0f-%.0f%%\t%8d (%5.1f%%)\n",
 166              i * 100.0 / n_bins,
 167              (i + 1) * 100.0 / n_bins, bins[i],
 168              (100.0 * bins[i]) / total);
 169 }
 170
 171
 172 /* Print a log histogram with message MSG to FILE.  */
 173 static void
 174 bitset_log_histogram_print (file, name, msg, n_bins, bins)
 175      FILE *file;
 176      const char *name;
 177      const char *msg;
 178      unsigned int n_bins;
 179      unsigned int *bins;
 180 {
 181   unsigned int i;
 182   unsigned int total;
 183   unsigned int max_width;
 184   unsigned int last_bin;
 185
 186   total = 0;
 187   for (i = 0; i < n_bins; i++)
 188     total += bins[i];
 189
 190   if (!total)
 191     return;
 192
 193   for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
 194      continue;
 195   last_bin = i - 1;
 196
 197   /* 2 * ceil (log10 (2) * (N - 1)) + 1.  */
 198   max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;
 199
 200   fprintf (file, "%s %s", name, msg);
 201   for (i = 0; i < 2; i++)
 202     fprintf (file, "%*d\t%8d (%5.1f%%)\n",
 203              max_width, i, bins[i], 100.0 * bins[i] / total);
 204
 205   for (; i <= last_bin; i++)
 206     fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n",
 207              max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
 208              1 << (i - 1), (1 << i) - 1, bins[i],
 209              (100.0 * bins[i]) / total);
 210 }
 211
 212
 213 /* Print bitset statistics to FILE.  */
 214 static void
 215 bitset_stats_print_1 (file, name, stats)
 216      FILE *file;
 217      const char *name;
 218      struct bitset_type_info_struct *stats;
 219 {
 220   if (!stats)
 221     return;
 222
 223   fprintf (file, "%s:\n", name);
 224   fprintf (file, "%d bitset_allocs, %d freed (%.2f%%).\n",
 225            stats->allocs, stats->frees,
 226            stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
 227   fprintf (file, "%d bitset_sets, %d cached (%.2f%%)\n",
 228            stats->sets, stats->cache_sets,
 229            stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
 230   fprintf (file, "%d bitset_resets, %d cached (%.2f%%)\n",
 231            stats->resets, stats->cache_resets,
 232            stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
 233   fprintf (file, "%d bitset_tests, %d cached (%.2f%%)\n",
 234            stats->tests, stats->cache_tests,
 235            stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);
 236
 237   fprintf (file, "%d bitset_lists\n", stats->lists);
 238
 239   bitset_log_histogram_print (file, name, "count log histogram\n",
 240                               BITSET_LOG_COUNT_BINS, stats->list_counts);
 241
 242   bitset_log_histogram_print (file, name, "size log histogram\n",
 243                               BITSET_LOG_SIZE_BINS, stats->list_sizes);
 244
 245   bitset_percent_histogram_print (file, name, "density histogram\n",
 246                                   BITSET_DENSITY_BINS, stats->list_density);
 247 }
 248
 249
 250 /* Print all bitset statistics to FILE.  */
 251 static void
 252 bitset_stats_print (file, verbose)
 253      FILE *file;
 254      int verbose ATTRIBUTE_UNUSED;
 255 {
 256   int i;
 257   static const char *names[] = BITSET_TYPE_NAMES;
 258
 259   if (!bitset_stats_info)
 260     return;
 261
 262   fprintf (file, "Bitset statistics:\n\n");
 263
 264   if (bitset_stats_info->runs > 1)
 265     fprintf (file, "Accumulated runs = %d\n", bitset_stats_info->runs);
 266
 267   for (i = 0; i < BITSET_TYPE_NUM; i++)
 268     bitset_stats_print_1 (file, names[i], &bitset_stats_info->types[i]);
 269 }
 270
 271
 272 /* Initialise bitset statistics logging.  */
 273 void
 274 bitset_stats_enable ()
 275 {
 276   if (!bitset_stats_info)
 277     bitset_stats_info = &bitset_stats_info_data;
 278   bitset_stats_enabled = 1;
 279 }
 280
 281
 282 void
 283 bitset_stats_disable ()
 284 {
 285   bitset_stats_enabled = 0;
 286 }
 287
 288
 289 /* Read bitset statistics file.  */
 290 void
 291 bitset_stats_read (filename)
 292      const char *filename;
 293 {
 294   FILE *file;
 295
 296   if (!bitset_stats_info)
 297     return;
 298
 299   if (!filename)
 300     filename = BITSET_STATS_FILE;
 301
 302   file = fopen (filename, "r");
 303   if (file)
 304     {
 305       if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
 306                  1, file) != 1)
 307         {
 308           if (ferror (file))
 309             perror ("Could not read stats file.");
 310           else
 311             fprintf (stderr, "Bad stats file size.\n");
 312         }
 313       fclose (file);
 314     }
 315   bitset_stats_info_data.runs++;
 316 }
 317
 318
 319 /* Write bitset statistics file.  */
 320 void
 321 bitset_stats_write (filename)
 322      const char *filename;
 323 {
 324   FILE *file;
 325
 326   if (!bitset_stats_info)
 327     return;
 328
 329   if (!filename)
 330     filename = BITSET_STATS_FILE;
 331
 332   file = fopen (filename, "w");
 333   if (file)
 334     {
 335       if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
 336                   1, file) != 1)
 337         perror ("Could not write stats file.");
 338       fclose (file);
 339     }
 340   else
 341     perror ("Could not open stats file for writing.");
 342 }
 343
 344
 345 /* Dump bitset statistics to FILE.  */
 346 void
 347 bitset_stats_dump (file)
 348      FILE *file;
 349 {
 350   bitset_stats_print (file, 0);
 351 }
 352
 353
 354 /* Function to be called from debugger to print bitset stats.  */
 355 void
 356 debug_bitset_stats (void)
 357 {
 358   bitset_stats_print (stderr, 1);
 359 }
 360
 361
 362 static void
 363 bitset_stats_set (dst, bitno)
 364      bitset dst;
 365      bitset_bindex bitno;
 366 {
 367   bitset bset = dst->s.bset;
 368   bitset_windex index = bitno / BITSET_WORD_BITS;
 369   bitset_windex offset = index - bset->b.cindex;
 370
 371   BITSET_STATS_SETS_INC (bset);
 372
 373   if (offset < bset->b.csize)
 374     {
 375       bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
 376       BITSET_STATS_CACHE_SETS_INC (bset);
 377     }
 378   else
 379     BITSET_SET_ (bset, bitno);
 380 }
 381
 382
 383 static void
 384 bitset_stats_reset (dst, bitno)
 385      bitset dst;
 386      bitset_bindex bitno;
 387 {
 388   bitset bset = dst->s.bset;
 389   bitset_windex index = bitno / BITSET_WORD_BITS;
 390   bitset_windex offset = index - bset->b.cindex;
 391
 392   BITSET_STATS_RESETS_INC (bset);
 393
 394   if (offset < bset->b.csize)
 395     {
 396       bset->b.cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
 397       BITSET_STATS_CACHE_RESETS_INC (bset);
 398     }
 399   else
 400     BITSET_RESET_ (bset, bitno);
 401 }
 402
 403
 404 static int
 405 bitset_stats_test (src, bitno)
 406      bitset src;
 407      bitset_bindex bitno;
 408 {
 409   bitset bset = src->s.bset;
 410   bitset_windex index = bitno / BITSET_WORD_BITS;
 411   bitset_windex offset = index - bset->b.cindex;
 412
 413   BITSET_STATS_TESTS_INC (bset);
 414
 415   if (offset < bset->b.csize)
 416     {
 417       BITSET_STATS_CACHE_TESTS_INC (bset);
 418       return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
 419     }
 420   else
 421     return BITSET_TEST_ (bset, bitno);
 422 }
 423
 424
 425 static int
 426 bitset_stats_size (src)
 427      bitset src;
 428 {
 429   return BITSET_SIZE_ (src->s.bset);
 430 }
 431
 432
 433 static int
 434 bitset_stats_op1 (dst, op)
 435      bitset dst;
 436      enum bitset_ops op;
 437 {
 438   return BITSET_OP1_ (dst->s.bset, op);
 439 }
 440
 441
 442 static int
 443 bitset_stats_op2 (dst, src, op)
 444      bitset dst;
 445      bitset src;
 446      enum bitset_ops op;
 447 {
 448   BITSET_CHECK2_ (dst, src);
 449   return BITSET_OP2_ (dst->s.bset, src->s.bset, op);
 450 }
 451
 452
 453 static int
 454 bitset_stats_op3 (dst, src1, src2, op)
 455      bitset dst;
 456      bitset src1;
 457      bitset src2;
 458      enum bitset_ops op;
 459 {
 460   BITSET_CHECK3_ (dst, src1, src2);
 461   return BITSET_OP3_ (dst->s.bset, src1->s.bset, src2->s.bset, op);
 462 }
 463
 464
 465 static int
 466 bitset_stats_op4 (dst, src1, src2, src3, op)
 467      bitset dst;
 468      bitset src1;
 469      bitset src2;
 470      bitset src3;
 471      enum bitset_ops op;
 472 {
 473   BITSET_CHECK4_ (dst, src1, src2, src3);
 474
 475   /* This is a bit of a hack.  If the implementation handles
 476      a four operand operation then vector to it, passing
 477      the enclosed bitsets.  Otherwise use the fallback
 478      bitset_op4 routine.  */
 479   if (dst->s.bset->b.ops->op4 != bitset_op4)
 480      return BITSET_OP4_ (dst->s.bset, src1->s.bset, src2->s.bset,
 481                          src3->s.bset, op);
 482
 483   return bitset_op4 (dst, src1, src2, src3, op);
 484 }
 485
 486
 487 static int
 488 bitset_stats_list (bset, list, num, next)
 489      bitset bset;
 490      bitset_bindex *list;
 491      bitset_bindex num;
 492      bitset_bindex *next;
 493 {
 494   bitset_bindex count;
 495   bitset_bindex tmp;
 496   bitset_bindex size;
 497   bitset_bindex i;
 498   enum bitset_type type;
 499
 500   count = BITSET_LIST_ (bset->s.bset, list, num, next);
 501
 502   type = BITSET_TYPE_ (bset->s.bset);
 503   BITSET_STATS_LISTS_INC (bset->s.bset);
 504
 505   /* Log histogram of number of set bits.  */
 506   for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
 507      continue;
 508   if (i >= BITSET_LOG_COUNT_BINS)
 509      i = BITSET_LOG_COUNT_BINS - 1;
 510   BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i);
 511
 512   /* Log histogram of number of bits in set.  */
 513   size = BITSET_SIZE_ (bset->s.bset);
 514   for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
 515      continue;
 516   if (i >= BITSET_LOG_SIZE_BINS)
 517      i = BITSET_LOG_SIZE_BINS - 1;
 518   BITSET_STATS_LIST_SIZES_INC (bset->s.bset, i);
 519
 520   /* Histogram of fraction of bits set.  */
 521   i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
 522   if (i >= BITSET_DENSITY_BINS)
 523      i = BITSET_DENSITY_BINS - 1;
 524   BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i);
 525   return count;
 526 }
 527
 528
 529 static int
 530 bitset_stats_reverse_list (bset, list, num, next)
 531      bitset bset;
 532      bitset_bindex *list;
 533      bitset_bindex num;
 534      bitset_bindex *next;
 535 {
 536   return BITSET_REVERSE_LIST_ (bset->s.bset, list, num, next);
 537 }
 538
 539
 540 static void
 541 bitset_stats_free (bset)
 542      bitset bset;
 543 {
 544   BITSET_STATS_FREES_INC (bset->s.bset);
 545   BITSET_FREE_ (bset->s.bset);
 546 }
 547
 548
 549 struct bitset_ops_struct bitset_stats_ops = {
 550   bitset_stats_set,
 551   bitset_stats_reset,
 552   bitset_stats_test,
 553   bitset_stats_size,
 554   bitset_stats_op1,
 555   bitset_stats_op2,
 556   bitset_stats_op3,
 557   bitset_stats_op4,
 558   bitset_stats_list,
 559   bitset_stats_reverse_list,
 560   bitset_stats_free,
 561   BITSET_STATS
 562 };
 563
 564
 565 /* Return enclosed bitset type.  */
 566 enum bitset_type
 567 bitset_stats_type_get (bset)
 568    bitset bset;
 569 {
 570    return BITSET_TYPE_ (bset->s.bset);
 571 }
 572
 573
 574 int bitset_stats_bytes (void)
 575 {
 576   return sizeof (struct bitset_struct);
 577 }
 578
 579
 580 bitset
 581 bitset_stats_init (bset, n_bits, type)
 582      bitset bset;
 583      bitset_bindex n_bits;
 584      enum bitset_type type;
 585 {
 586   unsigned int bytes;
 587   bitset sbset;
 588
 589   bset->b.ops = &bitset_stats_ops;
 590
 591   /* Disable cache.  */
 592   bset->b.cindex = 0;
 593   bset->b.csize = 0;
 594   bset->b.cdata = 0;
 595
 596   /* Set up the actual bitset implementation that
 597      we are a wrapper over.  */
 598   switch (type)
 599     {
 600     case BITSET_ARRAY:
 601       bytes = abitset_bytes (n_bits);
 602       sbset = (bitset) xcalloc (1, bytes);
 603       abitset_init (sbset, n_bits);
 604       break;
 605
 606     case BITSET_LIST:
 607       bytes = lbitset_bytes (n_bits);
 608       sbset = (bitset) xcalloc (1, bytes);
 609       lbitset_init (sbset, n_bits);
 610       break;
 611
 612     case BITSET_TABLE:
 613       bytes = ebitset_bytes (n_bits);
 614       sbset = (bitset) xcalloc (1, bytes);
 615       ebitset_init (sbset, n_bits);
 616       break;
 617
 618     default:
 619       abort ();
 620     }
 621
 622   bset->s.bset = sbset;
 623
 624   BITSET_STATS_ALLOCS_INC (type);
 625
 626   return bset;
 627 }