Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2211 > unrolled thread

Re: Optimization techniques

Back to article view | Back to comp.compilers

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Optimization techniques Martin Ward <martin@gkc.org.uk> - 2019-04-26 19:46 +0100
    Re: language design and Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-04-26 21:06 +0000
    Re: Optimization techniques and consistent results David Brown <david.brown@hesbynett.no> - 2019-04-29 16:31 +0200
    Re: Optimization techniques Martin Ward <martin@gkc.org.uk> - 2019-05-02 10:56 +0100
      Re: Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-05-02 17:51 +0000

#2211 — Re: Optimization techniques

On 25/04/19 20:58, David Brown wrote:
> It is a serious mistake to mix up "defined behaviour" and "correct
> behaviour".  Only defined behaviour can be correct, but you can't fix
> incorrect code by making it defined behaviour.

"Defined behaviour" *can* be "correct behaviour"
"undefined behaviour" can *never* be correct and therefore
must be avoided at all costs.

You dismiss cases of security holes due to undefined behaviour
as "just program bugs, because programmers didn't do the right thing".
The C ANSI standard is over 500 pages long and includes 199
different cases of undefined behaviour. A quick quiz:
without referencing the standard, how many of the 199 cases
of undefined behaviour can you list off the top of your head?
Remember: a *good* programmer (one that you would describe
as an engineer who knows what they are doing) must avoid
all 199 cases of undefined behaviour in every line of code
that they write.

Dijkstra wrote this in his ACL Turing Award Lecture in 1972:

"Using PL/1 must be like flying a plane with 7000 buttons, switches
and handles to manipulate in the cockpit.  I absolutely fail to see
how we can keep our growing programs firmly within our intellectual
grip when by its sheer baroqueness the programming language -- our
basic tool, mind you! -- already escapes our intellectual control."

Note that even knowing that there is undefined behaviour, you still
may not be able to avoid it by testing for its occurrence: the
optimiser might spot that you are testing for undefined behaviour and
optimise away your test, because it is allowed to assume that the
undefined behaviour can never happen!  (This is what actually occurred
in the last example I gave).

You say "The trick is to write the tests correctly" but don't tell us
what clever tricks we can use in order to fool the optimised into
thinking we are testing for something *other* than undefined behaviour
and so head it off from optimising away our test.  Even if we manage
this: how can we be sure that the next version of the compiler will
not include a cleverer optimiser which sees through our trickery and
optimises away the test once again?  There seems to be an arms race
between programmers trying to write safe code and compiler writers
detecting and optimising away their safety nets.

--
			Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

[toc] | [next] | [standalone]

#2213 — Re: language design and Optimization techniques

On 2019-04-26, Martin Ward <martin@gkc.org.uk> wrote:
> On 25/04/19 20:58, David Brown wrote:
>> It is a serious mistake to mix up "defined behaviour" and "correct
>> behaviour".  Only defined behaviour can be correct, but you can't fix
>> incorrect code by making it defined behaviour.
>
> "Defined behaviour" *can* be "correct behaviour"
> "undefined behaviour" can *never* be correct and therefore
> must be avoided at all costs.

That is only right if we are talking about *absolutely* undefined
behavior.

The term "undefined behavior" in a programming language standrad isn't
absolute. It just refers to a way of using a language for which the
standard imposes no requirements.

Some undefined behaviors are used for providing documented extensions.

In C, all platforms-specific functions are essentially such an
extension.

Consider that if we write this program:

  int main(void)
  {
    extern int write(double);
    return write(3.14);
  }

We have not defined the external symbol "write" anywhere, and so
this will fail to link on many platforms. That failure is allowed
because of "undefined behavior".

Now if we compile this on a POSIX system, it almost certainly will link;
we get an executable which calls the POSIX write function with invalid,
incompatible arguments. The consequences of this are also consistent
with "undefined behavior".

There could be a platform where there is an int write(double), where
the program is just fine! Also allowed by undefined behavior.

The unescapable interpretation is that the use of platform libraries
constitutes the use of documented extensions that supplant undefined
behavior.

A program that uses a platform specific function, interpreted in a pure
standard context, can have any behavior whatsoever: failing to link,
crashing, or producing the expectd behavior. None of those behaviors is
specifically required, and the choice of behavior is not required to be
documented.

