This source file includes following definitions.
- bitset_percent_histogram_print
- bitset_log_histogram_print
- bitset_stats_print_1
- bitset_stats_print
- bitset_stats_enable
- bitset_stats_disable
- bitset_stats_read
- bitset_stats_write
- bitset_stats_dump
- debug_bitset_stats
- bitset_stats_set
- bitset_stats_reset
- bitset_stats_toggle
- bitset_stats_test
- bitset_stats_resize
- bitset_stats_size
- bitset_stats_count
- bitset_stats_empty_p
- bitset_stats_ones
- bitset_stats_zero
- bitset_stats_copy
- bitset_stats_disjoint_p
- bitset_stats_equal_p
- bitset_stats_not
- bitset_stats_subset_p
- bitset_stats_and
- bitset_stats_and_cmp
- bitset_stats_andn
- bitset_stats_andn_cmp
- bitset_stats_or
- bitset_stats_or_cmp
- bitset_stats_xor
- bitset_stats_xor_cmp
- bitset_stats_and_or
- bitset_stats_and_or_cmp
- bitset_stats_andn_or
- bitset_stats_andn_or_cmp
- bitset_stats_or_and
- bitset_stats_or_and_cmp
- bitset_stats_list
- bitset_stats_list_reverse
- bitset_stats_free
- bitset_stats_type_get
- bitset_stats_bytes
- bitset_stats_init
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 #include <config.h>
28
29 #include "bitset/stats.h"
30
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34
35 #include "gettext.h"
36 #define _(Msgid) gettext (Msgid)
37
38 #include "bitset/array.h"
39 #include "bitset/base.h"
40 #include "bitset/list.h"
41 #include "bitset/table.h"
42 #include "bitset/vector.h"
43
44
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
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 struct bitset_type_info_struct
79 {
80 unsigned allocs;
81 unsigned frees;
82 unsigned lists;
83 unsigned sets;
84 unsigned cache_sets;
85 unsigned resets;
86 unsigned cache_resets;
87 unsigned tests;
88 unsigned cache_tests;
89 unsigned list_counts[BITSET_LOG_COUNT_BINS];
90 unsigned list_sizes[BITSET_LOG_SIZE_BINS];
91 unsigned list_density[BITSET_DENSITY_BINS];
92 };
93
94 struct bitset_stats_info_struct
95 {
96 unsigned runs;
97 struct bitset_type_info_struct types[BITSET_TYPE_NUM];
98 };
99
100
101 struct bitset_stats_info_struct bitset_stats_info_data;
102 struct bitset_stats_info_struct *bitset_stats_info;
103 bool bitset_stats_enabled = false;
104
105
106
107 static void
108 bitset_percent_histogram_print (FILE *file, const char *name, const char *msg,
109 unsigned n_bins, unsigned *bins)
110 {
111 unsigned total = 0;
112 for (unsigned i = 0; i < n_bins; i++)
113 total += bins[i];
114
115 if (!total)
116 return;
117
118 fprintf (file, "%s %s", name, msg);
119 for (unsigned i = 0; i < n_bins; i++)
120 fprintf (file, "%.0f-%.0f%%\t%8u (%5.1f%%)\n",
121 i * 100.0 / n_bins,
122 (i + 1) * 100.0 / n_bins, bins[i],
123 (100.0 * bins[i]) / total);
124 }
125
126
127
128 static void
129 bitset_log_histogram_print (FILE *file, const char *name, const char *msg,
130 unsigned n_bins, unsigned *bins)
131 {
132 unsigned total = 0;
133 for (unsigned i = 0; i < n_bins; i++)
134 total += bins[i];
135
136 if (!total)
137 return;
138
139
140 {
141 unsigned i;
142 for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
143 continue;
144 n_bins = i;
145 }
146
147
148 unsigned max_width = 2 * (unsigned) (0.30103 * (n_bins - 1) + 0.9999) + 1;
149
150 fprintf (file, "%s %s", name, msg);
151 {
152 unsigned i;
153 for (i = 0; i < 2; i++)
154 fprintf (file, "%*d\t%8u (%5.1f%%)\n",
155 max_width, i, bins[i], 100.0 * bins[i] / total);
156
157 for (; i < n_bins - 1; i++)
158 fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n",
159 max_width - ((unsigned) (0.30103 * (i) + 0.9999) + 1),
160 1UL << (i - 1),
161 (1UL << i) - 1,
162 bins[i],
163 (100.0 * bins[i]) / total);
164
165 fprintf (file, "%*lu-...\t%8u (%5.1f%%)\n",
166 max_width - ((unsigned) (0.30103 * (i) + 0.9999) + 1),
167 1UL << (i - 1),
168 bins[i],
169 (100.0 * bins[i]) / total);
170 }
171 }
172
173
174
175 static void
176 bitset_stats_print_1 (FILE *file, const char *name,
177 struct bitset_type_info_struct *stats)
178 {
179 if (!stats)
180 return;
181
182 fprintf (file, "%s:\n", name);
183 fprintf (file, _("%u bitset_allocs, %u freed (%.2f%%).\n"),
184 stats->allocs, stats->frees,
185 stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
186 fprintf (file, _("%u bitset_sets, %u cached (%.2f%%)\n"),
187 stats->sets, stats->cache_sets,
188 stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
189 fprintf (file, _("%u bitset_resets, %u cached (%.2f%%)\n"),
190 stats->resets, stats->cache_resets,
191 stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
192 fprintf (file, _("%u bitset_tests, %u cached (%.2f%%)\n"),
193 stats->tests, stats->cache_tests,
194 stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);
195
196 fprintf (file, _("%u bitset_lists\n"), stats->lists);
197
198 bitset_log_histogram_print (file, name, _("count log histogram\n"),
199 BITSET_LOG_COUNT_BINS, stats->list_counts);
200
201 bitset_log_histogram_print (file, name, _("size log histogram\n"),
202 BITSET_LOG_SIZE_BINS, stats->list_sizes);
203
204 bitset_percent_histogram_print (file, name, _("density histogram\n"),
205 BITSET_DENSITY_BINS, stats->list_density);
206 }
207
208
209
210 static void
211 bitset_stats_print (FILE *file, MAYBE_UNUSED bool verbose)
212 {
213 if (!bitset_stats_info)
214 return;
215
216 fprintf (file, _("Bitset statistics:\n\n"));
217
218 if (bitset_stats_info->runs > 1)
219 fprintf (file, _("Accumulated runs = %u\n"), bitset_stats_info->runs);
220
221 for (int i = 0; i < BITSET_TYPE_NUM; i++)
222 bitset_stats_print_1 (file, bitset_type_names[i],
223 &bitset_stats_info->types[i]);
224 }
225
226
227
228 void
229 bitset_stats_enable (void)
230 {
231 if (!bitset_stats_info)
232 bitset_stats_info = &bitset_stats_info_data;
233 bitset_stats_enabled = true;
234 }
235
236
237 void
238 bitset_stats_disable (void)
239 {
240 bitset_stats_enabled = false;
241 }
242
243
244
245 void
246 bitset_stats_read (const char *file_name)
247 {
248 if (!bitset_stats_info)
249 return;
250
251 if (!file_name)
252 file_name = BITSET_STATS_FILE;
253
254 FILE *file = fopen (file_name, "re");
255 if (file)
256 {
257 if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
258 1, file) != 1)
259 {
260 if (ferror (file))
261 perror (_("cannot read stats file"));
262 else
263 fprintf (stderr, _("bad stats file size\n"));
264 }
265 if (fclose (file) != 0)
266 perror (_("cannot read stats file"));
267 }
268 bitset_stats_info_data.runs++;
269 }
270
271
272
273 void
274 bitset_stats_write (const char *file_name)
275 {
276 if (!bitset_stats_info)
277 return;
278
279 if (!file_name)
280 file_name = BITSET_STATS_FILE;
281
282 FILE *file = fopen (file_name, "we");
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
297 void
298 bitset_stats_dump (FILE *file)
299 {
300 bitset_stats_print (file, false);
301 }
302
303
304
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 = BITSET_LIST_ (bset->s.bset, list, num, next);
576
577 BITSET_STATS_LISTS_INC (bset->s.bset);
578
579
580 {
581 bitset_bindex i;
582 bitset_bindex tmp;
583 for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
584 continue;
585 if (i >= BITSET_LOG_COUNT_BINS)
586 i = BITSET_LOG_COUNT_BINS - 1;
587 BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i);
588 }
589
590
591 bitset_bindex size = BITSET_SIZE_ (bset->s.bset);
592 {
593 bitset_bindex i;
594 bitset_bindex tmp;
595 for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
596 continue;
597 if (i >= BITSET_LOG_SIZE_BINS)
598 i = BITSET_LOG_SIZE_BINS - 1;
599 BITSET_STATS_LIST_SIZES_INC (bset->s.bset, i);
600 }
601
602
603 {
604 bitset_bindex i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
605 if (i >= BITSET_DENSITY_BINS)
606 i = BITSET_DENSITY_BINS - 1;
607 BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i);
608 }
609 return count;
610 }
611
612
613 static bitset_bindex
614 bitset_stats_list_reverse (bitset bset, bitset_bindex *list,
615 bitset_bindex num, bitset_bindex *next)
616 {
617 return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next);
618 }
619
620
621 static void
622 bitset_stats_free (bitset bset)
623 {
624 BITSET_STATS_FREES_INC (bset->s.bset);
625 BITSET_FREE_ (bset->s.bset);
626 }
627
628
629 struct bitset_vtable bitset_stats_vtable = {
630 bitset_stats_set,
631 bitset_stats_reset,
632 bitset_stats_toggle,
633 bitset_stats_test,
634 bitset_stats_resize,
635 bitset_stats_size,
636 bitset_stats_count,
637 bitset_stats_empty_p,
638 bitset_stats_ones,
639 bitset_stats_zero,
640 bitset_stats_copy,
641 bitset_stats_disjoint_p,
642 bitset_stats_equal_p,
643 bitset_stats_not,
644 bitset_stats_subset_p,
645 bitset_stats_and,
646 bitset_stats_and_cmp,
647 bitset_stats_andn,
648 bitset_stats_andn_cmp,
649 bitset_stats_or,
650 bitset_stats_or_cmp,
651 bitset_stats_xor,
652 bitset_stats_xor_cmp,
653 bitset_stats_and_or,
654 bitset_stats_and_or_cmp,
655 bitset_stats_andn_or,
656 bitset_stats_andn_or_cmp,
657 bitset_stats_or_and,
658 bitset_stats_or_and_cmp,
659 bitset_stats_list,
660 bitset_stats_list_reverse,
661 bitset_stats_free,
662 BITSET_STATS
663 };
664
665
666
667 enum bitset_type
668 bitset_stats_type_get (bitset bset)
669 {
670 return BITSET_TYPE_ (bset->s.bset);
671 }
672
673
674 size_t
675 bitset_stats_bytes (void)
676 {
677 return sizeof (struct bitset_stats_struct);
678 }
679
680
681 bitset
682 bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
683 {
684 bset->b.vtable = &bitset_stats_vtable;
685
686
687 bset->b.cindex = 0;
688 bset->b.csize = 0;
689 bset->b.cdata = 0;
690
691 BITSET_NBITS_ (bset) = n_bits;
692
693
694
695 switch (type)
696 {
697 default:
698 abort ();
699
700 case BITSET_ARRAY:
701 {
702 size_t bytes = abitset_bytes (n_bits);
703 bset->s.bset = xzalloc (bytes);
704 abitset_init (bset->s.bset, n_bits);
705 }
706 break;
707
708 case BITSET_LIST:
709 {
710 size_t bytes = lbitset_bytes (n_bits);
711 bset->s.bset = xzalloc (bytes);
712 lbitset_init (bset->s.bset, n_bits);
713 }
714 break;
715
716 case BITSET_TABLE:
717 {
718 size_t bytes = tbitset_bytes (n_bits);
719 bset->s.bset = xzalloc (bytes);
720 tbitset_init (bset->s.bset, n_bits);
721 }
722 break;
723
724 case BITSET_VECTOR:
725 {
726 size_t bytes = vbitset_bytes (n_bits);
727 bset->s.bset = xzalloc (bytes);
728 vbitset_init (bset->s.bset, n_bits);
729 }
730 break;
731 }
732
733 BITSET_STATS_ALLOCS_INC (type);
734
735 return bset;
736 }