1/* Bitset statistics.
2
3   Copyright (C) 2002-2006, 2009-2012 Free Software Foundation, Inc.
4
5   Contributed by Michael Hayes (m.hayes@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
77struct 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
93struct bitset_stats_info_struct
94{
95  unsigned int runs;
96  struct bitset_type_info_struct types[BITSET_TYPE_NUM];
97};
98
99
100struct bitset_stats_info_struct bitset_stats_info_data;
101struct bitset_stats_info_struct *bitset_stats_info;
102bool bitset_stats_enabled = false;
103
104
105/* Print a percentage histogram with message MSG to FILE.  */
106static void
107bitset_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.  */
130static void
131bitset_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.  */
169static void
170bitset_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.  */
204static void
205bitset_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.  */
224void
225bitset_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
233void
234bitset_stats_disable (void)
235{
236  bitset_stats_enabled = false;
237}
238
239
240/* Read bitset statistics file.  */
241void
242bitset_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.  */
271void
272bitset_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.  */
297void
298bitset_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.  */
305void
306debug_bitset_stats (void)
307{
308  bitset_stats_print (stderr, true);
309}
310
311
312static void
313bitset_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
331static void
332bitset_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
351static bool
352bitset_stats_toggle (bitset src, bitset_bindex bitno)
353{
354    return BITSET_TOGGLE_ (src->s.bset, bitno);
355}
356
357
358static bool
359bitset_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
377static bitset_bindex
378bitset_stats_resize (bitset src, bitset_bindex size)
379{
380    return BITSET_RESIZE_ (src->s.bset, size);
381}
382
383
384static bitset_bindex
385bitset_stats_size (bitset src)
386{
387  return BITSET_SIZE_ (src->s.bset);
388}
389
390
391static bitset_bindex
392bitset_stats_count (bitset src)
393{
394  return BITSET_COUNT_ (src->s.bset);
395}
396
397
398static bool
399bitset_stats_empty_p (bitset dst)
400{
401  return BITSET_EMPTY_P_ (dst->s.bset);
402}
403
404
405static void
406bitset_stats_ones (bitset dst)
407{
408  BITSET_ONES_ (dst->s.bset);
409}
410
411
412static void
413bitset_stats_zero (bitset dst)
414{
415  BITSET_ZERO_ (dst->s.bset);
416}
417
418
419static void
420bitset_stats_copy (bitset dst, bitset src)
421{
422  BITSET_CHECK2_ (dst, src);
423  BITSET_COPY_ (dst->s.bset, src->s.bset);
424}
425
426
427static bool
428bitset_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
435static bool
436bitset_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
443static void
444bitset_stats_not (bitset dst, bitset src)
445{
446  BITSET_CHECK2_ (dst, src);
447  BITSET_NOT_ (dst->s.bset, src->s.bset);
448}
449
450
451static bool
452bitset_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
459static void
460bitset_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
467static bool
468bitset_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
475static void
476bitset_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
483static bool
484bitset_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
491static void
492bitset_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
499static bool
500bitset_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
507static void
508bitset_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
515static bool
516bitset_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
523static void
524bitset_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
531static bool
532bitset_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
539static void
540bitset_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
547static bool
548bitset_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
555static void
556bitset_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
563static bool
564bitset_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
571static bitset_bindex
572bitset_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
608static bitset_bindex
609bitset_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
616static void
617bitset_stats_free (bitset bset)
618{
619  BITSET_STATS_FREES_INC (bset->s.bset);
620  BITSET_FREE_ (bset->s.bset);
621}
622
623
624struct 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.  */
662enum bitset_type
663bitset_stats_type_get (bitset bset)
664{
665   return BITSET_TYPE_ (bset->s.bset);
666}
667
668
669size_t
670bitset_stats_bytes (void)
671{
672  return sizeof (struct bitset_stats_struct);
673}
674
675
676bitset
677bitset_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