[RFA] Extend hashed symbol dictionaries to work with Ada
Doug Evans
dje@google.com
Wed Oct 6 23:59:00 GMT 2010
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;
> +}
> +
More information about the Gdb-patches
mailing list