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

Groups > comp.arch > #6227 > unrolled thread

Hardware for linked lists

Back to article view | Back to comp.arch

Contents

  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

Page 1 of 2  [1] 2  Next page →

#6227 — Hardware for linked lists

Almost everything that seems important to me in computer architecture is 
connected either with moving data around or accessing memory (possibly a 
redundant characterization).

No matter how I approach the subject: bandwidth, switch connectivity, 
prefetch, whatever, I come up against what I take to be a version of an 
argument that Andy Glew has passed along to me:

You're so old-school, man.  No one uses arrays any more.  People use, as 
Terje put it some years ago, irregular data structures (as opposed to, 
again, as Terje put it, naive data structures--like arrays).

Rather than trying to find yet another way to ask the same question, I 
decided to try Google.  I put in the query:

linked lists hardware architecture

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

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

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

Thoughts?

Robert.

[toc] | [next] | [standalone]

#6230

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).
>
> 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).
>
> 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).
>
> Thoughts?

I'd suggest linked lists of chunks (i.e. arrays!) of items.

This makes most memory accesses sequential, while keeping the overhead 
of inserting/deleting items "in the middle" relatively small.

It also corresponds well with how we used to write disk-based database 
index storage.:-)

Since RAM today works just like disks 30-40 years ago, this makes sense.

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#6244

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.

[toc] | [prev] | [next] | [standalone]

#6273

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.

[toc] | [prev] | [next] | [standalone]

#6278

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

[toc] | [prev] | [next] | [standalone]

#6279

In article <9rmb8uFb3U1@mid.individual.net>,
Andrew Reilly  <areilly---@bigpond.net.au> wrote:
>
>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.

No, that ain't so.  It's certainly true of people who follow the path
of modern 'computer science', without having got further than the
basics (which includes a regrettable number of professors and other
supposed experts) but it isn't true of traditional scientific programmers
and a fair number of other groups.

Look at modern Fortran and MPI for clear examples of where unordered
aggregate access is used to get much better analysability and leave
the implementation much more scope to optimise.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#6285

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.

[toc] | [prev] | [next] | [standalone]

#6286

Bakul Shah wrote:
> 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.

Yeah, that's exactly right.

I would grab back some of the space savings in order to make each chunk 
a little larger than needed (maybe using powers of two or fibonacci 
sizes?), then have a little header in each chunk that states how large 
it is, how many items are currently stored, and the link to the next 
chunk. (Possibly also an index to the first item if removing datafrom 
the head is common enough.)

Insert/delete in the middle of a chunk will require the tail to be 
copied, and when a chunk grows too large it is either extended (copying 
the data to the new location) or split.

The key idea is to make a large percentage of all memory accesses 
sequential, this allows a lot of time/room for occasional (partial) 
chunk copying.

Since RAM is the current disk, it makes sense to work with disk block 
algorithms!

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#6280

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).
>>
>> 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).
>>
>> 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).
>>
>> Thoughts?
> 
> I'd suggest linked lists of chunks (i.e. arrays!) of items.

Or the STL's deque.

http://www.sgi.com/tech/stl/Deque.html
http://en.wikipedia.org/wiki/Double-ended_queue

[toc] | [prev] | [next] | [standalone]

#6281

Noob wrote:
> Terje Mathisen wrote:
>> I'd suggest linked lists of chunks (i.e. arrays!) of items.
>
> Or the STL's deque.
>
> http://www.sgi.com/tech/stl/Deque.html
> http://en.wikipedia.org/wiki/Double-ended_queue

Why?

Unless you only need front/back operations, this is only marginally 
better than a regular array, and most easily implemented as such, but 
with the free space equally distributed before/after the active region.

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#6231

In article <J9R4r.11081$jU1.4604@newsfe08.iad>,
Robert Myers  <rbmyersusa@gmail.com> wrote:
>
>No matter how I approach the subject: bandwidth, switch connectivity, 
>prefetch, whatever, I come up against what I take to be a version of an 
>argument that Andy Glew has passed along to me:
>
>You're so old-school, man.  No one uses arrays any more.  People use, as 
>Terje put it some years ago, irregular data structures (as opposed to, 
>again, as Terje put it, naive data structures--like arrays).

Well, they do.  However, few computer scientists do, because they
rarely understand arrays.  The rot started with Wirth, who produced
an utterly insane specification for them in Pascal, whereupon
Pascal was rejected by the scientific programming community.
The insanity spread into C, and we now have TWO generations of
computer scientists without a clue about arrays, which is why
C++'s (and even Boost's) are incredibly complicated but not actually
very powerful.  Fortran, not surprisingly, is VASTLY better.

