51w5 table resize regressions

[Mike Pall <mikelu-0503@...>]

Hi,

Lua 5.1-work5 has a lot of changes in table management compared to work4.
In particular the initial allocation for the hash part of table
constructors changed:

                      | # of hash slots |
constructor           |  51w4  |  51w5  |
----------------------+--------+--------+
{}                    |   1    |   0    |
{a=1}                 |   2    |   1    |
{a=1,b=2}             |   4    |   2    |
{a=1,b=2,c=3}         |   4    |   4    |
{a=1,b=2,c=3,d=4}     |   8    |   4    |
{a=1,b=2,c=3,d=4,e=5} |   8    |   8    |

As you can see 51w5 allocates only what is really needed, whereas 51w4
always has at least one more free slot in the hash part of the table.

Unfortunately this means that e.g. the object instantiation benchmark
from the shootout tests (objinst.lua) is 22% slower. Other OO tests show
regressions, too.

Tracing reveals that 51w4 does many 2->4 resizes of the hash part and
51w5 does many 1->2->4 resizes in this particular test. The resize/realloc
overhead seems to make a major difference.

Maybe a better progression to reduce resizes would be:

  0 -> 4 -> 4*4 -> 4*4*4 -> 4*4*4*4=256 -> 2*256 -> 2*2*256 -> ...

Starting with zero has the advantage that integer arrays do not get dummy
hash slots. Initial quadrupling reduces the reallocations for small sizes.
Doubling starts around 8K size for the hash part for x86 and around 10K on
most 32 bit and all 64 bit CPUs.

Python does something similar, but has a fixed initial allocation (8) that
is stored in the dictionary object itself. This is not directly applicable
to Lua since sizeof(Node) (28 or 40) is relatively large with tagged values.

Opinions?

Bye,
     Mike