Patchwork ObjC: interface hashtable rewritten for speed and simplicity

login
register
mail settings
Submitter Nicola Pero
Date April 11, 2011, 6:21 p.m.
Message ID <1302546080.945510734@192.168.4.58>
Download mbox | patch
Permalink /patch/90632/
State New
Headers show

Comments

Nicola Pero - April 11, 2011, 6:21 p.m.
This patch rewrites the ObjC interface hashtable for speed, saving
in excess of 100k function calls per typical compilation run in my
benchmarks.

I did extensively benchmark this solution (and other solutions) while
developing it a few months ago.  trunk has changed substantially in
the meanwhile, so those results do not necessarily apply, and I now
just want to get the changes into trunk without having to rebenchmark
everything, but to give an idea, I'd expect this change to speed up
the compiler by about 1% to 2% when compiling real code with -fsyntax-only
in release mode.

Anyhow, the new data structure is really simple and obvious, it is
exactly designed for the task, it is (clearly) lot more efficient
as all the function calls that used to be required to do anything are
gone, and the hashtable size has been tuned.

Ok to commit ?

Thanks
Mike Stump - April 11, 2011, 10:18 p.m.
On Apr 11, 2011, at 11:21 AM, Nicola Pero wrote:
> This patch rewrites the ObjC interface hashtable for speed, saving
> in excess of 100k function calls per typical compilation run in my
> benchmarks.

Does this change a log n lookup to a linear search look up?

Patch

Index: ChangeLog
===================================================================
--- ChangeLog   (revision 172255)
+++ ChangeLog   (working copy)
@@ -1,3 +1,15 @@ 
+2011-04-11  Nicola Pero  <nicola.pero@meta-innovation.com>
+
+       Rewritten the hashtable holding interfaces for speed.
+       * objc-act.h (INTERFACE_HASHTABLE_SIZE, interface_hashtable_entry,
+       interface_hash, interface_hashtable): New.
+       (interface_chain, OCTI_INF_CHAIN): Removed.
+       * objc-act.c (interface_tuple, interface_htab, hash_interface,
+       eq_interface): Removed.
+       (lookup_interface): Rewritten.
+       (add_class): Renamed to add_interface, reimplemented.
+       (interface_hashtable): New.
+
 2011-04-06  Joseph Myers  <joseph@codesourcery.com>
 
        * objc-act.c: Include c-target.h instead of target.h.
Index: objc-act.c
===================================================================
--- objc-act.c  (revision 172255)
+++ objc-act.c  (working copy)
@@ -187,7 +187,11 @@  static hash hash_lookup (hash *, tree);
 static tree lookup_method (tree, tree);
 static tree lookup_method_static (tree, tree, int);
 
-static tree add_class (tree, tree);
+/* Hashtable with all the interfaces.  You can look things up in it by
+   using lookup_interface().  */
+interface_hash *interface_hashtable = 0;
+static void add_interface (tree, tree);
+
 static void add_category (tree, tree);
 static inline tree lookup_category (tree, tree);
 
@@ -3764,27 +3768,6 @@  objc_generate_write_barrier (tree lhs, enum tree_c
   return result;
 }
 
-struct GTY(()) interface_tuple {
-  tree id;
-  tree class_name;
-};
-
-static GTY ((param_is (struct interface_tuple))) htab_t interface_htab;
-
-static hashval_t
-hash_interface (const void *p)
-{
-  const struct interface_tuple *d = (const struct interface_tuple *) p;
-  return IDENTIFIER_HASH_VALUE (d->id);
-}
-
-static int
-eq_interface (const void *p1, const void *p2)
-{
-  const struct interface_tuple *d = (const struct interface_tuple *) p1;
-  return d->id == p2;
-}
-
 tree
 lookup_interface (tree ident)
 {
@@ -3797,19 +3780,19 @@  lookup_interface (tree ident)
     return NULL_TREE;
 
   {
-    struct interface_tuple **slot;
-    tree i = NULL_TREE;
+    interface_hash target;
+    
+    target = interface_hashtable[IDENTIFIER_HASH_VALUE (ident) % INTERFACE_HASHTABLE_SIZE];
 
-    if (interface_htab)
+    while (target)
       {
-       slot = (struct interface_tuple **)
-         htab_find_slot_with_hash (interface_htab, ident,
-                                   IDENTIFIER_HASH_VALUE (ident),
-                                   NO_INSERT);
-       if (slot && *slot)
-         i = (*slot)->class_name;
+       if (ident == target->ident)
+         return target->class_name;
+
+       target = target->next;
       }
-    return i;
+    
+    return NULL_TREE;
   }
 }
 @@ -5507,6 +5490,8 @@ hash_init (void)
 
   ivar_offset_hash_list = ggc_alloc_cleared_vec_hash (SIZEHASHTABLE);
 
