Hi, I've updated this patch to trunk and rebootstrapped it, so I'm
resubmitting it, I'm also making a try to CC all relevant maintainers,
sorry for spamming but even though this patch is simple, it touches many
parts.
I'm also adding stats to pointer_{set,map} but it will come in a separate
patch. The notes quoted from earlier mail still apply:
On Sun, 8 Jul 2012, Dimitrios Apostolou wrote:
Hi,
This patch adds many nice stats about hash tables when gcc is run with
-fmem-report. Attached patch tested on x86, no regressions.
Also attached is sample output of -fmem-report when compiling reload.c with
-O2 -g. Especially interesting is the extreme htab usage in var-tracking
(ofcourse we already knew that... :-) and maybe symtab's slightly high
collision rate (given it's a very hot hash table). Moreover it's notable that
since last year, collision rate for mem_attrs_htab has been reduced from
around 8 to 1, still not good enough but major improvement.
Jan: It has negligible overhead in runtime, that's why I'm pushing it again
as it is. Having compile-time instrumentation is something different, but
still I'm not quite sure if it's worth the effort. IMHO doing separate builds
to get memory info is tedious and even I've stopped doing them. If it has no
overhead maybe it's better as a runtime option?
Any way, compile-time instrumentation can come later.
Finally I repost some of my notes I'd like to get feedback on:
* Is it OK that I included <assert.h> in libiberty's hashtab.c? What's the
proper way to assert stuff, since gcc_assert() is not accessible?
* Many hash tables are created with htab_create_ggc(), for example
referenced_vars and default_defs in tree-ssa.c. I collect statistics in
delete_tree_ssa() but maybe some are not deallocated in there but
automatically garbage collected?
* Obviously hash table sizes are inflated where two entries might reference
the same element (for example in symtab_hash) but I don't handle this.
* Changes that reduce load factor have been backed out since they brought
controversy. I still think they are good, at least for symtab. I'll measure
numbers separately for this after this patch makes it.
Thanks,
Dimitris
=== modified file 'gcc/Makefile.in'
--- gcc/Makefile.in 2012-07-26 13:10:04 +0000
+++ gcc/Makefile.in 2012-08-03 14:37:47 +0000
@@ -2679,7 +2679,7 @@ toplev.o : toplev.c $(CONFIG_H) $(SYSTEM
langhooks.h insn-flags.h $(CFGLOOP_H) hosthooks.h \
$(CGRAPH_H) $(COVERAGE_H) alloc-pool.h $(GGC_H) \
$(OPTS_H) params.def tree-mudflap.h $(TREE_PASS_H) $(GIMPLE_H) \
- tree-ssa-alias.h $(PLUGIN_H) realmpfr.h tree-diagnostic.h \
+ tree-ssa-alias.h $(PLUGIN_H) cselib.h realmpfr.h tree-diagnostic.h \
$(TREE_PRETTY_PRINT_H) opts-diagnostic.h $(COMMON_TARGET_H)
hwint.o : hwint.c $(CONFIG_H) $(SYSTEM_H) $(DIAGNOSTIC_CORE_H)
=== modified file 'gcc/cgraph.c'
--- gcc/cgraph.c 2012-07-16 11:32:42 +0000
+++ gcc/cgraph.c 2012-08-03 14:37:47 +0000
@@ -1066,6 +1066,13 @@ cgraph_update_edges_for_call_stmt (gimpl
}
+/* Keep statistics about call_site_hash hash tables. */
+static unsigned int call_site_hash_num;
+static unsigned long call_site_hash_expands;
+static unsigned long call_site_hash_searches;
+static unsigned long call_site_hash_collisions;
+
+
/* Remove all callees from the node. */
void
@@ -1096,6 +1103,16 @@ cgraph_node_remove_callees (struct cgrap
node->callees = NULL;
if (node->call_site_hash)
{
+ if (mem_report)
+ {
+ call_site_hash_num++;
+ call_site_hash_expands +=
+ htab_expands_num (node->call_site_hash);
+ call_site_hash_searches +=
+ htab_searches_num (node->call_site_hash);
+ call_site_hash_collisions +=
+ htab_collisions_num (node->call_site_hash);
+ }
htab_delete (node->call_site_hash);
node->call_site_hash = NULL;
}
@@ -1252,6 +1269,16 @@ cgraph_remove_node (struct cgraph_node *
node->symbol.decl = NULL;
if (node->call_site_hash)
{
+ if (mem_report)
+ {
+ call_site_hash_num++;
+ call_site_hash_expands +=
+ htab_expands_num (node->call_site_hash);
+ call_site_hash_searches +=
+ htab_searches_num (node->call_site_hash);
+ call_site_hash_collisions +=
+ htab_collisions_num (node->call_site_hash);
+ }
htab_delete (node->call_site_hash);
node->call_site_hash = NULL;
}
@@ -2457,4 +2484,18 @@ verify_cgraph (void)
FOR_EACH_FUNCTION (node)
verify_cgraph_node (node);
}
+
+void
+cgraph_dump_stats (void)
+{
+ fprintf (stderr, "\ncgraph.c hash table stats:\n");
+ fprintf (stderr, "\t%u cgraph_node->call_site_hash hash tables:\n",
+ call_site_hash_num);
+ fprintf (stderr, "\t\ttotal expansions\t%lu\n", call_site_hash_expands);
+ fprintf (stderr, "\t\ttotal searches\t\t%lu\n", call_site_hash_searches);
+ fprintf (stderr, "\t\ttotal collisions\t%lu\n", call_site_hash_collisions);
+ fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",
+ (float) call_site_hash_collisions / call_site_hash_searches);
+}
+
#include "gt-cgraph.h"
=== modified file 'gcc/cgraph.h'
--- gcc/cgraph.h 2012-06-26 10:15:18 +0000
+++ gcc/cgraph.h 2012-08-03 14:36:06 +0000
@@ -492,6 +492,7 @@ void verify_symtab_node (symtab_node);
bool verify_symtab_base (symtab_node);
bool symtab_used_from_object_file_p (symtab_node);
void symtab_make_decl_local (tree);
+void symtab_dump_stats (void);
/* In cgraph.c */
void dump_cgraph (FILE *);
@@ -586,6 +587,7 @@ struct cgraph_2node_hook_list *cgraph_ad
void cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *);
gimple cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *);
bool cgraph_propagate_frequency (struct cgraph_node *node);
+void cgraph_dump_stats (void);
/* In cgraphunit.c */
struct asm_node *add_asm_node (tree);
=== modified file 'gcc/cselib.c'
--- gcc/cselib.c 2012-07-16 11:32:42 +0000
+++ gcc/cselib.c 2012-08-03 14:37:47 +0000
@@ -2692,6 +2692,11 @@ cselib_init (int record_what)
next_uid = 1;
}
+static unsigned int cselib_htab_num;
+static unsigned long cselib_htab_expands;
+static unsigned long cselib_htab_searches;
+static unsigned long cselib_htab_collisions;
+
/* Called when the current user is done with cselib. */
void
@@ -2706,6 +2711,13 @@ 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_expands += htab_expands_num (cselib_hash_table);
+ 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);
@@ -2808,4 +2820,18 @@ 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 expansions\t%lu\n", cselib_htab_expands);
+ 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 2012-03-01 16:58:11 +0000
+++ gcc/cselib.h 2012-08-03 14:36:06 +0000
@@ -101,6 +101,7 @@ extern void cselib_add_permanent_equiv (
extern bool cselib_have_permanent_equivalences (void);
extern void dump_cselib_table (FILE *);
+extern void cselib_dump_stats (void);
/* Return the canonical value for VAL, following the equivalence chain
towards the earliest (== lowest uid) equivalent value. */
=== modified file 'gcc/dwarf2out.c'
--- gcc/dwarf2out.c 2012-07-24 17:31:01 +0000
+++ gcc/dwarf2out.c 2012-08-03 14:37:47 +0000
@@ -22223,6 +22223,13 @@ dwarf2out_finish (const char *filename)
add_comp_dir_attribute (comp_unit_die ());
}
+ if (mem_report)
+ {
+ fprintf(stderr, "\ndwarf2out.c: file_table hash table statistics:\n");
+ htab_dump_statistics(file_table, sizeof (struct dwarf_file_data));
+ }
+
+
for (i = 0; i < VEC_length (deferred_locations, deferred_locations_list);
i++)
{
add_location_or_const_value_attribute (
=== modified file 'gcc/emit-rtl.c'
--- gcc/emit-rtl.c 2012-07-30 02:30:52 +0000
+++ gcc/emit-rtl.c 2012-08-03 14:37:47 +0000
@@ -5486,6 +5486,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 2012-06-20 01:05:25 +0000
+++ gcc/emit-rtl.h 2012-08-03 14:36:06 +0000
@@ -68,6 +68,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);
extern bool need_atomic_barrier_p (enum memmodel, bool);
=== modified file 'gcc/rtl.h'
--- gcc/rtl.h 2012-07-24 18:28:15 +0000
+++ gcc/rtl.h 2012-08-03 14:37:47 +0000
@@ -2609,6 +2609,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/symtab.c'
--- gcc/symtab.c 2012-05-23 09:23:40 +0000
+++ gcc/symtab.c 2012-08-03 14:36:06 +0000
@@ -750,4 +750,20 @@ symtab_make_decl_local (tree decl)
SYMBOL_REF_WEAK (symbol) = DECL_WEAK (decl);
}
+
+void symtab_dump_stats (void)
+{
+ fprintf (stderr, "\nsymtab.c:symtab_hash hash table stats:\n");
+ if (symtab_hash != NULL)
+ htab_dump_statistics (symtab_hash, sizeof (union symtab_node_def));
+ else
+ fprintf (stderr, "\tEmpty!\n\n");
+
+ fprintf (stderr, "\nsymtab.c:assembler_name_hash hash table stats:\n");
+ if (assembler_name_hash != NULL)
+ htab_dump_statistics (assembler_name_hash, sizeof (union symtab_node_def));
+ else
+ fprintf (stderr, "\tEmpty!\n\n");
+}
+
#include "gt-symtab.h"
=== modified file 'gcc/toplev.c'
--- gcc/toplev.c 2012-07-14 17:28:31 +0000
+++ gcc/toplev.c 2012-08-03 14:37:47 +0000
@@ -75,6 +75,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(DBX_DEBUGGING_INFO) || defined(XCOFF_DEBUGGING_INFO)
#include "dbxout.h"
@@ -1764,8 +1765,14 @@ dump_memory_report (bool final)
dump_line_table_statistics ();
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 ();
+ symtab_dump_stats();
dump_rtx_statistics ();
dump_alloc_pool_statistics ();
dump_bitmap_statistics ();
=== modified file 'gcc/tree-ssa.c'
--- gcc/tree-ssa.c 2012-07-20 12:56:41 +0000
+++ gcc/tree-ssa.c 2012-08-03 14:37:47 +0000
@@ -1100,6 +1100,12 @@ uid_ssaname_map_hash (const void *item)
return ((const_tree)item)->ssa_name.var->decl_minimal.uid;
}
+/* hash table statistics */
+
+static unsigned long referenced_vars_expands, default_defs_expands;
+static unsigned long referenced_vars_searches, default_defs_searches;
+static unsigned long referenced_vars_collisions, default_defs_collisions;
+static unsigned int referenced_vars_num, default_defs_num;
/* Initialize global DFA and SSA structures. */
@@ -1159,6 +1165,25 @@ delete_tree_ssa (void)
ggc_free (var_ann (var));
*DECL_VAR_ANN_PTR (var) = NULL;
}
+
+ if (mem_report)
+ {
+ referenced_vars_num++;
+ referenced_vars_expands +=
+ htab_expands_num (gimple_referenced_vars (cfun));
+ referenced_vars_searches +=
+ htab_searches_num (gimple_referenced_vars (cfun));
+ referenced_vars_collisions +=
+ htab_collisions_num (gimple_referenced_vars (cfun));
+ default_defs_num++;
+ default_defs_expands +=
+ htab_expands_num (cfun->gimple_df->default_defs);
+ default_defs_searches +=
+ htab_searches_num (cfun->gimple_df->default_defs);
+ default_defs_collisions +=
+ htab_collisions_num (cfun->gimple_df->default_defs);
+ }
+
htab_delete (gimple_referenced_vars (cfun));
cfun->gimple_df->referenced_vars = NULL;
@@ -1181,6 +1206,26 @@ delete_tree_ssa (void)
redirect_edge_var_map_destroy ();
}
+void
+tree_ssa_dump_stats (void)
+{
+ fprintf (stderr, "\ntree-ssa.c stats\n");
+
+ fprintf (stderr, "\t%u referenced_vars hash tables:\n", referenced_vars_num);
+ fprintf (stderr, "\t\ttotal expansions\t%lu\n", referenced_vars_expands);
+ fprintf (stderr, "\t\ttotal searches\t\t%lu\n", referenced_vars_searches);
+ fprintf (stderr, "\t\ttotal collisions\t%lu\n", referenced_vars_collisions);
+ fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",
+ (float) referenced_vars_collisions / referenced_vars_searches);
+
+ fprintf (stderr, "\t%u default_defs hash tables\n", default_defs_num);
+ fprintf (stderr, "\t\ttotal expansions\t%lu\n", default_defs_expands);
+ fprintf (stderr, "\t\ttotal searches\t\t%lu\n", default_defs_searches);
+ fprintf (stderr, "\t\ttotal collisions\t%lu\n", default_defs_collisions);
+ fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",
+ (float) default_defs_collisions / default_defs_searches);
+}
+
/* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
useless type conversion, otherwise return false.
=== modified file 'gcc/tree.c'
--- gcc/tree.c 2012-07-25 19:43:15 +0000
+++ gcc/tree.c 2012-08-03 14:48:41 +0000
@@ -6332,10 +6332,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
@@ -8703,10 +8701,11 @@ dump_tree_statistics (void)
else
fprintf (stderr, "(No per-node statistics)\n");
- print_type_hash_statistics ();
print_debug_expr_statistics ();
print_value_expr_statistics ();
lang_hooks.print_statistics ();
+ print_type_hash_statistics ();
+ tree_ssa_dump_stats ();
}
#define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
=== modified file 'gcc/tree.h'
--- gcc/tree.h 2012-07-25 19:43:15 +0000
+++ gcc/tree.h 2012-08-03 14:37:47 +0000
@@ -5871,6 +5871,7 @@ struct GTY(()) tree_vec_map {
/* In tree-ssa.c */
tree target_for_debug_bind (tree);
+void tree_ssa_dump_stats (void);
/* In tree-ssa-address.c. */
extern tree tree_mem_ref_addr (tree, tree);
=== modified file 'gcc/var-tracking.c'
--- gcc/var-tracking.c 2012-07-16 11:32:42 +0000
+++ gcc/var-tracking.c 2012-08-03 14:37:47 +0000
@@ -1581,6 +1581,11 @@ shared_hash_copy (shared_hash vars)
return vars;
}
+static unsigned long vars_htab_expands;
+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. */
@@ -1590,6 +1595,13 @@ shared_hash_destroy (shared_hash vars)
gcc_checking_assert (vars->refcount > 0);
if (--vars->refcount == 0)
{
+ if (mem_report)
+ {
+ vars_htab_num++;
+ vars_htab_expands += htab_expands_num (vars->htab);
+ 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);
}
@@ -9208,6 +9220,14 @@ emit_notes_in_bb (basic_block bb, datafl
}
}
+
+/* Keep stats for dropped_values hash table */
+static unsigned long dropval_htab_expands;
+static unsigned long dropval_htab_searches;
+static unsigned long dropval_htab_collisions;
+static unsigned int dropval_htab_num;
+
+
/* Emit notes for the whole function. */
static void
@@ -9259,7 +9279,16 @@ vt_emit_notes (void)
dataflow_set_destroy (&cur);
if (MAY_HAVE_DEBUG_INSNS)
- htab_delete (dropped_values);
+ {
+ if (mem_report)
+ {
+ dropval_htab_num++;
+ dropval_htab_expands += htab_expands_num (dropped_values);
+ dropval_htab_searches += htab_searches_num (dropped_values);
+ dropval_htab_collisions += htab_collisions_num (dropped_values);
+ }
+ htab_delete (dropped_values);
+ }
emit_notes = false;
}
@@ -9934,6 +9963,12 @@ vt_debug_insns_local (bool skipped ATTRI
delete_debug_insns ();
}
+/* Keep stats for changed_variables hash table */
+static unsigned long cv_htab_expands;
+static unsigned long cv_htab_searches;
+static unsigned long cv_htab_collisions;
+static unsigned int cv_htab_num;
+
/* Free the data structures needed for variable tracking. */
static void
@@ -9958,6 +9993,13 @@ vt_finalize (void)
}
free_aux_for_blocks ();
htab_delete (empty_shared_hash->htab);
+ if (mem_report)
+ {
+ cv_htab_num++;
+ cv_htab_expands += htab_expands_num (changed_variables);
+ 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);
@@ -9986,6 +10028,36 @@ 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 expansions\t%lu\n", vars_htab_expands);
+ 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 expansions\t%lu\n", cv_htab_expands);
+ 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 dropped_values hash tables\n", dropval_htab_num);
+ fprintf (stderr, "\t\ttotal expansions\t%lu\n", dropval_htab_expands);
+ fprintf (stderr, "\t\ttotal searches\t\t%lu\n", dropval_htab_searches);
+ fprintf (stderr, "\t\ttotal collisions\t%lu\n", dropval_htab_collisions);
+ fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",
+ (float) dropval_htab_collisions / dropval_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 2012-08-03 14:36:06 +0000
@@ -127,6 +127,9 @@ struct GTY(()) htab {
of collisions fixed for time of work with the hash table. */
unsigned int collisions;
+ /* Number of times we reallocated the table to change its capacity. */
+ unsigned int expands;
+
/* Pointers to allocate/free functions. */
htab_alloc alloc_f;
htab_free free_f;
@@ -187,6 +190,10 @@ 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);
+extern unsigned int htab_expands_num (htab_t);
/* A hash function for pointers. */
extern htab_hash htab_hash_pointer;
=== modified file 'libcpp/include/symtab.h'
--- libcpp/include/symtab.h 2011-01-03 20:52:22 +0000
+++ libcpp/include/symtab.h 2012-08-03 14:36:06 +0000
@@ -63,6 +63,7 @@ struct ht
struct cpp_reader *pfile;
/* Table usage statistics. */
+ unsigned int expands;
unsigned int searches;
unsigned int collisions;
=== modified file 'libcpp/symtab.c'
--- libcpp/symtab.c 2009-07-18 02:22:16 +0000
+++ libcpp/symtab.c 2012-08-03 14:36:06 +0000
@@ -219,6 +219,7 @@ ht_expand (hash_table *table)
table->entries_owned = true;
table->entries = nentries;
table->nslots = size;
+ table->expands++;
}
/* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
@@ -276,7 +277,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, headers;
size_t total_bytes, longest, deleted = 0;
double sum_of_squares, exp_len, exp_len2, exp2_len;
hashnode *p, *limit;
@@ -307,34 +308,41 @@ 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);
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%u\n",
+ 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, "\texpansions\t%u\n",
+ table->expands);
+ fprintf (stderr, "\tsearches\t%u\n",
+ table->searches);
+ fprintf (stderr, "\tcollisions\t%u\n",
+ 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-02-03 07:23:20 +0000
+++ libiberty/hashtab.c 2012-08-03 14:36:06 +0000
@@ -58,6 +58,7 @@ Boston, MA 02110-1301, USA. */
#endif
#include <stdio.h>
+#include <assert.h>
#include "libiberty.h"
#include "ansidecl.h"
@@ -563,6 +564,7 @@ htab_expand (htab_t htab)
htab->size_prime_index = nindex;
htab->n_elements -= htab->n_deleted;
htab->n_deleted = 0;
+ htab->expands++;
p = oentries;
do
@@ -812,6 +814,107 @@ htab_collisions (htab_t htab)
return (double) htab->collisions / (double) htab->searches;
}
+/* Return the number of expands */
+
+unsigned int
+htab_expands_num (htab_t htab)
+{
+ return htab->expands;
+}
+
+/* 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, total;
+ 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;
+ total = sizeof (*table) + headers + contents;
+
+ fprintf (stderr, "\tslots\t\t%lu\n",
+ (unsigned long) table->size);
+
+ fprintf (stderr, "\tused\t\t%lu (%.2f%%)\n",
+ (unsigned long) table->n_elements,
+ table->n_elements * 100.0 / table->size);
+ fprintf (stderr, "\t\tvalid\t\t%lu\n",
+ (unsigned long) n_valid);
+ fprintf (stderr, "\t\tdeleted\t\t%lu\n",
+ (unsigned long) table->n_deleted);
+
+ fprintf(stderr, "\ttotal size\t%lu %cB\n",
+ SCALE (total), LABEL (total));
+ fprintf (stderr, "\t\tstruct htab\t%lu\t B\n",
+ (unsigned long) sizeof (*table));
+ fprintf (stderr, "\t\ttable\t\t%lu\t%cB\n",
+ SCALE (headers), LABEL (headers));
+ if (elem_size > 0)
+ {
+ fprintf (stderr, "\t\tone element\t%lu\t B\n",
+ (unsigned long) elem_size);
+ fprintf (stderr, "\t\tall elements\t%lu\t%cB\n",
+ SCALE (contents), LABEL (contents));
+ }
+ else
+ fprintf (stderr, "\t\tactual contents not included\n");
+
+ fprintf (stderr, "\texpansions\t%u\n",
+ table->expands);
+ fprintf (stderr, "\tsearches\t%u\n",
+ table->searches);
+ fprintf (stderr, "\tcollisions\t%u\n",
+ 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
