Re: [Fwd: glib::GList:g_list_append(), g_list_last() performance problem]

[Havoc Pennington <hp redhat com>]

Andrew Bartle / 93011 <a_bartle stest ch> writes:
> 
> As supplementary info, m'colleague indicates that this performance problem also exists
> in glib-1.2.8
> 
> Am I sending this to the right place now ? Still no answer from "the other place"
> gnu gnu org
> 

This is the right place. g_list_last() and g_list_append() are defined
to be O(n) operations; they are not fast for long lists. GList is
modeled on the lists found in Scheme, Haskell, etc. which behave the
same way.

If you want O(1) append, you can simply cache the tail item in the
list; my book GTK+/Gnome Application Development has an example in the
GLib chapter I think. You could also write a simple AppendList
datatype that was implemented in terms of GList but stored
the tail pointer, if you wanted to.

Havoc