Hello list,

the attach simple patch saves reproducively a tiny bit of time on various -O0 compilations I've performed, for example 5ms out of 627ms. Tested on i386.

We trade a little bit of memory (maxmem2.sh from [1] reported 25240 KB instead of 25080 KB without the patch) to allow our hash tables be more sparsely populated (always at least half-empty). Since our hash tables resolve conflicts by rehashing, reducing collisions is good.

Another patch that I'll post soon helped me measure collisions/searches ratio for the hottest hash tables. What could be easily noticed was that the ratio was too high, reaching 0.5 or even 0.7 in some cases. This made clear that we need some deep refactoring of our hash tables, either changing hash functions or the complete hash table implementation, to not involve any rehashing for collision handling. Unfortunately such tries failed either because they were too simple to show any difference, or they were too intrusive and involved changes everywhere htab_t is used (almost everywhere).

This patch is the simplest one to show positive change but I believe that some careful hash table redesign must be planned. For example, for the mem_attrs_htab hash table, coll/searches ratio is still sometimes higher than 0.5.

Changelog:

2011-08-09  Dimitrios Apostolou  <ji...@gmx.net>

        * symtab.c (ht_lookup_with_hash): Hash table will now be doubled
        when 50% full, not 75%, to reduce collisions.
        * hashtab.c (find_empty_slot_for_expand)
        (htab_find_slot_with_hash): The same.



Thanks,
Dimitris



[1] http://gcc.gnu.org/wiki/PerformanceTesting
=== modified file 'libcpp/symtab.c'
--- libcpp/symtab.c     2009-07-18 02:22:16 +0000
+++ libcpp/symtab.c     2011-08-09 02:39:45 +0000
@@ -172,7 +172,7 @@
     HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack,
                                                           str, len);
 
-  if (++table->nelements * 4 >= table->nslots * 3)
+  if (++table->nelements * 2 > table->nslots)
     /* Must expand the string table.  */
     ht_expand (table);
 

=== modified file 'libiberty/hashtab.c'
--- libiberty/hashtab.c 2011-02-03 07:23:20 +0000
+++ libiberty/hashtab.c 2011-08-09 02:39:45 +0000
@@ -515,8 +515,9 @@
 }
 
 /* The following function changes size of memory allocated for the
-   entries and repeatedly inserts the table elements.  The occupancy
-   of the table after the call will be about 50%.  Naturally the hash
+   entries and repeatedly inserts the table elements.  It is designed to
+   be called when table is half-full. The occupancy
+   of the table after the call will be about 25%.  Naturally the hash
    table must already exist.  Remember also that the place of the
    table entries is changed.  If memory allocation failures are allowed,
    this function will return zero, indicating that the table could not be
@@ -542,7 +543,7 @@
      too full or too empty.  */
   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
     {
-      nindex = higher_prime_index (elts * 2);
+      nindex = higher_prime_index (elts * 4);
       nsize = prime_tab[nindex].prime;
     }
   else
@@ -648,7 +649,7 @@
   PTR entry;
 
   size = htab_size (htab);
-  if (insert == INSERT && size * 3 <= htab->n_elements * 4)
+  if (insert == INSERT && htab->n_elements * 2 > size)
     {
       if (htab_expand (htab) == 0)
        return NULL;

Reply via email to