Thankyou for your prompt reply. I do already cash the end of the list as a solution to the performance problem. For a list of 10000 elements the performance gain is a factor of thousands ! Such lists map well as time series data buffers where the list allows us to put data on at the end and take it off at the front.
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 ?
Thankyou again,
Andrew
Havoc Pennington wrote:
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
-- | 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