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

Groups > comp.arch > #6285

Re: Hardware for linked lists

Show all headers | View raw

On 3/5/12 7:53 PM, Andy (Super) Glew wrote:
> (0) If you are building linked data structures inside arrays by using array indices - well, that is
> not very much different from using pointers, from the point of view of hardware optimizations. The
> indices may be smaller than pointers, and the objects are constrained to a smaller memory region -
> but they have the same issues.

I understood what Terje was suggesting (linked lists of chunks) to be
similar to "cdr-coding" of a singly linked list. That is, instead of
[a|*]->[b|*]->...[x|*]->... you store [a|b|...|x|*]->... You need to
encode the fact that the cdr of some pair p is at &p[1] and not p[1]
and if cdr(p) is overwritten to point elsewhere, you need to do the
right thing. That is instead of needing 2*n cells for a list of n
elements, you need n+1 cells and it saves you a bunch of fetches. A
win if your lists are typically not mutated.

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