On Tue, Dec 04, 2001 at 09:15:48AM -0600, Bill Gribble was heard to remark: > On Tue, 2001-12-04 at 07:55, Linas Vepstas wrote:
[ ... stuff omitted about bad bad O(n^2) performance of using g_list_append() to build lists ... ] > > What you say is true for GSList, which is singly-linked. > > > > But GList is doubly-linked, so an append is same speeed as > > a prepend. > > GList is doubly linked but not double ended. In order to append, it > still has to traverse the entire list; the "prev" pointer of the first > element of the list is NULL. So: dave's right, it's much faster to > build the list backwards and reverse. Dohhh! I just wrote a little program to check this, and indeed. My gut reaction is 'that is the stupidest thing I ever heard, what's the point of a doubly linked list if you can't find the tail instantly?' Isn't this a glib bug? Did anyone try to report this as a glib bug? What did the glib people say about it? ??? I suppose someone would take my head off if I just went into the cvs tree, and fixed it there ... Fixing it risks breaking some unknown program, may there is a way of making this feature/bug in g_list 'depricated' ? I can't be the first person bit in the ass by this stupidity! --linas -- pub 1024D/01045933 2001-02-01 Linas Vepstas (Labas!) <[EMAIL PROTECTED]> PGP Key fingerprint = 8305 2521 6000 0B5E 8984 3F54 64A9 9A82 0104 5933
msg01773/pgp00000.pgp
Description: PGP signature
