Re: GLib queue and stack, alloca discussion
- From: Jeff Garzik <jgarzik pobox com>
- To: gtk-devel-list redhat com
- Subject: Re: GLib queue and stack, alloca discussion
- Date: Sat, 23 Jan 1999 13:16:51 -0500 (EST)
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
I tend to agree, but still dislike the slight bloat that comes with the
> 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
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.
] [Thread Prev