Re: 51w5 table resize regressions

[skaller <skaller@...>]

On Mon, 2005-03-07 at 07:53, Mike Pall wrote:

> 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 -> ...
> 

FWIW my only published article includes a study of this problem.
Since requirements vary greatly, the best solution is probably
to have a user installable C function which calculates the
size. This function has the signature:

int sizcal(int request, int used, int allocated)

where 'request' is the number of slots required, 'used' is the number
of used up slots, and 'allocated' is the total number of slots.

For maximum flexibility, there is a global default, and a per-table
value initialised to the default (or NULL), however this costs
one pointer in the table data structure. 

Typical formulas look like:

/* LINEAR ALLOCATOR */
float scale = 1.5;

int sizcal(int request, int used, int allocated) {
  if (request == 0) return 0;
  if (request > allocated) 
  {
    int tmp = allocated;
    while(request > tmp) tmp = tmp * scale + 4;
    return tmp;
  }
  if (request < allocated && request > allocated/2) return allocated;
  return request;
}

A scale factor of 2 (doubling) is common but extremely bad, it wastes
a HUGE amount of memory. A factor of 4 is ludicrous (sorry).

There are other better formulas, for example, for a typical linearly
expanding array, a logarithmic solution is probably best.
For many applications, a constant is best. 

In almost all cases hysteresis is mandatory. This means you don't
get thrashing when you add one slot, then remove one. This is
handled by the line:

if (request < allocated && request > allocated/2) return allocated;

which only reduces the number of slots when half are unused.
(of course there are many formulas possible).

For applications like games with many small tables, a constant is
probably the best (this is just 'round up') because it minimises
memory use.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net