Re: Hardware for linked lists

From	Andrew Reilly <areilly---@bigpond.net.au>
Newsgroups	comp.arch
Subject	Re: Hardware for linked lists
Date	2012-03-05 03:59 +0000
Message-ID	<9ris1oF4r1U1@mid.individual.net> (permalink)
References	<J9R4r.11081$jU1.4604@newsfe08.iad>

Show all headers | View raw

On Sun, 04 Mar 2012 16:29:44 -0500, Robert Myers wrote:

> Now, mind you, just as with smart phones (which I never use), I rarely
> use linked lists, but since a computer that can't do linked lists
> handily is no longer of any interest, I'm interested in any way of
> attacking this problem--even though it's not usually my problem.
> 
> What do I turn up?
> 
> http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-
lists.html
> 
> "Should you ever use linked lists" (why not use arrays instead).

Bjarne Stroustrup made a similar argument in the last issue of IEEE 
Computer magazine that crossed my desk.  He explained that while linked 
lists are nominally O(1) for some sorts of variable-length update tasks, 
modern hardware can make the constant scale factor quite large, compared 
to using explicit arrays to do the same thing.  His example pitted a 
doubly-linked list against an array for a random insertion and deletion 
task on integers (yes, dumb), and found that the linked list only got 
faster for problems larger than 500000 elements (on his laptop.)  Not a 
terribly convincing argument, but there is definitely value in picking 
the right structure for the job.

One of the supposed benefits of "modern" programming languages is exactly 
that these sorts of "collections" are interchangeable, and you can swap 
an array implementation for a linked one as part of the overall tuning 
process.  That makes a lot of sense: a lot of software fails because it 
trips over "optimisations" made too early in the process.

> Since I don't use linked lists, I can't really evaluate the arguments,
> but naturally, I like the drift of the implied these (no, you probably
> should be using arrays instead of linked lists).

Yes, you should, execpt for the situations where a linked structure is 
more appropriate...

> Now, i realize that this is actually a software question, but my
> sneaking suspicion is that hardware is being built to conform to
> sub-optimal programming practices (using fancy data structures instead
> of "naive" data structures).

The whole point of modern, out-of-order processor design seems to be to 
deal with sub-optimal programs.  That includes instruction selection and 
sequencing as well as data structure access.  If you've got the resources 
to "optimise" your problem, you wind up putting it on arrays of much 
cheaper processors like DSPs, or FPGAs or even ASICs.  If you're not 
doing that then you are leaving some performance or power consumption on 
the floor, which is probably an entirley fair trade-off.  Lots of 
software is limited by time-to-market (or time-to-solution), rather than 
any particular mechanical efficiency.

Having said all that: PDP-10 could chase pointers in hardware, as has 
been mentioned.  A little later than that, before the "AI Winter", there 
were a bunch of dedicated LISP computers, many of which had hardware and/
or software runtime support for special optimisations of linked list 
handling.  (http://en.wikipedia.org/wiki/CDR_coding)

Cheers,

-- 
Andrew

Thread

Hardware for linked lists Robert Myers <rbmyersusa@gmail.com> - 2012-03-04 16:29 -0500
  Re: Hardware for linked lists Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-03-04 22:41 +0100
    Re: Hardware for linked lists "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-03-04 20:15 -0800
      Re: Hardware for linked lists "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-03-05 19:53 -0800
        Re: Hardware for linked lists Andrew Reilly <areilly---@bigpond.net.au> - 2012-03-06 11:38 +0000
          Re: Hardware for linked lists nmm1@cam.ac.uk - 2012-03-06 12:16 +0000
        Re: Hardware for linked lists Bakul Shah <usenet@bitblocks.com> - 2012-03-06 23:24 -0800
          Re: Hardware for linked lists Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-03-07 09:08 +0100
    Re: Hardware for linked lists Noob <root@127.0.0.1> - 2012-03-06 13:25 +0100
      Re: Hardware for linked lists Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-03-06 17:11 +0100
  Re: Hardware for linked lists nmm1@cam.ac.uk - 2012-03-04 21:51 +0000
    Re: Hardware for linked lists Robert Myers <rbmyersusa@gmail.com> - 2012-03-04 17:16 -0500
      Re: Hardware for linked lists nmm1@cam.ac.uk - 2012-03-04 23:15 +0000
    Re: Hardware for linked lists Chris Gray <cg@GraySage.com> - 2012-03-04 17:04 -0700
      Re: Hardware for linked lists nmm1@cam.ac.uk - 2012-03-05 09:01 +0000
        Re: Hardware for linked lists Chris Gray <cg@GraySage.com> - 2012-03-05 14:07 -0700
    Re: Hardware for linked lists George Neuner <gneuner2@comcast.net> - 2012-03-05 00:57 -0500
  Re: Hardware for linked lists cjt <cheljuba@prodigy.net> - 2012-03-04 19:09 -0600
  Re: Hardware for linked lists MitchAlsup <MitchAlsup@aol.com> - 2012-03-04 18:24 -0800
    Re: Hardware for linked lists Robert Myers <rbmyersusa@gmail.com> - 2012-03-04 22:26 -0500
  Re: Hardware for linked lists Andrew Reilly <areilly---@bigpond.net.au> - 2012-03-05 03:59 +0000
    Re: Hardware for linked lists Anne & Lynn Wheeler <lynn@garlic.com> - 2012-03-04 23:38 -0500
      Re: Hardware for linked lists Jim Haynes <jhaynes@alumni.uark.edu> - 2012-03-05 11:08 -0600
  Re: Hardware for linked lists jgk@panix.com (Joe keane) - 2012-03-05 22:21 +0000
    Re: Hardware for linked lists Michael S <already5chosen@yahoo.com> - 2012-03-05 15:14 -0800
      Re: Hardware for linked lists John Levine <johnl@iecc.com> - 2012-03-06 01:44 +0000
        Re: Hardware for linked lists Michael S <already5chosen@yahoo.com> - 2012-03-06 00:41 -0800
  Re: Hardware for linked lists torbenm@diku.dk (Torben Ægidius Mogensen) - 2012-03-06 11:19 +0100
    Re: Hardware for linked lists nmm1@cam.ac.uk - 2012-03-06 11:07 +0000

csiph-web