home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / c / 16579 < prev    next >
Encoding:
Text File  |  1992-11-15  |  2.6 KB  |  62 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!gatech!hubcap!mjs
  3. From: mjs@hubcap.clemson.edu (M. J. Saltzman)
  4. Subject: Re: Reasons for using C vs. Fortran or vic
  5. Message-ID: <1992Nov15.224010.13609@hubcap.clemson.edu>
  6. Organization: Clemson University, Clemson SC
  7. References: <1992Nov12.205823.13951@u.washington.edu> <1992Nov13.162451.13049@zia.aoc.nrao.edu> <1992Nov15.201555.20678@thunder.mcrcim.mcgill.edu>
  8. Date: Sun, 15 Nov 1992 22:40:10 GMT
  9. Lines: 51
  10.  
  11. In article <1992Nov15.201555.20678@thunder.mcrcim.mcgill.edu> mouse@thunder.mcrcim.mcgill.edu (der Mouse) writes:
  12. >In article <1992Nov13.162451.13049@zia.aoc.nrao.edu>, cflatter@nrao.edu (Chris Flatters) writes:
  13. >
  14. >> Storing arrays by column or by row doesn't make any difference
  15. >> whatsoever to the speed of matrix operations: it is merely a notation
  16. >> change.
  17. >
  18. >This is true only in the abstract.  I have experienced (not just heard
  19. >about) multiple orders of magnitude speed differences, because going
  20. >through arrays "the wrong way" had catastrohpically bad VM behavior:
  21. >essentially, every access involved a page fault.  Doing it "the right
  22. >way" stepped through VM in a nice sequential way, with minimal paging.
  23.  
  24. Note that you do have to adjust the details of the access pattern to
  25. match the storage patter, in order to not suffer performance penalties
  26. because of lack of locality.  For example, if you are storing matrices
  27. in row-major order, you should perform matrix-vector multiplication as
  28. a sequence of inner products of the vector with the rows of the
  29. matrix:
  30.  
  31.     /* Compute y = y + Ax, accessing A in row-major order */
  32.  
  33.     for i = 1 to m do
  34.       for j = 1 to n do
  35.         y[i] = y[i] + A[i][j] * x[j]
  36.  
  37. If your matrices are stored in column-major order, you should
  38. perform matrix-vector multiplication by summing scalar multiples of
  39. the columns of the matrix:
  40.  
  41.     /* Compute y = y + Ax, accessing A in column-major order */
  42.  
  43.     for j = 1 to n do
  44.       for i = 1 to m do
  45.         y[i] = y[i] + A[i][j] * x[j]
  46.  
  47. Thus, there is a "right way" for either storage pattern, but they are
  48. different.
  49.  
  50. Now, if you are doing matrix-matrix multiplication for matrices stored
  51. in column-major order, the "right way" is a natural extension of the
  52. second algorithm above (i.e., C = AB is computed by multiplying A by
  53. successive columns of B).  If your matrices are in row-major order,
  54. the interpretation of the appropriate sequential-access algorithm is
  55. not so straightforward.  I conjecture that this is why Fortran
  56. designers chose column-major storage for matrices.  Once that's done,
  57. the extension to more than two dimensions is pretty much dictated.
  58. -- 
  59.         Matthew Saltzman
  60.         Clemson University Math Sciences
  61.         mjs@clemson.edu
  62.