From patchwork Mon Apr 11 18:21:20 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicola Pero X-Patchwork-Id: 90632 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 85EF8B6F0B for ; Tue, 12 Apr 2011 04:21:31 +1000 (EST) Received: (qmail 23318 invoked by alias); 11 Apr 2011 18:21:29 -0000 Received: (qmail 23308 invoked by uid 22791); 11 Apr 2011 18:21:29 -0000 X-SWARE-Spam-Status: No, hits=-1.4 required=5.0 tests=AWL, BAYES_00, TW_BJ, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (140.186.70.10) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 11 Apr 2011 18:21:24 +0000 Received: from eggs.gnu.org ([140.186.70.92]:54508) by fencepost.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1Q9Ljn-0006OE-7x for gcc-patches@gnu.org; Mon, 11 Apr 2011 14:21:23 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Q9Ljl-0002HY-Jd for gcc-patches@gnu.org; Mon, 11 Apr 2011 14:21:22 -0400 Received: from smtp111.iad.emailsrvr.com ([207.97.245.111]:60344) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Q9Ljl-0002HU-FD for gcc-patches@gnu.org; Mon, 11 Apr 2011 14:21:21 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp41.relay.iad1a.emailsrvr.com (SMTP Server) with ESMTP id 3C4CA29153C for ; Mon, 11 Apr 2011 14:21:21 -0400 (EDT) Received: from dynamic6.wm-web.iad.mlsrvr.com (dynamic6.wm-web.iad1a.rsapps.net [192.168.2.147]) by smtp41.relay.iad1a.emailsrvr.com (SMTP Server) with ESMTP id 2557E291513 for ; Mon, 11 Apr 2011 14:21:21 -0400 (EDT) Received: from meta-innovation.com (localhost [127.0.0.1]) by dynamic6.wm-web.iad.mlsrvr.com (Postfix) with ESMTP id E79C18B8001 for ; Mon, 11 Apr 2011 14:21:20 -0400 (EDT) Received: by www2.webmail.us (Authenticated sender: nicola.pero@meta-innovation.com, from: nicola.pero@meta-innovation.com) with HTTP; Mon, 11 Apr 2011 20:21:20 +0200 (CEST) Date: Mon, 11 Apr 2011 20:21:20 +0200 (CEST) Subject: ObjC: interface hashtable rewritten for speed and simplicity From: "Nicola Pero" To: "gcc-patches@gnu.org" MIME-Version: 1.0 X-Type: plain Message-ID: <1302546080.945510734@192.168.4.58> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 207.97.245.111 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 + + 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 * 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]