1 /* Bitset statistics. 2 3 Copyright (C) 2002-2006, 2009-2012 Free Software Foundation, Inc. 4 5 Contributed by Michael Hayes (m.hayes (at) elec.canterbury.ac.nz). 6 7 This program is free software: you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation, either version 3 of the License, or 10 (at your option) any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 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 #include <config.h> 28 29 #include "bitset_stats.h" 30 31 #include "bbitset.h" 32 #include "abitset.h" 33 #include "ebitset.h" 34 #include "lbitset.h" 35 #include "vbitset.h" 36 #include <stdlib.h> 37 #include <string.h> 38 #include <stdio.h> 39 40 #include "gettext.h" 41 #define _(Msgid) gettext (Msgid) 42 43 /* Configuration macros. */ 44 #define BITSET_STATS_FILE "bitset.dat" 45 #define BITSET_LOG_COUNT_BINS 10 46 #define BITSET_LOG_SIZE_BINS 16 47 #define BITSET_DENSITY_BINS 20 48 49 50 /* Accessor macros. */ 51 #define BITSET_STATS_ALLOCS_INC(TYPE) \ 52 bitset_stats_info->types[(TYPE)].allocs++ 53 #define BITSET_STATS_FREES_INC(BSET) \ 54 bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++ 55 #define BITSET_STATS_SETS_INC(BSET) \ 56 bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++ 57 #define BITSET_STATS_CACHE_SETS_INC(BSET) \ 58 bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++ 59 #define BITSET_STATS_RESETS_INC(BSET) \ 60 bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++ 61 #define BITSET_STATS_CACHE_RESETS_INC(BSET) \ 62 bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++ 63 #define BITSET_STATS_TESTS_INC(BSET) \ 64 bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++ 65 #define BITSET_STATS_CACHE_TESTS_INC(BSET) \ 66 bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++ 67 #define BITSET_STATS_LISTS_INC(BSET) \ 68 bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++ 69 #define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \ 70 bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++ 71 #define BITSET_STATS_LIST_SIZES_INC(BSET, I) \ 72 bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++ 73 #define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \ 74 bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++ 75 76 77 struct bitset_type_info_struct 78 { 79 unsigned int allocs; 80 unsigned int frees; 81 unsigned int lists; 82 unsigned int sets; 83 unsigned int cache_sets; 84 unsigned int resets; 85 unsigned int cache_resets; 86 unsigned int tests; 87 unsigned int cache_tests; 88 unsigned int list_counts[BITSET_LOG_COUNT_BINS]; 89 unsigned int list_sizes[BITSET_LOG_SIZE_BINS]; 90 unsigned int list_density[BITSET_DENSITY_BINS]; 91 }; 92 93 struct bitset_stats_info_struct 94 { 95 unsigned int runs; 96 struct bitset_type_info_struct types[BITSET_TYPE_NUM]; 97 }; 98 99 100 struct bitset_stats_info_struct bitset_stats_info_data; 101 struct bitset_stats_info_struct *bitset_stats_info; 102 bool bitset_stats_enabled = false; 103 104 105 /* Print a percentage histogram with message MSG to FILE. */ 106 static void 107 bitset_percent_histogram_print (FILE *file, const char *name, const char *msg, 108 unsigned int n_bins, unsigned int *bins) 109 { 110 unsigned int i; 111 unsigned int total; 112 113 total = 0; 114 for (i = 0; i < n_bins; i++) 115 total += bins[i]; 116 117 if (!total) 118 return; 119 120 fprintf (file, "%s %s", name, msg); 121 for (i = 0; i < n_bins; i++) 122 fprintf (file, "%.0f-%.0f%%\t%8u (%5.1f%%)\n", 123 i * 100.0 / n_bins, 124 (i + 1) * 100.0 / n_bins, bins[i], 125 (100.0 * bins[i]) / total); 126 } 127 128 129 /* Print a log histogram with message MSG to FILE. */ 130 static void 131 bitset_log_histogram_print (FILE *file, const char *name, const char *msg, 132 unsigned int n_bins, unsigned int *bins) 133 { 134 unsigned int i; 135 unsigned int total; 136 unsigned int max_width; 137 138 total = 0; 139 for (i = 0; i < n_bins; i++) 140 total += bins[i]; 141 142 if (!total) 143 return; 144 145 /* Determine number of useful bins. */ 146 for (i = n_bins; i > 3 && ! bins[i - 1]; i--) 147 continue; 148 n_bins = i; 149 150 /* 2 * ceil (log10 (2) * (N - 1)) + 1. */ 151 max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1; 152 153 fprintf (file, "%s %s", name, msg); 154 for (i = 0; i < 2; i++) 155 fprintf (file, "%*d\t%8u (%5.1f%%)\n", 156 max_width, i, bins[i], 100.0 * bins[i] / total); 157 158 for (; i < n_bins; i++) 159 fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n", 160 max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1), 161 1UL << (i - 1), 162 (1UL << i) - 1, 163 bins[i], 164 (100.0 * bins[i]) / total); 165 } 166 167 168 /* Print bitset statistics to FILE. */ 169 static void 170 bitset_stats_print_1 (FILE *file, const char *name, 171 struct bitset_type_info_struct *stats) 172 { 173 if (!stats) 174 return; 175 176 fprintf (file, "%s:\n", name); 177 fprintf (file, _("%u bitset_allocs, %u freed (%.2f%%).\n"), 178 stats->allocs, stats->frees, 179 stats->allocs ? 100.0 * stats->frees / stats->allocs : 0); 180 fprintf (file, _("%u bitset_sets, %u cached (%.2f%%)\n"), 181 stats->sets, stats->cache_sets, 182 stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0); 183 fprintf (file, _("%u bitset_resets, %u cached (%.2f%%)\n"), 184 stats->resets, stats->cache_resets, 185 stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0); 186 fprintf (file, _("%u bitset_tests, %u cached (%.2f%%)\n"), 187 stats->tests, stats->cache_tests, 188 stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0); 189 190 fprintf (file, _("%u bitset_lists\n"), stats->lists); 191 192 bitset_log_histogram_print (file, name, _("count log histogram\n"), 193 BITSET_LOG_COUNT_BINS, stats->list_counts); 194 195 bitset_log_histogram_print (file, name, _("size log histogram\n"), 196 BITSET_LOG_SIZE_BINS, stats->list_sizes); 197 198 bitset_percent_histogram_print (file, name, _("density histogram\n"), 199 BITSET_DENSITY_BINS, stats->list_density); 200 } 201 202 203 /* Print all bitset statistics to FILE. */ 204 static void 205 bitset_stats_print (FILE *file, bool verbose ATTRIBUTE_UNUSED) 206 { 207 int i; 208 209 if (!bitset_stats_info) 210 return; 211 212 fprintf (file, _("Bitset statistics:\n\n")); 213 214 if (bitset_stats_info->runs > 1) 215 fprintf (file, _("Accumulated runs = %u\n"), bitset_stats_info->runs); 216 217 for (i = 0; i < BITSET_TYPE_NUM; i++) 218 bitset_stats_print_1 (file, bitset_type_names[i], 219 &bitset_stats_info->types[i]); 220 } 221 222 223 /* Initialise bitset statistics logging. */ 224 void 225 bitset_stats_enable (void) 226 { 227 if (!bitset_stats_info) 228 bitset_stats_info = &bitset_stats_info_data; 229 bitset_stats_enabled = true; 230 } 231 232 233 void 234 bitset_stats_disable (void) 235 { 236 bitset_stats_enabled = false; 237 } 238 239 240 /* Read bitset statistics file. */ 241 void 242 bitset_stats_read (const char *file_name) 243 { 244 FILE *file; 245 246 if (!bitset_stats_info) 247 return; 248 249 if (!file_name) 250 file_name = BITSET_STATS_FILE; 251 252 file = fopen (file_name, "r"); 253 if (file) 254 { 255 if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data), 256 1, file) != 1) 257 { 258 if (ferror (file)) 259 perror (_("cannot read stats file")); 260 else 261 fprintf (stderr, _("bad stats file size\n")); 262 } 263 if (fclose (file) != 0) 264 perror (_("cannot read stats file")); 265 } 266 bitset_stats_info_data.runs++; 267 } 268 269 270 /* Write bitset statistics file. */ 271 void 272 bitset_stats_write (const char *file_name) 273 { 274 FILE *file; 275 276 if (!bitset_stats_info) 277 return; 278 279 if (!file_name) 280 file_name = BITSET_STATS_FILE; 281 282 file = fopen (file_name, "w"); 283 if (file) 284 { 285 if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data), 286 1, file) != 1) 287 perror (_("cannot write stats file")); 288 if (fclose (file) != 0) 289 perror (_("cannot write stats file")); 290 } 291 else 292 perror (_("cannot open stats file for writing")); 293 } 294 295 296 /* Dump bitset statistics to FILE. */ 297 void 298 bitset_stats_dump (FILE *file) 299 { 300 bitset_stats_print (file, false); 301 } 302 303 304 /* Function to be called from debugger to print bitset stats. */ 305 void 306 debug_bitset_stats (void) 307 { 308 bitset_stats_print (stderr, true); 309 } 310 311 312 static void 313 bitset_stats_set (bitset dst, bitset_bindex bitno) 314 { 315 bitset bset = dst->s.bset; 316 bitset_windex wordno = bitno / BITSET_WORD_BITS; 317 bitset_windex offset = wordno - bset->b.cindex; 318 319 BITSET_STATS_SETS_INC (bset); 320 321 if (offset < bset->b.csize) 322 { 323 bset->b.cdata[offset] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS); 324 BITSET_STATS_CACHE_SETS_INC (bset); 325 } 326 else 327 BITSET_SET_ (bset, bitno); 328 } 329 330 331 static void 332 bitset_stats_reset (bitset dst, bitset_bindex bitno) 333 { 334 bitset bset = dst->s.bset; 335 bitset_windex wordno = bitno / BITSET_WORD_BITS; 336 bitset_windex offset = wordno - bset->b.cindex; 337 338 BITSET_STATS_RESETS_INC (bset); 339 340 if (offset < bset->b.csize) 341 { 342 bset->b.cdata[offset] &= 343 ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS)); 344 BITSET_STATS_CACHE_RESETS_INC (bset); 345 } 346 else 347 BITSET_RESET_ (bset, bitno); 348 } 349 350 351 static bool 352 bitset_stats_toggle (bitset src, bitset_bindex bitno) 353 { 354 return BITSET_TOGGLE_ (src->s.bset, bitno); 355 } 356 357 358 static bool 359 bitset_stats_test (bitset src, bitset_bindex bitno) 360 { 361 bitset bset = src->s.bset; 362 bitset_windex wordno = bitno / BITSET_WORD_BITS; 363 bitset_windex offset = wordno - bset->b.cindex; 364 365 BITSET_STATS_TESTS_INC (bset); 366 367 if (offset < bset->b.csize) 368 { 369 BITSET_STATS_CACHE_TESTS_INC (bset); 370 return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1; 371 } 372 else 373 return BITSET_TEST_ (bset, bitno); 374 } 375 376 377 static bitset_bindex 378 bitset_stats_resize (bitset src, bitset_bindex size) 379 { 380 return BITSET_RESIZE_ (src->s.bset, size); 381 } 382 383 384 static bitset_bindex 385 bitset_stats_size (bitset src) 386 { 387 return BITSET_SIZE_ (src->s.bset); 388 } 389 390 391 static bitset_bindex 392 bitset_stats_count (bitset src) 393 { 394 return BITSET_COUNT_ (src->s.bset); 395 } 396 397 398 static bool 399 bitset_stats_empty_p (bitset dst) 400 { 401 return BITSET_EMPTY_P_ (dst->s.bset); 402 } 403 404 405 static void 406 bitset_stats_ones (bitset dst) 407 { 408 BITSET_ONES_ (dst->s.bset); 409 } 410 411 412 static void 413 bitset_stats_zero (bitset dst) 414 { 415 BITSET_ZERO_ (dst->s.bset); 416 } 417 418 419 static void 420 bitset_stats_copy (bitset dst, bitset src) 421 { 422 BITSET_CHECK2_ (dst, src); 423 BITSET_COPY_ (dst->s.bset, src->s.bset); 424 } 425 426 427 static bool 428 bitset_stats_disjoint_p (bitset dst, bitset src) 429 { 430 BITSET_CHECK2_ (dst, src); 431 return BITSET_DISJOINT_P_ (dst->s.bset, src->s.bset); 432 } 433 434 435 static bool 436 bitset_stats_equal_p (bitset dst, bitset src) 437 { 438 BITSET_CHECK2_ (dst, src); 439 return BITSET_EQUAL_P_ (dst->s.bset, src->s.bset); 440 } 441 442 443 static void 444 bitset_stats_not (bitset dst, bitset src) 445 { 446 BITSET_CHECK2_ (dst, src); 447 BITSET_NOT_ (dst->s.bset, src->s.bset); 448 } 449 450 451 static bool 452 bitset_stats_subset_p (bitset dst, bitset src) 453 { 454 BITSET_CHECK2_ (dst, src); 455 return BITSET_SUBSET_P_ (dst->s.bset, src->s.bset); 456 } 457 458 459 static void 460 bitset_stats_and (bitset dst, bitset src1, bitset src2) 461 { 462 BITSET_CHECK3_ (dst, src1, src2); 463 BITSET_AND_ (dst->s.bset, src1->s.bset, src2->s.bset); 464 } 465 466 467 static bool 468 bitset_stats_and_cmp (bitset dst, bitset src1, bitset src2) 469 { 470 BITSET_CHECK3_ (dst, src1, src2); 471 return BITSET_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); 472 } 473 474 475 static void 476 bitset_stats_andn (bitset dst, bitset src1, bitset src2) 477 { 478 BITSET_CHECK3_ (dst, src1, src2); 479 BITSET_ANDN_ (dst->s.bset, src1->s.bset, src2->s.bset); 480 } 481 482 483 static bool 484 bitset_stats_andn_cmp (bitset dst, bitset src1, bitset src2) 485 { 486 BITSET_CHECK3_ (dst, src1, src2); 487 return BITSET_ANDN_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); 488 } 489 490 491 static void 492 bitset_stats_or (bitset dst, bitset src1, bitset src2) 493 { 494 BITSET_CHECK3_ (dst, src1, src2); 495 BITSET_OR_ (dst->s.bset, src1->s.bset, src2->s.bset); 496 } 497 498 499 static bool 500 bitset_stats_or_cmp (bitset dst, bitset src1, bitset src2) 501 { 502 BITSET_CHECK3_ (dst, src1, src2); 503 return BITSET_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); 504 } 505 506 507 static void 508 bitset_stats_xor (bitset dst, bitset src1, bitset src2) 509 { 510 BITSET_CHECK3_ (dst, src1, src2); 511 BITSET_XOR_ (dst->s.bset, src1->s.bset, src2->s.bset); 512 } 513 514 515 static bool 516 bitset_stats_xor_cmp (bitset dst, bitset src1, bitset src2) 517 { 518 BITSET_CHECK3_ (dst, src1, src2); 519 return BITSET_XOR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); 520 } 521 522 523 static void 524 bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3) 525 { 526 BITSET_CHECK4_ (dst, src1, src2, src3); 527 BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); 528 } 529 530 531 static bool 532 bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 533 { 534 BITSET_CHECK4_ (dst, src1, src2, src3); 535 return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); 536 } 537 538 539 static void 540 bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3) 541 { 542 BITSET_CHECK4_ (dst, src1, src2, src3); 543 BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); 544 } 545 546 547 static bool 548 bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 549 { 550 BITSET_CHECK4_ (dst, src1, src2, src3); 551 return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); 552 } 553 554 555 static void 556 bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3) 557 { 558 BITSET_CHECK4_ (dst, src1, src2, src3); 559 BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); 560 } 561 562 563 static bool 564 bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 565 { 566 BITSET_CHECK4_ (dst, src1, src2, src3); 567 return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); 568 } 569 570 571 static bitset_bindex 572 bitset_stats_list (bitset bset, bitset_bindex *list, 573 bitset_bindex num, bitset_bindex *next) 574 { 575 bitset_bindex count; 576 bitset_bindex tmp; 577 bitset_bindex size; 578 bitset_bindex i; 579 580 count = BITSET_LIST_ (bset->s.bset, list, num, next); 581 582 BITSET_STATS_LISTS_INC (bset->s.bset); 583 584 /* Log histogram of number of set bits. */ 585 for (i = 0, tmp = count; tmp; tmp >>= 1, i++) 586 continue; 587 if (i >= BITSET_LOG_COUNT_BINS) 588 i = BITSET_LOG_COUNT_BINS - 1; 589 BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i); 590 591 /* Log histogram of number of bits in set. */ 592 size = BITSET_SIZE_ (bset->s.bset); 593 for (i = 0, tmp = size; tmp; tmp >>= 1, i++) 594 continue; 595 if (i >= BITSET_LOG_SIZE_BINS) 596 i = BITSET_LOG_SIZE_BINS - 1; 597 BITSET_STATS_LIST_SIZES_INC (bset->s.bset, i); 598 599 /* Histogram of fraction of bits set. */ 600 i = size ? (count * BITSET_DENSITY_BINS) / size : 0; 601 if (i >= BITSET_DENSITY_BINS) 602 i = BITSET_DENSITY_BINS - 1; 603 BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i); 604 return count; 605 } 606 607 608 static bitset_bindex 609 bitset_stats_list_reverse (bitset bset, bitset_bindex *list, 610 bitset_bindex num, bitset_bindex *next) 611 { 612 return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next); 613 } 614 615 616 static void 617 bitset_stats_free (bitset bset) 618 { 619 BITSET_STATS_FREES_INC (bset->s.bset); 620 BITSET_FREE_ (bset->s.bset); 621 } 622 623 624 struct bitset_vtable bitset_stats_vtable = { 625 bitset_stats_set, 626 bitset_stats_reset, 627 bitset_stats_toggle, 628 bitset_stats_test, 629 bitset_stats_resize, 630 bitset_stats_size, 631 bitset_stats_count, 632 bitset_stats_empty_p, 633 bitset_stats_ones, 634 bitset_stats_zero, 635 bitset_stats_copy, 636 bitset_stats_disjoint_p, 637 bitset_stats_equal_p, 638 bitset_stats_not, 639 bitset_stats_subset_p, 640 bitset_stats_and, 641 bitset_stats_and_cmp, 642 bitset_stats_andn, 643 bitset_stats_andn_cmp, 644 bitset_stats_or, 645 bitset_stats_or_cmp, 646 bitset_stats_xor, 647 bitset_stats_xor_cmp, 648 bitset_stats_and_or, 649 bitset_stats_and_or_cmp, 650 bitset_stats_andn_or, 651 bitset_stats_andn_or_cmp, 652 bitset_stats_or_and, 653 bitset_stats_or_and_cmp, 654 bitset_stats_list, 655 bitset_stats_list_reverse, 656 bitset_stats_free, 657 BITSET_STATS 658 }; 659 660 661 /* Return enclosed bitset type. */ 662 enum bitset_type 663 bitset_stats_type_get (bitset bset) 664 { 665 return BITSET_TYPE_ (bset->s.bset); 666 } 667 668 669 size_t 670 bitset_stats_bytes (void) 671 { 672 return sizeof (struct bitset_stats_struct); 673 } 674 675 676 bitset 677 bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) 678 { 679 size_t bytes; 680 bitset sbset; 681 682 bset->b.vtable = &bitset_stats_vtable; 683 684 /* Disable cache. */ 685 bset->b.cindex = 0; 686 bset->b.csize = 0; 687 bset->b.cdata = 0; 688 689 BITSET_NBITS_ (bset) = n_bits; 690 691 /* Set up the actual bitset implementation that 692 we are a wrapper over. */ 693 switch (type) 694 { 695 default: 696 abort (); 697 698 case BITSET_ARRAY: 699 bytes = abitset_bytes (n_bits); 700 sbset = xcalloc (1, bytes); 701 abitset_init (sbset, n_bits); 702 break; 703 704 case BITSET_LIST: 705 bytes = lbitset_bytes (n_bits); 706 sbset = xcalloc (1, bytes); 707 lbitset_init (sbset, n_bits); 708 break; 709 710 case BITSET_TABLE: 711 bytes = ebitset_bytes (n_bits); 712 sbset = xcalloc (1, bytes); 713 ebitset_init (sbset, n_bits); 714 break; 715 716 case BITSET_VARRAY: 717 bytes = vbitset_bytes (n_bits); 718 sbset = xcalloc (1, bytes); 719 vbitset_init (sbset, n_bits); 720 break; 721 } 722 723 bset->s.bset = sbset; 724 725 BITSET_STATS_ALLOCS_INC (type); 726 727 return bset; 728 } 729
