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

From: Edward G. Nilges (spinoza1111_at_yahoo.com)
Date: 09/13/04 

Date: 13 Sep 2004 00:50:11 -0700

EMonk <emonk@slingshot.no.uce> wrote in message news:<1095042898.663397@ftpsrv1>...
> Edward G. Nilges wrote:
> > Randy Howard <randyhoward@FOOverizonBAR.net> wrote in message news:<MPG.1bad904be7df72cc9899f7@news.verizon.net>...
> <snip>
> >
> >>Sort of like using "variable hoisting" to express trivial code
> >>modifications which can result in massive performance improvements, even
> >>with compilers known to have quite good optimizers, eh?
> >
> > Ooo, massive performance improvements.
> >
> > Pray present an example of this to substantiate it. For if the
> > optimizer is halfway acceptable, it will hoist in all verifiable
> > cases.
>
> He did that in a post to the Variable Hoisting thread. You dismissed
> that post - apparently without reading it. To quote you:
>
> "I am not going to waste my time, since Randy's misuse of the term
> means he has, in all probabilities, no insights worth my time."
>
> 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.
Programming, in and of itself, has long been known to be a trivial and
nasty skill (which I mastered in 1971) in and of itself and I find it
especially uncongenial when conducted in bad faith.

> compiled with GCC and VC++ both with and without optimisation. Nick
> Landsberg subsequently posted the results of running the same code
> through GCC on an iMac. If you'd like I'll provide another sample as
> substantiation.

I won't read any of it, since you are acting in bad faith so as to
shore up your shaky egoes by dominating this ng (primarily in your
mind).

>
> > Do you mean something boneheaded like finding that the compiler has
> > refused to hoist a variable because in the loop it participates as a
> > reference parameter in a function call, "discovering" that the
> > function used does not modify the variable passed as a reference
> > parameter, and then (instead of changing the function) "hoisting" the
> > variable to preserve your amour propre as a Clever Dick?
> >
> > For many such "manual optimizations" made by "great programmers" which
> > circumvent the automatic optimizer have as their purpose vanity alone.
>
> 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.

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".

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.

>
> > A typical gesture is to FAIL to fix the REAL design error which in
> > this scenario is the fact that the function uses a REFERENCE parameter
> > and not a VALUE parameter. Authoritarian personalities are loth to
> > make genuine changes of this nature.
>
> 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. In fact, considered independent of C
bias and coding monkey-ism, 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.

In fact, some of the arguments for not doing so are based NOT ONLY on
good style ("code what you mean and write it once") but even on
EFFICIENCY. 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).

Indeed, your vanity, and worse your Sodomite unkindness toward the
stranger, is completely blinding you towards the costs of "temp"
variables and although I refuse to look at your benchmarks based on
your behavior, I am certain that other benchmarks will get different
results, benchmarks having this tendency.

> You have been defending that position for long enough to establish quite
> firmly that inflexibility is one of YOUR attributes.
>
> Can't you ever admit that you're wrong?

Not when I'm not wrong. This entire exchange is complete bullshit.
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.

You are free with the word "troll" but this is obviously psychological
transference, since you are terrified by actual collegiality (which
includes being wrong) and as such transfer your fear of isolation to
what you think is a safe target.

>
> > Instead, the problem is compounded by creating a hidden relation
> > between the now hoisted variable, and the by reference call such that
> > when the function is modified to change the variable, the code breaks.
> >
> > Much of what you regard as opportunities to optimize consists of
> > vanity optimization which creates more problems than it solves.
>
> You're prevaricating again. Modifications to the variable are no more a
> problem than modifications to the un-hoisted invariant expression, and
> no more likely. There's no reason to believe that such modifications
> will happen, or that they will happen more often in one form than the other.

You don't even understand the example. IF the variable is passed by
reference then this means the original intent of the code was to
modify it, and to exploit the fact that in the actual text, the
variable is not modified, is to add code-that-will-break when the
reference variable is modified, and also to fail to do due diligence
and to find out why the variable was (1) passed by ref and (2) not
modified.

