Hello list,
this is the second part of my patch. It collects and prints some memory
statistics for hash tables that I've measured as the hottest ones. Tested
together with previous patch on i386. Example output:
libcpp symtab string pool:
identifiers 32644 (100.00%)
entries 32644 (49.81%)
deleted 0
slots 65536
string bytes 445k (4064 obstack_memory_used)
table size 256k
searches 234217
collisions 86838
coll/search 0.3708
ins/search 0.1394
avg. entry 13.97 bytes (+/- 6.42)
longest entry 52
No gimple statistics
??? tree nodes created
(No per-node statistics)
DECL_DEBUG_EXPR hash: size 1021, 23 elements, 0.000000 collisions
DECL_VALUE_EXPR hash: size 1021, 0 elements, 0.000000 collisions
tree.c:type_hash_table stats
slots 32749
identifiers 5605
entries 5605 (17.12%)
deleted 0
struct htab 60 B
table size 127 kB
element 8 B
total contents 43 kB
searches 27032
collisions 9148
coll/search 0.3384
emit-rtl.c:mem_attrs_htab hash table:
slots 8191
identifiers 2295
entries 2295 (28.02%)
deleted 0
struct htab 60 B
table size 31 kB
element 24 B
total contents 53 kB
searches 7166
collisions 3784
coll/search 0.5280
cgraph.c:cgraph_hash hash table stats:
slots 8191
identifiers 198
entries 3100 (37.85%)
deleted 2902
struct htab 60 B
table size 31 kB
element 160 B
total contents 30 kB
searches 103425
collisions 32761
coll/search 0.3168
var-tracking.c stats
2363 vars->htab hash tables:
total searches 483055
total collisions 68621
total coll/search 0.1421
54 changed_variables hash tables
total searches 33417
total collisions 14253
total coll/search 0.4265
54 value_chains hash tables
total searches 43924
total collisions 14027
total coll/search 0.3193
cselib stats for 614 hash tables
total searches 52840
total collisions 9597
total coll/search 0.1816
Changelog:
2011-08-09 Dimitrios Apostolou <ji...@gmx.net>
* cgraph.c, cgraph.h (cgraph_dump_stats): New function to dump
stats about cgraph_hash hash table.
* cselib.c, cselib.h (cselib_dump_stats): New function to dump
stats about cselib_hash_table.
* cselib.c (cselib_finish): Keep statistics by increasing values
of new global variables cselib_htab_{num,searches,collisions} if
-fmem-report.
* emit-rtl.c, emit-rtl.h (mem_attrs_dump_stats): New function to
dump statistics about mem_attrs_htab hash table.
* tree.c (print_type_hash_statistics): Used the new
htab_dump_statistics() function.
* var-tracking.c (shared_hash_destroy): Keep statistics by
increasing values of new global variables
vars_htab_{num,searches,collisions} if -fmem-report.
(vt_finalize): Keep statistics by increasing values of new global
variables cv_htab_{num,searches,collisions} and
vc_htab_{num,searches,collisions} if -fmem-report.
* var-tracking.c, rtl.h (vt_dump_stats): New function to dump
stats about vars->htab, changed_variables and value_chains hash
tables.
* toplev.c: Included cselib.h for cselib_dump_stats().
(dump_memory_report): Call all the above functions to provide
better statistics.
* hashtab.c, hashtab.h (htab_dump_statistics, htab_collisions_num)
(htab_searches_num): New functions for statistics.
* hashtab.c: Included assert.h for checks in htab_dump_statistics.
* symtab.c (ht_dump_statistics): Beautified stats output.
Thanks,
Dimitris
=== modified file 'gcc/cgraph.c'
--- gcc/cgraph.c 2011-06-06 17:12:25 +0000
+++ gcc/cgraph.c 2011-08-09 01:01:19 +0000
@@ -2897,4 +2897,11 @@ cgraph_used_from_object_file_p (struct c
return false;
}
+void
+cgraph_dump_stats (void)
+{
+ fprintf (stderr, "\ncgraph.c:cgraph_hash hash table stats:\n");
+ htab_dump_statistics (cgraph_hash, sizeof (struct cgraph_node));
+}
+
#include "gt-cgraph.h"
=== modified file 'gcc/cgraph.h'
--- gcc/cgraph.h 2011-05-31 14:58:49 +0000
+++ gcc/cgraph.h 2011-08-08 23:19:51 +0000
@@ -540,6 +540,7 @@ bool cgraph_can_remove_if_no_direct_call
bool resolution_used_from_other_file_p (enum ld_plugin_symbol_resolution
resolution);
bool cgraph_used_from_object_file_p (struct cgraph_node *node);
bool varpool_used_from_object_file_p (struct varpool_node *node);
+void cgraph_dump_stats (void);
/* In cgraphunit.c */
extern FILE *cgraph_dump_file;
=== modified file 'gcc/cselib.c'
--- gcc/cselib.c 2011-05-31 19:14:21 +0000
+++ gcc/cselib.c 2011-08-09 01:38:54 +0000
@@ -2518,6 +2518,10 @@ cselib_init (int record_what)
next_uid = 1;
}
+static unsigned int cselib_htab_num;
+static unsigned long cselib_htab_searches;
+static unsigned long cselib_htab_collisions;
+
/* Called when the current user is done with cselib. */
void
@@ -2531,6 +2535,12 @@ cselib_finish (void)
free_alloc_pool (elt_loc_list_pool);
free_alloc_pool (cselib_val_pool);
free_alloc_pool (value_pool);
+ if (mem_report)
+ {
+ cselib_htab_num++;
+ cselib_htab_searches += htab_searches_num (cselib_hash_table);
+ cselib_htab_collisions += htab_collisions_num (cselib_hash_table);
+ }
cselib_clear_table ();
htab_delete (cselib_hash_table);
free (used_regs);
@@ -2630,4 +2640,17 @@ dump_cselib_table (FILE *out)
fprintf (out, "next uid %i\n", next_uid);
}
+void
+cselib_dump_stats (void)
+{
+ if (cselib_htab_num > 0)
+ {
+ fprintf (stderr, "\ncselib stats for %u hash tables\n", cselib_htab_num);
+ fprintf (stderr, "\ttotal searches\t\t%lu\n", cselib_htab_searches);
+ fprintf (stderr, "\ttotal collisions\t%lu\n", cselib_htab_collisions);
+ fprintf (stderr, "\ttotal coll/search\t%.4f\n",
+ (float) cselib_htab_collisions / cselib_htab_searches);
+ }
+}
+
#include "gt-cselib.h"
=== modified file 'gcc/cselib.h'
--- gcc/cselib.h 2011-02-03 06:04:04 +0000
+++ gcc/cselib.h 2011-08-09 01:35:31 +0000
@@ -98,3 +98,4 @@ extern void cselib_preserve_only_values
extern void cselib_preserve_cfa_base_value (cselib_val *, unsigned int);
extern void dump_cselib_table (FILE *);
+extern void cselib_dump_stats (void);
=== modified file 'gcc/emit-rtl.c'
--- gcc/emit-rtl.c 2011-05-29 17:40:05 +0000
+++ gcc/emit-rtl.c 2011-08-09 01:02:24 +0000
@@ -5425,6 +5425,13 @@ gen_rtx_CONST_VECTOR (enum machine_mode
return gen_rtx_raw_CONST_VECTOR (mode, v);
}
+void
+mem_attrs_dump_stats (void)
+{
+ fprintf (stderr, "\nemit-rtl.c:mem_attrs_htab hash table:\n");
+ htab_dump_statistics (mem_attrs_htab, sizeof (mem_attrs));
+}
+
/* Initialise global register information required by all functions. */
void
=== modified file 'gcc/emit-rtl.h'
--- gcc/emit-rtl.h 2011-01-03 20:52:22 +0000
+++ gcc/emit-rtl.h 2011-08-08 15:44:42 +0000
@@ -62,6 +62,7 @@ extern void set_reg_attrs_for_parm (rtx,
extern void set_reg_attrs_for_decl_rtl (tree t, rtx x);
extern void adjust_reg_mode (rtx, enum machine_mode);
extern int mem_expr_equal_p (const_tree, const_tree);
+extern void mem_attrs_dump_stats (void);
/* Return the first insn of the current sequence or current function. */
=== modified file 'gcc/rtl.h'
--- gcc/rtl.h 2011-05-03 13:08:36 +0000
+++ gcc/rtl.h 2011-08-08 22:34:19 +0000
@@ -2527,6 +2527,7 @@ extern bool expensive_function_p (int);
/* In var-tracking.c */
extern unsigned int variable_tracking_main (void);
+extern void vt_dump_stats (void);
/* In stor-layout.c. */
extern void get_mode_bounds (enum machine_mode, int, enum machine_mode,
=== modified file 'gcc/toplev.c'
--- gcc/toplev.c 2011-05-25 11:00:14 +0000
+++ gcc/toplev.c 2011-08-09 01:40:53 +0000
@@ -77,6 +77,7 @@ along with GCC; see the file COPYING3.
#include "gimple.h"
#include "tree-ssa-alias.h"
#include "plugin.h"
+#include "cselib.h" /* only for cselib_dump_stats() */
#if defined (DWARF2_UNWIND_INFO) || defined (DWARF2_DEBUGGING_INFO)
#include "dwarf2out.h"
@@ -1824,8 +1825,13 @@ dump_memory_report (bool final)
{
ggc_print_statistics ();
stringpool_statistics ();
- dump_tree_statistics ();
dump_gimple_statistics ();
+ dump_tree_statistics ();
+ mem_attrs_dump_stats ();
+ cgraph_dump_stats ();
+ if (flag_var_tracking)
+ vt_dump_stats ();
+ cselib_dump_stats ();
dump_rtx_statistics ();
dump_alloc_pool_statistics ();
dump_bitmap_statistics ();
=== modified file 'gcc/tree.c'
--- gcc/tree.c 2011-06-07 14:37:39 +0000
+++ gcc/tree.c 2011-08-09 01:04:09 +0000
@@ -6225,10 +6225,8 @@ type_hash_marked_p (const void *p)
static void
print_type_hash_statistics (void)
{
- fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
- (long) htab_size (type_hash_table),
- (long) htab_elements (type_hash_table),
- htab_collisions (type_hash_table));
+ fprintf (stderr, "\ntree.c:type_hash_table stats\n");
+ htab_dump_statistics (type_hash_table, sizeof (struct type_hash));
}
/* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
@@ -8564,10 +8562,10 @@ dump_tree_statistics (void)
#else
fprintf (stderr, "(No per-node statistics)\n");
#endif
- print_type_hash_statistics ();
print_debug_expr_statistics ();
print_value_expr_statistics ();
lang_hooks.print_statistics ();
+ print_type_hash_statistics ();
}
#define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
=== modified file 'gcc/var-tracking.c'
--- gcc/var-tracking.c 2011-06-03 01:42:31 +0000
+++ gcc/var-tracking.c 2011-08-09 01:34:31 +0000
@@ -1422,6 +1422,10 @@ shared_hash_copy (shared_hash vars)
return vars;
}
+static unsigned long vars_htab_searches;
+static unsigned long vars_htab_collisions;
+static unsigned int vars_htab_num;
+
/* Decrement reference counter and destroy hash table if not shared
anymore. */
@@ -1431,6 +1435,12 @@ shared_hash_destroy (shared_hash vars)
gcc_checking_assert (vars->refcount > 0);
if (--vars->refcount == 0)
{
+ if (mem_report)
+ {
+ vars_htab_num++;
+ vars_htab_searches += htab_searches_num (vars->htab);
+ vars_htab_collisions += htab_collisions_num (vars->htab);
+ }
htab_delete (vars->htab);
pool_free (shared_hash_pool, vars);
}
@@ -8982,6 +8992,10 @@ vt_debug_insns_local (bool skipped ATTRI
delete_debug_insns ();
}
+static unsigned long cv_htab_searches, vc_htab_searches;
+static unsigned long cv_htab_collisions, vc_htab_collisions;
+static unsigned int cv_htab_num, vc_htab_num;
+
/* Free the data structures needed for variable tracking. */
static void
@@ -9006,6 +9020,12 @@ vt_finalize (void)
}
free_aux_for_blocks ();
htab_delete (empty_shared_hash->htab);
+ if (mem_report)
+ {
+ cv_htab_num++;
+ cv_htab_searches += htab_searches_num (changed_variables);
+ cv_htab_collisions += htab_collisions_num (changed_variables);
+ }
htab_delete (changed_variables);
free_alloc_pool (attrs_pool);
free_alloc_pool (var_pool);
@@ -9014,6 +9034,12 @@ vt_finalize (void)
if (MAY_HAVE_DEBUG_INSNS)
{
+ if (mem_report)
+ {
+ vc_htab_num++;
+ vc_htab_searches += htab_searches_num (value_chains);
+ vc_htab_collisions += htab_collisions_num (value_chains);
+ }
htab_delete (value_chains);
free_alloc_pool (value_chain_pool);
free_alloc_pool (valvar_pool);
@@ -9029,6 +9055,33 @@ vt_finalize (void)
vui_allocated = 0;
}
+void
+vt_dump_stats (void)
+{
+ fprintf (stderr, "\nvar-tracking.c stats\n");
+
+ fprintf (stderr, "\t%u vars->htab hash tables:\n", vars_htab_num);
+ fprintf (stderr, "\t\ttotal searches\t\t%lu\n", vars_htab_searches);
+ fprintf (stderr, "\t\ttotal collisions\t%lu\n", vars_htab_collisions);
+ fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",
+ (float) vars_htab_collisions / vars_htab_searches);
+
+ fprintf (stderr, "\t%u changed_variables hash tables\n", cv_htab_num);
+ fprintf (stderr, "\t\ttotal searches\t\t%lu\n", cv_htab_searches);
+ fprintf (stderr, "\t\ttotal collisions\t%lu\n", cv_htab_collisions);
+ fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",
+ (float) cv_htab_collisions / cv_htab_searches);
+
+ if (MAY_HAVE_DEBUG_INSNS)
+ {
+ fprintf (stderr, "\t%u value_chains hash tables\n", vc_htab_num);
+ fprintf (stderr, "\t\ttotal searches\t\t%lu\n", vc_htab_searches);
+ fprintf (stderr, "\t\ttotal collisions\t%lu\n", vc_htab_collisions);
+ fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",
+ (float) vc_htab_collisions / vc_htab_searches);
+ }
+}
+
/* The entry point to variable tracking pass. */
static inline unsigned int
=== modified file 'include/hashtab.h'
--- include/hashtab.h 2010-06-08 06:25:24 +0000
+++ include/hashtab.h 2011-08-06 22:04:26 +0000
@@ -187,6 +187,9 @@ extern void htab_traverse_noresize (htab
extern size_t htab_size (htab_t);
extern size_t htab_elements (htab_t);
extern double htab_collisions (htab_t);
+extern void htab_dump_statistics (htab_t, size_t);
+extern unsigned int htab_collisions_num (htab_t);
+extern unsigned int htab_searches_num (htab_t);
/* A hash function for pointers. */
extern htab_hash htab_hash_pointer;
=== modified file 'libcpp/symtab.c'
--- libcpp/symtab.c 2011-08-09 02:39:45 +0000
+++ libcpp/symtab.c 2011-08-09 03:24:09 +0000
@@ -276,7 +276,7 @@ ht_load (hash_table *ht, hashnode *entri
void
ht_dump_statistics (hash_table *table)
{
- size_t nelts, nids, overhead, headers;
+ size_t nelts, nids, obmem, overhead, headers;
size_t total_bytes, longest, deleted = 0;
double sum_of_squares, exp_len, exp_len2, exp2_len;
hashnode *p, *limit;
@@ -307,34 +307,40 @@ ht_dump_statistics (hash_table *table)
while (++p < limit);
nelts = table->nelements;
- overhead = obstack_memory_used (&table->stack) - total_bytes;
+ obmem= obstack_memory_used (&table->stack);
+ overhead = obmem - total_bytes;
headers = table->nslots * sizeof (hashnode);
- fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
- (unsigned long) nelts);
- fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
+ fprintf (stderr, "\nlibcpp symtab string pool:\n");
+ fprintf (stderr, "\tidentifiers\t%lu (%.2f%%)\n",
(unsigned long) nids, nids * 100.0 / nelts);
- fprintf (stderr, "slots\t\t%lu\n",
- (unsigned long) table->nslots);
- fprintf (stderr, "deleted\t\t%lu\n",
+ fprintf (stderr, "\tentries\t\t%lu (%.2f%%)\n",
+ (unsigned long) nelts, nelts * 100.0 / table->nslots);
+ fprintf (stderr, "\tdeleted\t\t%lu\n",
(unsigned long) deleted);
- fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
+ fprintf (stderr, "\tslots\t\t%lu\n",
+ (unsigned long) table->nslots);
+ fprintf (stderr, "\tstring bytes\t%lu%c (%lu%c obstack_memory_used)\n",
SCALE (total_bytes), LABEL (total_bytes),
- SCALE (overhead), LABEL (overhead));
- fprintf (stderr, "table size\t%lu%c\n",
+ SCALE (obmem), LABEL (obmem));
+ fprintf (stderr, "\ttable size\t%lu%c\n",
SCALE (headers), LABEL (headers));
exp_len = (double)total_bytes / (double)nelts;
exp2_len = exp_len * exp_len;
exp_len2 = (double) sum_of_squares / (double) nelts;
- fprintf (stderr, "coll/search\t%.4f\n",
+ fprintf (stderr, "\tsearches\t%lu\n",
+ (unsigned long) table->searches);
+ fprintf (stderr, "\tcollisions\t%lu\n",
+ (unsigned long) table->collisions);
+ fprintf (stderr, "\tcoll/search\t%.4f\n",
(double) table->collisions / (double) table->searches);
- fprintf (stderr, "ins/search\t%.4f\n",
+ fprintf (stderr, "\tins/search\t%.4f\n",
(double) nelts / (double) table->searches);
- fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
+ fprintf (stderr, "\tavg. entry\t%.2f bytes (+/- %.2f)\n",
exp_len, approx_sqrt (exp_len2 - exp2_len));
- fprintf (stderr, "longest entry\t%lu\n",
+ fprintf (stderr, "\tlongest entry\t%lu\n",
(unsigned long) longest);
#undef SCALE
#undef LABEL
=== modified file 'libiberty/hashtab.c'
--- libiberty/hashtab.c 2011-08-09 02:39:45 +0000
+++ libiberty/hashtab.c 2011-08-09 03:24:09 +0000
@@ -58,6 +58,7 @@ Boston, MA 02110-1301, USA. */
#endif
#include <stdio.h>
+#include <assert.h>
#include "libiberty.h"
#include "ansidecl.h"
@@ -813,6 +814,90 @@ htab_collisions (htab_t htab)
return (double) htab->collisions / (double) htab->searches;
}
+/* Return the number of collisions */
+
+unsigned int
+htab_collisions_num (htab_t htab)
+{
+ return htab->collisions;
+}
+
+/* Return the number of searches */
+
+unsigned int
+htab_searches_num (htab_t htab)
+{
+ return htab->searches;
+}
+
+/* Dump allocation statistics to stderr. If elem_size > 0 display total memory
+ * usage of hash table too. */
+
+void
+htab_dump_statistics (htab_t table, size_t elem_size)
+{
+ size_t n_valid, headers, contents, empties, deleted;
+ void **p, **limit;
+
+#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
+ ? (x) \
+ : ((x) < 1024*1024*10 \
+ ? (x) / 1024 \
+ : (x) / (1024*1024))))
+#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
+
+ deleted = n_valid = empties = 0;
+ p = table->entries;
+ limit = p + table->size;
+ do
+ if (*p == HTAB_DELETED_ENTRY)
+ ++deleted;
+ else if (*p == HTAB_EMPTY_ENTRY)
+ ++empties;
+ else
+ ++n_valid;
+ while (++p < limit);
+
+ assert (deleted == table->n_deleted);
+ assert (empties == table->size - table->n_elements);
+ assert (n_valid + deleted == table->n_elements);
+
+ headers = table->size * sizeof (*(table->entries));
+ contents = n_valid * elem_size;
+
+ fprintf (stderr, "\tslots\t\t%lu\n",
+ (unsigned long) table->size);
+ fprintf (stderr, "\tidentifiers\t%lu\n",
+ (unsigned long) n_valid);
+ fprintf (stderr, "\tentries\t\t%lu (%.2f%%)\n",
+ (unsigned long) table->n_elements,
+ table->n_elements * 100.0 / table->size);
+ fprintf (stderr, "\tdeleted\t\t%lu\n",
+ (unsigned long) table->n_deleted);
+ fprintf (stderr, "\tstruct htab\t%u B\n",
+ sizeof (*table));
+ fprintf (stderr, "\ttable size\t%lu %cB\n",
+ SCALE (headers), LABEL (headers));
+ if (elem_size > 0)
+ {
+ fprintf (stderr, "\telement\t\t%lu B\n",
+ (unsigned long) elem_size);
+ fprintf (stderr, "\ttotal contents\t%lu %cB\n",
+ SCALE (contents), LABEL (contents));
+ }
+
+ fprintf (stderr, "\tsearches\t%lu\n",
+ (unsigned long) table->searches);
+ fprintf (stderr, "\tcollisions\t%lu\n",
+ (unsigned long) table->collisions);
+ fprintf (stderr, "\tcoll/search\t%.4f\n",
+ (double) table->collisions / (double) table->searches);
+
+#undef SCALE
+#undef LABEL
+}
+
+
/* Hash P as a null-terminated string.
Copied from gcc/hashtable.c. Zack had the following to say with respect