Andy and Terje have a point, but the claim that nobody uses them
is a sound-bite rather than a fact.  The point is that irregular
data structures are far more important, not that the naive ones
aren't used (and used a lot).

>http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>
>"Should you ever use linked lists" (why not use arrays instead).
>
>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).

I do, a lot, and in several forms.  That argument is equally insane
in the other direction.  There are very good reasons to use linked
lists instead of arrays, and the only sane approach is to use the
most suitable data structure for your requirement, not to shoehorn
your requirement into an unsuitable structure.  Oh, and a linked
list IS a naive data structure!


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#6232

On 3/4/2012 4:51 PM, nmm1@cam.ac.uk wrote:
> Oh, and a linked
> list IS a naive data structure!
>

Well, help my naive and uneducated mind.  Once you've allowed for the 
possibility of a pointer to a pointer, I don't know what kind of 
generalization is possible, short of effectively including executable or 
at least interpreted embedded code in the data.

Robert.

[toc] | [prev] | [next] | [standalone]

#6233

In article <dRR4r.9429$wf.617@newsfe09.iad>,
Robert Myers  <rbmyersusa@gmail.com> wrote:
>
>> Oh, and a linked
>> list IS a naive data structure!
>
>Well, help my naive and uneducated mind.  Once you've allowed for the 
>possibility of a pointer to a pointer, I don't know what kind of 
>generalization is possible, short of effectively including executable or 
>at least interpreted embedded code in the data.

The usual meaning of a linked list is a simple chain, with the
pointer to the next element at a fixed location in each one.
That could be optimised in hardware, and I believe has been.

Trees are trickier, DAGs trickier still, and structures like
Dirichlet tesselations extremely hard to do anything with.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#6234

nmm1@cam.ac.uk writes:

> Well, they do.  However, few computer scientists do, because they
> rarely understand arrays.  The rot started with Wirth, who produced
> an utterly insane specification for them in Pascal, whereupon
> Pascal was rejected by the scientific programming community.
> The insanity spread into C, and we now have TWO generations of
> computer scientists without a clue about arrays, which is why
> C++'s (and even Boost's) are incredibly complicated but not actually
> very powerful.  Fortran, not surprisingly, is VASTLY better.

Perhaps I'll come to deeply regret this, but...

Ok, what's wrong with them that Fortran gets better?

I'm asking because I might be able to add what you want to my Zed language -
I did the informal docs on array (static sized) and matrix (dynamically
allocated) types last week.

Note: abstractions/formalisms and I don't get along, but a friend a couple
blocks away is good at that stuff. We both know Fortran, C, Pascal,...,
but not at the language-lawyer level.

-- 
Chris Gray

[toc] | [prev] | [next] | [standalone]

#6254

In article <87hay3lxpq.fsf@GraySage.com>, Chris Gray  <cg@GraySage.com> wrote:
>
>> Well, they do.  However, few computer scientists do, because they
>> rarely understand arrays.  The rot started with Wirth, who produced
>> an utterly insane specification for them in Pascal, whereupon
>> Pascal was rejected by the scientific programming community.
>> The insanity spread into C, and we now have TWO generations of
>> computer scientists without a clue about arrays, which is why
>> C++'s (and even Boost's) are incredibly complicated but not actually
>> very powerful.  Fortran, not surprisingly, is VASTLY better.
>
>Perhaps I'll come to deeply regret this, but...
>
>Ok, what's wrong with them that Fortran gets better?
>
>I'm asking because I might be able to add what you want to my Zed language -
>I did the informal docs on array (static sized) and matrix (dynamically
>allocated) types last week.
>
>Note: abstractions/formalisms and I don't get along, but a friend a couple
>blocks away is good at that stuff. We both know Fortran, C, Pascal,...,
>but not at the language-lawyer level.

Firstly, the C++ and Boost people believe that a multi-dimensional
array is the same as a (single-dimensional) array of (s-d) arrays
of ...  That is a fundamental error, and has been known to be for
50 years, because it leads to subsequent mistakes.

Secondly, it isn't possible to handle a linear subset (array section)
as an array in its own right, without taking a copy, as introduced by
Algol 68.  Despite appearances, Boost views do not cut the mustard,
because of the first mistake!

I am not claiming that Fortran is perfect.  Because it has only
value-returning functions, and not variable/lvalue/name-returning
ones, it isn't possible to code an aliasing transpose or diagonal
section etc.

Thirdly, the C++ STL is terribly sequential, at a fundamental level,
and iterators are precisely the wrong concept for such uses.  Most
array operations are order-independent, which should be reflected
in the language.

