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;