Of course, it is more "fun" to show what a "great programmer" you are
than to find out why the variable is passed by reference in the first
place.

>
> So FUD aside, you're argument is shown to be irrelevant.
>
> Just to nail this down, so that there's no possibly misinterpretation,
> we're talking about the following code style:
>
> void test_1(char* somestr)
> {
> for (int i = 0; i < strlen(somestr); ++i)
> {
> // do something here
> }
> }
>
> vs:
>
> void test_2(char* somestr)
> {
> int len = strlen(somestr);
> for (int i = 0; i < len; ++i)
> {
> // do something here
> }
> }
>
> While those are simplistic examples, they adequately demonstrate the
> issue. Randy's posted code is more interesting. Personally I'd have
> done it differently, but then I'm not Randy.
>
> You have made a couple of assertions, which I paraphrase as:
>
> 1) There is no - or little - difference in efficiency of the two forms
> when the compiler's optimizer is enabled.

That's a complete and deliberate confusion and a lie, since the use of
strlen in a loop is a separate issue.

In this example, the compiler doesn't know whether somestr is modified
lengthwise by an alias and therefore a C optimizer (as opposed to an
optimizer for a grownup's language with no unnecessary aliasing) will
NOT optimize the strlen, at least without special permission in the
form of an option.

Therefore, if the programmer discovers (while testing first for
correctness and not microefficiency) that the for loop is a hotspot
which is taking too much time (using let us say a code profiler) then
the strlen will have to be manually "hoisted", misusing "hoisting" to
refer to mere good practice.

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.

>
> 2) The second form - where the loop invariant is "hoisted" - is less
> readable and more prone to error.
>
> The first assertion has been disproven by the simple expedient of
> testing the code with various compilers and optimization settings. The

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.

> second remains a matter of opinion, but I strongly disagree with it, as
> do others here.

Retreating inside the herd, I see...the sheep look up...

>
> Defend those assertions if you can.

I've already done so. You and Randy have proven that you are the last
of a breed, that individual who actually wastes his time on issues
which don't matter but are sops to vanity alone.

Efficiency doesn't consist in these contrivances. 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.

Relevant Pages

  • Re: Evolution of PL/I
    ... If the programmer knows which way the loop is running ... In the case of variable BY where the programmer knows the sign but the ... compiler doesn't, I wonder if ABSwould help. ... It doesn't need an optimizer ...
    (comp.lang.pl1)
  • Re: Evolution of PL/I
    ... If the programmer knows which way the loop is running ... In the case of variable BY where the programmer knows the sign but the ... compiler doesn't, I wonder if ABSwould help. ... It doesn't need an optimizer ...
    (comp.lang.pl1)
  • Re: Evolution of PL/I
    ... If the programmer knows which way the loop is running ... compiler doesn't, I wonder if ABSwould help. ... It doesn't need an optimizer ...
    (comp.lang.pl1)
  • Re: The inaugural VB6 vs dot net test
    ... I'm not sure what you mean by that, Ralph? ... But re-arranging code is all in a day's work of an Optimizer. ... may change a While loop into a Do/While wrapped in a Conditional. ... The language design has much to do with the ability to successfully optimize -- one of the prime reasons Fortran was considered historically as a "better" language for computing speed was that the language was specifically designed to minimize the use of features which caused difficulties. ...
    (microsoft.public.vb.general.discussion)
  • Re: is C implementation allowed to terminate an infinite loop?
    ... the programmer intended for it to loop forever. ... I'm not an optimizer expert either, but my understanding is that optimizers generally don't work directly with high-level constructs such as iteration statements, but disassemble your code into a graph and then optimize it by transforming that graph. ... Imagine that at some point the optimizer notices that the only way to reach node B in the graph leads from node A through a complicated knot that performs a lot of operations on local variables but doesn't touch any volatiles or make any I/O calls. ... The choice the optimizer has now is to either generate code that actually performs all those complicated operations, for the sole purpose of determining whether B is ever reached or not; or to just "assume" that the knot is not an infinite loop, and just throw it away. ...
    (comp.std.c)