Reduce startup cost of compiler (patch 4)

Reduce startup cost of compiler (patch 4)

[Jan Hubicka]

Hi,
now we spend most of time at startup initializing builtins because of
incredibly slow way we parse attributes (by comparing each attribute by
each possible attribute defined).  This patch introduce simple hashtable
of attribute names poluted on startup.

Dirk mentioned he has more involved solution in preparation that moves
stuff into .def files. With that we probably can precompute lengths and
hashtable easilly, but this patch itself seems to do the trip pushing
the initialization off the top of profile.  It saves more than the
previous two patches combined.

Bootstrapped/regtested i686-linux, OK?
Honza

        * attribs.c: Include hashtab.h
	(attribute_hash): New.
	(substring): New structure.
	(extract_attribute_substring, substring_hash, hash_attr, eq_attr):
	New function.
	(init_attributes): Initialize attribute hash.
	(decl_attributes): Use attribute hash.
	* Makefile.in (attribs.c): Depend on hashtab.h.

Index: attribs.c
===================================================================
--- attribs.c	(revision 126859)
+++ attribs.c	(working copy)
@@ -33,6 +33,7 @@ Software Foundation, 51 Franklin Street,
 #include "cpplib.h"
 #include "target.h"
 #include "langhooks.h"
+#include "hashtab.h"
 
 static void init_attributes (void);
 
@@ -40,14 +41,70 @@ static void init_attributes (void);
    searched.  */
 static const struct attribute_spec *attribute_tables[4];
 
+/* Hashtable mapping names (represented as substrings) to attribute specs. */
+static htab_t attribute_hash;
+
+/* Substring representation.  */
+
+struct substring
+{
+  const char *str;
+  int length;
+};
+
 static bool attributes_initialized = false;
 
 /* Default empty table of attributes.  */
+
 static const struct attribute_spec empty_attribute_table[] =
 {
   { NULL, 0, 0, false, false, false, NULL }
 };
 
+/* Return base name of the attribute.  Ie '__attr__' is turned into 'attr'.
+   To avoid need for copying, we simply return length of the string.  */
+
+static void
+extract_attribute_substring (struct substring *str)
+{
+  if (str->length > 4 && str->str[0] == '_' && str->str[1] == '_'
+      && str->str[str->length - 1] == '_' && str->str[str->length - 2] == '_')
+    {
+      str->length -= 4;
+      str->str += 2;
+    }
+}
+
+/* Simple hash function to avoid need to scan whole string.  */
+
+static inline hashval_t
+substring_hash (const char *str, int l)
+{
+  return str[0] + str[l - 1] * 256 + l * 65536;
+}
+
+/* Used for attribute_hash.  */
+
+static hashval_t
+hash_attr (const void *p)
+{
+  struct attribute_spec *spec = (struct attribute_spec *) p;
+  int l = strlen (spec->name);
+
+  return substring_hash (spec->name, l);
+}
+
+/* Used for attribute_hash.  */
+
+static int
+eq_attr (const void *p, const void *q)
+{
+  const struct attribute_spec *spec = (struct attribute_spec *) p;
+  const struct substring *str = (struct substring *) q;
+
+  return (!strncmp (spec->name, str->str, str->length) && !spec->name[str->length]);
+}
+
 /* Initialize attribute tables, and make some sanity checks
    if --enable-checking.  */
 
@@ -55,6 +112,7 @@ static void
 init_attributes (void)
 {
   size_t i;
+  int k;
 
   attribute_tables[0] = lang_hooks.common_attribute_table;
   attribute_tables[1] = lang_hooks.attribute_table;
@@ -121,6 +179,21 @@ init_attributes (void)
     }
 #endif
 
