Path: utzoo!yunexus!geac!daveb
From: daveb@geac.UUCP (David Collier-Brown)
Newsgroups: comp.lang.c
Subject: Re: Fast way to update grids
Summary: Given multiplicative indexing...
Message-ID: <2212@geac.UUCP>
Date: 5 Feb 88 14:10:15 GMT
Article-I.D.: geac.2212
Posted: Fri Feb  5 09:10:15 1988
References: <255@imagine.PAWL.RPI.EDU> <690005@hpfelg.HP.COM>
Reply-To: daveb@geac.UUCP (David Collier-Brown)
Organization: The G. Yac Co. Ltd.
Lines: 25

In article <690005@hpfelg.HP.COM> jk@hpfelg.HP.COM (John Kessenich) writes:
>    Use an array (it is the fastest know data structure for linear 
>    traversal in an arbitrary direction), but take advantage of C's
>    pointer arithmetic.  Example:
[elided]
>    If you are going through the array in some order, the address step 
>    may not even be necessary.
>    Also, for addressing, subscript ranges equal to powers of two will
>    yield faster results.  Why?  They are compiled as << instead of *.
>
  This is true for compilers using real multiplicative indexing.  As
the white book is written to allow edge-vector addressing, and at
least one pcc-based compiler uses it, this turns out to be
compiler-dependent.  
  As it happens, the Waterloo (GCOS) C compiler uses edge-vectors, but
also (if memory serves) keeps the pointed-at data contiguous to
allow such assumptions to work nevertheless.  Something of a ``best
of both worlds'' effect, at no extra cost to the program/programmer.

 --dave (I was the bug-fix guy at the acceptor site) c-b
-- 
 David Collier-Brown.                 {mnetor yunexus utgpu}!geac!daveb
 Geac Computers International Inc.,   |  Computer Science loses its
 350 Steelcase Road,Markham, Ontario, |  memory (if not its mind) 
 CANADA, L3R 1B3 (416) 475-0525 x3279 |  every 6 months.