From: Nick Keighley on 29 Apr 2010 04:03 On 28 Apr, 13:59, "Daniel T." <danie...(a)earthlink.net> wrote: > In article > <dbac22e7-4667-485e-b829-2505e2bd9...(a)q23g2000yqd.googlegroups.com>, > SG <s.gesem...(a)gmail.com> wrote: > > On 28 Apr., 11:02, Richard Heathfield wrote: > > > Juha Nieminen wrote: <snip> > > > > Value_t* MyClass::findValue(const Value_t& value) > > > > { > > > > for(size_t xInd = 0; xInd < data.size(); ++xInd) > > > > for(size_t yInd = 0; yInd < data[xInd].size(); ++yInd) > > > > for(size_t zInd = 0; zInd < data[xInd][yInd].size(); ++zInd) > > > > { > > > > if(data[xInd][yInd][zInd] == value) > > > > return &data[xInd][yInd][zInd]; > > > > } > > > > return 0; > > > > } > > > > > In any case, your loop condition expressions do not correctly describe > > > the conditions under which the loop will terminate. > > > This was probably intentional. Expressing it "correctly" forces you to > > write slightly more comprex loop conditions which contain some kind of > > "i'm done"-flag like this: > > > Value_t* MyClass::findValue(const Value_t& value) > > { > > Value_t* result = 0; > > for(size_t xInd = 0; !result && xInd < data.size(); ++xInd) > > for(size_t yInd = 0; !result && yInd < data[xInd].size(); > > ++yInd) > > for(size_t zInd = 0; !result && zInd < data[xInd] > > [yInd].size(); > > ++zInd) > > { > > if(data[xInd][yInd][zInd] == value) > > result = &data[xInd][yInd][zInd]; > > } > > return result; > > } > > > I don't know about you but I like the first version better. It's more > > concise. I find it easier to see what the loop's doing. Maybe it's > > just me. I guess I'm used to these kinds of loops. > > Since the sample code is obviously in c++, I would rather see something > like: > > Iterator it = data.begin() > while(it != data.end() && *it != value) > ++it; > return it != data.end(); is a for-loop regarded as poor style in C++? for (Iterator it = data.begin(); it != data.end() && *it != value; + +it) ; -- "Perilous to us all are the devices of an art deeper than we possess ourselves." Gandalf The Grey (discussing Template Meta-programming)
From: Tim Rentsch on 29 Apr 2010 04:20 Keith H Duggar <duggar(a)alum.mit.edu> writes: > On Apr 24, 6:41 pm, James Kanze <james.ka...(a)gmail.com> wrote: >> On Apr 24, 5:12 pm, "Daniel T." <danie...(a)earthlink.net> wrote: >> >> > "Leigh Johnston" <le...(a)i42.co.uk> wrote: >> >> [...] >> >> > In C and C++, goto is sufficiently restricted that as long as >> > your functions are small, it is largely harmless. >> >> In C and C++, if your functions are small enough, goto is >> largely harmless. And also useless. All of the examples I've >> seen defending goto introduce excessively complex functions in >> order to justify it. > > The Kuzmin circle tracing algorithm is certainly not "excessively > complex" and is an (elegant) example of goto being /necessary/ to > to provide the optimal solution in some very real and important > scenarios. There was a moderated flame war about this nine months > ago culminating with these final posts > > http://groups.google.com/group/comp.lang.c++.moderated/msg/3ac2368e485e740d > http://groups.google.com/group/comp.lang.c++.moderated/msg/5beca2fac77f7ab9 > > that empirically proved beyond any contestation at the time that > the goto version was optimal in some scenarios. All the source > code, scripts, etc are still available at > > http://www.duggar.org/pub/code/circle/ > > to anyone who wishes to /rationally/ challenge the results with > empirical evidence. Otherwise continued unconditional anti-goto > preaching is simply anti-intellectual religion and certainly not > computer science. Good of you to make this available. I do have some other comments further down, but I think the effort and general approach should be applauded. > [snip] > > Finally, if you do try and measure results note that the provided > code takes exceptional care when it comes to certain things that > to the naive might seem unimportant such as removal of constants, > randomization, control of inlining, avoidance of monolithic > compilation, etc. That is all /necessary/ for accurate profiling > which can be tricky to say the least. That was one source of the > disagreement in that original thread, ie one participant who > thought he was "all that" was simply ignorant of many of those > real world profiling and measurement considerations. Some comments and suggestions -- Good points: The measurement methodology looks fairly good. The things you mention certainly can have large effects on performance. It might be good to report results also for different optimization levels (because different algorithms respond differently to different levels of optimization, and it's good to know what those differences are). Bad points: The output is baffling. No labels on the columns, no units shown for the different measurements. What is being measured exactly, and what do the different columns represent? The output should say, in English that is at least decipherable. Missing (?) points: It isn't clear what ranges of radius values are being measured. In this kind of measurement it's valuable to see results for several restricted ranges of argument values (say 1-10, 10-50, 50-250, 500+), as well as several weighted averages. Perhaps some of these different possibilities are shown, the unlabelled output makes it difficult to tell (and one should never have to rummage around in the source code to discover such things). Returning to the algorithm... Clearly it's a clever person who devised the algorithm. Is it excessively complex? Maybe not, but it isn't excessively simple either. To say that another way, although it's easy in some sense to see what it's doing, it's harder to say how it works or why. For reference I am talking about circle0 (shown as in the original except for some white space changes, and leaving out 'inline'): int circle0( int r ){ int x = r; int y = 0; int e = - r / 2; if( r & 1 ){ --e; goto odd; } even: if( y >= x ) return y+1; e += y++; if( e >= 0 ) e -= --x; odd: if( y >= x ) return y+1; e += ++y; if( e >= 0 ) e -= --x; goto even; } There's a much simpler way of coding this algorithm (ie, one that goes through the same sequence of x,y values): int circle_simple( int r ){ int x = r; int y = 0; int e = -r; while(1){ if( y >= x ) return y+1; e += y+y+1, y++; if( e >= 0 ) x--, e -= x+x; } } In my measurements circle_simple performed better than circle0 by between 1 and 8 percent (for large radius values), and by larger amounts, up to 25 percent, for smaller radius values. Of course, YMMV, and I'm sure it will in other environments, but certainly this simpler algorithm is at least competitive performance wise. (The smaller code footprint is another plus.) Given that, the argument that using goto is necessary here seems a little bit overstated. > Subsequently I discussed that flame war with one of the worlds > genius compiler writers who confirmed the necessity of the inlining > etc controls explained above. However, he also added that in his > experience it is pointless to argue with the anti-goto mob because > it is a religion that ignores all inconvenient empirical evidence. Essentially the same thing could be said of the pro-goto mob. P.S. I've kept the original set of newsgroups even though I don't read most of them.
From: Daniel T. on 29 Apr 2010 07:51 Nick Keighley <nick_keighley_nospam(a)hotmail.com> wrote: > On 28 Apr, 13:59, "Daniel T." <danie...(a)earthlink.net> wrote: > > �SG <s.gesem...(a)gmail.com> wrote: > > > On 28 Apr., 11:02, Richard Heathfield wrote: > > > > Juha Nieminen wrote: > > <snip> > > > > > > Value_t* MyClass::findValue(const Value_t& value) > > > > > { > > > > > for(size_t xInd = 0; xInd < data.size(); ++xInd) > > > > > for(size_t yInd = 0; yInd < data[xInd].size(); ++yInd) > > > > > for(size_t zInd = 0; zInd < data[xInd][yInd].size(); ++zInd) > > > > > { > > > > > if(data[xInd][yInd][zInd] == value) > > > > > return &data[xInd][yInd][zInd]; > > > > > } > > > > > return 0; > > > > > } > > > > > > > In any case, your loop condition expressions do not correctly describe > > > > the conditions under which the loop will terminate. > > > > > This was probably intentional. Expressing it "correctly" forces you to > > > write slightly more comprex loop conditions which contain some kind of > > > "i'm done"-flag like this: > > > > > � Value_t* MyClass::findValue(const Value_t& value) > > > � { > > > � � Value_t* result = 0; > > > � � for(size_t xInd = 0; !result && xInd < data.size(); ++xInd) > > > � � � for(size_t yInd = 0; !result && yInd < data[xInd].size(); > > > � � � � � ++yInd) > > > � � � � for(size_t zInd = 0; !result && zInd < data[xInd] > > > [yInd].size(); > > > � � � � � � ++zInd) > > > � � � � { > > > � � � � � if(data[xInd][yInd][zInd] == value) > > > � � � � � � result = &data[xInd][yInd][zInd]; > > > � � � � } > > > � � return result; > > > � } > > > > > I don't know about you but I like the first version better. It's more > > > concise. I find it easier to see what the loop's doing. Maybe it's > > > just me. I guess I'm used to these kinds of loops. > > > > Since the sample code is obviously in c++, I would rather see something > > like: > > > > Iterator it = data.begin() > > while(it != data.end() && *it != value) > > � �++it; > > return it != data.end(); > > is a for-loop regarded as poor style in C++? > > for (Iterator it = data.begin(); it != data.end() && *it != value; + > +it) > ; No, but I consider an empty statement poor style. In this specific case, I can't help but wonder what you were planning on returning since you throw away the result. 'it' doesn't live outside the for loop in C++. The point of my example was to show that the problem with Juha's code wasn't that it had multiple exits, but rather that it was at the wrong level of abstraction and therefore seemed to need multiple exits. Richard, removed the multiple exits without fixing the abstraction problem and he ended up with a worse result.
From: tonydee on 30 Apr 2010 04:58 On Apr 29, 8:51 pm, "Daniel T." <danie...(a)earthlink.net> wrote: > Nick Keighley <nick_keighley_nos...(a)hotmail.com> wrote: > > On 28 Apr, 13:59, "Daniel T." <danie...(a)earthlink.net> wrote: > > > SG <s.gesem...(a)gmail.com> wrote: > > > > On 28 Apr., 11:02, Richard Heathfield wrote: > > > > Value_t* MyClass::findValue(const Value_t& value) > > > > { > > > > Value_t* result = 0; > > > > for(size_t xInd = 0; !result && xInd < data.size(); ++xInd) > > > > for(size_t yInd = 0; !result && yInd < data[xInd].size(); > > > > ++yInd) > > > > for(size_t zInd = 0; !result && zInd < data[xInd] > > > > [yInd].size(); > > > > ++zInd) > > > > { > > > > if(data[xInd][yInd][zInd] == value) > > > > result = &data[xInd][yInd][zInd]; > > > > } > > > > return result; > > > > } > > > > > I don't know about you but I like the first version better. It's more > > > > concise. I find it easier to see what the loop's doing. Maybe it's > > > > just me. I guess I'm used to these kinds of loops. > > > > Since the sample code is obviously in c++, I would rather see something > > > like: > > > > Iterator it = data.begin() > > > while(it != data.end() && *it != value) > > > ++it; > > > return it != data.end(); > [snip] > The point of my example was to show that the problem with Juha's code > wasn't that it had multiple exits, but rather that it was at the wrong > level of abstraction and therefore seemed to need multiple exits. > Richard, removed the multiple exits without fixing the abstraction > problem and he ended up with a worse result. That's a very insightful point, and in many ways good practice - particularly if it prevents client code coupling to the implementation or layout of your container. In this case though, the find function might be a member of the container - inside the encapsulation - and coupling quite acceptable. Further, say you want something just marginally more complicated - like skipping every second value of yInd: you can't do that with your iterator (the x/y/z boundaries are lost), but it would be a trivial modification to the explicit loop. Localisation, concision, directness and simplicity must be balanced against abstraction - the latter is not always better. So, while I agree an iterator may sometimes be good, I strongly disagree that the explicitly nested loops were inherently at the wrong level of abstraction, yielding a necessarily worse result. Cheers, Tony
From: Daniel T. on 30 Apr 2010 10:36
tonydee <tony_in_da_uk(a)yahoo.co.uk> wrote: > On Apr 29, 8:51�pm, "Daniel T." <danie...(a)earthlink.net> wrote: > > Nick Keighley <nick_keighley_nos...(a)hotmail.com> wrote: > > > On 28 Apr, 13:59, "Daniel T." <danie...(a)earthlink.net> wrote: > > > > �SG <s.gesem...(a)gmail.com> wrote: > > > > > On 28 Apr., 11:02, Richard Heathfield wrote: > > > > > > > > > > � Value_t* MyClass::findValue(const Value_t& value) > > > > > � { > > > > > � � Value_t* result = 0; > > > > > � � for(size_t xInd = 0; !result && xInd < data.size(); ++xInd) > > > > > � � � for(size_t yInd = 0; !result && yInd < data[xInd].size(); > > > > > � � � � � ++yInd) > > > > > � � � � for(size_t zInd = 0; !result && zInd < data[xInd] > > > > > [yInd].size(); > > > > > � � � � � � ++zInd) > > > > > � � � � { > > > > > � � � � � if(data[xInd][yInd][zInd] == value) > > > > > � � � � � � result = &data[xInd][yInd][zInd]; > > > > > � � � � } > > > > > � � return result; > > > > > � } > > > > > > > > > > I don't know about you but I like the first version better. It's more > > > > > concise. I find it easier to see what the loop's doing. Maybe it's > > > > > just me. I guess I'm used to these kinds of loops. > > > > > > > > Since the sample code is obviously in c++, I would rather see something > > > > like: > > > > > > > > Iterator it = data.begin() > > > > while(it != data.end() && *it != value) > > > > � �++it; > > > > return it != data.end(); > > [snip] > > The point of my example was to show that the problem with Juha's code > > wasn't that it had multiple exits, but rather that it was at the wrong > > level of abstraction and therefore seemed to need multiple exits. > > Richard, removed the multiple exits without fixing the abstraction > > problem and he ended up with a worse result. > > That's a very insightful point, and in many ways good practice - > particularly if it prevents client code coupling to the implementation > or layout of your container. In this case though, the find function > might be a member of the container - inside the encapsulation - and > coupling quite acceptable. Further, say you want something just > marginally more complicated - like skipping every second value of > yInd: you can't do that with your iterator (the x/y/z boundaries are > lost), but it would be a trivial modification to the explicit loop. > Localisation, concision, directness and simplicity must be balanced > against abstraction - the latter is not always better. So, while I > agree an iterator may sometimes be good, I strongly disagree that the > explicitly nested loops were inherently at the wrong level of > abstraction, yielding a necessarily worse result. In this case, the nested for loops were the wrong level, even if the code was embedded in a member function. For your, rather arbitrary, modification they may not be, but even there an iterator that knows how to skip every second value of yInd might be more appropriate IMHO (if such a construct is needed once for this container type, it probably is needed in other places and duplicating the nested for loop construct is even worse than putting it in once. That said, finding examples where multiple returns are a good idea is not hard, even with the code I presented something like this: for (Iterator it = data.begin(); it != data.end(); ++it) if (*it == value) return true; return false; Here I have removed the extra conditional by introducing an extra return. It's not how I would write it, but the above is quite acceptable IMHO. There is a general pattern here I think. When there are multiple exit conditions to a loop (there is an && in the exit condition,) and we have to be able to distinguish after the loop which condition caused it to exit, then it may be appropriate to have multiple exits from the loop. I'm just musing here, but what do you guys think? |