Re: Does the array part of a table ever shrink?

[Dirk Laurie <dirk.laurie@...>]

2013/5/29 Luther <lutheroto@gmail.com>:
> In a nutshell, my question is this: If I put lots of nils into a long
> array, will the table move its elements to the hash part to save memory?
>
> I'm implementing the Sieve of Eratosthenes. I have a table with indexes
> 2 through a length parameter all set to true, where the length is rarely
> more than 1000, but it could be any positive integer. I then set most of
> the indexes to false.
>
> If I use nil instead of false, will it save memory, or will the array
> allocation stay the same?

The officially available information is:

/*
** Implementation of tables (aka arrays, objects, or hash tables).
** Tables keep its elements in two parts: an array part and a hash part.
** Non-negative integer keys are all candidates to be kept in the array
** part. The actual size of the array is the largest `n' such that at
** least half the slots between 0 and n are in use.
** Hash uses a mix of chained scatter table with Brent's variation.
** A main invariant of these tables is that, if an element is not
** in its main position (i.e. the `original' position that its hash gives
** to it), then the colliding element is in its own main position.
** Hence even when the load factor reaches 100%, performance remains good.
*/

Note the sentence:

   The actual size of the array is the largest `n' such that at
   least half the slots between 0 and n are in use.

Later in the code (this is ltable.c, BTW) one finds

   if (nasize < oldasize) {  /* array part must shrink? */

So, without actually analyzing code flow, I think it is safe to say
that sooner or later the array part will shrink.