On Sun, May 29, 2011 at 4:31 PM, Jan Hubicka <hubi...@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 *,
>
