Re: GLib queue and stack, alloca discussion

[Jeff Garzik <jgarzik pobox com>]

On Fri, 22 Jan 1999, Havoc Pennington wrote:
> On Fri, 22 Jan 1999, Jeff Garzik wrote:
> > If GtkCList was implemented using GQueue, you would either need to
> > manipulate the list yourself, or create g_queue_insert and the other
> > g_list_* wrapper functions, so that the list_end and list_size vars are
> > maintained.

> > If the programmer manipulates the list themselves, a g_queue_update()
> > function may be needed to notify GQueue that it needs to possibly
> > recalculate list_end and list_size.

> I think g_queue_update() sucks a lot, so I'd vote for the wrappers.  (I'm
> sure we'd all forget to call g_queue_update, and it would be a nightmare
> bug to find since the segfault would come at some mysterious future
> time...) 

I tend to agree, but still dislike the slight bloat that comes with the
wrappers.:)


> For this purpose it might be nice to be even more like deque:  implement
> it as a vector. Then you save memory and get fast subscripting, at the
> expense of slower insertions. But one almost always appends or prepends to
> a CList, or sets the value of some particular row. Inserts are relatively
> uncommon. Since there can be thousands of rows, the memory overhead of a
> list is not insignificant, seems more important than fast insertions.
> 
> If slow insertions/removals make us nervous, the ability to insert or
> remove an entire block at once would solve that.

IIRC one of the STL deque implementations works by allocating space for
N elements at a time, much like the behavior of mem chunks.  If a lot of
new data is either appended or prepended, additions occur fairly
quickly, with a new allocation only occuring once every N elements. 
Insertions into the middle of the deque cause only a single block to be
reallocated, not the entire array.

I think using blocks makes index-based access slower by adding a level
of indirection, so the complexity of dealing with blocks would be less
than useful if the majority of the cases do not involve middle-of-queue
insertions.

So if slow insertions are acceptable, I may stick with 'simple' and
simply allocate extra space at the beginning and ends of the array to
make insertions at the extremities fast.

	Jeff