Re: Interesting article on hash table performance

[Francisco Olarte <folarte@...>]

Ahmed:

On Wed, Mar 1, 2017 at 10:52 AM, Ahmed Charles <acharles@outlook.com> wrote:
> I'm not familiar with Lua's algorithm for hash tables, but removing the
> bounds check for the array in the inner loop by having allocating a
> slightly larger array reminds me of removing the bounds check in
> insertion sort by placing the smallest/largest element at the
> beginning/end, respectively, based on which way you search the array.

You normally ( specially when table is something like a table of
pointers in C, or references in other languages ) just put the
inserted element as sentinel ( that's what they are tipically called )
as the smalest/largest may be difficult to construct or not even exist
( specially in qsort(3) type functions, which took table, element
size, comparator function ). And the same trick was used typically for
lineal search ( in the times where testing the loop counter was really
expensive, this days I do it more for reducing instruction count, and
thus bug surface, than speed ).

Francisco Olarte.