Re: It's time for 5.0.1

[Peter Stephenson <p.w.stephenson@xxxxxxxxxxxx>]

On Wed, 12 Dec 2012 11:29:13 -0800
Bart Schaefer <schaefer@xxxxxxxxxxxxxxxx> wrote:
> } it's much less wasteful to forget about
> } heapstacks altogether and simply mark the current heap and start a new
> } one when you push.  Then you just have the one linked list and
> } everything stays linear.
> 
> Well, there are still two linked lists: the currently growing heap and
> the stack of pushed heaps.  I think we can do away with the Heapstack
> struct and use the heapstack pointer in the Heap struct to manage the
> pushed heaps.

Right, there's the full linked list and what is essentially a parallel
linked list with each link pointing some way back into the full list.
So I suppose by default you'd just duplicate the second link from the
previous node when you pushed something onto the main list.

> } I think wasting something of order 16 kB each
> } time we push (and getting it back when we pop) is probably neither here
> } nor there these days.
> 
> Well ... in a pathological case (lots of allocations of 8k+1 bytes) you
> might be wasting as much space as was already in use.  But you could
> construct a similar pathological case for the current algorithm, so I
> don't think it's worth solving right now.

Actually, given that the whole point of the heap is so you don't have to
free things immediately and hence you're already sacrificing memory you
don't strictly need in favour of speed, I don't regard even that case as
particularly high up the pathology scale; it registers as a moderate
cold rather than the black death.

Anyway, it sounds to me like this is a post-5.0.1 project and there's
not a lot of point in short term fiddling, given that the problems
aren't new.

-- 
Peter Stephenson <p.w.stephenson@xxxxxxxxxxxx>
Web page now at http://homepage.ntlworld.com/p.w.stephenson/