smryan@garth.UUCP (Steven Ryan) (12/13/90)
>has essentially only one form of data structuring, the array, while in >C arrays are much less commonly used, other more appropriate data >structures taking their place. Thus, while vectorization is important >. . . I infer from this that chasing pointers throughout memory is considerred a better programming practice. Pointer chasing is not only good for trashing the cache but for thrashing virtual memory as well. Generally, pointers are used to implement graphs. However graphs are just a special form of relations, so that pointers are an implementation of an implementation of a relation. There are other ways of representing a relation. For example, as an associative memory. Related items can then be defined as a predicate on their data fields. In this way, rather than explicitly link related items, a sweep across the memory brings them together. Is this more efficient? Well, it might be easier on the programmer, which some think is the most important efficiency consideration. As far as machine efficiency is concerned, pointer chasing can require fewer probes, but it is sequential and accesses memory randomly and unpredicatably. Memory sweeping probes every item, but it is parallel (or vectorisable) and accesses memory predicatably and sequentially. -- ...!uunet!ingr!apd!smryan Steven Ryan ...!{apple|pyramid}!garth!smryan 2400 Geng Road, Palo Alto, CA
userAKDU@mts.ucs.UAlberta.CA (Al Dunbar) (12/14/90)
In article <11@garth.UUCP>, smryan@garth.UUCP (Steven Ryan) writes: >>has essentially only one form of data structuring, the array, while in >>C arrays are much less commonly used, other more appropriate data >>structures taking their place. Thus, while vectorization is important >>. . . > >I infer from this that chasing pointers throughout memory is considerred >a better programming practice. Pointer chasing is not only good for trashing >the cache but for thrashing virtual memory as well. <<<deletions>>> >As far as machine efficiency is concerned, pointer chasing can require >fewer probes, but it is sequential and accesses memory randomly and >unpredicatably. Memory sweeping probes every item, but it is parallel >(or vectorisable) and accesses memory predicatably and sequentially. The only "randomly and unpredictably" aspects of how "pointer chasing" works is when someone tries to drive a C compiler without at least a learner's permit. Pointer operations in a "correct" program is completely predictable, in that the results achieved are correct. If you are concerned with the fact that the values of the actual addresses used in pointers is difficult to determine from reading the code, you may have missed the whole point of "abstraction". The address values are a detail that, like hexadecimal arithmetic, you can usually forget about. -------------------+------------------------------------------- Al Dunbar | Edmonton, Alberta | "this mind left intentionally blank" CANADA | - Manuel Writer -------------------+-------------------------------------------
rh@smds.UUCP (Richard Harter) (12/17/90)
In article <2011@mts.ucs.UAlberta.CA>, userAKDU@mts.ucs.UAlberta.CA (Al Dunbar) writes: > In article <11@garth.UUCP>, smryan@garth.UUCP (Steven Ryan) writes: > >>has essentially only one form of data structuring, the array, while in > >>C arrays are much less commonly used, other more appropriate data > >>structures taking their place. Thus, while vectorization is important > >I infer from this that chasing pointers throughout memory is considerred > >a better programming practice. Pointer chasing is not only good for trashing > >the cache but for thrashing virtual memory as well. > <<<deletions>>> > >As far as machine efficiency is concerned, pointer chasing can require > >fewer probes, but it is sequential and accesses memory randomly and > >unpredicatably. Memory sweeping probes every item, but it is parallel > >(or vectorisable) and accesses memory predicatably and sequentially. > The only "randomly and unpredictably" aspects of how "pointer > chasing" works is when someone tries to drive a C compiler > without at least a learner's permit. Pointer operations in > a "correct" program is completely predictable, in that the > results achieved are correct. If you are concerned with the > fact that the values of the actual addresses used in pointers > is difficult to determine from reading the code, you may have > missed the whole point of "abstraction". The address values > are a detail that, like hexadecimal arithmetic, you can > usually forget about. I don't know about others but I find this exchange a little bit disturbing. If I read it correctly Dunbar has missed the point and is totally unaware that he has missed the point. Briefly: It can make a large difference in execution time if data is accessed sequentially rather than by random address. Current computer architectures and OS's typically have heirarchical access (cache's, resident pages in virtual memory management, etc). Data is made accessible in blocks. It is much faster to access the data within the current block than data which is not; moreover this fact is relevant throughout the access heirarchy. Ryan's point, such as it is, is that the array based paradigm of Fortran corresponds to the physical architecture whereas the pointer based paradigm of C does not. One can make the point that it is perfectly possible in C to access data sequentially. One could also make the counter-point that although it is possible the language does not naturally lead one to do the efficient thing. One could also make the point that C is an "experts" language that provides flexibility in making the right choice. And, of course, one can make the counter point the widespread use of an "experts" language by people who are not experts leads to large numbers of distressing messes. I suppose that the thing that is particularly distressing about Dunbar's response, as I have interpreted it, is that it is representative of a wide-spread misunderstanding of the art of programming. In designing software one naturally takes into account various principles of software design and construction that facilitate design, implementation, and maintenance. However these principles (rules of thumb? superstitious incantations?) are not the only things to be taken into account. A good design also takes into account things such as the mode of usage and the architecture in which the software is embedded. (A good designer also takes into account potential changes in these environmental parameters.) I get the impression that there are a number of people teaching and people learning from these teachers that real world (environmental) considerations are irrelevant to "good" programming. These people believe that they are propounding the solution; the truth is that they are making the problem worse. -- Richard Harter, Software Maintenance and Development Systems, Inc. Net address: jjmhome!smds!rh Phone: 508-369-7398 US Mail: SMDS Inc., PO Box 555, Concord MA 01742 This sentence no verb. This sentence short. This signature done.
hotte@sunrise.in-berlin.de (Horst Laumer) (12/17/90)
userAKDU@mts.ucs.UAlberta.CA (Al Dunbar) writes: >In article <11@garth.UUCP>, smryan@garth.UUCP (Steven Ryan) writes: >>>has essentially only one form of data structuring, the array, while in >>>C arrays are much less commonly used, other more appropriate data >>>structures taking their place. Thus, while vectorization is important >>>. . . >> >>I infer from this that chasing pointers throughout memory is considerred >>a better programming practice. Pointer chasing is not only good for trashing >>the cache but for thrashing virtual memory as well. ><<<deletions>>> >>As far as machine efficiency is concerned, pointer chasing can require >>fewer probes, but it is sequential and accesses memory randomly and >>unpredicatably. Memory sweeping probes every item, but it is parallel >>(or vectorisable) and accesses memory predicatably and sequentially. > >The only "randomly and unpredictably" aspects of how "pointer >chasing" works is when someone tries to drive a C compiler >without at least a learner's permit. Pointer operations in >a "correct" program is completely predictable, in that the >results achieved are correct. If you are concerned with the >fact that the values of the actual addresses used in pointers >is difficult to determine from reading the code, you may have >missed the whole point of "abstraction". The address values >are a detail that, like hexadecimal arithmetic, you can >usually forget about. > Right, my dear! C ain't PASCAL, where "address of object X" may not be the same as "pointer to object X". (BTW, in another article, I saw the question "how to PEEK() and POKE() in C....". Horrible imagination!) Suggestion: try to understand the man-page of qsort(3) or something like that! --HL -- ============================================================================ Horst Laumer, Kantstrasse 107, D-1000 Berlin 12 ! Bang-Adress: Junk-Food INET: hotte@sunrise.in-berlin.de ! for Autorouters -- me -- UUCP: ..unido!fub!geminix!sunrise.in-berlin.de!hotte