> You dismiss cases of security holes due to undefined behaviour
> as "just program bugs, because programmers didn't do the right thing".
> The C ANSI standard is over 500 pages long and includes 199
> different cases of undefined behaviour. A quick quiz:
> without referencing the standard, how many of the 199 cases
> of undefined behaviour can you list off the top of your head?
> Remember: a *good* programmer (one that you would describe
> as an engineer who knows what they are doing) must avoid
> all 199 cases of undefined behaviour in every line of code
> that they write.

Not all cases are potentially relevant to every line of code.

For instance, only one line of code in the program can commit
the error of "void main". That line "takes one for the team", so the
remaining lines face at most 198 threats. :)

[toc] | [prev] | [next] | [standalone]

#2225 — Re: Optimization techniques and consistent results

On 26/04/2019 20:46, Martin Ward wrote:
> On 25/04/19 20:58, David Brown wrote:
>> It is a serious mistake to mix up "defined behaviour" and "correct
>> behaviour".  Only defined behaviour can be correct, but you can't fix
>> incorrect code by making it defined behaviour.
>
> "Defined behaviour" *can* be "correct behaviour"
> "undefined behaviour" can *never* be correct and therefore
> must be avoided at all costs.

Yes - that is what I said, just worded slightly differently (and perhaps
in a better way).

>
> You dismiss cases of security holes due to undefined behaviour
> as "just program bugs, because programmers didn't do the right thing".

Yes.  I can't see why they should be considered differently.  Bugs of
any sort can have any kind of effect - ranging from no noticeable issue
to serious security breaches.  I am not happy with the idea that some
bugs are minor and some are serious because of the nature of the bug -
the seriousness depends on the effect of the bug, not the cause.

> The C ANSI standard is over 500 pages long and includes 199
> different cases of undefined behaviour. A quick quiz:
> without referencing the standard, how many of the 199 cases
> of undefined behaviour can you list off the top of your head?
> Remember: a *good* programmer (one that you would describe
> as an engineer who knows what they are doing) must avoid
> all 199 cases of undefined behaviour in every line of code
> that they write.

That is getting things backwards.  My job as a programmer is not to know
what code I write has undefined behaviour so that I don't write it - my job is
to know what code has /defined/ behaviour, so that I can stick to it.
More precisely, my job is to stick to code that I know has defined
behaviour - referring to documentation as needed.

For example, I don't know any details about the mbrtoc16 function.  I
even had to look up its name just now - my coding does not involve any
multi-byte character work.  I can easily avoid any undefined behaviour
for this function by not using it.  If I needed the function, then it is
my responsibility to read the documentation, find out what the
requirements and preconditions of the function are, and ensure that
these are satisfied before calling it.  That is all that is needed -
fulfil the preconditions to functions (or operators) that you use.

A good programmer does not need to know /everything/ about a programming
language or its libraries - but he/she does need to know how to use the
bits of the language that they are using.

Understanding the defined and undefined parts of basic arithmetic are,
however, reasonable demands of any programmer of a language.  A great
deal of C programs can be written without using the multi-byte character
support, but very few can be written without doing signed integer
arithmetic.

>
> Dijkstra wrote this in his ACL Turing Award Lecture in 1972:
>
> "Using PL/1 must be like flying a plane with 7000 buttons, switches
> and handles to manipulate in the cockpit.  I absolutely fail to see
> how we can keep our growing programs firmly within our intellectual
> grip when by its sheer baroqueness the programming language -- our
> basic tool, mind you! -- already escapes our intellectual control."
>
> Note that even knowing that there is undefined behaviour, you still
> may not be able to avoid it by testing for its occurrence: the
> optimiser might spot that you are testing for undefined behaviour and
> optimise away your test, because it is allowed to assume that the
> undefined behaviour can never happen!  (This is what actually occurred
> in the last example I gave).

No, that does not happen - unless of course the checks themselves are
badly written, with undefined behaviour.  There is nothing special about
code that does some checks - it is just code, and if it has undefined
behaviour then you can't expect it to work correctly.

>
> You say "The trick is to write the tests correctly" but don't tell us
> what clever tricks we can use in order to fool the optimised into
> thinking we are testing for something *other* than undefined behaviour
> and so head it off from optimising away our test.

