Re: Bug in ltable.c

[Roberto Ierusalimschy <roberto@...>]

>    It counts a key one off its correct position so that in border cases it
>    is counted in the wrong bucket. If a table is only populated by increasing
>    integer keys starting from 1, the hashtable should never be used. But the
>    erroneous counting would use it e.g. for a key '2^m+1', which does not fit
>    in the allocated array. This slows down performance, because a rehash has
>    to be done twice (for '2^m+1' and for '2^m+2').

Did you check that? Simple tests indicate otherwise. For instance, the
loop |a = {} for i=1,10 do a[i] = i end| produces the following
sequence of table sizes:

i      array   hash
1	1	0
2	2	0
3	4	0
4	4	0
5	8	0
6	8	0
7	8	0
8	8	0
9	16	0
10	16	0


>    My suggestion:
> 
>    static int countint (const TValue *key, int *nums) {
>      int k = arrayindex(key);
>      if (0 < k && k <= MAXASIZE) {  /* is `key' an appropriate array index?
>    */
>        /* nums[luaO_ceillog2(k)]++;  */ /* count as such */
>        nums[luaO_ceillog2(k-1)]++  /* count as such [CORRECTING BUG] */
>        return 1;
>      }
>      else
>        return 0;
>    }

Did you check that? The above simple loop seems to seg. fault with
this change.


>    In addition if  key = MAXASIZE = 2^MAXBITS is used, the non existent
>    bucket 'nums[MAXBITS+1]' is used with unpredictable results.

This may be true (I still did not check it), but your suggestion would
not fix this problem, because ceillog2(2^MAXBITS - 1) is equal to
ceillog2(2^MAXBITS) (both are MAXBITS).

-- Roberto