This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Reduce startup cost of compiler (patch 4)

> On 7/24/07, Jan Hubicka <> wrote:
> >Hi,
> >now we spend most of time at startup initializing builtins because of
> >incredibly slow way we parse attributes (by comparing each attribute by
> >each possible attribute defined).  This patch introduce simple hashtable
> >of attribute names poluted on startup.
> >
> >Dirk mentioned he has more involved solution in preparation that moves
> >stuff into .def files. With that we probably can precompute lengths and
> >hashtable easilly, but this patch itself seems to do the trip pushing
> >the initialization off the top of profile.  It saves more than the
> >previous two patches combined.
> >
> >Bootstrapped/regtested i686-linux, OK?
> This looks good, but - did you look at how many collisions you
> generate?  It _is_ an incredibly stup^H^H^Himple hash function ;)

There is one coliding pair with same hash value: nocommon and noreturn
(in general this kind of hash function works well for language keywords).

After adding %251 by the hashtable implementation:
 $7 = {hash_f = 0x4044db <hash_attr>, eq_f = 0x40454a <eq_attr>, del_f =
 0, entries = 0xf48c60, size = 251, n_elements = 52,
 n_deleted = 0, searches = 52, collisions = 11, alloc_f = 0xaa74d0
 <xcalloc>, free_f = 0x4039b0 <free@plt>, alloc_arg = 0x0,
 alloc_with_arg_f = 0, free_with_arg_f = 0, size_prime_index = 5}

But since you asked, given the "no" pattern in attribute names killing
part of hash value, I changed hashtable to:
 static inline hashval_t
 substring_hash (const char *str, int l)
   if (l > 4)
     return str[0] + str[4] * 3 + str[l - 1] * 7 + l * 257;
     return str[0] + str[l - 1] * 3 + l * 257;
It is similiarly cheap and cuts collisions after hashing down to 7 :)
> Btw, how does this handle target attributes?

I first build table of all attributes using the former method and then
just put them into hashtable, so they should not be problem.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]