443,432 Members | 795 Online Need help? Post your question and get tips & solutions from a community of 443,432 IT Pros & Developers. It's quick & easy.

# Numerical Recipes vector and matrix definition

 P: n/a Hi, I've developed a C program which contains a large number of vectors and matrices operations. Throughout my code, I used the template from the Numerical Recipes book to define vectors and matrices and access their elements. For example, to define a vector I used the function: my_vector=vector(0,n-1); Which actually allocate the memory as follows: my_vector = (float *) malloc ( n*sizeof(float) ); and then to access its elements, I used my_vector,......., my_vector[n] The execution time of the program is extremely important for me and it should be made as short as possible. I was wondering if the method that I used for vector and matrix notation in my code is the most efficient one. Does anybody know the best method (in terms of efficiency) to define matrices and perform operations on their elements in C? Even a small speedup in my code would be valuable for me. Thanks for your help Jun 27 '08 #1
10 Replies

 P: n/a "Babak"

 P: n/a On May 24, 6:28*pm, "Bartc"

 P: n/a Babak wrote: On May 24, 6:28 pm, "Bartc" "Babak" >I've developed a C program which contains a large number of vectorsand matrices operations. Throughout my code, I used the templatefrom the Numerical Recipes book to define vectors and matrices andaccess their elements. For example, to define a vector I used thefunction: >>my_vector=vector(0,n-1); >>Which actually allocate the memory as follows: >>my_vector = (float *) malloc ( n*sizeof(float) ); >>and then to access its elements, I used my_vector,.......,my_vector[n] >>The execution time of the program is extremely important for me andit should be made as short as possible. I was wondering if themethod that I used for vector and matrix notation in my code is themost efficient one. Does anybody know the best method (in terms ofefficiency) to define matrices and perform operations on theirelements in C? Even a small speedup in my code would be valuable forme. That looks pretty efficient to me, assuming my_vector is a pointerto float.What does the matrix code look like? The matrix code is like: my_matrix=matrix(0,n-1,0,n-1); which is equivalent to: /* allocate pointers to rows */ my_matrix=(float **) malloc(n*sizeof(float*)); /* allocate rows and set pointers to them */ my_matrix[i]=(float *) malloc(n*sizeof(float)); i=0,...,n-1 and I access its elements like my_matrix,........... That looks fairly standard too. Your compiler will take care of low-level optimisation such as converting between indexing and pointer operations. What sort of speedup are you looking for? Have you actually measured the execution time yet? The math(s) calculations in your code are lilely to have a much bigger impact on speed than the mode of array access. -- Bartc Jun 27 '08 #4

 P: n/a Babak

 P: n/a Babak "Babak" I've developed a C program which contains a large number of vectors and matrices operations. >What does the matrix code look like?--Bartc- Hide quoted text -- Show quoted text - When replying through the Google interface, it helps if you remove this sort of thing. The matrix code is like: my_matrix=matrix(0,n-1,0,n-1); which is equivalent to: /* allocate pointers to rows */ my_matrix=(float **) malloc(n*sizeof(float*)); /* allocate rows and set pointers to them */ my_matrix[i]=(float *) malloc(n*sizeof(float)); i=0,...,n-1 and I access its elements like my_matrix,........... I'm not sure if working with pointers instead of array indices will make any difference in the speed of the code. Bartc already said this but I will repeat it: measure. In particular profile the code. There is no point in doing anything to the array parts if it is, say, some trigonometric functions that are taking the time. Some general observations: (1) This array of pointers method can be either faster or slower than the direct 2D array method. It all depends on the sizes, the access pattern, and the processor. (2) double can be faster than float. (3) If your array sizes are compile-time constants it may pay to declare the arrays rather than allocating them. (4) If the sizes are not constant, C99 can still let you declare the arrays. You need a compiler that does variable length arrays (and you need to not mind loosing some portability). The problem here is that you need a program to measure to find out what is and is not costly, but you want to write using the fastest method (for your type of problem) from the start. It might help to find someone who has done something similar and has measured the performance of different techniques on a similar system. -- Ben. Jun 27 '08 #6

 P: n/a On Sun, 25 May 2008 11:55:05 +0000, Jens Thoms Toerring wrote: Babak I'm not sure if working with pointers instead of array indices willmake any difference in the speed of the code. There's no difference at all between using a[ i ] and *( a + i ) Correct, as far as the language is concerned, but... The index notation is just a bit easier to read for humans, but the compiler will rewrite index to pointer notattion in a first step. ....at least one common compiler (and probably more) does not simply translate [] to * and +, or vice versa. It's not required; all that matters is that you, the programmer, can freely mix them. Whether the compiler translates should not normally be visible to its users, but in this case a minor bug exists that affects [], but not * and +. Jun 27 '08 #7

 P: n/a Babak wrote: Hi, I've developed a C program which contains a large number of vectors and matrices operations. Throughout my code, I used the template from the Numerical Recipes book to define vectors and matrices and access their elements. For example, to define a vector I used the function: my_vector=vector(0,n-1); Which actually allocate the memory as follows: my_vector = (float *) malloc ( n*sizeof(float) ); and then to access its elements, I used my_vector,......., my_vector[n] Did you really go all the way to element [n], inclusive? That's unfortunate, because no memory has been allocated for that element: You've requested n elements altogether, and the sequence 0,1,...,n-1,n has n+1 values. The execution time of the program is extremely important for me and it should be made as short as possible. I was wondering if the method that I used for vector and matrix notation in my code is the most efficient one. Does anybody know the best method (in terms of efficiency) to define matrices and perform operations on their elements in C? Even a small speedup in my code would be valuable for me. What you've shown in this posting is likely to be as fast as anything else. Or to turn it around, there's no reason to expect it to be any slower. However, I see from the follow-up messages that what you've shown here is *not* actually what you're trying to do, which is to use a *two*-dimensional array. There are three main approaches: 1) If the row and column count are known at compile time, just declare the array as matrix[nrows][ncols] and be done with it. (Variation: use matrix[ncols][nrows] instead; if the operations you're interested in are heavily row-oriented or column-oriented, interchanging subscripts *might* make a difference. This should be investigated for the other approaches, too.) 2) Allocate a one-dimensional array of pointers to rows (columns), and for each of them allocate a one-dimensional row (column). I gather this is the arrangement the macros you're now using will produce. 3) Allocate one big nrows*ncols block of memory, and do the indexing "by hand:" matrix[i][j] <==block[i*ncols+j] (or block[i+j*nrows]). A macro can might make the index calculation more readable; be lavish with parentheses. The multiplications may look scarily slow, but the compiler will probably find ways to perform "strength reduction" on them. Which of these three (six) will be fastest on your machine with your compiler and your algorithms? Would it be worth while to make the rows (columns) a little longer than necessary and use just the first ncols (nrows) positions, in hopes of getting better behavior from memory caches? The only way to tell for sure is to measure, measure, measure. -- Eric Sosman es*****@ieee-dot-org.invalid Jun 27 '08 #8

 P: n/a On Sat, May 24, 2008 at 06:39:32PM -0700, Babak wrote: > The matrix code is like: my_matrix=matrix(0,n-1,0,n-1); which is equivalent to: /* allocate pointers to rows */ my_matrix=(float **) malloc(n*sizeof(float*)); /* allocate rows and set pointers to them */ my_matrix[i]=(float *) malloc(n*sizeof(float)); i=0,...,n-1 I think the numerical recipes matrix routine does _not_ work like this. my_matrix has to be declared as float**, then it rather does: int i; my_matrix= malloc(n*sizeof(float*)); /* as you wrote */ my_matrix=malloc(n*n*sizeof(float*)); /* as you wrote */ for(i=1;i

 P: n/a jt@toerring.de (Jens Thoms Toerring) writes: Babak I'm not sure if working with pointers instead of array indices willmake any difference in the speed of the code. There's no difference at all between using a[ i ] and *( a + i ) The index notation is just a bit easier to read for humans, but the compiler will rewrite index to pointer notattion in a first step. That's why you can even write 'i[a]' instead of 'a[i]', both get translated to '*(a+i)'. Right, but there is a difference, at least potentially, between a[i] and *p. For example, consider the two equivalent loops in this program: #include int main(void) { #define LEN 4 double arr[LEN] = { 1.2, 3.4, 5.6, 7.8 }; int i; double *p; for (i = 0; i < LEN; i ++) { printf("%g ", arr[i]); } putchar('\n'); for (p = arr; p < arr+LEN; p ++) { printf("%g ", *p); } putchar('\n'); return 0; } In the first, you're implicitly doing a multiplication and an addition to compute arr[i]. In the second, you're just doing a dereference; the more expensive multiplication has been "strength-reduced" into repeated addtion in "p ++". *But* this strength-reduction optimization is something that modern compilers are often able to do for you. In the old days, it made sense to use the pointer form because it could be substantially faster. Today, such micro-optimizations are just as likely to inferfere with the optimizer and give you worse code. -- Keith Thompson (The_Other_Keith) ks***@mib.org Nokia "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Jun 27 '08 #10

 P: n/a On May 25, 8:23*am, Babak

### This discussion thread is closed

Replies have been disabled for this discussion. 