Re: Great hack I just learned for linked lists

[Mark-Jason Dominus <mjd@xxxxxxxxxx>]

>  a game programmer told me a great efficiency hack for 
>  linked lists.  He said it's well known among game programmers
>  but not otherwise.

I'd say it's well-known among assembly-language programmers.
High-level languages usually go to some trouble to make a distinction
between numbers and pointers, because it reduces the chance of errors
and increases portability to different systems.

The benefit usually claimed for this trick is that a to make alist
that is linked in both directionsm, you normally need to store two
pointers per item, one pointing to the next item in each direction.
But with the trick, you only store one pointer.

Until now, I have never heard anyone claim that this promoted a time
efficiency, and I am very doubtful that it would actually deliver on
that promise.  Following a pointer in the normal way is not
an expensive operation.  

Also, it isn't applicable to ZigZag, because it is only useful for
complete traversals of a list.  If you are at the nth item in the
list, and you just came from the (n-1)th item, you use the trick to
find the (n+1)th item.  But if you happen to be at the nth item, and
you don't know what the (n-1)th item is, there is absolutely no way to
find the (n+1)th item.  But this situation occurs all the time in
ZigZag.

>  However, maybe we could figure some way
>  to crank this up for greater efficiency ...

In my experience, this kind of extremely low-level micro-optimization
is usually a mistake even in the advanced stages of a project that is
already almost complete.  The existing system already performs
adequately.  I think we should be considering issues of scalability
and function before we worry about how to save a few bytes in the
database.