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