Re: [EGN] Hoisting Loop Invariants (Was: Re: [EGN] Numerical Accuracy)

From: Randy Howard (randyhoward_at_FOOverizonBAR.net)
Date: 09/13/04 

Date: Mon, 13 Sep 2004 16:16:29 GMT

In article <f5dda427.0409122350.1eeec956@posting.google.com>, spinoza1111
@yahoo.com says...
> EMonk <emonk@slingshot.no.uce> wrote in message news:<1095042898.663397@ftpsrv1>...
> > Edward G. Nilges wrote:
> > Randy posted COMPILABLE C code, as well as the output of that code when
>
> I am unimpressed by "compilable" C code when it is posted in bad faith
> as part not of technical exchange but of character assassination.

It was not posted in bad faith. I genuinely wanted to *know* whether or
not your claims were correct, before claiming otherwise. This is one of
the key differences between us Nilges, I actually try and find out if what
I say is true before saying it, rather than avoiding facts after I have
claimed something counter to them. Making up excuses like "in bad faith"
to justify burying you head in the sand (or elsewhere) does not change
that.

If the results had provided evidence that your claim was accurate, I would
have posted those results here. The reason for posting the code was so
that my claims could be verified (something you care not one iota about
in your own claims) and so that others with different compiler and system
platforms might also experiment and see if perhaps there was a magical
compiler out there somewhere that did as you claim. Several have tried,
to date nobody has posted a combination that does verify your statements.

Perhaps you can, since you made the claim yourself, identify a compiler
which performs the optimizations you claim?

> Programming, in and of itself, has long been known to be a trivial and
> nasty skill

Primarily to those who do not understand it, perhaps.

> (which I mastered in 1971)

If that were true, you must have had enough fun in the 70's to erase
all evidence of it today.

> > While this may be true of certain practices, hoisting loop invariants is
> > not one of them. In a large number of cases manually hoisting those
> > invariants can lead to large improvements in efficiency... as has been
> > demonstrated. I'm sorry that you aren't capable of understanding this,
> > but it is true nonetheless.
>
> I'd be interested to know what those instances are apart from the fact
> that I won't accept any examples from you or Randy, since you are
> behaving in bad faith.

Translation: EGN will pretend that he is still correct, despite evidence
to the contrary. Nick Landsberg has himself done as your ask, and he is
not "one of those", so what's your excuse?

> What they MEAN is you "know" independent of the compiler's analysis
> that the variable may be hoisted, and in many cases I've seen, this
> "knowledge" makes it impossible to change the program to another form
> without breaking the "optimization".

What the hell does that mean? It is not impossible, it is trivial. A
simple #ifdef was sufficient to achieve *both* modes and see their
impact. You know this. Pretending that you didn't read it (and in
all likelihood verified the results yourself) doesn't change that.

> IF the compiler doesn't know that the variable is loop invariant, but
> the programmer has this knowledge, then the programmer should not use
> the knowledge so as to avoid making the program unmaintainable at a
> deep and semantic level.

This is completely wrong. You are just playing a silly little CYA game
now, the above paragraph is probably as close to an admission as we'll
see here. A program that uses idiomatic and classically trained practices
such as moving loop invariants outside of loops is not unmaintainable.
It may be unreadable to sociologist poseurs attempting to work in a field
for which they are not qualified, but it is certainly maintainable by
almost anyone who is so qualified.

> > Keep in mind that the specifics here are from YOUR code. You're the one
> > who thinks it's a good idea to calculate the length of an invariant
> > string in a loop, regardless of the blatant inefficiency of doing so.
>
> Guy is here referring to one incident where the length was
> pragmatically bounded by the length of a line entered by hand and has
> made himself look repeatedly foolish by trying to base charges of
> incompetence on this practice.

Even with short strings, the kind which can be easily entered by hand on
the command line to a program, your claims are proven false. You can
repeat the lie above all you like, the empirical data PROVES otherwise.

