This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
Re: [RFA] Extend hashed symbol dictionaries to work with Ada
- From: Doug Evans <dje at google dot com>
- To: Hilfinger at adacore dot com, Tom Tromey <tromey at redhat dot com>, Joel Brobecker <brobecker at adacore dot com>
- Cc: gdb-patches at sourceware dot org
- Date: Wed, 6 Oct 2010 16:59:45 -0700
- Subject: Re: [RFA] Extend hashed symbol dictionaries to work with Ada
- References: <201010050820.o958Kf42002588@syracuse.mckusick.com>
On Tue, Oct 5, 2010 at 1:20 AM, Paul Hilfinger
<hilfingr@syracuse.mckusick.com> wrote:
>
> This patch allows Ada to speed up symbol lookup by using the facilities
> in dictionary.[ch] for hashed lookups. ?First, we generalize dictionary
> search to allow clients to specify any matching function compatible with
> the hashing function. Next, we modify the hashing algorithm so that symbols
> that wild-match a name hash to the same value. ?Finally, we modify Ada
> symbol lookup to use these facilities.
>
> Because this patch touches on a hashing algorithm used by other
> languages, I took the precaution of doing a speed test on a list of
> about 12000 identifiers (repeatedly inserting all of them into a table
> and then doing a lookup on a million names at random, thus testing the
> speed of the hashing algorithm and how well it distributed names).
> There was actually a slight speedup, probably as a result of open-
> coding some of the tests in msymbol_hash_iw. ?By design, the revised
> hashing algorithm produces the same results as the original on most
> "normal" C identifiers.
>
> We considered augmenting the dictionary interface still further by allowing
> different hashing algorithms for different dictionaries, based on the
> (supposed) language of the symbols in that dictionary. ?While this produced
> better isolation of the changes to Ada programs, the additional flexibility
> also complicated the dictionary interface. ?I'd prefer to keep things
> simple for now.
>
>[...]
Hi. I wouldn't mind having a couple of comments added to this function:
>
> +static unsigned int
> +dict_hash (const char *string)
> +{
> + ?unsigned int hash;
> + ?int c;
> +
> + ?if (*string == '_' && strncmp (string, "_ada_", 5) == 0)
> + ? ?string += 5;
> +
> + ?hash = 0;
> + ?while (*string)
> + ? ?{
> + ? ? ?switch (*string)
> + ? ? ? {
> + ? ? ? case '$': case '.': case 'X': case '(':
Why is 'X' special cased?
[Actually, I'd have the comment explain all of these special cases.]
> + ? ? ? ? return hash;
> + ? ? ? case ' ':
> + ? ? ? ? string += 1;
> + ? ? ? ? break;
> + ? ? ? case '_':
> + ? ? ? ? if (string[1] == '_')
> + ? ? ? ? ? {
> + ? ? ? ? ? ? if (((c = string[2]) < 'a' || c > 'z') && c != 'O')
Why does this `if' exist?
> + ? ? ? ? ? ? ? return hash;
> + ? ? ? ? ? ? hash = 0;
Why do we restart calculating the hash here?
> + ? ? ? ? ? ? string += 2;
> + ? ? ? ? ? ? break;
> + ? ? ? ? ? }
> + ? ? ? ? /* FALL THROUGH */
> + ? ? ? default:
> + ? ? ? ? hash = hash * 67 + *string - 113;
> + ? ? ? ? string += 1;
> + ? ? ? ? break;
> + ? ? ? }
> + ? ?}
> + ?return hash;
> +}
> +