* Dump stats about hottest hash tables when -fmem-report
@ 2011-08-09 8:07 Dimitrios Apostolou
2011-08-09 9:19 ` Dimitrios Apostolou
2011-08-09 13:56 ` Tom Tromey
0 siblings, 2 replies; 12+ messages in thread
From: Dimitrios Apostolou @ 2011-08-09 8:07 UTC (permalink / raw)
To: gcc-patches; +Cc: Steven Bosscher, Nicola Pero
[-- Attachment #1: Type: TEXT/PLAIN, Size: 4244 bytes --]
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 <jimis@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
[-- Attachment #2: Type: TEXT/plain, Size: 15556 bytes --]
=== 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 ();
}
\f
#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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-09 8:07 Dump stats about hottest hash tables when -fmem-report Dimitrios Apostolou
@ 2011-08-09 9:19 ` Dimitrios Apostolou
2011-08-09 13:56 ` Tom Tromey
1 sibling, 0 replies; 12+ messages in thread
From: Dimitrios Apostolou @ 2011-08-09 9:19 UTC (permalink / raw)
To: gcc-patches; +Cc: Steven Bosscher, Nicola Pero
[-- Attachment #1: Type: TEXT/PLAIN, Size: 228 bytes --]
I forgot to include the dwarf2out.c:file_table. Stats are printed when -g.
See attached patch. Additional Changelog:
* dwarf2out.c (dwarf2out_finish): Call htab_dump_statistics() if
-fmem-report.
Dimitris
[-- Attachment #2: Type: TEXT/plain, Size: 591 bytes --]
=== modified file 'gcc/dwarf2out.c'
--- gcc/dwarf2out.c 2011-06-06 17:46:00 +0000
+++ gcc/dwarf2out.c 2011-08-09 07:56:11 +0000
@@ -24820,6 +24820,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 (
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-09 8:07 Dump stats about hottest hash tables when -fmem-report Dimitrios Apostolou
2011-08-09 9:19 ` Dimitrios Apostolou
@ 2011-08-09 13:56 ` Tom Tromey
2011-08-09 14:22 ` Richard Guenther
1 sibling, 1 reply; 12+ messages in thread
From: Tom Tromey @ 2011-08-09 13:56 UTC (permalink / raw)
To: Dimitrios Apostolou; +Cc: gcc-patches, Steven Bosscher, Nicola Pero
>>>>> "Dimitrios" == Dimitrios Apostolou <jimis@gmx.net> writes:
Dimitrios> 2011-08-09 Dimitrios Apostolou <jimis@gmx.net>
[...]
Dimitrios> * symtab.c (ht_dump_statistics): Beautified stats output.
Make sure the ChangeLog entries go in the correct directories.
Dimitrios> + obmem= obstack_memory_used (&table->stack);
Missing a space before the "=".
The libcpp part is ok with this change.
Tom
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-09 13:56 ` Tom Tromey
@ 2011-08-09 14:22 ` Richard Guenther
2011-08-09 17:57 ` Tom Tromey
0 siblings, 1 reply; 12+ messages in thread
From: Richard Guenther @ 2011-08-09 14:22 UTC (permalink / raw)
To: Tom Tromey; +Cc: Dimitrios Apostolou, gcc-patches, Steven Bosscher, Nicola Pero
On Tue, Aug 9, 2011 at 3:18 PM, Tom Tromey <tromey@redhat.com> wrote:
>>>>>> "Dimitrios" == Dimitrios Apostolou <jimis@gmx.net> writes:
>
> Dimitrios> 2011-08-09 Dimitrios Apostolou <jimis@gmx.net>
> [...]
> Dimitrios> * symtab.c (ht_dump_statistics): Beautified stats output.
>
> Make sure the ChangeLog entries go in the correct directories.
>
> Dimitrios> + obmem= obstack_memory_used (&table->stack);
>
> Missing a space before the "=".
>
> The libcpp part is ok with this change.
Note that sparsely populated hashes come at the cost of increased
cache footprint. Not sure what is more important here though, memory
access or hash computation.
Richard.
> Tom
>
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-09 14:22 ` Richard Guenther
@ 2011-08-09 17:57 ` Tom Tromey
2011-08-10 4:58 ` Dimitrios Apostolou
0 siblings, 1 reply; 12+ messages in thread
From: Tom Tromey @ 2011-08-09 17:57 UTC (permalink / raw)
To: Richard Guenther
Cc: Dimitrios Apostolou, gcc-patches, Steven Bosscher, Nicola Pero
>>>>> "Richard" == Richard Guenther <richard.guenther@gmail.com> writes:
>> The libcpp part is ok with this change.
Richard> Note that sparsely populated hashes come at the cost of increased
Richard> cache footprint. Not sure what is more important here though, memory
Richard> access or hash computation.
I was only approving the change to the dumping.
I am undecided about making the hash tables more sparse.
Tom
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-09 17:57 ` Tom Tromey
@ 2011-08-10 4:58 ` Dimitrios Apostolou
2011-08-19 19:07 ` Tom Tromey
0 siblings, 1 reply; 12+ messages in thread
From: Dimitrios Apostolou @ 2011-08-10 4:58 UTC (permalink / raw)
To: Tom Tromey; +Cc: Richard Guenther, gcc-patches, Steven Bosscher, Nicola Pero
On Tue, 9 Aug 2011, Tom Tromey wrote:
>>>>>> "Richard" == Richard Guenther <richard.guenther@gmail.com> writes:
>
>>> The libcpp part is ok with this change.
>
> Richard> Note that sparsely populated hashes come at the cost of increased
> Richard> cache footprint. Not sure what is more important here though, memory
> Richard> access or hash computation.
>
> I was only approving the change to the dumping.
> I am undecided about making the hash tables more sparse.
Since my Core Quad processor has large caches and the i386 has small
pointer size, the few extra empty buckets impose small overhead, which as
it seems is minor in comparison to gains due to less rehashes.
Maybe that's not true on older or alternate equipment. I'd be very
interested to hear about runtime measurements on various equipment, please
let me know if you do any.
Thanks,
Dimitris
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-10 4:58 ` Dimitrios Apostolou
@ 2011-08-19 19:07 ` Tom Tromey
2011-08-19 19:35 ` Dimitrios Apostolou
2011-08-20 10:47 ` Richard Guenther
0 siblings, 2 replies; 12+ messages in thread
From: Tom Tromey @ 2011-08-19 19:07 UTC (permalink / raw)
To: Dimitrios Apostolou
Cc: Richard Guenther, gcc-patches, Steven Bosscher, Nicola Pero
>>>>> "Dimitrios" == Dimitrios Apostolou <jimis@gmx.net> writes:
Richard> Note that sparsely populated hashes come at the cost of increased
Richard> cache footprint. Not sure what is more important here though, memory
Richard> access or hash computation.
Tom> I was only approving the change to the dumping.
Tom> I am undecided about making the hash tables more sparse.
Dimitrios> Since my Core Quad processor has large caches and the i386
Dimitrios> has small pointer size, the few extra empty buckets impose
Dimitrios> small overhead, which as it seems is minor in comparison to
Dimitrios> gains due to less rehashes.
Dimitrios> Maybe that's not true on older or alternate equipment. I'd be
Dimitrios> very interested to hear about runtime measurements on various
Dimitrios> equipment, please let me know if you do any.
I think you are the most likely person to do this sort of testing.
You can use machines on the GCC compile farm for this.
Your patch to change the symbol table's load factor is fine technically.
I think the argument for putting it in is lacking; what I would like to
see is either some rationale explaining that the increased memory use is
not important, or some numbers showing that it still performs well on
more than a single machine. My reason for wanting this is just that,
historically, GCC has been very sensitive to increases in memory use.
Alternatively, comments from more active maintainers indicating that
they don't care about this would also help your case.
I can't approve or reject the libiberty change, just the libcpp one.
Tom
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-19 19:07 ` Tom Tromey
@ 2011-08-19 19:35 ` Dimitrios Apostolou
2011-08-20 10:47 ` Richard Guenther
1 sibling, 0 replies; 12+ messages in thread
From: Dimitrios Apostolou @ 2011-08-19 19:35 UTC (permalink / raw)
To: Tom Tromey; +Cc: Richard Guenther, gcc-patches, Steven Bosscher, Nicola Pero
On Fri, 19 Aug 2011, Tom Tromey wrote:
> I think you are the most likely person to do this sort of testing.
> You can use machines on the GCC compile farm for this.
>
> Your patch to change the symbol table's load factor is fine technically.
> I think the argument for putting it in is lacking; what I would like to
> see is either some rationale explaining that the increased memory use is
> not important, or some numbers showing that it still performs well on
> more than a single machine. My reason for wanting this is just that,
> historically, GCC has been very sensitive to increases in memory use.
> Alternatively, comments from more active maintainers indicating that
> they don't care about this would also help your case.
>
> I can't approve or reject the libiberty change, just the libcpp one.
Hi Tom, thanks for your comments. I'm well aware that I should test on
more equipment besides i386 and x86_64 and I certainly plan to. It's just
that writing patches is one thing, but advocating them on gcc-patches is
an equally hard thing, and I plan on doing the latter correctly after GSOC
ends.
As for the technical side of this patch, I've noticed that while in
general there is a good gain to be earned from reduced collisions, there
is an overhead in htab_traverse() and htab_delete() that iterate over the
array. This is evident primarily in var-tracking, which is more
htab-intensive than the rest of the compiler alltogether! So I plan to
resubmit my patch together with small changes in var-tracking.
Thanks,
Dimitris
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-19 19:07 ` Tom Tromey
2011-08-19 19:35 ` Dimitrios Apostolou
@ 2011-08-20 10:47 ` Richard Guenther
2011-08-22 9:58 ` Dimitrios Apostolou
1 sibling, 1 reply; 12+ messages in thread
From: Richard Guenther @ 2011-08-20 10:47 UTC (permalink / raw)
To: Tom Tromey; +Cc: Dimitrios Apostolou, gcc-patches, Steven Bosscher, Nicola Pero
On Fri, Aug 19, 2011 at 6:40 PM, Tom Tromey <tromey@redhat.com> wrote:
>>>>>> "Dimitrios" == Dimitrios Apostolou <jimis@gmx.net> writes:
>
> Richard> Note that sparsely populated hashes come at the cost of increased
> Richard> cache footprint. Not sure what is more important here though, memory
> Richard> access or hash computation.
>
> Tom> I was only approving the change to the dumping.
> Tom> I am undecided about making the hash tables more sparse.
>
> Dimitrios> Since my Core Quad processor has large caches and the i386
> Dimitrios> has small pointer size, the few extra empty buckets impose
> Dimitrios> small overhead, which as it seems is minor in comparison to
> Dimitrios> gains due to less rehashes.
>
> Dimitrios> Maybe that's not true on older or alternate equipment. I'd be
> Dimitrios> very interested to hear about runtime measurements on various
> Dimitrios> equipment, please let me know if you do any.
>
> I think you are the most likely person to do this sort of testing.
> You can use machines on the GCC compile farm for this.
>
> Your patch to change the symbol table's load factor is fine technically.
> I think the argument for putting it in is lacking; what I would like to
> see is either some rationale explaining that the increased memory use is
> not important, or some numbers showing that it still performs well on
> more than a single machine. My reason for wanting this is just that,
> historically, GCC has been very sensitive to increases in memory use.
> Alternatively, comments from more active maintainers indicating that
> they don't care about this would also help your case.
>
> I can't approve or reject the libiberty change, just the libcpp one.
Yes, memory usage is as important as compile-time. We still have testcases
that show a vast imbalance of them. I don't know if the symbol table hash
is ever the problem, but changing the generic load factor in libiberty doesn't
sound a good idea - maybe instead have a away of specifying that factor
per hashtable instance. Or, as usual, improve the hash function to
reduce the collision rate and/or to make re-hashing cheaper.
Richard.
> Tom
>
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-20 10:47 ` Richard Guenther
@ 2011-08-22 9:58 ` Dimitrios Apostolou
2011-08-22 12:36 ` Dimitrios Apostolou
0 siblings, 1 reply; 12+ messages in thread
From: Dimitrios Apostolou @ 2011-08-22 9:58 UTC (permalink / raw)
To: Richard Guenther
Cc: Tom Tromey, Dimitrios Apostolou, gcc-patches, Steven Bosscher,
Nicola Pero
[-- Attachment #1: Type: TEXT/PLAIN, Size: 6081 bytes --]
Hello,
I'm attaching here the final version of statistics dumping, I think I made
some stylistic/insignificant changes. Tested on i386 and x86_64. I have
withheld the hash table size changes, so please apply if you find
everything good.
Would you agree on a future patch that would make such statistics being
computed only when the gather-mem-stats compile-time variable is set?
On Sat, 20 Aug 2011, Richard Guenther wrote:
> On Fri, Aug 19, 2011 at 6:40 PM, Tom Tromey <tromey@redhat.com> wrote:
>>
>> Your patch to change the symbol table's load factor is fine technically.
>> I think the argument for putting it in is lacking; what I would like to
>> see is either some rationale explaining that the increased memory use is
>> not important, or some numbers showing that it still performs well on
>> more than a single machine. Â My reason for wanting this is just that,
>> historically, GCC has been very sensitive to increases in memory use.
>> Alternatively, comments from more active maintainers indicating that
>> they don't care about this would also help your case.
>>
>> I can't approve or reject the libiberty change, just the libcpp one.
>
> Yes, memory usage is as important as compile-time. We still have testcases
> that show a vast imbalance of them. I don't know if the symbol table hash
> is ever the problem, but changing the generic load factor in libiberty doesn't
> sound a good idea - maybe instead have a away of specifying that factor
> per hashtable instance. Or, as usual, improve the hash function to
> reduce the collision rate and/or to make re-hashing cheaper.
Regarding hash table size, I will back off from hashtab.c. I really
believe that even though it makes a difference the proper solution would
be a much more intrusive one: complete reimplementation.
If we primarily care about memory usage we should use a closed-addressing
(with linked-lists in each bucket) hash table, and set the load-factor
high. If we care about cache-efficiency and speed we should use an
open-addressing hash table, like the one we have, but decrease the
load-factor and resolve collisions by quadratic probing instead of
rehashing. Also we should make sure our hash table is always power-of-2
sized, and that hash values are always computed using good and proved hash
functions (we use Bob Jenkins v2 hash, we should upgrade to v3 even though
v2 seems very good *when* we actually do use it). That would probably mean
the interface should change to disallow custom hash values, and while we
do that I'd really like to see new functions dedicated to searching and
inserting.
I've experimented with some of these changes, but these changes
individually do not offer significant speed-up. I believe that change will
show if hash tables are completely reimplemented.
But regarding symtab.c, I only see benefits. Collisions are reduced and
extra memory usage is negligible. For a hash table with 32K elements and
64K slots, the overhead of empty slots is 32K*8 = 256KB. It it was 75%
full it would be 128KB. Actual measurements on i386 show negligible
overhead, it could be by luck that final ht size is the same (they are
always power-of-2 sized, so it's possible). Anyway I'll hopefully test in
other platforms within September and report back.
A change that would probably help for symtab would be to store custom
string structs, that include string length so we avoid several strlen()
calls. Another could be to not support deletion of strings (since what we
are actually doing is string interning, isn't it?). This would make the
open-addressing hash table much simpler, and I think there is only one
case we actually delete strings. Have to look further into this one.
All comments welcome,
Dimitris
Changelog:
2011-08-22 Dimitrios Apostolou <jimis@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,expands,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,expands,searches,collisions} if -fmem-report.
(vt_finalize): Keep statistics by increasing values of new global
variables cv_htab_{num,expands,searches,collisions} and
vc_htab_{num,expands,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.
* hashtab.c, hashtab.h: Added "expands" variable to htab_t type
for tracking total times the hash table was expanded.
* hashtab.c, hashtab.h (htab_dump_statistics, htab_collisions_num)
(htab_searches_num, htab_expands_num): New functions for statistics.
* hashtab.c: Included assert.h for checks in htab_dump_statistics.
* symtab.c, symtab.h: Added "expands" variable to hash_table type
for tracking total times the hash table was expanded.
* symtab.c (ht_dump_statistics): Beautified stats output.
* dwarf2out.c (dwarf2out_finish): Call htab_dump_statistics() if
-fmem-report.
* cgraph.h, varpool.c (varpool_dump_stats): New function to dump
stats about varpool_hash hash table.
* tree-ssa.c (delete_tree_ssa): Keep statistics for hash tables by
increasing the new referenced_vars_* and default_defs_* global
variables.
* tree.h, tree-ssa.c (tree_ssa_dump_stats): New function to print
statistics about all referenced_vars and default_defs hash tables.
* tree.c (dump_tree_statistics): Call tree_ssa_dump_stats().
* toplev.c: Included cselib.h for cselib_dump_stats().
(dump_memory_report): Call all the above functions to provide
better statistics.
[-- Attachment #2: Type: TEXT/PLAIN, Size: 21950 bytes --]
=== modified file 'gcc/cgraph.c'
--- gcc/cgraph.c 2011-06-06 17:12:25 +0000
+++ gcc/cgraph.c 2011-08-22 08:41:38 +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-22 08:41:38 +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;
@@ -659,6 +660,7 @@ struct varpool_node * varpool_extra_name
const char * varpool_node_name (struct varpool_node *node);
void varpool_reset_queue (void);
bool const_value_known_p (tree);
+void varpool_dump_stats (void);
/* Walk all reachable static variables. */
#define FOR_EACH_STATIC_VARIABLE(node) \
=== modified file 'gcc/cselib.c'
--- gcc/cselib.c 2011-05-31 19:14:21 +0000
+++ gcc/cselib.c 2011-08-22 08:41:38 +0000
@@ -2518,6 +2518,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
@@ -2531,6 +2536,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);
@@ -2630,4 +2642,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 2011-02-03 06:04:04 +0000
+++ gcc/cselib.h 2011-08-22 08:41:38 +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/dwarf2out.c'
--- gcc/dwarf2out.c 2011-06-06 17:46:00 +0000
+++ gcc/dwarf2out.c 2011-08-22 08:41:38 +0000
@@ -24820,6 +24820,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 2011-05-29 17:40:05 +0000
+++ gcc/emit-rtl.c 2011-08-22 08:41:38 +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-22 08:41:38 +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-22 08:41:38 +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-22 08:41:38 +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,14 @@ 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 ();
+ varpool_dump_stats ();
dump_rtx_statistics ();
dump_alloc_pool_statistics ();
dump_bitmap_statistics ();
=== modified file 'gcc/tree-ssa.c'
--- gcc/tree-ssa.c 2011-05-18 10:36:45 +0000
+++ gcc/tree-ssa.c 2011-08-22 08:41:38 +0000
@@ -1172,6 +1172,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. */
@@ -1208,6 +1214,25 @@ delete_tree_ssa (void)
*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;
@@ -1231,6 +1256,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 2011-06-07 14:37:39 +0000
+++ gcc/tree.c 2011-08-22 08:41:38 +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,11 @@ 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 ();
+ tree_ssa_dump_stats ();
}
\f
#define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
=== modified file 'gcc/tree.h'
--- gcc/tree.h 2011-06-07 14:37:39 +0000
+++ gcc/tree.h 2011-08-22 08:41:38 +0000
@@ -5698,6 +5698,7 @@ struct GTY(()) tree_priority_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 2011-06-03 01:42:31 +0000
+++ gcc/var-tracking.c 2011-08-22 08:41:38 +0000
@@ -1422,6 +1422,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. */
@@ -1431,6 +1436,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);
}
@@ -8982,6 +8994,11 @@ vt_debug_insns_local (bool skipped ATTRI
delete_debug_insns ();
}
+static unsigned long cv_htab_expands, vc_htab_expands;
+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 +9023,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);
@@ -9014,6 +9038,13 @@ vt_finalize (void)
if (MAY_HAVE_DEBUG_INSNS)
{
+ if (mem_report)
+ {
+ vc_htab_num++;
+ vc_htab_expands += htab_expands_num (value_chains);
+ 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 +9060,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 value_chains hash tables\n", vc_htab_num);
+ fprintf (stderr, "\t\ttotal expansions\t%lu\n", vc_htab_expands);
+ 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 'gcc/varpool.c'
--- gcc/varpool.c 2011-06-03 18:23:22 +0000
+++ gcc/varpool.c 2011-08-22 08:41:38 +0000
@@ -724,4 +724,11 @@ varpool_used_from_object_file_p (struct
return false;
}
+void
+varpool_dump_stats (void)
+{
+ fprintf (stderr, "\nvarpool.c:varpool_hash hash table stats:\n");
+ htab_dump_statistics (varpool_hash, sizeof (struct varpool_node));
+}
+
#include "gt-varpool.h"
=== modified file 'include/hashtab.h'
--- include/hashtab.h 2010-06-08 06:25:24 +0000
+++ include/hashtab.h 2011-08-22 08:41:38 +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 2011-08-22 08:41:38 +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 2011-08-09 02:39:45 +0000
+++ libcpp/symtab.c 2011-08-22 08:41:38 +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-08-09 02:39:45 +0000
+++ libiberty/hashtab.c 2011-08-22 08:41:38 +0000
@@ -58,6 +58,7 @@ Boston, MA 02110-1301, USA. */
#endif
#include <stdio.h>
+#include <assert.h>
#include "libiberty.h"
#include "ansidecl.h"
@@ -564,6 +565,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
@@ -813,6 +815,99 @@ 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;
+ 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%lu B\n",
+ (unsigned long) 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, "\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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-22 9:58 ` Dimitrios Apostolou
@ 2011-08-22 12:36 ` Dimitrios Apostolou
2011-08-22 13:18 ` Richard Guenther
0 siblings, 1 reply; 12+ messages in thread
From: Dimitrios Apostolou @ 2011-08-22 12:36 UTC (permalink / raw)
To: Dimitrios Apostolou
Cc: Richard Guenther, Tom Tromey, gcc-patches, Steven Bosscher, Nicola Pero
I should note here that specialised hash-tables in pointer-set.c have a
load-factor of at most 25%. Also another very fast hash table I've
studied, dense_hash_map from google's sparse_hash_table, has a load factor
of 50% max.
As I understand it a good hash function gives a perfectly random value up
to N. So if we have only 25% of slots empty, like we do with today's 75%
load factor, chances we won't have collision are small. And collisions
cost more for an open-addressing hash table.
But for implementing a closed-addressing hash-table with linked lists for
collision resolution, we'd need allocator pools within libiberty. Is it
OK to move alloc-pool.[ch] into libiberty as a first step?
Dimitris
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Dump stats about hottest hash tables when -fmem-report
2011-08-22 12:36 ` Dimitrios Apostolou
@ 2011-08-22 13:18 ` Richard Guenther
0 siblings, 0 replies; 12+ messages in thread
From: Richard Guenther @ 2011-08-22 13:18 UTC (permalink / raw)
To: Dimitrios Apostolou; +Cc: Tom Tromey, gcc-patches, Steven Bosscher, Nicola Pero
On Mon, Aug 22, 2011 at 1:37 PM, Dimitrios Apostolou <jimis@gmx.net> wrote:
> I should note here that specialised hash-tables in pointer-set.c have a
> load-factor of at most 25%. Also another very fast hash table I've studied,
> dense_hash_map from google's sparse_hash_table, has a load factor of 50%
> max.
>
> As I understand it a good hash function gives a perfectly random value up to
> N. So if we have only 25% of slots empty, like we do with today's 75% load
> factor, chances we won't have collision are small. And collisions cost more
> for an open-addressing hash table.
>
> But for implementing a closed-addressing hash-table with linked lists for
> collision resolution, we'd need allocator pools within libiberty. Is it OK
> to move alloc-pool.[ch] into libiberty as a first step?
Well, what would be the constant overhead for a closed-addressing hash
if it is empty and per element (per collision)? Decreasing the load factor
might be a better choice ...
Richard.
>
> Dimitris
>
>
>
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2011-08-22 11:57 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-08-09 8:07 Dump stats about hottest hash tables when -fmem-report Dimitrios Apostolou
2011-08-09 9:19 ` Dimitrios Apostolou
2011-08-09 13:56 ` Tom Tromey
2011-08-09 14:22 ` Richard Guenther
2011-08-09 17:57 ` Tom Tromey
2011-08-10 4:58 ` Dimitrios Apostolou
2011-08-19 19:07 ` Tom Tromey
2011-08-19 19:35 ` Dimitrios Apostolou
2011-08-20 10:47 ` Richard Guenther
2011-08-22 9:58 ` Dimitrios Apostolou
2011-08-22 12:36 ` Dimitrios Apostolou
2011-08-22 13:18 ` Richard Guenther
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).