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

[Vibhav Pant <vibhavp@gmail.com>]

On Fri, Feb 10, 2017 at 11:37 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>> 1. For jump tables, HASH_TABLE_SIZE (h) == h->count, so using h->count
>> directly saves the cost of an array lookup.
>
> That doesn't invalidate the usefulness of a linear search.
Sure, but that makes it better (IMO) to have separate code for linear
searching the jump table.
>
>> 2. Since the size equals the count, we don't need to check whether
>> HASH_HASH (h, i) (the hash code) is non nil in every pass of the
>> linear search loop (maphash needs to do this, before calling the
>> providing function).
>
> The linear search should compare HASH_HASH(h, i) to the search key's
> hash anyway, so this comparison against nil is not needed.

Is that strictly needed, though? In the case of jump tables, there is
no extra space reserved
in h->key_and_value for more keys to be stored, so the vector looks like
`[:group 14 :version 20 :package-version 25 :link 30 :load 35 :tag 40
:set-after 46]`
(the jump table for (custom-handle-keyword)). IIUC, this negates the
need for comparing
HASH_HASH (h, i), as our linear search code is effectively

for i from 0 to h->count
 if h->key_and_value [2*i] == key_needed // HASH_KEY, the value we're
comparing against
  return h->key_and_value[2*i + 1]; // HASH_VALUE, the address switch
is to jump to

Having said that, I think `gethash` should have it's own linear search
code, with all the checks you mentioned.

-- 
Vibhav Pant
vibhavp@gmail.com