+  interface_hashtable = ggc_alloc_cleared_vec_interface_hash (INTERFACE_HASHTABLE_SIZE);
+
   /* Initialize the hash table used to hold the constant string objects.  */
   string_htab = htab_create_ggc (31, string_hash,
                                   string_eq, NULL);
@@ -5878,29 +5863,16 @@  objc_add_method (tree klass, tree method, int is_c
   return method;
 }
 
-static tree
-add_class (tree class_name, tree name)
+static void
+add_interface (tree class_name, tree name)
 {
-  struct interface_tuple **slot;
-
-  /* Put interfaces on list in reverse order.  */
-  TREE_CHAIN (class_name) = interface_chain;
-  interface_chain = class_name;
-
-  if (interface_htab == NULL)
-    interface_htab = htab_create_ggc (31, hash_interface, eq_interface, NULL);
-  slot = (struct interface_tuple **)
-    htab_find_slot_with_hash (interface_htab, name,
-                             IDENTIFIER_HASH_VALUE (name),
-                             INSERT);
-  if (!*slot)
-    {
-      *slot = ggc_alloc_cleared_interface_tuple ();
-      (*slot)->id = name;
-    }
-  (*slot)->class_name = class_name;
-
-  return interface_chain;
+  int slot = IDENTIFIER_HASH_VALUE (name) % INTERFACE_HASHTABLE_SIZE;
+  interface_hash entry = ggc_alloc_interface_hashtable_entry ();
+  entry->ident = name;
+  entry->class_name = class_name;
+  
+  entry->next = interface_hashtable[slot];
+  interface_hashtable[slot] = entry;
 }
 
 static void
@@ -6633,8 +6605,8 @@  start_class (enum tree_code code, tree class_name,
         {
          warning (0, "cannot find interface declaration for %qE",
                   class_name);
-         add_class (implementation_template = objc_implementation_context,
-                    class_name);
+         add_interface (implementation_template = objc_implementation_context,
+                        class_name);
         }
 
       /* If a super class has been specified in the implementation,
@@ -6667,7 +6639,7 @@  start_class (enum tree_code code, tree class_name,
         warning (0, "duplicate interface declaration for class %qE", class_name);
 #endif
       else
-       add_class (klass, class_name);
+       add_interface (klass, class_name);
        
       if (protocol_list)
        CLASS_PROTOCOL_LIST (klass)
Index: objc-act.h
===================================================================
--- objc-act.h  (revision 172255)
+++ objc-act.h  (working copy)
@@ -258,6 +258,21 @@  extern GTY ((length ("SIZEHASHTABLE"))) hash *cls_
 extern GTY ((length ("SIZEHASHTABLE"))) hash *cls_name_hash_list;
 extern GTY ((length ("SIZEHASHTABLE"))) hash *als_name_hash_list;
 
+
+/* Hash table to manage the list of interfaces.  */
+
+#define INTERFACE_HASHTABLE_SIZE 257
+
+typedef struct interface_hashtable_entry *interface_hash;
+
+struct GTY(()) interface_hashtable_entry {
+  tree ident;
+  tree class_name;
+  interface_hash next;
+};
+
+extern GTY ((length ("INTERFACE_HASHTABLE_SIZE"))) interface_hash *interface_hashtable;
+
 /* An array of all the local variables in the current function that
    need to be marked as volatile.  */
 extern GTY(()) VEC(tree,gc) *local_variables_to_volatilize;
@@ -303,7 +318,6 @@  enum objc_tree_index
     OCTI_NST_TYPE,
     OCTI_PROTO_TYPE,
 
-    OCTI_INTF_CHAIN,
     OCTI_PROTO_CHAIN,
     OCTI_IMPL_CHAIN,
     OCTI_CLS_REF_CHAIN,
@@ -454,7 +468,6 @@  extern GTY(()) tree objc_global_trees[OCTI_MAX];
        (TREE_CODE (TYPE) == POINTER_TYPE                               \
         && TREE_TYPE (TYPE) == objc_super_template)
 
-#define interface_chain                objc_global_trees[OCTI_INTF_CHAIN]
 #define protocol_chain         objc_global_trees[OCTI_PROTO_CHAIN]
 #define implemented_classes    objc_global_trees[OCTI_IMPL_CHAIN]