lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Sat, May 30, 2015 at 11:48 PM, Brigham Toskin
<> wrote:
> Could you give a real world example?

easy:  a queue structure is sometimes implemented as:

---------- queue.lua
function new_queue()
   return {head = 0, tail = 0}

function num_objs(q)
   return q.head - q.tail

function push(q, v)
   q.head = q.head + 1
   q[q.head] = v

function pop(q)
   q.tail = q.tail+1
   local v = q[q.tail]
   q[q.tail] = nil
   return v

obviously, the q.head and q.tail cursors are monotonically growing,
but it would be a while before you have to worry about overflowing the
2^53 limit of integer precision.  since pop()ing a value at the tail
sets its table entry as nil, after a while the table won't use the
array optimization, and use hashes instead, keeping only the used
entries in memory and not allocating a huge array.

and what happens if you're at, say 1'000,000 entry and empty the
queue? currently, nothing.  you have a mostly empty table.  but if you
were internally tracking the "highest integer key" just in case the
user calls #q (which it doesn't in this case), then you have to
quickly find the new top, and all you know is that the latest integer
key deleted was 1'000,000.  I guess some heuristics could help on this
case, but it's easy to come up with slight modifications to the user
code (pop from the top, keep some 'intermediate' values, anything)
that would create large, unpredictable hiccups.