Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #6278

Re: Hardware for linked lists

Show all headers | View raw

On Mon, 05 Mar 2012 19:53:55 -0800, Andy (Super) Glew wrote:

> Arrays are only easier for hardware if accessed sequebntially, or in
> some other numerically regular pattern.

Yes, but (singly, doubly) linked lists demand sequential access, and that 
doesn't seem to be doing much to stop (a certain class of) programmers 
using them.  Take your order-of-magnitude performance improvement where 
you can find it!  Yes, "big data" database and filesystem coders know 
other techniques, but they're fairly thin on the ground.

Until Steele's "divide by halving, rather than "first | rest" (aka 
accumulators are poison) dictum, or the notion of abstract collections 
that understand associativity and commutativity become widespread, code 
is going to walk through data structures in-order.  Sequential access is 
a good bet, for hardware.  IMO.

Cheers,

-- 
Andrew

Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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