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

Groups > comp.arch > #6273

Re: Hardware for linked lists

Show all headers | View raw

On 3/4/2012 8:15 PM, Andy (Super) Glew wrote:
> On 3/4/2012 1:41 PM, Terje Mathisen wrote:
>> Robert Myers wrote:
>>> http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>>>
>>> "Should you ever use linked lists" (why not use arrays instead).
>
> Most programmers should not use either linked lists or arrays. They
> should not use low level data structures.
>
> They should use higher level data structures. Something like C++ STL
> list<T> or vector<T>. But ideally better - where the compiler and/or
> runtime can look at how the accesses are being dome, and change the
> underlying implementation to whatever is appropriate.
>
> ---
>
> By the way, I have many optimizations for linked lists in my toolbag. No
> company has yet chosen to implement them, AFAIK.

A topic close to my heart. The thing that I should have finished my 
Ph.D. on. Thinking about which led to my MLP (Memory Level Parallelism) 
talk.

A few random points:

(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.

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

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