Re: [PATCH]: Add new bytecode op `switch' for implementing branch tables.

[Vibhav Pant <vibhavp@gmail.com>]

On Wed, Feb 8, 2017 at 7:08 PM, Vibhav Pant <vibhavp@gmail.com> wrote:
> On Tue, Feb 7, 2017 at 9:26 PM, Clément Pit-Claudel
> <cpitclaudel@gmail.com> wrote:
>> The timings fluctuate quite a bit, but the byte-switch branch seems to be about 5-7% slower.  Hopefully linear-scan hash tables will make things much faster :)
>
> The following patch makes hash_lookup use linear search when the number of keys
> in the hash table is <= 5 (chosen arbitrarily). switch bytecode run with this
> patch takes 15.96 seconds to run the benchmark, while the goto-if-nil code takes
> 17.15 seconds.
>
> --
> Vibhav Pant
> vibhavp@gmail.com
>
> diff --git a/src/fns.c b/src/fns.c
> index ac7c1f265a..2940bfdfbb 100644
> --- a/src/fns.c
> +++ b/src/fns.c
> @@ -3915,6 +3915,17 @@ hash_lookup (struct Lisp_Hash_Table *h,
> Lisp_Object key, EMACS_UINT *hash)
>    ptrdiff_t start_of_bucket;
>    Lisp_Object idx;
>
> +  if (HASH_TABLE_SIZE (h) <= 5 && h->test.cmpfn) {
> +    /*Try doing a linear search first */
> +    ptrdiff_t i;
> +    for (i = 0; i < HASH_TABLE_SIZE (h); i++)
> +      {
> +        if (h->test.cmpfn (&h->test, key, HASH_KEY (h, i)))
> +          return i;
> +      }
> +    return -1;
> +  }
> +
>    hash_code = h->test.hashfn (&h->test, key);
>    eassert ((hash_code & ~INTMASK) == 0);
>    if (hash)

Looks like this is the incorrect way to linear-search a hash table, as
it's sometimes resulting
in duplicate hash table entries.

-- 
Vibhav Pant
vibhavp@gmail.com