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