Writing For loops efficiently

Question

I am constructing the partial derivative of a function in C. The process is mainly consisted of a large number of small loops. Each loop is responsible for filling a column of the matrix. Because the size of the matrix is huge, the code should be written efficiently. I have a number of plans in mind for the implementation which I do not want get into the details.

I know that the smart compilers try to take advantage of the cache automatically. But I would like to know more the details of using cache and writing an efficient code and efficient loops. It is appreciated if provide with some resources or websites so I can know more about writing the efficient codes in terms of reducing memory access time and taking advantage guy.

I know that my request my look sloppy, but I am not a computer guy. I did some research but with no success. So, any help is appreciated.

Thanks

http://stackoverflow.com/questions/9936132/why-does-the-order-of-the-loops-affect-performance-when-iterating-over-a-2d-arra, http://stackoverflow.com/questions/12264970/why-is-my-program-slow-when-looping-over-exactly-8192-elements, http://stackoverflow.com/questions/11413855/why-is-transposing-a-matrix-of-512x512-much-slower-than-transposing-a-matrix-of — Mysticial, Mar 02 '13 at 06:37
If the matrix is one big array in C, you should fill it row by row, not column by column, to not hurt yourself with cache misses. — Ben Zotto, Mar 02 '13 at 06:37
The matrix is sparse and therefore, three vectors are used to describe the Matrix. — Pouya, Mar 02 '13 at 06:52
@Pouya Oh... if the matrix is sparse, that changes ***everything***... — Mysticial, Mar 02 '13 at 06:54
What's inside the innermost loop? Are you calling the function you're taking the partial derivative of in there? If so, what you do outside it probably won't matter much. — Mike Dunlavey, Mar 02 '13 at 15:26

score 5 · Answer 1 · answered Mar 02 '13 at 06:36

5

Well written code tends to be efficient (though not always optimal). Start by writing good clean code, and if you actually have a performance problem that can be isolated and addressed.

answered Mar 02 '13 at 06:36

Pieter Geerkens

11,775
2
32
52

4

This is definitely not the right type of question to be playing the premature optimization card... – Mysticial Mar 02 '13 at 06:38
@Mystical: You said it, not me; I merely considered saying it. ;-) – Pieter Geerkens Mar 02 '13 at 06:44
It looked like you were implying it. :P – Mysticial Mar 02 '13 at 06:45

score 2 · Answer 2 · edited May 23 '17 at 11:57

It is probably best that you write the code in the most readable and understandable way you can and then profile it to see where the bottlenecks really are. Often times your conception of where you need efficiency doesn't match up with reality.

Modern compilers do a decent job with many aspects of optimization and it seems unlikely that the process of looping will itself be a problem. Perhaps you should consider focusing on simplifying the calculation done by each loop.

Otherwise, you'll be looking at things such as accessing your matrix row by row so that you take advantage of the row-major storage order C uses (see this question).

You'll want to build your for loops without if statements inside because if statements create what is called "branching". The computer essentially guesses which option will be right and pays a sometimes hefty option if it is wrong.

To extend that theme, you want to do as little inside the for loop as possible. You'll also want to define it with static limits, e.g.:

for(int i=1;i<100;i++) //This is better than
for(int i=1;i<N/i;i++) //this

Static limits means that very little effort is expended determining if the for loop should keep going. They also permit you to use OpenMP to divy up the work in the loops, which can sometimes speed things up considerably. This is simple to do:

#pragma omp parallel for
for(int i=0;i<100;i++)

And, walla! the code is parallelized.

Writing For loops efficiently

2 Answers2