Re: Faster string streaming

[Richard Guenther <richard dot guenther at gmail dot com>]

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 *,
>