g_list_append performance bug

[Linas Vepstas]

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

On Tue, Dec 04, 2001 at 10:58:22AM -0600, Bill Gribble was heard to remark:
> On Tue, 2001-12-04 at 10:02, Linas Vepstas wrote:
> > 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? ???
>=20
> No, I don't think it's a bug.  'Fixing' it would break basic operations
> you can do on a GList : iterating forward and backward to the end of the
> list, for example.  Since GLists don't have a special "head" structure
> and aren't usually circular, the beginning of the list is noted by a
> NULL prev pointer and the end by a NULL next.

Fixing this doesn't require making glist circular.  You can still make
the next pointer at the tail NULL, and this will uniquely identify the
tail.  However, iterating backwards will require testing for a NULL
next, instead of a NULL prev.   That is how double-linked lists
are supposed to be implemented, which is why glib is a bug.  Instead
of making the 'head/end-of-list' test unique, it was turned into two
tests.

> Keep in mind that there's no distinction between a "list" and a "list
> item" with GLists.  The only way to add a tail pointer without a new
> structure type to be the "list head" is to make the list circular, and
> then you can't iterate over it because you won't know where the end is.=
=20

Not true, you give the answer yourself, below.

> If you say you want to keep NULL next at the end but not NULL prev at
> the beginning, then you still lose the ability to iterate in reverse,

Not true, you just need to test for the right thing, which is NULL-ness
of next, not prev.  Making the list semi-circular does not prevent you
from correctly identifying the end when you iterate backwards.

> which is sort of the point of a doubly linked list.  And you would lose
> the ability to distinguish between a normal linked list and a circular
> linked list, which are sometimes useful and can be implemented using the
> current GList.=20
>=20
> The idea with GLists is that if you want a head and tail pointer, you
> maintain and update them in the application. =20

But there's a problem with that!  glib does not give you an O(1) way
of being able to maintain the pointer to the tail!  It can't be done!
There is no way to maintain the tail pointer in your application, except
by searching for it, which makes it totally pointless to maintain a
tail pointer!=20

Which is why g_list is fundamentally broken in its current
implementation.=20

The point is that no sane double-linked list is ever implenmented in
this way.  Its just not normal; glib is just plain crippled.   Its=20
current design offers no advantages that I can think of, and has=20
disadvantages compared to 'normal' doubly-linked list designs.

Anf finally, a fix can be made that is not likely to impact most
users of glist ...

> > I suppose someone would take my head off if I just went into the=20
> > cvs tree, and fixed it there ...=20
>=20
> Pretty likely, since it would break *everything* :) =20

My guess is it wouldn't break anything, since I doubt that there are
many apps that are backewards-iterating, and doing it 'by hand'. ...=20

> It's just not that
> big a deal to build the list backwards and reverse it;=20

That's just dopey.  There is not a single comp-sci book that would
recommend this, except as an illustration of why its a stupid idea ...

(comment about LISP elided, since that's a different beast anyway.)

--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

--u3/rZRmxL6MmkK24
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

iD8DBQE8DQo5ZKmaggEEWTMRAsrCAJwOeaCeDMYfz1YXVpD3pi485Xt7GQCfb+Fi
efS6OugsKKOE00in/sl9Avs=
=HOOL
-----END PGP SIGNATURE-----

--u3/rZRmxL6MmkK24--