Andrew Bartle / 93011 <a_bartle stest ch> writes:Where is GQueue ? Its not in glib as documented in http://developer.gnome.org/doc/API/glib/index.html
> Given the excellent work that has already gone into memory chunk allocation
> etc. to optimise list performance, do you think that hiding this small change
> in the list itself is worth the effort ?
>As Owen says, you could use GQueue in this case. It isn't worth the
effort for the list, if for no other reason that it breaks a lot of
existing code.
Neither is it in glib.h and I couldn't find it by searching http://www.gnu.org/cgi-bin/htsearch
The user wants an interface to a fast list, even if that means exposing an interface object and hiding the beautiful symmetry.Also though, there are tradeoffs. The virtue of this list
implementation is that all nodes are equal; the list is just a node,
as in lisp. i.e. instead of a List object with a pointer to some
Nodes, we have just a Node/List combination object.
To cache the tail, you'd have to do it on every node. That uses a lot
of memory, and makes manipulating the nodes painful, negating much of
the value of the recursive all-nodes-are-lists-are-nodes design.
Havoc
What I meant by "hiding it in the list itself" was, just as the
memory allocation is hidden to the user then so should the pointer to the
last node be hidden. You don't then have to cache the tail on each node
so you don't have to damage the symmetry by changing the node structure.
Alternatively a new interface class is easiest to provide as opposed
to the user remembering to correctly keep track
and update the last element.
I've just found your online book GTK+
/ Gnome Application Development
and in your overview on glib: Portability and Utility, you note:
"Note that glib does not store a pointer to the tail of the list, so prepending is a constant-time operation, while append, insert, and remove are proportional to the list's size. In particular, this means that constructing a list using g_slist_append() is a terrible idea;"
Do you use g_list_append() or g_slist_append() in other components
based on GList or GSList, such as GNode and Hash Tables ?
As you may have guessed, performance is VERY important to us and was one of the reasons for giving glib a try.
Regards,
Andrew
-- | Acterna - Communications Test Solutions | Tel +41 1 355 66 78 | Förrlibuckstrasse 62 / Postfach 74 | Fax +41 1 355 66 12 | CH - 8037, Zurich, | e-mail andrew bartle stest ch | Switzerland | http://www.stest.com