g_list_append performance bug

[Linas Vepstas]

--9amGYk9869ThD9tj
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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=20
g_list_append() to build lists ... ]

> > What you say is true for GSList, which is singly-linked.
> >=20
> > But GList is doubly-linked, so an append is same speeed as=20
> > a prepend. =20
>=20
> 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.=20

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=20
instantly?'  Isn't this a glib bug?  Did anyone try to report this=20
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=20
cvs tree, and fixed it there ...=20

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


--=20
pub  1024D/01045933 2001-02-01 Linas Vepstas (Labas!) <linas@linas.org>
PGP Key fingerprint =3D 8305 2521 6000 0B5E 8984  3F54 64A9 9A82 0104 5933

--9amGYk9869ThD9tj
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE8DPObZKmaggEEWTMRAuljAJ9ujTwwEY2btn28VnzjvStM7LkZMACaAhEF
C5OUAUsfNNYqIa9HJ+S2x38=
=p4RY
-----END PGP SIGNATURE-----

--9amGYk9869ThD9tj--