From: Nick Keighley on
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
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
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
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
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?