Re: [zzdev] Re: Hack for Linked Lists

[Ted Nelson <ted@xxxxxxxxxx>]

Yeah, I figured it would be something like that.
 Still, had to mention it.

Best, Ted


At 01:22 AM 12/20/98 -0500, you wrote:
>
>>  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.  
>
>
>
________________________________________________________
Theodor Holm Nelson, Visiting Professor of Environmental Information,
 Keio University, Shonan Fujisawa Campus, Fujisawa, Japan _____
http://www.sfc.keio.ac.jp/~ted/   ______
Permanent Address: Project Xanadu, 3020 Bridgeway #295, Sausalito CA 94965
_____  World Wide Fax +1-415-332-0136   World Wide Voicemail:
+1-415-331-4422 _____ PERMANENT E-MAIL: ted@xxxxxxxxxx
_________________________________________________________ 
Quotation of the day, 19 December 98:
"Denial is the longest river in the world."  TN94