> strlen(s) is semantically identical to Len(s) in any language where the
> length of s is stored in a word adjacent to the start of the string and
> as such, stylistically, there are strong arguments (based on occam's
> razor) for NOT, in a case where the length is bounded, creating a temporary
> variable with the length.

Obviously this is incorrect, for if it where accurate, there would be
no demonstrable impact on performance, with or without the optimizer,
in any language. There is no danger in creating temporary variables,
and writing code that is dependent upon non-portable knowledge of the
inner representation of specific data types is a junior mistake, sadly
the kind we are all too familiar with from you.

> In some environments (where the length of s is sufficiently bounded,
> either pragmatically) the creation of a temporary variable can even take
> more time than the strlen calculation (which in a C environment can be
> one instruction to find the offset of the Nul character).

Interesting. Post sample code, and test results from an environment
where your tests verify your claims. I would be very interested in
see that. I suspect for the time being that in any example in which
the loop was doing actual work and not just spinning in a tight loop
calling strlen() and nothing else, that the time to create the temp
variable would disappear in the noise, or be a constant adder, rather
than an exponential adder as your alternate code is in C.

Regardless of the outcome, it is obvious that the effect of using your
code might be trivially faster (one of your favorite micro optimizations
eh?) on some platform, but the risk is that will exhibit horrid
performance elsewhere. Clearly the downside risk is orders of magnitude
worse than the "upside" potential of such a convention. As such, the
idiomatic use of hoisting in the source itself is far more likely to
perform well in all cases, including C, which is still the most widely
used programming language on the planet.

> I am certain that other benchmarks will get different results,
> benchmarks having this tendency.

Fine, post one of your own choosing which verifies your claim. It's
really quite simple, even you should be capable of doing it.

> Not when I'm not wrong. This entire exchange is complete bull***.
> When the string s is pragmatically bounded by the length of the input
> string, strlen is definitely more readable even in a loop since the
> information is obtained and exists in one point...and, as I have
> indicated above, the allocation of the temp variable is itself a cost
> which you have conveniently ignored.

Childish. The usenet equivalent to sticking your fingers in your ears
and screaming "nanny nanny boo boo". It is not more readable, it is
counter-intuitive. Trained professionals are so used to it being the
opposite as you recommend that it would be counter-productive.

> But when as in the original example the length of the string is in
> fact bounded in all possible instances of the problem as considered,
> then the strlen is more readable, and possibly more efficient, than
> the creation of a separate variable.

Prove it. Post code that verifies your claim. Go ahead, show us that
you're not just 50 lbs of hot air in a 1 lb bag.

> Nothing is "proven" in this way except a limited set of empirical
> statements about one's various hobby-horses. And, the initial mistake
> is to think in terms of C almost exclusively. One of C's drawbacks is
> it can't be optimized fully because of aliasing.

Once again Nilges reverses himself. Now it can't be optimized, but just
a few days it could. Obviously he is reading the posts, he just pretends
that he is not. The reason we are thinking in terms of C is because the
CODE THAT YOU POSTED WAS IN C. You have claimed recently that you do
know C, very well, and have been an expert programmer since 1971. As such,
there is no excuse for using a construct in a language that you supposedly
know, which results in exponential runtime impacts. That is gross
incompetence, the kind for which you would be reprimanded at a minimum
for on the first occurrence in a professional development team. Attempting
to defend it on the grounds of a questionable, at best, readability claim
is ridiculous.

> Efficiency consists in a solution which scales up to large volumes
> properly while being readable and maintainable, and I am surprised that
> you haven't learned this.

Interesting. Your own definition does not support your claims. You
constantly make references to "bounded strings!, bounded strings!" in
defense of your code, yet you claim that any solution that does not
scale is not efficient. I accept your admission. 

-- 
Randy Howard
To reply, remove FOOBAR.
Loading