hiebeler@pawl19.pawl.rpi.edu (David E. Hiebeler) (01/27/88)
I've been working on a project for some time now which reads in an
algorithm, and writes a C program to run some 2-D automata. It's coming
along pretty well now, but now I'd like to get some input from people 'out
there.'
Basically, I'm looking for a fast (the fastest?) way of updating
grids, where each cell has to look at an arbitrary number of its neighbors.
I've seen some fast life-programs, but often they took advantage of particular
quirks of the the rules of Life.
I need some method more general. I've tried the simple method,
storing the grid in an array, and simply using 2 indices to cover the grid,
and each cell stores its new value in a 2nd copy of the grid. Say you have 5
neighbors, then each cell requires 5 things like "grid[x][y+1]" for example
to get the value of its south neighbor.
I tried a field of linked nodes; i defined a whole bunch of structs,
and each cell had a value, plus the structure contained pointers to all of
its neighbors. So the south neighbor might be (cell.south).value for example.
Both methods ran at about the same speed (this was on a Sequent
Balance 21000, using C).
Does anyone out there have some useful tips on what I can do to
speed up the program? Any comments would be greatly appreciated...
Thanks,
Dave Hiebeler Internet: hiebeler@csv.rpi.edu (preferred address)
R.D. Box 225A hiebeler@b21.cs.rpi.edu
Chatham, NY 12037 userfrzk%mts.rpi.edu@itsgw.rpi.edu
Bitnet: userfrzk@rpitsmts.bitnet
----
David Hiebeler hiebeler@csv.rpi.edu
Troy, NY "Wo bu jidow wo tzai
shua shumua"jk@hpfelg.HP.COM (John Kessenich) (02/02/88)
Use an array (it is the fastest know data structure for linear
traversal in an aribitrary direction), but take advantage of C's
pointer arithmetic. Example:
int a[16][16];
#define NO 1
#define SO -1
#define EA 16
#define WE -16
Then if you want to know about a[x][y] neighbors, look at
b = &a[x][y];
b + NO;
b + SO;
b + EA;
b + WE;
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 *.
--------------
John Kessenichdaveb@geac.UUCP (David Collier-Brown) (02/05/88)
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.
atbowler@watmath.waterloo.edu (Alan T. Bowler [SDG]) (02/19/88)
In article <2212@geac.UUCP> daveb@geac.UUCP (David Collier-Brown) writes: > 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. Sorry Dave, but that is just not true. You get edge vectors only if you declare the structure as having edgevectors. If you declare a multidimensional array you get the conventional contiguous chunk of memory and addressing polynomials to access it. Are you sure you aren't getting confused with B (and BCPL) where edgevectors was the only choice? Alan Bowler Product Support Software Development Group University of Waterloo