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

Groups > comp.arch > #6238

Re: Hardware for linked lists

Show all headers | View raw

A number of isses to be addressed:

Arrays are an ideal data structure for data that naturally falls into vector and matrix forms. The reason FORTRAN is better at this is because the memory ordering rules of FORTRAN are such that the compiler can figure out the aliasing and deal with the code (whereas C cannot).

Linked data structures are ideal for that kind of data that gets collected as the applications runs, and often gets moved around. By using pointers to the base data structures the moves are replaces with simply stores of pointers.

Side note: I have written FORTRAN programs that used linked lists--I just mapped FORTRAN indexing into a FORTRAN array and pretended that the indexes were actually pointers (which they are once you know which array they are indexing--which also illuminated the C aliasing problem--C does not know what array the pointer is pointing into--if it did, it could sovle the aliasing problem all by itself.); I have also written LISP code in C. Once you understand the need at hand, and the language in which to express the problem at hand, expressing the solution is rather straightforward.

Humerous Side Note: VAX 11/780 had HW linked list instructions. But even the valuted DEC engineers got the microcode wrong on the first several thousand VAXen such that these instructions were not robust in the face of traps, interrupts, and exceptions. DEC had to fix these.

Alternate Humerous Side note: PDP-10 KI had infinite indirect data structures with livelock prevented with a timeout mechanism. These worked really well for OS data structures ..... UNTIL one day they quadruppled the size of main memory at which time the watchdog timer started to go off all the time. It appears that the OS with 1/4 of the memory build data structures with insufficient tree depth to hit the timer, while the same OS with 4X more memory was not so suitably contrained and hit the timer all the time. Apparently the infinite indirect was routinely running near maximum permissible depth.

To Roberts point: If you can map all of the pointing problems into a single array, you can simply use array indexes as pointers. An array (base addres) with an index (and multiplicative data structure size) IS a real pointer!

Then again there are things one can do with indexes that one is not allowed to do with pointers. The old PDP11 trick of recording the forward and backwards pointers by XORing the two pointers and storeing the result in the bidirections linked list <thingamabob>. You traverse the linked list with a pointer to the bidirections container, XOR with the current pointer to get the successive pointer in which ever direction you are heading. This trick can be implemented in FORTRAN arrays is you like. However, languages with first class pointers in them seem to frown heavily onthis kind of trickery, and suffer memory footprint problems at the same time.

Mitch

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