| Message ID | 20110529143135.GC3577@kam.mff.cuni.cz |
|---|---|
| State | New |
| Headers | show |
On Sun, May 29, 2011 at 4:31 PM, Jan Hubicka <hubicka@ucw.cz> wrote: > Hi, > string straming is quite wasteful by creating a copy of every string it gets, > looking it up in hashtable, freeing if it is present and adding otherwise. The > copy is made just to add 0 value to terminate it since htab_hash_string is used > and it expects 0 terminated strings that is not always the case here. > > Additionally we end up copying every string we stream twice (once for hash, > once for output buffer) and because all the strings are persistently stored in > memory anyway, we end up with every string sitting in memory three times. > > This patch avoids early copying by inlining string hashing that takes length > parameter; avoids copying of the string when the string is known to stay in > memory during whole output block duration (that is always the case for all > strings we handle at the moment). > > I also added obstack into output block for allocating objects that needs to be > freed at the time OB is destructed that is the case of string copies and the > datastructure used to hold hashtable entries. > > This also makes me to wonder why output streams are not obstacks, they seems > to be fitting the purpose quite well here and are better optimized than our > implementation. Good question ... > > Bootstrapped/regtested x86_64-linux, OK? > Honza > > * lto-streamer-out.c (hash_string_slot_node): Hash string based on its > length. > (string_slot_free): Remove > (create_output_block): Initialize obstack. > (destroy_output_block): Free obstack. > (lto_string_index): Add PERSISTENT parameter; do not duplicate > the string unless it needs to be added into the hash. > (lto_output_string_with_length): Add persistent attribute; > handle NULL strings. > (lto_output_string): Add PERSISTENT parameter. > (output_string_cst, output_identifier): Simplify. > (lto_output_location_bitpack): Update. > (lto_output_builtin_tree): Update. > * lto-streamer.h (struct output_block): Add obstack. > (lto_output_string, lto_output_string_with_length): Remove declarations; > functions are static now. > > Index: lto-streamer-out.c > =================================================================== > --- lto-streamer-out.c (revision 174377) > +++ lto-streamer-out.c (working copy) > @@ -51,13 +51,19 @@ struct string_slot > }; > > > -/* Returns a hash code for P. */ > +/* Returns a hash code for P. > + Shamelessly*/ ... stolen from libiberty. ? Ok with that comment adjusted. Thanks, Richard. > > static hashval_t > hash_string_slot_node (const void *p) > { > const struct string_slot *ds = (const struct string_slot *) p; > - return (hashval_t) htab_hash_string (ds->s); > + hashval_t r = ds->len; > + int i; > + > + for (i = 0; i < ds->len; i++) > + r = r * 67 + (unsigned)ds->s[i] - 113; > + return r; > } > > > @@ -76,17 +82,6 @@ eq_string_slot_node (const void *p1, con > } > > > -/* Free the string slot pointed-to by P. */ > - > -static void > -string_slot_free (void *p) > -{ > - struct string_slot *slot = (struct string_slot *) p; > - free (CONST_CAST (void *, (const void *) slot->s)); > - free (slot); > -} > - > - > /* Clear the line info stored in DATA_IN. */ > > static void > @@ -118,7 +113,8 @@ create_output_block (enum lto_section_ty > clear_line_info (ob); > > ob->string_hash_table = htab_create (37, hash_string_slot_node, > - eq_string_slot_node, string_slot_free); > + eq_string_slot_node, NULL); > + gcc_obstack_init (&ob->obstack); > > return ob; > } > @@ -139,26 +135,27 @@ destroy_output_block (struct output_bloc > free (ob->cfg_stream); > > lto_streamer_cache_delete (ob->writer_cache); > + obstack_free (&ob->obstack, NULL); > > free (ob); > } > > /* Return index used to reference STRING of LEN characters in the string table > in OB. The string might or might not include a trailing '\0'. > - Then put the index onto the INDEX_STREAM. */ > + Then put the index onto the INDEX_STREAM. > + When PERSISTENT is set, the string S is supposed to not change during > + duration of the OB and thus OB can keep pointer into it. */ > > static unsigned > lto_string_index (struct output_block *ob, > const char *s, > - unsigned int len) > + unsigned int len, > + bool persistent) > { > struct string_slot **slot; > struct string_slot s_slot; > - char *string = (char *) xmalloc (len + 1); > - memcpy (string, s, len); > - string[len] = '\0'; > > - s_slot.s = string; > + s_slot.s = s; > s_slot.len = len; > s_slot.slot_num = 0; > > @@ -169,7 +166,17 @@ lto_string_index (struct output_block *o > struct lto_output_stream *string_stream = ob->string_stream; > unsigned int start = string_stream->total_size; > struct string_slot *new_slot > - = (struct string_slot *) xmalloc (sizeof (struct string_slot)); > + = XOBNEW (&ob->obstack, struct string_slot); > + const char *string; > + > + if (!persistent) > + { > + char *tmp; > + string = tmp = XOBNEWVEC (&ob->obstack, char, len); > + memcpy (tmp, s, len); > + } > + else > + string = s; > > new_slot->s = string; > new_slot->len = len; > @@ -182,7 +189,6 @@ lto_string_index (struct output_block *o > else > { > struct string_slot *old_slot = *slot; > - free (string); > return old_slot->slot_num + 1; > } > } > @@ -190,29 +196,39 @@ lto_string_index (struct output_block *o > > /* Output STRING of LEN characters to the string > table in OB. The string might or might not include a trailing '\0'. > - Then put the index onto the INDEX_STREAM. */ > + Then put the index onto the INDEX_STREAM. > + When PERSISTENT is set, the string S is supposed to not change during > + duration of the OB and thus OB can keep pointer into it. */ > > -void > +static void > lto_output_string_with_length (struct output_block *ob, > struct lto_output_stream *index_stream, > const char *s, > - unsigned int len) > + unsigned int len, > + bool persistent) > { > - lto_output_uleb128_stream (index_stream, > - lto_string_index (ob, s, len)); > + if (s) > + lto_output_uleb128_stream (index_stream, > + lto_string_index (ob, s, len, persistent)); > + else > + lto_output_1_stream (index_stream, 0); > } > > /* Output the '\0' terminated STRING to the string > - table in OB. Then put the index onto the INDEX_STREAM. */ > + table in OB. Then put the index onto the INDEX_STREAM. > + When PERSISTENT is set, the string S is supposed to not change during > + duration of the OB and thus OB can keep pointer into it. */ > > -void > +static void > lto_output_string (struct output_block *ob, > struct lto_output_stream *index_stream, > - const char *string) > + const char *string, > + bool persistent) > { > if (string) > lto_output_string_with_length (ob, index_stream, string, > - strlen (string) + 1); > + strlen (string) + 1, > + persistent); > else > lto_output_1_stream (index_stream, 0); > } > @@ -226,12 +242,10 @@ output_string_cst (struct output_block * > struct lto_output_stream *index_stream, > tree string) > { > - if (string) > - lto_output_string_with_length (ob, index_stream, > - TREE_STRING_POINTER (string), > - TREE_STRING_LENGTH (string )); > - else > - lto_output_1_stream (index_stream, 0); > + lto_output_string_with_length (ob, index_stream, > + TREE_STRING_POINTER (string), > + TREE_STRING_LENGTH (string), > + true); > } > > > @@ -243,12 +257,10 @@ output_identifier (struct output_block * > struct lto_output_stream *index_stream, > tree id) > { > - if (id) > - lto_output_string_with_length (ob, index_stream, > - IDENTIFIER_POINTER (id), > - IDENTIFIER_LENGTH (id)); > - else > - lto_output_1_stream (index_stream, 0); > + lto_output_string_with_length (ob, index_stream, > + IDENTIFIER_POINTER (id), > + IDENTIFIER_LENGTH (id), > + true); > } > > > @@ -618,8 +630,9 @@ lto_output_location_bitpack (struct bitp > bp_pack_value (bp, ob->current_file != xloc.file, 1); > if (ob->current_file != xloc.file) > bp_pack_var_len_unsigned (bp, lto_string_index (ob, > - xloc.file, > - strlen (xloc.file) + 1)); > + xloc.file, > + strlen (xloc.file) + 1, > + true)); > ob->current_file = xloc.file; > > bp_pack_value (bp, ob->current_line != xloc.line, 1); > @@ -1184,7 +1197,8 @@ static void > lto_output_ts_translation_unit_decl_tree_pointers (struct output_block *ob, > tree expr) > { > - lto_output_string (ob, ob->main_stream, TRANSLATION_UNIT_LANGUAGE (expr)); > + lto_output_string (ob, ob->main_stream, > + TRANSLATION_UNIT_LANGUAGE (expr), true); > } > > /* Helper for lto_output_tree. Write all pointer fields in EXPR to output > @@ -1350,12 +1364,12 @@ lto_output_builtin_tree (struct output_b > reader side from adding a second '*', we omit it here. */ > const char *str = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (expr)); > if (strlen (str) > 1 && str[0] == '*') > - lto_output_string (ob, ob->main_stream, &str[1]); > + lto_output_string (ob, ob->main_stream, &str[1], true); > else > - lto_output_string (ob, ob->main_stream, NULL); > + lto_output_string (ob, ob->main_stream, NULL, true); > } > else > - lto_output_string (ob, ob->main_stream, NULL); > + lto_output_string (ob, ob->main_stream, NULL, true); > } > > > @@ -1768,7 +1782,7 @@ output_gimple_stmt (struct output_block > lto_output_uleb128_stream (ob->main_stream, gimple_asm_noutputs (stmt)); > lto_output_uleb128_stream (ob->main_stream, gimple_asm_nclobbers (stmt)); > lto_output_uleb128_stream (ob->main_stream, gimple_asm_nlabels (stmt)); > - lto_output_string (ob, ob->main_stream, gimple_asm_string (stmt)); > + lto_output_string (ob, ob->main_stream, gimple_asm_string (stmt), true); > /* Fallthru */ > > case GIMPLE_ASSIGN: > Index: lto-streamer.h > =================================================================== > --- lto-streamer.h (revision 174377) > +++ lto-streamer.h (working copy) > @@ -700,6 +700,10 @@ struct output_block > > /* Cache of nodes written in this section. */ > struct lto_streamer_cache_d *writer_cache; > + > + /* All data persistent across whole duration of output block > + can go here. */ > + struct obstack obstack; > }; > > > @@ -873,13 +877,6 @@ extern struct output_block *create_outpu > extern void destroy_output_block (struct output_block *); > extern void lto_output_tree (struct output_block *, tree, bool); > extern void produce_asm (struct output_block *ob, tree fn); > -extern void lto_output_string (struct output_block *, > - struct lto_output_stream *, > - const char *); > -extern void lto_output_string_with_length (struct output_block *, > - struct lto_output_stream *, > - const char *, > - unsigned int); > void lto_output_decl_state_streams (struct output_block *, > struct lto_out_decl_state *); > void lto_output_decl_state_refs (struct output_block *, >
On 05/29/2011 06:14 PM, Richard Guenther wrote: >> > >> > -/* Returns a hash code for P. */ >> > +/* Returns a hash code for P. >> > + Shamelessly*/ > ... stolen from libiberty. > > ? > > Ok with that comment adjusted. Why steal it :) if you can instead add the code to libiberty? Paolo
> On 05/29/2011 06:14 PM, Richard Guenther wrote: >>> > >>> > -/* Returns a hash code for P. */ >>> > +/* Returns a hash code for P. >>> > + Shamelessly*/ >> ... stolen from libiberty. >> >> ? >> >> Ok with that comment adjusted. > > Why steal it :) if you can instead add the code to libiberty? Well, it is 3 lines of code so it seemed easier to steal it ;) You won't be able to use it directly anyway since you need wrapping structure around the string since libiberty hashtable won't let you store strings and sizes directly into it. Honza
Index: lto-streamer-out.c =================================================================== --- lto-streamer-out.c (revision 174377) +++ lto-streamer-out.c (working copy) @@ -51,13 +51,19 @@ struct string_slot }; -/* Returns a hash code for P. */ +/* Returns a hash code for P. + Shamelessly*/ static hashval_t hash_string_slot_node (const void *p) { const struct string_slot *ds = (const struct string_slot *) p; - return (hashval_t) htab_hash_string (ds->s); + hashval_t r = ds->len; + int i; + + for (i = 0; i < ds->len; i++) + r = r * 67 + (unsigned)ds->s[i] - 113; + return r; } @@ -76,17 +82,6 @@ eq_string_slot_node (const void *p1, con } -/* Free the string slot pointed-to by P. */ - -static void -string_slot_free (void *p) -{ - struct string_slot *slot = (struct string_slot *) p; - free (CONST_CAST (void *, (const void *) slot->s)); - free (slot); -} - - /* Clear the line info stored in DATA_IN. */ static void @@ -118,7 +113,8 @@ create_output_block (enum lto_section_ty clear_line_info (ob); ob->string_hash_table = htab_create (37, hash_string_slot_node, - eq_string_slot_node, string_slot_free); + eq_string_slot_node, NULL); + gcc_obstack_init (&ob->obstack); return ob; } @@ -139,26 +135,27 @@ destroy_output_block (struct output_bloc free (ob->cfg_stream); lto_streamer_cache_delete (ob->writer_cache); + obstack_free (&ob->obstack, NULL); free (ob); } /* Return index used to reference STRING of LEN characters in the string table in OB. The string might or might not include a trailing '\0'. - Then put the index onto the INDEX_STREAM. */ + Then put the index onto the INDEX_STREAM. + When PERSISTENT is set, the string S is supposed to not change during + duration of the OB and thus OB can keep pointer into it. */ static unsigned lto_string_index (struct output_block *ob, const char *s, - unsigned int len) + unsigned int len, + bool persistent) { struct string_slot **slot; struct string_slot s_slot; - char *string = (char *) xmalloc (len + 1); - memcpy (string, s, len); - string[len] = '\0'; - s_slot.s = string; + s_slot.s = s; s_slot.len = len; s_slot.slot_num = 0; @@ -169,7 +166,17 @@ lto_string_index (struct output_block *o struct lto_output_stream *string_stream = ob->string_stream; unsigned int start = string_stream->total_size; struct string_slot *new_slot - = (struct string_slot *) xmalloc (sizeof (struct string_slot)); + = XOBNEW (&ob->obstack, struct string_slot); + const char *string; + + if (!persistent) + { + char *tmp; + string = tmp = XOBNEWVEC (&ob->obstack, char, len); + memcpy (tmp, s, len); + } + else + string = s; new_slot->s = string; new_slot->len = len; @@ -182,7 +189,6 @@ lto_string_index (struct output_block *o else { struct string_slot *old_slot = *slot; - free (string); return old_slot->slot_num + 1; } } @@ -190,29 +196,39 @@ lto_string_index (struct output_block *o /* Output STRING of LEN characters to the string table in OB. The string might or might not include a trailing '\0'. - Then put the index onto the INDEX_STREAM. */ + Then put the index onto the INDEX_STREAM. + When PERSISTENT is set, the string S is supposed to not change during + duration of the OB and thus OB can keep pointer into it. */ -void +static void lto_output_string_with_length (struct output_block *ob, struct lto_output_stream *index_stream, const char *s, - unsigned int len) + unsigned int len, + bool persistent) { - lto_output_uleb128_stream (index_stream, - lto_string_index (ob, s, len)); + if (s) + lto_output_uleb128_stream (index_stream, + lto_string_index (ob, s, len, persistent)); + else + lto_output_1_stream (index_stream, 0); } /* Output the '\0' terminated STRING to the string - table in OB. Then put the index onto the INDEX_STREAM. */ + table in OB. Then put the index onto the INDEX_STREAM. + When PERSISTENT is set, the string S is supposed to not change during + duration of the OB and thus OB can keep pointer into it. */ -void +static void lto_output_string (struct output_block *ob, struct lto_output_stream *index_stream, - const char *string) + const char *string, + bool persistent) { if (string) lto_output_string_with_length (ob, index_stream, string, - strlen (string) + 1); + strlen (string) + 1, + persistent); else lto_output_1_stream (index_stream, 0); } @@ -226,12 +242,10 @@ output_string_cst (struct output_block * struct lto_output_stream *index_stream, tree string) { - if (string) - lto_output_string_with_length (ob, index_stream, - TREE_STRING_POINTER (string), - TREE_STRING_LENGTH (string )); - else - lto_output_1_stream (index_stream, 0); + lto_output_string_with_length (ob, index_stream, + TREE_STRING_POINTER (string), + TREE_STRING_LENGTH (string), + true); } @@ -243,12 +257,10 @@ output_identifier (struct output_block * struct lto_output_stream *index_stream, tree id) { - if (id) - lto_output_string_with_length (ob, index_stream, - IDENTIFIER_POINTER (id), - IDENTIFIER_LENGTH (id)); - else - lto_output_1_stream (index_stream, 0); + lto_output_string_with_length (ob, index_stream, + IDENTIFIER_POINTER (id), + IDENTIFIER_LENGTH (id), + true); } @@ -618,8 +630,9 @@ lto_output_location_bitpack (struct bitp bp_pack_value (bp, ob->current_file != xloc.file, 1); if (ob->current_file != xloc.file) bp_pack_var_len_unsigned (bp, lto_string_index (ob, - xloc.file, - strlen (xloc.file) + 1)); + xloc.file, + strlen (xloc.file) + 1, + true)); ob->current_file = xloc.file; bp_pack_value (bp, ob->current_line != xloc.line, 1); @@ -1184,7 +1197,8 @@ static void lto_output_ts_translation_unit_decl_tree_pointers (struct output_block *ob, tree expr) { - lto_output_string (ob, ob->main_stream, TRANSLATION_UNIT_LANGUAGE (expr)); + lto_output_string (ob, ob->main_stream, + TRANSLATION_UNIT_LANGUAGE (expr), true); } /* Helper for lto_output_tree. Write all pointer fields in EXPR to output @@ -1350,12 +1364,12 @@ lto_output_builtin_tree (struct output_b reader side from adding a second '*', we omit it here. */ const char *str = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (expr)); if (strlen (str) > 1 && str[0] == '*') - lto_output_string (ob, ob->main_stream, &str[1]); + lto_output_string (ob, ob->main_stream, &str[1], true); else - lto_output_string (ob, ob->main_stream, NULL); + lto_output_string (ob, ob->main_stream, NULL, true); } else - lto_output_string (ob, ob->main_stream, NULL); + lto_output_string (ob, ob->main_stream, NULL, true); } @@ -1768,7 +1782,7 @@ output_gimple_stmt (struct output_block lto_output_uleb128_stream (ob->main_stream, gimple_asm_noutputs (stmt)); lto_output_uleb128_stream (ob->main_stream, gimple_asm_nclobbers (stmt)); lto_output_uleb128_stream (ob->main_stream, gimple_asm_nlabels (stmt)); - lto_output_string (ob, ob->main_stream, gimple_asm_string (stmt)); + lto_output_string (ob, ob->main_stream, gimple_asm_string (stmt), true); /* Fallthru */ case GIMPLE_ASSIGN: Index: lto-streamer.h =================================================================== --- lto-streamer.h (revision 174377) +++ lto-streamer.h (working copy) @@ -700,6 +700,10 @@ struct output_block /* Cache of nodes written in this section. */ struct lto_streamer_cache_d *writer_cache; + + /* All data persistent across whole duration of output block + can go here. */ + struct obstack obstack; }; @@ -873,13 +877,6 @@ extern struct output_block *create_outpu extern void destroy_output_block (struct output_block *); extern void lto_output_tree (struct output_block *, tree, bool); extern void produce_asm (struct output_block *ob, tree fn); -extern void lto_output_string (struct output_block *, - struct lto_output_stream *, - const char *); -extern void lto_output_string_with_length (struct output_block *, - struct lto_output_stream *, - const char *, - unsigned int); void lto_output_decl_state_streams (struct output_block *, struct lto_out_decl_state *); void lto_output_decl_state_refs (struct output_block *,