+  attribute_hash = htab_create (200, hash_attr, eq_attr, NULL);
+  for (i = 0; i < ARRAY_SIZE (attribute_tables); i++)
+    for (k = 0; attribute_tables[i][k].name != NULL; k++)
+      {
+	struct substring str;
+	void **slot;
+
+	str.str = attribute_tables[i][k].name;
+	str.length = strlen (attribute_tables[i][k].name);
+	slot = htab_find_slot_with_hash (attribute_hash, &str,
+					 substring_hash (str.str, str.length),
+					 INSERT);
+	gcc_assert (!*slot);
+	*slot = (void *)&attribute_tables[i][k];
+      }
   attributes_initialized = true;
 }
 \f
@@ -152,23 +225,13 @@ decl_attributes (tree *node, tree attrib
       const struct attribute_spec *spec = NULL;
       bool no_add_attrs = 0;
       tree fn_ptr_tmp = NULL_TREE;
-      size_t i;
-
-      for (i = 0; i < ARRAY_SIZE (attribute_tables); i++)
-	{
-	  int j;
+      struct substring attr;
 
-	  for (j = 0; attribute_tables[i][j].name != NULL; j++)
-	    {
-	      if (is_attribute_p (attribute_tables[i][j].name, name))
-		{
-		  spec = &attribute_tables[i][j];
-		  break;
-		}
-	    }
-	  if (spec != NULL)
-	    break;
-	}
+      attr.str = IDENTIFIER_POINTER (name);
+      attr.length = IDENTIFIER_LENGTH (name);
+      extract_attribute_substring (&attr);
+      spec = htab_find_with_hash (attribute_hash, &attr,
+				  substring_hash (attr.str, attr.length));
 
       if (spec == NULL)
 	{
@@ -184,6 +247,7 @@ decl_attributes (tree *node, tree attrib
 		 IDENTIFIER_POINTER (name));
 	  continue;
 	}
+      gcc_assert (is_attribute_p (spec->name, name));
 
       if (spec->decl_required && !DECL_P (*anode))
 	{
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 126879)
+++ Makefile.in	(working copy)
@@ -1789,7 +1789,7 @@ c-cppbuiltin.o : c-cppbuiltin.c $(CONFIG
 
 attribs.o : attribs.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
 	$(FLAGS_H) toplev.h output.h $(RTL_H) $(GGC_H) $(TM_P_H) \
-	$(TARGET_H) langhooks.h $(CPPLIB_H)
+	$(TARGET_H) langhooks.h $(CPPLIB_H) $(HASHTAB_H)
 
 c-format.o : c-format.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) langhooks.h \
 	$(C_COMMON_H) $(FLAGS_H) toplev.h intl.h $(DIAGNOSTIC_H) c-format.h

Re: Reduce startup cost of compiler (patch 4)

[Richard Guenther]

On 7/24/07, Jan Hubicka <jh@suse.cz> wrote:
> Hi,
> now we spend most of time at startup initializing builtins because of
> incredibly slow way we parse attributes (by comparing each attribute by
> each possible attribute defined).  This patch introduce simple hashtable
> of attribute names poluted on startup.
>
> Dirk mentioned he has more involved solution in preparation that moves
> stuff into .def files. With that we probably can precompute lengths and
> hashtable easilly, but this patch itself seems to do the trip pushing
> the initialization off the top of profile.  It saves more than the
> previous two patches combined.
>
> Bootstrapped/regtested i686-linux, OK?

This looks good, but - did you look at how many collisions you
generate?  It _is_ an incredibly stup^H^H^Himple hash function ;)

Btw, how does this handle target attributes?

Thanks,
Richard.

