Re: CList glitch (some kind o off-topic response)

[Kevin Handy <kth srv net>]

Soeren Sandmann wrote:
> 
> leon@udmnet.ru writes:
> 
> > BTW, if I *prepend*, not *append* to the list, will it reduce the time
> > to O(n)? Is it possible?
> 
> Yes, prepending is much faster. GLib does not keep track of the tail
> of lists, so appending an item will be an O(n) operation, making
> appending n items an O(n^2) operation.
> 
> Prepending is O(1), so prepending n items will be O(n).
> 
> In my opinion it is a mistake that GLib doesn't keep track of tails.
> I don't think it is possible to fix it, though, since lists are not
> opaque and a lot of code depends on the structure of list items.

Since glib scans to find the end of the list, your big loss of
speed is probibly caused by paging/(swapping). Once everything won't fit
in RAM, it starts to store stuff in the page file, and scanning through
the whole list is likely to be paging everything in/out as it moves
across
the data.