* ObjC: interface hashtable rewritten for speed and simplicity
@ 2011-04-11 18:21 Nicola Pero
2011-04-11 22:19 ` Mike Stump
0 siblings, 1 reply; 2+ messages in thread
From: Nicola Pero @ 2011-04-11 18:21 UTC (permalink / raw)
To: gcc-patches
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
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]
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2011-04-11 22:19 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-04-11 18:21 ObjC: interface hashtable rewritten for speed and simplicity Nicola Pero
2011-04-11 22:19 ` Mike Stump
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).