> Honza
>
>         * attribs.c: Include hashtab.h
>         (attribute_hash): New.
>         (substring): New structure.
>         (extract_attribute_substring, substring_hash, hash_attr, eq_attr):
>         New function.
>         (init_attributes): Initialize attribute hash.
>         (decl_attributes): Use attribute hash.
>         * Makefile.in (attribs.c): Depend on hashtab.h.
>
> Index: attribs.c
> ===================================================================
> --- attribs.c   (revision 126859)
> +++ attribs.c   (working copy)
> @@ -33,6 +33,7 @@ Software Foundation, 51 Franklin Street,
>  #include "cpplib.h"
>  #include "target.h"
>  #include "langhooks.h"
> +#include "hashtab.h"
>
>  static void init_attributes (void);
>
> @@ -40,14 +41,70 @@ static void init_attributes (void);
>     searched.  */
>  static const struct attribute_spec *attribute_tables[4];
>
> +/* Hashtable mapping names (represented as substrings) to attribute specs. */
> +static htab_t attribute_hash;
> +
> +/* Substring representation.  */
> +
> +struct substring
> +{
> +  const char *str;
> +  int length;
> +};
> +
>  static bool attributes_initialized = false;
>
>  /* Default empty table of attributes.  */
> +
>  static const struct attribute_spec empty_attribute_table[] =
>  {
>    { NULL, 0, 0, false, false, false, NULL }
>  };
>
> +/* Return base name of the attribute.  Ie '__attr__' is turned into 'attr'.
> +   To avoid need for copying, we simply return length of the string.  */
> +
> +static void
> +extract_attribute_substring (struct substring *str)
> +{
> +  if (str->length > 4 && str->str[0] == '_' && str->str[1] == '_'
> +      && str->str[str->length - 1] == '_' && str->str[str->length - 2] == '_')
> +    {
> +      str->length -= 4;
> +      str->str += 2;
> +    }
> +}
> +
> +/* Simple hash function to avoid need to scan whole string.  */
> +
> +static inline hashval_t
> +substring_hash (const char *str, int l)
> +{
> +  return str[0] + str[l - 1] * 256 + l * 65536;
> +}
> +
> +/* Used for attribute_hash.  */
> +
> +static hashval_t
> +hash_attr (const void *p)
> +{
> +  struct attribute_spec *spec = (struct attribute_spec *) p;
> +  int l = strlen (spec->name);
> +
> +  return substring_hash (spec->name, l);
> +}
> +
> +/* Used for attribute_hash.  */
> +
> +static int
> +eq_attr (const void *p, const void *q)
> +{
> +  const struct attribute_spec *spec = (struct attribute_spec *) p;
> +  const struct substring *str = (struct substring *) q;
> +
> +  return (!strncmp (spec->name, str->str, str->length) && !spec->name[str->length]);
> +}
> +
>  /* Initialize attribute tables, and make some sanity checks
>     if --enable-checking.  */
>
> @@ -55,6 +112,7 @@ static void
>  init_attributes (void)
>  {
>    size_t i;
> +  int k;
>
>    attribute_tables[0] = lang_hooks.common_attribute_table;
>    attribute_tables[1] = lang_hooks.attribute_table;
> @@ -121,6 +179,21 @@ init_attributes (void)
>      }
>  #endif
>
> +  attribute_hash = htab_create (200, hash_attr, eq_attr, NULL);
> +  for (i = 0; i < ARRAY_SIZE (attribute_tables); i++)
> +    for (k = 0; attribute_tables[i][k].name != NULL; k++)
> +      {
> +       struct substring str;
> +       void **slot;
> +
> +       str.str = attribute_tables[i][k].name;
> +       str.length = strlen (attribute_tables[i][k].name);
> +       slot = htab_find_slot_with_hash (attribute_hash, &str,
> +                                        substring_hash (str.str, str.length),
> +                                        INSERT);
> +       gcc_assert (!*slot);
> +       *slot = (void *)&attribute_tables[i][k];
> +      }
>    attributes_initialized = true;
>  }
>
> @@ -152,23 +225,13 @@ decl_attributes (tree *node, tree attrib
>        const struct attribute_spec *spec = NULL;
>        bool no_add_attrs = 0;
>        tree fn_ptr_tmp = NULL_TREE;
> -      size_t i;
> -
> -      for (i = 0; i < ARRAY_SIZE (attribute_tables); i++)
> -       {
> -         int j;
> +      struct substring attr;
>
> -         for (j = 0; attribute_tables[i][j].name != NULL; j++)
> -           {
> -             if (is_attribute_p (attribute_tables[i][j].name, name))
> -               {
> -                 spec = &attribute_tables[i][j];
> -                 break;
> -               }
> -           }
> -         if (spec != NULL)
> -           break;
> -       }
> +      attr.str = IDENTIFIER_POINTER (name);
> +      attr.length = IDENTIFIER_LENGTH (name);
> +      extract_attribute_substring (&attr);
> +      spec = htab_find_with_hash (attribute_hash, &attr,
> +                                 substring_hash (attr.str, attr.length));
>
>        if (spec == NULL)
>         {
> @@ -184,6 +247,7 @@ decl_attributes (tree *node, tree attrib
>                  IDENTIFIER_POINTER (name));
>           continue;
>         }
> +      gcc_assert (is_attribute_p (spec->name, name));
>
>        if (spec->decl_required && !DECL_P (*anode))
>         {
> Index: Makefile.in
> ===================================================================
> --- Makefile.in (revision 126879)
> +++ Makefile.in (working copy)
> @@ -1789,7 +1789,7 @@ c-cppbuiltin.o : c-cppbuiltin.c $(CONFIG
>
>  attribs.o : attribs.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
>         $(FLAGS_H) toplev.h output.h $(RTL_H) $(GGC_H) $(TM_P_H) \
> -       $(TARGET_H) langhooks.h $(CPPLIB_H)
> +       $(TARGET_H) langhooks.h $(CPPLIB_H) $(HASHTAB_H)
>
>  c-format.o : c-format.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) langhooks.h \
>         $(C_COMMON_H) $(FLAGS_H) toplev.h intl.h $(DIAGNOSTIC_H) c-format.h
>

Re: Reduce startup cost of compiler (patch 4)

[Jan Hubicka]

> On 7/24/07, Jan Hubicka <jh@suse.cz> wrote:
> >Hi,
> >now we spend most of time at startup initializing builtins because of
> >incredibly slow way we parse attributes (by comparing each attribute by
> >each possible attribute defined).  This patch introduce simple hashtable
> >of attribute names poluted on startup.
> >
> >Dirk mentioned he has more involved solution in preparation that moves
> >stuff into .def files. With that we probably can precompute lengths and
> >hashtable easilly, but this patch itself seems to do the trip pushing
> >the initialization off the top of profile.  It saves more than the
> >previous two patches combined.
> >
> >Bootstrapped/regtested i686-linux, OK?
> 
> This looks good, but - did you look at how many collisions you
> generate?  It _is_ an incredibly stup^H^H^Himple hash function ;)

There is one coliding pair with same hash value: nocommon and noreturn
(in general this kind of hash function works well for language keywords).

After adding %251 by the hashtable implementation:
 $7 = {hash_f = 0x4044db <hash_attr>, eq_f = 0x40454a <eq_attr>, del_f =
 0, entries = 0xf48c60, size = 251, n_elements = 52,
 n_deleted = 0, searches = 52, collisions = 11, alloc_f = 0xaa74d0
 <xcalloc>, free_f = 0x4039b0 <free@plt>, alloc_arg = 0x0,
 alloc_with_arg_f = 0, free_with_arg_f = 0, size_prime_index = 5}

But since you asked, given the "no" pattern in attribute names killing
part of hash value, I changed hashtable to:
 static inline hashval_t
 substring_hash (const char *str, int l)
 {
   if (l > 4)
     return str[0] + str[4] * 3 + str[l - 1] * 7 + l * 257;
   else
     return str[0] + str[l - 1] * 3 + l * 257;
 }
It is similiarly cheap and cuts collisions after hashing down to 7 :)
> 
> Btw, how does this handle target attributes?

I first build table of all attributes using the former method and then
just put them into hashtable, so they should not be problem.

Honza