|
Florin Jurcovici wrote: That was the case with ancient compilers/interpreters.
If anything, modern CPU architectures make these things more complex than they have ever been before: pipelining, prefetching, synchronising processes - you name it. Passing function arguments is just one of many things to take care of, and many of these things didn't even exist 20 years ago.
Acually, because modern compilers are so much smarter and modern hardware so much more capable, that in fact increases the cost of function calls: within a single function, prefetching and pipelining allows the CPU to process a whole series of consecutive commands much faster. Interrupting the control flow by calling another function however prevents all this optimization! Suddenly the whole processing chain comes to a full stop! The context is saved, the new context created, and a new pipeline slowly set into motion. The context change isn't the big thing. You're right about that. But preventing your highly optimized parallel pipelining multicore CPU from optimizing the tasks with it's inherent parallelism is going to adversely affect program performance.
This, by the way, is also one of the bigger challenges of parallel programming: spreading a simple loop (nested or not) on multiple processors is only going to help up to a certain point: the cost of context change and not going to be able to take full advantage of CPU-internal parallelism is much higher than many people think.
You may not be aware of it, but you are using parallel programming as well: the compilers will take advantage of your CPUs or Multi-CPU System's inherent parallelism as much as it can. But it cannot parallize code across function call boundaries! Even if your code doesn't lend itself well to parallelization - at the very least the CPU can load chunks of the big array you're iterating through into the L2 cache, so reading and writing will be much faster. If you extract your inner loops into another function however, the higher level function has no way of knowing which data that function accesses, and therefore won't preload anything. Instead, each function call will load the data range needed there.
That's fine if the first call accesses only the first part of the big array, and the next calls consecutive parts. But there's no guarantee for that: maybe the first call reads the 1st, 11th, 21st, 31st, etc. element, the second call reads the 2nd, 12th, 22nd, etc.. In that case, each function call will load the entire array, with just a little offset. In short, the decision of putting that internal loop into a separate function costs you the additional time needed for reading the entire data structure into the L2 cache. For. Every. Single. Call.
Florin Jurcovici wrote: In C++, you can declare the functions inline
Careful - declaring them inline doesn't make them so. inline is just a request to the compiler to do this, but it will not do so for every function*, and even if it does, only up to a limited call-depth. Also, AFAIK it's impossible to inline recursive functions.
*: In my experience, there are functions that the compiler can't inline, as well as those that it won't, for one reason or another. The documentation I've found so far was mostly vague, and indicated that the compiler, depending on the context, may sometimes decide this way or that...
it's mostly templated functions (or maybe member functions of templated classes) that a compiler may not want to inline, but I'm almost certain I've had cases of non-template functions that were also not inlined (possibly on the basis that it was too long, I don't know)
|
|
|
|
|
That's exactly the kind of pitfall DB programmers fall into. You have to see the whole picture if you wish to optimize such involved queries. You may have successfully hidden the fact there are 3+ nested loops, but that doesn't do away with them, and all you achieved is that it's now impossible to see any possible relations that may help you optimize away some of the looping:
e. g. if you're checking a motorway network, you may want to restrict your loops only to such vehicles allowed on motorways in CheckNetworkSpeeds() . By separating the loops you make it much harder to spot such optimizations.
Wasn't the whole point of avoiding nesting to make the code easier to maintain?
|
|
|
|
|
Depends
thatrajaNobody remains a virgin, Life screws everyone 
|
|
|
|
|
Do you use them? I feel sorry for you... 
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braun
|
|
|
|
|
Use as many as the algorithm requires.
If you need to examine every single point in a three dimensional space, then trying to do it without nesting three deep is messy, inefficient, and wastefull.
for (int x = 0; x < 100; x++)
{
for (int y = 0; y < 100; y++)
{
for (int z = 0; z < 100; z++)
{
...
}
}
}Worse, moving the nesting to methods to "make it look tidier" may well hide the amount of processing that is going on since it is no longer obvious that the single instruction in the middle of the centre loop is being executed 100 * 100 * 100 times, not just 100 times...
Having a blanket rule "This is messy!" is wrong, and counter productive.
Ideological Purity is no substitute for being able to stick your thumb down a pipe to stop the water
|
|
|
|
|
|
From that article:
Here's a common example:
double sum = 0;for (int i = 0; i < array.length; i++) { sum += array[i];}
What's going on here? I've been programming for years, and I'm comfortable speed-reading this idiom; it's obviously a summation of a set of values in an array. But to actually read this block of code, I need to process about 30 tokens spread out over four lines.
And here are programmers writing pragma, karma and dogma at the beginning of their programs and they have the gall to complain about a for loop? 
|
|
|
|
|
I never go further than 26 levels, because then I've run out of variables to control the loops with.
I could of course start using aa, ab, ac...but that gets confusing.
|
|
|
|
|
I like to use Z1, Z2, Z3, etc... Then I can have hundreds and thousands of nested loops
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braun
|
|
|
|
|
Problem with that is the indentation gets too large and you keep having to scroll to the right.
|
|
|
|
|
Buy a wider monitor.
Ideological Purity is no substitute for being able to stick your thumb down a pipe to stop the water
|
|
|
|
|
Mmmmmm....Hundreds and Thousands[^]
Ideological Purity is no substitute for being able to stick your thumb down a pipe to stop the water
|
|
|
|
|
mmmmmmmmmmmm, doughnut 
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braun
|
|
|
|
|
Wrong of you to use a thru z as control variables.
Use a1, a2, ......... and it will not be confusing at all! 
|
|
|
|
|
Add, as comments to the end of the loops, the containing logic and you can have as many nested as required...
for(int i=0; i<100; i++) {
for(int j=0; j<100; j++) {
for(int k=0; k<100; k++) {
}
}
}
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
|
|
|
|
|
As many as required, but no more.
Limiting the number of nested loops is like prescribing a length for variable names:
"Variable names must be at least six characters and no more than 31 characters in length, must begin with an upper case alphabetic character, may not include an underscore, and must consist of one or more complete English words, signified through use of upper case characters at the beginning of each word".
Picking names will be like playing Scrabble...
Software Zen: delete this;
|
|
|
|
|
Sounds like a valid password policy!
'As programmers go, I'm fairly social. Which still means I'm a borderline sociopath by normal standards.' Jeff Atwood
'I'm French! Why do you think I've got this outrrrrageous accent?' Monty Python and the Holy Grail
|
|
|
|
|
Is this from a wikipedia study:
Shameel wrote: Most people would agree that three levels is acceptable
|
|
|
|
|
How about looping through a n-dimensional table where n>3?
|
|
|
|
|
I would say that a rule is ok and if that rule gets broken, a good justification as to why it was broken needs to be given.
One can always refactor code to eliminate loops/complexity.
I feel that it is especially important if the code needs to be tested to make such a rule. (else the testing cost more money than you're making on the project)
Bad Example:
String name[100][100] = fill_string();
void loop_level_1()
{
for(int i=0; i<100; i++)
{
loop_level_2(i);
}
}
void loop_level_2(int i)
{
for(int j=0; j<100; j++)
{
loop_level_3(i, j);
}
}
void loop_level_3(int i, int j)
{
for(int k=0; k<100; k++)
{
print(k + ": " + name[i][j]);
}
}
This way, each function can be tested in isolation.
"Program testing can be used to show the presence of bugs, but never to show their absence."
<< please vote!! >>
|
|
|
|
|
The question is why you think nested loops are broken in the first place?
The only thing you achieve is separate the context in which the need for nested loops arose, and therefore remove the ability to spot possible optimizations easily.
|
|
|
|
|
Not with you regarding the question you are asking... I was referring to the braking of the rule, not the loop.
"Program testing can be used to show the presence of bugs, but never to show their absence."
<< please vote!! >>
|
|
|
|
|
Refer to:
http://en.wikipedia.org/wiki/Cyclomatic_complexity[^] more specifically the section on "Implications for Software Testing", for a better understanding from where I'm coming from.
"Program testing can be used to show the presence of bugs, but never to show their absence."
<< please vote!! >>
|
|
|
|
|
Interesting article. However, according to these definitions a triple nested loop only has a complexity of 4, and the inventer suggested to break up code when exceeding a maximum complexity of 10(!).
(1)->(2)->(3)->(4)->(5)->(6)->(7)->(8)
^ ^ ^ | | |
| | | | | |
| | (9)<--- | |
| (0)<------------- |
(a)<-----------------------
M = E − N + 2P = 13 - 11 + 2*1 = 4
Also, extracting the inner loop into a separate function does not even help, as it increases P:
(1)->(2)->(3)---(call)-->(4)->(5)->(6)
^ ^ | |
| | | |
| (7)<------------- |
(8)<-----------------------
M1 = E1 − N1 + 2P1 = 9 - 8 + 2*1 = 3
(1)->(2)->(3)->(4)
^ |
| |
(5)<---
M2 = E2 − N2 + 2P2 = 5 - 5 + 2*1 = 2
and
M = E - N + 2P = 14 - 13 +2*2 = 5
So, by extracting a loop into another function, you are actually increasing the complexity, instead of reducing it!
|
|
|
|
|
"One common testing strategy, espoused for example by the NIST Structured Testing methodology, is to use the cyclomatic complexity of a module to determine the number of white-box tests that are required to obtain sufficient coverage of the module."
The word module that they are referring to is basically a function.
So the complexity generally gets measured on the function and not the whole program. Therefor braking a nested if into function calls will actually reduce/spread the complexity of each function making them simpler and easier to test.
So instead of having one function with example a complexity of 25, you'll have 3 functions with a complexity of 10 each.
"Program testing can be used to show the presence of bugs, but never to show their absence."
<< please vote!! >>
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