I'm sorry, I can't quite follow that sentence.  If you are suggesting
that you need tricks to fool the compiler, then you are wrong - trying
to fool the compiler always ends in tears.  By "the trick", I mean
merely that this is part of the skill of programming.  No one said that
programming was always easy.

>  Even if we manage
> this: how can we be sure that the next version of the compiler will
> not include a cleverer optimiser which sees through our trickery and
> optimises away the test once again?  There seems to be an arms race
> between programmers trying to write safe code and compiler writers
> detecting and optimising away their safety nets.
>

Again, I can't follow your logic here.  Are you trying to say that the
only way to avoid undefined behaviour is to use code that has undefined
behaviour to detect the problem?  Certainly that is not remotely what I
have been suggesting.

> --
>              Martin

[toc] | [prev] | [next] | [standalone]

#2241

On 26/04/19 19:46, Martin Ward wrote:
> Note that even knowing that there is undefined behaviour, you still
> may not be able to avoid it by testing for its occurrence: the
> optimiser might spot that you are testing for undefined behaviour and
> optimise away your test, because it is allowed to assume that the
> undefined behaviour can never happen!  (This is what actually occurred
> in the last example I gave).

I was a little hasty here. As I now understand it, the real problem
with the example was that undefined behaviour occured before
it was tested for, and this resulted in the test being optimised away:

   struct agnx_priv *priv = dev->priv;
   if (!dev) return;
   ... do stuff using dev ...

The assignment *priv = dev->priv is undefined when dev is null
(so could be deleted when dev is null). After the assignment,
the compiler can assume that dev is not null, so can delete
the test (!dev).

Undefined behaviour must be avoided under all circumstances,
even when you do not care what result is computed!

For example, suppose that, in testing for signed overflow,
instead of writing:

signed int sum;
if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
     ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
   /* Handle error */
} else {
   sum = si_a + si_b;
}

you were to write:

signed int sum = si_a + si_b;
if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
     ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
   /* Handle error */
}

This is shorter, but possibly less efficient.
However, if overflow is very rare then the efficiency
concern might be considered unimportant.

Since you are not using the value of sum in the case
of overflow, you might think that there is no problem.

But "undefined behaviour" does not simply mean
"the compiler can return any value for sum" but
"the compiler is absolutely unrestricted in the code that
it generates". So the statement:

signed int sum = si_a + si_b;

could compile to code which searches your filesystem for
bank details and uploads them to a server in China
whenever si_a + si_b overflows!

In my opinion, *any* defined behaviour (including nondeterministic
defined behaviour) is preferable to undefined behaviour.
If the compiler were allowed to return any bit pattern as
the result of overflow, then the code above would be OK,
and all the optimisations on signed arithmetic would still
be possible, but your bank details would be safe.

--
			Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

[toc] | [prev] | [next] | [standalone]

#2248

On 2019-05-02, Martin Ward <martin@gkc.org.uk> wrote:
> On 26/04/19 19:46, Martin Ward wrote:
>> Note that even knowing that there is undefined behaviour, you still
>> may not be able to avoid it by testing for its occurrence: the
>> optimiser might spot that you are testing for undefined behaviour and
>> optimise away your test, because it is allowed to assume that the
>> undefined behaviour can never happen!  (This is what actually occurred
>> in the last example I gave).
>
> I was a little hasty here. As I now understand it, the real problem
> with the example was that undefined behaviour occured before
> it was tested for, and this resulted in the test being optimised away:
>
>    struct agnx_priv *priv = dev->priv;
>    if (!dev) return;
>    ... do stuff using dev ...

Here, clearly, the compiler is acting on knowledge that is supicious,
without sharing it in the form of a diagnostic.

The compiler knows that the pointer is used first, and then tested
for null afterward, because that's the logical basis for removing the
test. The pointer being used is what it's taking as the assurance that
it isn't null, which is the basis for deleting the null test.

But if a pointer is used first, and tested for null afterward, that
is, first and foremost, a code smell which deserves a diagnostic.

Tests of run-time conditions should not be carelessly deleted without a
diagnostic. Especially tests that speak to the grave validity of a datum
such as a pointer.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web