Interestingly, they both have a very restricted view of elemental
operations, but that's not a fundamental defect, just something
that hasn't been done.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#6267

nmm1@cam.ac.uk writes:

<<trimmed my question>>

> Firstly, the C++ and Boost people believe that a multi-dimensional
> array is the same as a (single-dimensional) array of (s-d) arrays
> of ...  That is a fundamental error, and has been known to be for
> 50 years, because it leads to subsequent mistakes.

This isn't an issue in my Zed - it has proper multi-dimensional arrays.
You can of course have arrays of arrays if you want. I also define the
storage order, but allow a super-optimizing compiler to change it if it
is sure that is safe.

However, I don't see why it is a big issue. In C you can end up with
pointers into the middle of arrays and do really bad things, but that
also allows you to do the slicing thing.

> Secondly, it isn't possible to handle a linear subset (array section)
> as an array in its own right, without taking a copy, as introduced by
> Algol 68.  Despite appearances, Boost views do not cut the mustard,
> because of the first mistake!

Zed does not have this. My friend created (but not implemented) a language
of his own which has "rangers" which allow this. My problem with his
general form of them is that you can end up with a pointer into the middle
of an allocated piece of storage being the only remaining reference to
that storage. In a system that does reference counting or garbage collection,
that adds significantly to the cost, for just that one capability.

I imagine some limited subset of what he does can be done. It is easier
with fixed-size arrays than with dynamically allocated matrices, because
there is no need to decide where the bounds are stored. To allow more
flexible use of some kind of sectioning, an extra chunk of memory is needed,
which can slow down accessing of dynamic matrices.

> Thirdly, the C++ STL is terribly sequential, at a fundamental level,
> and iterators are precisely the wrong concept for such uses.  Most
> array operations are order-independent, which should be reflected
> in the language.

Some of the higher-level languages have things like "map" operators which
operate on entire vectors. These are possible in my language, and could be
defined (by whoever writes them) in such a way as to take advantage of
multiple cores/processors, vector instructions, etc. You don't get the
terse syntax of, say, APL, but that can be a good thing!

--

-Chris Gray

[toc] | [prev] | [next] | [standalone]

#6249

On Sun, 4 Mar 2012 21:51:03 +0000 (GMT), nmm1@cam.ac.uk wrote:

>The rot started with Wirth, who produced
>an utterly insane specification for them in Pascal, whereupon
>Pascal was rejected by the scientific programming community.
>The insanity spread into C, and we now have TWO generations of
>computer scientists without a clue about arrays

Nick, could you elaborate a bit on which particular Pascal array
insanities you consider infected C?  

Leaving the issue of string types aside, nearly everyone hated that
Pascal considered array dimensionality to be part of the array's type.
Combined with no (safe or otherwise) ability to overlay/alias types,
that made working with arrays of differing dimensions sometimes very
difficult.

But equally a lot of people (me included) disliked that C arrays were
zero based whereas Pascal permitted arbitrary integer bounds.  Wirth
switched to zero based arrays in Modula-2 and later (though unlike C
the upper bounds were known and obtainable).  It seems to me that, if
anything, C arrays infected the Pascal family of languages rather than
the other way around.

Just wondering,
George

[toc] | [prev] | [next] | [standalone]

#6236

On 03/04/2012 03:29 PM, Robert Myers wrote:
> Almost everything that seems important to me in computer architecture is
> connected either with moving data around or accessing memory (possibly a
> redundant characterization).
>
> No matter how I approach the subject: bandwidth, switch connectivity,
> prefetch, whatever, I come up against what I take to be a version of an
> argument that Andy Glew has passed along to me:
>
> You're so old-school, man. No one uses arrays any more. People use, as
> Terje put it some years ago, irregular data structures (as opposed to,
> again, as Terje put it, naive data structures--like arrays).
>
> Rather than trying to find yet another way to ask the same question, I
> decided to try Google. I put in the query:
>
> linked lists hardware architecture
>
> 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).
>
> 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).
>
> 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).
>
> Thoughts?
>
> Robert.

As I recall, and FWIW, the IBM 360 we had at U. Michigan back in the 
'60's had some special microcode +/- for traversing linked lists, so the 
question is not exactly a new one.

[toc] | [prev] | [next] | [standalone]

#6238

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

[toc] | [prev] | [next] | [standalone]

#6240

On 3/4/2012 9:24 PM, MitchAlsup wrote:

>
> 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!
>

I have always coded that way.  If I had my way, everyone would.

I have an entire graphics library written in Fortran 66.

You would need to do something a little more elaborate if you were 
worried about the compiler being confused about aliasing.  $IVDEP is all 
I ever needed.

Robert.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.arch

csiph-web