David Brown <david.brown@hesbynett.no> writes:
>On 27/10/2021 23:11, Anton Ertl wrote:
>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>> Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>>>> Jon Bentley wrote "Writing Efficient Programs" in 1982, and he gave an
>>>> example in Pascal. I transliterated them to C IIRC in 1999 and you
>>>> can find the results at
>>>> <http://www.complang.tuwien.ac.at/anton/lvas/effizienz/tsp.html>.
>>>>
>>>> Last I looked, the manual optimization steps that Jon Bentley
>>>> described in 1982 still produced a speedup factor of >2.7,
....
>One thing compilers do not do (and should not do) is change the results
>of your code. That puts limits on how they can rearrange things.

Exactly. That's one advantage that programmers have over compilers:
Programmers program against the requirements (or against the
specification, if there is one), not the overspecification that is the
original source code.

>They
>are also not (yet!) smart enough to do much in the way of algorithmic
>rearrangements, except specific cases programmed by their creators. So
>a compiler cannot be expected to figure out that you can work with the
>square of the distances instead of the distances.

That's the step from tsp2.c to tsp3.c. On the bottom of that is a
simple algebraic transformation:

sqrt(a)<sqrt(b) => a<b (if !(a<0) && !(b<0))

Determining the condition may already be doable with gcc's number
range analysis, and is certainly in reach. Determining that both
sides of the < are sqrt() results requires established data-flow
analysis. If gcc does not do this, it's not because it requires new
techniques, but because it is just one possible algebraic
transformation out of a huge number of possible transformations; I
think it also would increase the compile time to keep track of this
information, and it would certainly increase the development effort
and the potential for bugs. It's no surprise (and I don't hold it
against gcc (or clang)) if they don't apply this optimization.

So there you have another advantage of programmers over compilers:
They can apply a much larger arsenal of transformations.

As for algorithmic changes. It's a bit hard to draw the line between
what is an algorithmic change and what is not, but if you look at
tsp3.c->tsp4.c, we would probably both call this an algorithmic
change: Instead of checking in an array of visited flags whether the
city has already been visited, tsp4.c rearranges the data so that only
unvisited cities are considered.

So here you have another advantage of programmers over compilers: They
can perform general algorithmic changes.

Actually the tsp3.c->tsp4.c transformation also needs the programmer
to program against the requirements, not the original source code: If
two cities have the same distance from ThisPt, the transformation may
change the result. However, if the requirememt was to produce the
same output as tsp3.c, this could be achieved by comparing the indices
of the cities if two cities have the same distance from ThisPt, and
selecting the one with the lower index.

>However, you can write code clearly with separate functions, and let the
>compiler do the inlining - manual inlining is not needed.

Indeed, the manual inlining (tsp4.c->tsp5.c) is the step that resulted
in exactly the same timings from all tested C compilers with -O3.

However, if you then look at tsp5.c->tsp6.c (and further steps), will
that step be clearer if you don't inline first?

>The whole point of using a compiler that does the donkey work of
>re-arrangements and optimisations is so that the programmer can
>concentrate on the high-level algorithmic work - and these often make a
>big difference.

True, but besides the point. The point is:

Manual optimization provides a large speedup by a factor of 2.7
between tsp1 and tsp9 for gcc-5.2.0 -O3 (and more for other compiler
and optimization combinations).

Compiler optimization (-O0 vs. -O3) provides a large speedup (factor
5.6 for gcc-5.2.0 on tsp9.c), but largely indepenent of the manual
optimizations: most manual transformations that provide a speedup to
-O0 also provide a speedup to -O3 (most notable exception: inlining).

Disabling optimizations based on the assumption that undefined
behaviour does not happen with "-fno-aggressive-loop-optimizations
-fno-unsafe-loop-optimizations-fno-delete-null-pointer-checks
-fno-strict-aliasing-fno-strict-overflow
-fno-isolate-erroneous-paths-dereference-fwrapv" (or, for clang, a
subset thereof) makes no difference (same code) for clang-3.5 -O3, no
difference (same code) for tsp1..tsp3 with gcc-5.2.0 -O3, no
measurable timing difference for tsp4 and tsp5, and speedups of
0.95-1.04 for tsp6, tsp8, tsp9. So much for the argument that nasal
demons are needed for optimization purposes.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:

> That's the step from tsp2.c to tsp3.c. On the bottom of that is a
> simple algebraic transformation:
>
> sqrt(a)<sqrt(b) => a<b (if !(a<0) && !(b<0))

Has this been proven for all IEEE numbers and relevant
arithmetic on all relevant processors?

> Determining the condition may already be doable with gcc's number
> range analysis, and is certainly in reach.

Usually, compilers leave floating point reordering well alone
(unless the user supplies a flag like -ffast-math, in which case
said user gets what he asks for and what he deserves, but probably
not what he expects).

On 01/11/2021 16:38, Anton Ertl wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> On 28/10/2021 11:41, David Brown wrote:
>>> On 27/10/2021 19:34, Anton Ertl wrote:
>>>> Read all about it in Section 4.2 of
>>>> <https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf>.
> ...
>> How about presenting
>> some facts and data?
> [Later you write:]
>> Eventually, I gave up reading the rest of the paper too.
>
> If you really are interested in facts and data, maybe you should not
> have skipped them.
>

Let's be clear here - my main complaint is the way you present your
argument. No one who reads the things you publish, posts you make, or
code you write can be in any doubt that you are highly knowledgeable and
experienced in areas such as understanding what is needed to get the
highest possible efficiency from a wide variety of processors when
implementing interpreters and virtual machines, and some of the
challenges involved in getting good results for such code from
general-purpose C compilers.

I challenge you to re-read your paper (just the first few pages). But
do so imagining that you were a gcc developer. Perhaps you are an
amateur contributor - you've made some changes and improvements over the
years, maybe with optimisation passes that suit the particular code that
interests you in your main projects. Perhaps you are employed by a big
development company with the aim of generally improving the tool.
Perhaps you are paid by a chip manufacturer to maintain the backend for
that device. Alternatively, imagine the paper was not about C and gcc,
but about Forth and Gforth.

How do you feel when reading it? Do you feel the paper's author is
bringing up real issues? Do you feel he is interested in working with
you towards dealing with the issues? Do you feel he understands the
tool and its developers, and the challenges and compromises they face?

Or do you feel the author is petty and selfish, and thinks the world
should revolve around his needs and the needs of his particular code?
Do you feel the author is blaming /you/ for his own failings?
Condemning and ridiculing the work you have done over countless hours to
help programmers everywhere just because it does not benefit the
peculiar smart-arse coding of the one author?

Can't you see how this is all a wasted opportunity? The position you
have taken in that paper - and in many other posts I have seen -
guarantees that you will fail to influence either C standards or C
compilers in the way you want, and that ensures that no other
interpreter or VM writer can benefit from the kind of improvements to
compilers that could be made here.

(This is all independent from our differences of opinions regarding some
kinds of undefined behaviour.)

>> The paper has references taken out of context or designed to give the
>> incorrect impression. For example, on page 4 we have:
>>
>> """
>> The GCC maintainers subsequently disabled this optimization for the case
>> occuring in SPEC, demonstrating that, inofficially, GCC supports Cbench,
>> not “C”.
>> """
>>
>> The associated footnote refers to a gcc bug report which you presumably
>> hope readers of your paper will not bother checking. If they do, they
>> will see that the reporter of the "bug" thanks the gcc developers for
>> helping him find the error in his code, and that report is marked as
>> "invalid" - not a bug in the compiler.
>
> If the gcc developers mark a bug report as "invalid", that means that
> they don't consider it to be a bug. It does not mean that it is not a
> bug.
>
> In the case at hand, the bug report is
> <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66875>.

Yes, I looked at it. The person making the report, and all the
developers involved, agree that it's not a bug in gcc - that makes it
quite reasonable to assume it is correct to mark it as "invalid".

> Here gcc finds
> out that it can prove that there will be an out-of-bounds access if
> execution reaches the loop. What does gcc do? Does it warn about the
> out-of-bounds access? No. There would not have been a bug report if
> it did. Which reminds me of the first specification for FORTRAN,
> which states: "no special provisions havebeen included in the FORTRAN
> system for locating errors in formulas".
>
> So what does gcc do instead? It quietly deletes the loop.
>
> I checked with gcc-10.2 -Wall -O3 and it still does not warn about the
> out-of-bounds access and it still deletes the loop.
>

I think we (including the gcc developers) can all agree that more
warnings would be good in cases like that. We can all agree that the
compiler is not perfect, or as ideal and helpful as it could be. Like
any compiler, gcc does a large number of passes that manipulate the code
tree in various ways on each pass. This sometimes means that by the
time you are at a pass that might give a warning on something, it's
possible that an earlier pass has already changed or removed the code
sections that would trigger the warning. And if the warning check came
at an earlier pass, maybe there would not be enough information at the
time to get accurate warnings - there'd be too many false positives or
false negatives.

Thomas Koenig <tkoenig@netcologne.de> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>
>> That's the step from tsp2.c to tsp3.c. On the bottom of that is a
>> simple algebraic transformation:
>>
>> sqrt(a)<sqrt(b) => a<b (if !(a<0) && !(b<0))
>
>Has this been proven for all IEEE numbers and relevant
>arithmetic on all relevant processors?

For CPUs implementing IEEE FP, IIRC sqrt is one of those operations
that are guaranteed to return the rounded result of the infinitely
precise mathematical square root. The mathematical square root is
monotonous for the non-negative numbers, and rounding does not change
a monotonous function into a non-monotonous one, so for finite,
positive numbers this monotonicity result holds. For the special
cases (infinities and NaNs), it's also true, but I leave the case
analysis as an exercise to the reader.

Actually the condition can be relaxed:

sqrt(a)<sqrt(b) => a<b (if !(a<0))

That's because if b<0, sqrt(b) is NaN, so sqrt(a)<sqrt(b) delivers
false, just like a<b (if !(a<0)).

As for "relevant arithmetic on all relevant processors", if I try to
guess any meaning for that, you will accuse me of making a straw man
argument. If you want an answer for that, please state your question
more clearly.

>> Determining the condition may already be doable with gcc's number
>> range analysis, and is certainly in reach.
>
>Usually, compilers leave floating point reordering well alone

Number range analysis has nothing to do with anything that comes to my
mind upon reading "floating point reordering". BTW, compilers have no
problem at all at reordering independent FP operations, and they do it
regularly, e.g., in vectorization.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>>
>>> That's the step from tsp2.c to tsp3.c. On the bottom of that is a
>>> simple algebraic transformation:
>>>
>>> sqrt(a)<sqrt(b) => a<b (if !(a<0) && !(b<0))
>>
>>Has this been proven for all IEEE numbers and relevant
>>arithmetic on all relevant processors?
>
> For CPUs implementing IEEE FP, IIRC sqrt is one of those operations
> that are guaranteed to return the rounded result of the infinitely
> precise mathematical square root. The mathematical square root is
> monotonous for the non-negative numbers, and rounding does not change
> a monotonous function into a non-monotonous one, so for finite,
> positive numbers this monotonicity result holds. For the special
> cases (infinities and NaNs), it's also true, but I leave the case
> analysis as an exercise to the reader.

OK.

In that case, you can try out for yourself what effect it
has on gcc (using POWER because I happen to have a window open):

[tkoenig@gcc135 tmp]$ cat compare.c
int compare (float a, float b)
{ return __builtin_sqrt(a) > __builtin_sqrt(b);
} [tkoenig@gcc135 tmp]$ gcc -c -O3 -ffast-math compare.c && objdump --disassemble compare.o

compare.o: file format elf64-powerpcle

Disassembly of section .text:

0000000000000000 <compare>:
0: 00 10 01 fc fcmpu cr0,f1,f2
4: 26 00 78 7c mfocrf r3,128
8: fe 17 63 54 rlwinm r3,r3,2,31,31
c: 20 00 80 4e blr

So the optimzation is (partially) in already; you can find it on
recent trunk in match.pd:

/* Fold comparisons against built-in math functions. */
(if (flag_unsafe_math_optimizations && ! flag_errno_math)

[snipped a whole lot of stuff, some of which may be
relevant]

/* Transform sqrt(x) cmp sqrt(y) -> x cmp y. */
(simplify
(cmp (sq @0) (sq @1))
(if (! HONOR_NANS (@0))
(cmp @0 @1))))))

but some more fine-tuning is of course possible, but it is all
guarded behind -funsafe-math-optimizations, to be on the safe
side. So, some fine-tuning is still possible.

The syntax for match.pd is straightforward enough so that it is
possible to play around with this, and there are certainly enough
examples in that file.

For a travelling salesman problem, I would probably accept
-ffast-math :-)

On Tuesday, November 2, 2021 at 11:26:21 AM UTC+2, Anton Ertl wrote:
> Thomas Koenig <tko...@netcologne.de> writes:
> >Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
> >
> >> That's the step from tsp2.c to tsp3.c. On the bottom of that is a
> >> simple algebraic transformation:
> >>
> >> sqrt(a)<sqrt(b) => a<b (if !(a<0) && !(b<0))
> >
> >Has this been proven for all IEEE numbers and relevant
> >arithmetic on all relevant processors?
> For CPUs implementing IEEE FP, IIRC sqrt is one of those operations
> that are guaranteed to return the rounded result of the infinitely
> precise mathematical square root. The mathematical square root is
> monotonous for the non-negative numbers, and rounding does not change
> a monotonous function into a non-monotonous one, so for finite,
> positive numbers this monotonicity result holds. For the special
> cases (infinities and NaNs), it's also true, but I leave the case
> analysis as an exercise to the reader.
>
> Actually the condition can be relaxed:
>
> sqrt(a)<sqrt(b) => a<b (if !(a<0))
>
> That's because if b<0, sqrt(b) is NaN, so sqrt(a)<sqrt(b) delivers
> false, just like a<b (if !(a<0)).
>
> As for "relevant arithmetic on all relevant processors", if I try to
> guess any meaning for that, you will accuse me of making a straw man
> argument. If you want an answer for that, please state your question
> more clearly.
> >> Determining the condition may already be doable with gcc's number
> >> range analysis, and is certainly in reach.
> >
> >Usually, compilers leave floating point reordering well alone
> Number range analysis has nothing to do with anything that comes to my
> mind upon reading "floating point reordering". BTW, compilers have no
> problem at all at reordering independent FP operations, and they do it
> regularly, e.g., in vectorization.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

I am jumping into middle of discussion, so, may be, I am missing something obvious or don't understand an issue altogether, but I want to point out that there are plenty of cases where a < b, but sqrt(a)==sqrt(b).
In fact, it happens in ~50% of the cases of b=nextafter(a, DBL_MAX)

Michael S <already5chosen@yahoo.com> writes:
>On Tuesday, November 2, 2021 at 11:26:21 AM UTC+2, Anton Ertl wrote:
>> Thomas Koenig <tko...@netcologne.de> writes:
>> >Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
>> >> sqrt(a)<sqrt(b) => a<b (if !(a<0) && !(b<0))
....
>> sqrt(a)<sqrt(b) => a<b (if !(a<0))
....
>I am jumping into middle of discussion, so, may be, I am missing something obvious or don't understand an issue altogether, but I want to point out that there are plenty of cases where a < b, but sqrt(a)==sqrt(b).

So while the above holds for the case where sqrt(a)<sqrt(b) is true,
the two expressions do not necessarily produce the same results in the
false case. And I don't see a fast way to fix this. So that's why
gcc does this transformation only with -ffast-math.

For the requirements of the tsp example, using a<b is actually better
than using sqrt(a)<sqrt(b) (because the rounding in sqrt() can mask
that one distance is smaller than the other), but there is no way for
the compiler to know this from the source code. Which leads us back
to the #1 advantage that manual optimization has over compilers:
requirements instead of source code equivalence.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 02/11/2021 17:35, Anton Ertl wrote:
> Michael S <already5chosen@yahoo.com> writes:
>> On Tuesday, November 2, 2021 at 11:26:21 AM UTC+2, Anton Ertl wrote:
>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>> Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
>>>>> sqrt(a)<sqrt(b) => a<b (if !(a<0) && !(b<0))
> ...
>>> sqrt(a)<sqrt(b) => a<b (if !(a<0))
> ...
>> I am jumping into middle of discussion, so, may be, I am missing something obvious or don't understand an issue altogether, but I want to point out that there are plenty of cases where a < b, but sqrt(a)==sqrt(b).
>
> So while the above holds for the case where sqrt(a)<sqrt(b) is true,
> the two expressions do not necessarily produce the same results in the
> false case. And I don't see a fast way to fix this. So that's why
> gcc does this transformation only with -ffast-math.
>
> For the requirements of the tsp example, using a<b is actually better
> than using sqrt(a)<sqrt(b) (because the rounding in sqrt() can mask
> that one distance is smaller than the other), but there is no way for
> the compiler to know this from the source code. Which leads us back
> to the #1 advantage that manual optimization has over compilers:
> requirements instead of source code equivalence.
>

I think we all know that is something programmers can do that compilers
cannot. I'm not sure why you feel the need to emphasise it so often -
are you under the impression that some people think compilers read
programmers' minds to learn information not expressed in the source code?

David Brown <david.brown@hesbynett.no> writes:
>On 02/11/2021 17:35, Anton Ertl wrote:
>> Which leads us back
>> to the #1 advantage that manual optimization has over compilers:
>> requirements instead of source code equivalence.
>>
>
>I think we all know that is something programmers can do that compilers
>cannot. I'm not sure why you feel the need to emphasise it so often -
>are you under the impression that some people think compilers read
>programmers' minds to learn information not expressed in the source code?

There is a widespread myth that compilers are so good at optimization
that there is no point for programmers to think about optimization
(with some variations; e.g., selecting a good algorithm is admitted as
being outside of the realm of compilers, if algorithms are discussed
at all).

The difference between the requirements that the programmer has to
satisfy and the source code that the compiler has to implement is not
mentioned at all by those spreading the myth.

It does play into the "undefined-behaviour" discussions, though: The
less is defined by the source program, the more freedom the compiler
has to "optimize" during compilation. If that was all there is to it,
the ideal would be a programming language that defines nothing; then
the compiler can compile any source program to just exit immediately,
consuming the minimum of time and space.

But of course that's not all there is to it, and even fans of
"undefined behaviour" accept that. The problem of such a programming
language is that the programmer cannot use it to express the
requirements that the program has to satisfy.

Standard C is such a programming language; it only specifies how
"strictly conforming programs" should behave, which excludes all
terminating programs and most non-terminating programs (not sure if it
actually includes any non-terminating programs; you cannot just
replace the exit() with an endless empty loop, that's undefined in
standard C, too).

So the only practical way to deal with C programs is to consider
Standard C to be a partial specification. Both sides of the debate
accept that in some way, but in a different way.

When pressed, the fans of undefined behaviours point to
implementation-defined behaviour, additional specifications (like
POSIX), cases where the compiler actually defines some common practice
(in earlier discussions, type punning has been mentioned as such, but
recent posts have claimed that type punning is actually standardized
in C (but not in C++)) and compiler flags/pragmas that enable a more
defined source language. But they tend to switch back to talking
about standard C as soon as possible, as if that was a complete
specification.

My position is basically that a responsible maintainer for a
widely-used compiler does not break existing source code (for details,
read <https://www.complang.tuwien.ac.at/papers/ertl17kps.pdf>). If you
have a fully-defined source language, that's straightforward, for a
partially specified language like C, it's harder. This is the same
position that Linus Torvalds has wrt to the partial specification
called POSIX.

From what I read, gcc releases are now tested against the Debian
packages (as far as they are testable), which is the right direction.
But when somebody reports that a new gcc release breaks a program that
used to work with an old release, how do the gcc maintainers react?
Will they accept it as regression, or will they try to find some
behaviour in the program that the C standard does not define, and use
that as excuse to declare the bug report invalid?

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Thomas Koenig wrote:
> Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>
>> That's the step from tsp2.c to tsp3.c. On the bottom of that is a
>> simple algebraic transformation:
>>
>> sqrt(a)<sqrt(b) => a<b (if !(a<0) && !(b<0))
>
> Has this been proven for all IEEE numbers and relevant
> arithmetic on all relevant processors?

Not relevant here: Both a and b are the result of squaring a number, if
the original inputs are faulty (i.e. Inf/NaN coordinates), then the
sqrt() step does not add any benefits at all, the computation would have
trapped during the calcualtion of the square.
>
>> Determining the condition may already be doable with gcc's number
>> range analysis, and is certainly in reach.
>
> Usually, compilers leave floating point reordering well alone
> (unless the user supplies a flag like -ffast-math, in which case
> said user gets what he asks for and what he deserves, but probably
> not what he expects).

FP reorder is indeed a nice way to shoot yourself in the foot, unless
you can prove (like here) that all inputs are valid and cannot lead to
intermediate overflows or other errors: (Using meter (UTM) coordinates
means tha the maximum possible input values are in the +/- 10M range
which will lead to squares that are less than 100e12, i.e. well within
normal float numbers.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On 03/11/2021 09:25, Anton Ertl wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> On 02/11/2021 17:35, Anton Ertl wrote:
>>> Which leads us back
>>> to the #1 advantage that manual optimization has over compilers:
>>> requirements instead of source code equivalence.
>>>
>>
>> I think we all know that is something programmers can do that compilers
>> cannot. I'm not sure why you feel the need to emphasise it so often -
>> are you under the impression that some people think compilers read
>> programmers' minds to learn information not expressed in the source code?
>
> There is a widespread myth that compilers are so good at optimization
> that there is no point for programmers to think about optimization
> (with some variations; e.g., selecting a good algorithm is admitted as
> being outside of the realm of compilers, if algorithms are discussed
> at all).

Compiler optimisation does a lot of things well, and understanding this
can let you write code in a clearer, safer and more maintainable fashion
with less programmer effort and more efficient results. Compilers also
know a lot more details about the target architecture and its timings
than the great majority of programmers. Failing to understand this, or
failing to use good tools in a good way, means more manual work and
sometimes manual "micro-optimisations" that are actually
counter-productive in practice.

On the other hand, if you expect the compiler to work miracles you are
also going to be disappointed and miss out on opportunities for
improvements.

As in most things, a balance is needed, and if you want the best from
your tools, you need to know them well.

Writing source code that gives efficient object code on a wide variety
of compilers and targets is often extremely difficult, as the balance
point changes.

>
> The difference between the requirements that the programmer has to
> satisfy and the source code that the compiler has to implement is not
> mentioned at all by those spreading the myth.
>

The more the programmer can inform the compiler about the true
requirements of the code, the better. (Again, it doesn't mean compilers
will perform miracles - but can give them a better chance of optimising,
and also of spotting errors in the code.) It is also critically
important that the programmer writes the code to give the minimum
requirements - if the programmer requires wrapping overflow, for
example, then the compiler must be informed in a language it understands
(such as using unsigned types, or using compiler extensions, pragmas or
flags).

Unfortunately, C does not have a good way to express additional
information or requirements. Often you have no choice but to use
compiler extensions here.

(And of course there is no way to tell the compiler /everything/ - and
even if you could, the compiler is still not a miracle worker.)

> It does play into the "undefined-behaviour" discussions, though: The
> less is defined by the source program, the more freedom the compiler
> has to "optimize" during compilation.

Yes - although there is no need to use "scare quotation marks". If you
tell the compiler that something is undefined behaviour - either by
explicitly using an extension such as gcc's __builtin_unreachable(), or
by using language features that have undefined behaviour in some
circumstances, then the compiler can freely use the information for
optimisation purposes. If that's not what you want, then tell the
compiler - that's the programmer's job.

(Note that a compiler can only optimise with regard to undefined
behaviour in cases where it /knows/ the behaviour is undefined. A great
many things do not have behaviour defined by the C standards, but if
they are not within the compiler's responsibility, it cannot know if
they are truly UB or simply behaviour that is unknown to the compiler -
thus it assumes the later.)

> If that was all there is to it,
> the ideal would be a programming language that defines nothing; then
> the compiler can compile any source program to just exit immediately,
> consuming the minimum of time and space.
>

If you ask for nothing, you get nothing!

> But of course that's not all there is to it, and even fans of
> "undefined behaviour" accept that. The problem of such a programming
> language is that the programmer cannot use it to express the
> requirements that the program has to satisfy.
>

C cannot express all requires a programmer might want to say - all
programming languages are limited.

> Standard C is such a programming language; it only specifies how
> "strictly conforming programs" should behave, which excludes all
> terminating programs and most non-terminating programs (not sure if it
> actually includes any non-terminating programs; you cannot just
> replace the exit() with an endless empty loop, that's undefined in
> standard C, too).
>

All programming languages are limited in what they cover and what they
specify. The only thing unusual about C is that it is clear about some
aspects being undefined - most languages are not as explicit in their
standards. (Actually, a good many languages don't have anything close
to a standard document in the first place.)

> So the only practical way to deal with C programs is to consider
> Standard C to be a partial specification. Both sides of the debate
> accept that in some way, but in a different way.
>

You really are tilting at windmills. No one has ever taken the C
standards to be anything other than a partial specification! It is
stated right in section 1 on page 1 - "Scope". More detail is found
later under sections for conformance, execution, etc.

> When pressed, the fans of undefined behaviours point to
> implementation-defined behaviour, additional specifications (like
> POSIX), cases where the compiler actually defines some common practice
> (in earlier discussions, type punning has been mentioned as such, but
> recent posts have claimed that type punning is actually standardized
> in C (but not in C++)) and compiler flags/pragmas that enable a more
> defined source language. But they tend to switch back to talking
> about standard C as soon as possible, as if that was a complete
> specification.
>

I guess when you are so fixed in your opinions as you seem to be, it
makes it difficult to see how things work in the real world, or how
other people view matters. Other people understand that some aspects of
writing, compiling and running C code are covered in the C standards,
while some aspects are covered elsewhere. Undefined behaviour means it
is not covered anywhere in the particular chain (compiler, library, ABI,
etc.) in use.

> My position is basically that a responsible maintainer for a
> widely-used compiler does not break existing source code (for details,
> read <https://www.complang.tuwien.ac.at/papers/ertl17kps.pdf>). If you
> have a fully-defined source language, that's straightforward, for a
> partially specified language like C, it's harder. This is the same
> position that Linus Torvalds has wrt to the partial specification
> called POSIX.
>
> From what I read, gcc releases are now tested against the Debian
> packages (as far as they are testable), which is the right direction.
> But when somebody reports that a new gcc release breaks a program that
> used to work with an old release, how do the gcc maintainers react?
> Will they accept it as regression, or will they try to find some
> behaviour in the program that the C standard does not define, and use
> that as excuse to declare the bug report invalid?
>

You could try asking the gcc developers here, for concrete examples. I
suggest you try asking them /politely/. Given your past history, you
might find it useful to use a pseudonym.

The answer will depend on the circumstance. Bugs in the compiler will,
of course, be treated as such - but priorities must always be made as
developer resources are not unlimited. If the cause is errors in the
source code, and it is a widely used technique or piece of code, then
they may change the compiler or default flags in order to add a
definition of the behaviour in question. The preference is always to
fix the problem at the source of the problem (usually the users' code),
but practicalities can override that.

On Wednesday, November 3, 2021 at 10:45:53 AM UTC-6, David Brown wrote:
> Given your past history, you
> might find it useful to use a pseudonym.

Um, that wouldn't help.

The issue about which Anton Ertl is concerned is... one that a *lot* of
people are concerned about.

And a lot of them are less polite than him.

Basically, the question of whether C should embrace the future, or stay
compatible with K&R C, is something of a *religious war* in the C
community.

Since the other side has already won, C99 being an official standard
and all that, I think that forking gcc is the only reasonable measure
available at this late date.

John Savard

On Wednesday, November 3, 2021 at 3:19:19 PM UTC-5, Quadibloc wrote:
> On Wednesday, November 3, 2021 at 10:45:53 AM UTC-6, David Brown wrote:
> > Given your past history, you
> > might find it useful to use a pseudonym.
> Um, that wouldn't help.
>
> The issue about which Anton Ertl is concerned is... one that a *lot* of
> people are concerned about.
>
> And a lot of them are less polite than him.
>
> Basically, the question of whether C should embrace the future, or stay
> compatible with K&R C, is something of a *religious war* in the C
> community.
>
> Since the other side has already won, C99 being an official standard
> and all that, I think that forking gcc is the only reasonable measure
> available at this late date.
<
But does K&R C get the name 'C' or does modern C get to use that name ?
<
Does BSD still compile without a laundry list of flags to shut the compiler up ?
<
Does PDP-11 UNIX compile .......... ?
<
What about a system library that has not been touched for 40 years ?
>
> John Savard

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

> [..if freedom in compiling were everything..]
> the ideal would be a programming language that defines nothing;
> then the compiler can compile any source program to just exit
> immediately, consuming the minimum of time and space.
>
> But of course that's not all there is to it, and even fans of
> "undefined behaviour" accept that. The problem of such a
> programming language is that the programmer cannot use it to
> express the requirements that the program has to satisfy.
>
> Standard C is such a programming language; it only specifies
> how "strictly conforming programs" should behave, [...]

That statement is patently false.

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>

[...]

>> I think it's misleading to characterize the terms "conforming
>> program" and "strictly conforming program" as conformance
>> levels. The ISO C standard defines these terms for its own
>> purposes, not as metrics for general C programs to be measured
>> against.
>
> What are these purposes?

The purpose of defining "strictly conforming program" is to
draw a clear lower bound on what constitutes a conforming
implementation.

The purpose of defining "conforming program" is to provide
a pragmatic upper bound on the C language: any program
accepted by a conforming implementation may be counted as
being written in C.

MitchAlsup <MitchAlsup@aol.com> writes:

> On Tuesday, October 26, 2021 at 10:58:24 PM UTC-5, Tim Rentsch wrote:
>
>> MitchAlsup <Mitch...@aol.com> writes:
>>
>>> On Monday, October 25, 2021 at 12:59:40 PM UTC-5, Tim Rentsch wrote:
>>>
>>>> MitchAlsup <Mitch...@aol.com> writes:
>>>>
>>>>> On Saturday, October 23, 2021 at 6:09:53 PM UTC-5, Tim Rentsch wrote:
>>>>>
>>>>>> In truth GC works just fine for many or most application areas,
>>>>>
>>>>> The other truth is that most applications do not need any GC
>>>>> whatsoever. {Where most means over 50%}
>>>>
>>>> That is a vacuous statement.
>>>
>>> OK, how much GC does 'cat' need ? 'more' ? 'less', 'ls', '|',
>>> 'vi',.....'dev/null',...
>>
>> Here the word vacuous does not mean wrong or stupid but devoid
>> of any useful content. Sorry for the ambiguity.
>
> So the billion uses of 'cat' every day performs nothing of value
> to the users invoking 'cat' ?

The question is not whether a program can be written without
using GC. Any program _can_ be written without using GC.
The question is which programming tasks benefit from having
GC available. The answer is that a lot of them do and a
lot of them don't; just which is which depends on what it
is that needs to be accomplished.

David Brown wrote:
> On 03/11/2021 09:25, Anton Ertl wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>> On 02/11/2021 17:35, Anton Ertl wrote:
>>>> Which leads us back
>>>> to the #1 advantage that manual optimization has over compilers:
>>>> requirements instead of source code equivalence.
>>>>
>>>
>>> I think we all know that is something programmers can do that compilers
>>> cannot. I'm not sure why you feel the need to emphasise it so often -
>>> are you under the impression that some people think compilers read
>>> programmers' minds to learn information not expressed in the source code?
>>
>> There is a widespread myth that compilers are so good at optimization
>> that there is no point for programmers to think about optimization
>> (with some variations; e.g., selecting a good algorithm is admitted as
>> being outside of the realm of compilers, if algorithms are discussed
>> at all).
>
> Compiler optimisation does a lot of things well, and understanding this
> can let you write code in a clearer, safer and more maintainable fashion
> with less programmer effort and more efficient results. Compilers also
> know a lot more details about the target architecture and its timings
> than the great majority of programmers. Failing to understand this, or
> failing to use good tools in a good way, means more manual work and
> sometimes manual "micro-optimisations" that are actually
> counter-productive in practice.

This is both correct, and misleading:

Yes, compilers do know a lot more about the nooks & crannies of cpu
performance than the vast majority of programmers, but OTOH, the type of
optimizations you have to employ to handle micro-architectural balance
shifts can very often be far larger than anything a compiler would be
allowed to do.

A case in point: I have done several conference presentations and a
university guest lecture on a single program/algorithm (unix wc - word
count) which I've optimized for most generations of x86 cpus from 8088
to Pentium and PentiumPro.

The type of optimizations needed consisted of total rewrites, using new
algorithms, but still achieving the same end result.

None of those rewrites will ever become possible for any compiler I can
imagine, besides the fact that most of them was written in pure asm to
be able to control everything. I did have C or Pascal equivalents though.

The main steps were (8088) unrolled in-word and white space scanners,
with absolute minimum code and data byte counts, via runtime-generated
state machines carefully located at all 128-byte boundaries of a 64K
segment) (similar to direct threaded forth) that would load the next
input byte and use that as the high part of a direct branch address,
with the lower 8 bits containing either 0 or 128 to indicate the current
in-word status, then around the Pentium time frame I switched to a pure
data state machine where the code had no branches at all when processing
a block of 256 input bytes.

For the Out-of-Order class machines (PentiumPro etc) most of the code
has both C and asm versions, I have a bunch (6-8?) different
implementations and pick the best at runtime by benchmarking all of them
against the first 4K block of input.

Somewhat coincidentally, those final versions tend to produce very near
asm-speed results for the C implementations since there is no need to
trick the compiler into generating the code I need.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>> [..if freedom in compiling were everything..]
>> the ideal would be a programming language that defines nothing;
>> then the compiler can compile any source program to just exit
>> immediately, consuming the minimum of time and space.
>>
>> But of course that's not all there is to it, and even fans of
>> "undefined behaviour" accept that. The problem of such a
>> programming language is that the programmer cannot use it to
>> express the requirements that the program has to satisfy.
>>
>> Standard C is such a programming language; it only specifies
>> how "strictly conforming programs" should behave, [...]
>
>That statement is patently false.

Please tell us where the C standard specifies how, e.g., the following
program should behave:

int main() {
return 0;
}

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 03/11/2021 21:19, Quadibloc wrote:
> On Wednesday, November 3, 2021 at 10:45:53 AM UTC-6, David Brown wrote:
>> Given your past history, you
>> might find it useful to use a pseudonym.
>
> Um, that wouldn't help.
>
> The issue about which Anton Ertl is concerned is... one that a *lot* of
> people are concerned about.

Anton appears to be concerned about several issues. Some are real, and
definitely worth discussing and considering. Others are imagined or
misunderstood. He conflates these, throws in a healthy dose of
conspiracy theory and false history, turns it into insults against the
very people who might be in a position to improve the situation, clarify
details, or find a way to let programmers choose what they want.

But you are right that he is not alone in this.

>
> And a lot of them are less polite than him.

And you are right that some are less polite (and usually less
knowledgeable, and with an even less accurate understanding of history).

>
> Basically, the question of whether C should embrace the future, or stay
> compatible with K&R C, is something of a *religious war* in the C
> community.

Like most "religious wars", there is a small but highly vocal group of
fanatics with a seriously distorted view of reality. These fanatics
listen only to each other, not to anyone from outside, and re-enforce
their own convictions. Meanwhile, the rest of the world pretty much
ignores them and gets on with their lives - in this case, that includes
making new C standards, developing compilers, and programming in C. We
all know C is not perfect, compilers are not perfect, and no language or
tool is going to be ideal for every programmer and every programming task.

So yes, "religious war" seems to be quite a good analogy.

>
> Since the other side has already won, C99 being an official standard
> and all that, I think that forking gcc is the only reasonable measure
> available at this late date.
>

If there were people on your "side" who were interested in doing
something more than just preaching on street corners, there would
already be a fork of gcc. It's been over 20 years since C99 was
standardised - there have been two (minor) C standards since then with
another in the works, and countless gcc versions in that time. (And of
course you really meant to talk about C90, rather than C99.)

More helpfully, instead of endless rants about how wrapping is the
"right" answer to overflow or meaningless complaints about compilers
doing what they said, not what they meant, there could have been
proposals, lobbying, patches, etc., to get standardised pragmas,
standardised __builtin_overflow_add functions, and that kind of thing.
gcc and clang already support many of the semantics that these people
want, but do so using compiler-specific extensions. Instead of working
towards spreading and standardising these features, they decided to
daemonize the gcc developers. A more idiotic strategy would be
difficult to concoct.

If the undefined behaviour in C were as remotely problematic as some
people seem to think, do you not think we would have noticed some time
during the last 30 years since standardisation? Do you not think people
who are qualified and dedicated to the furtherance of the language - the
folks writing the standards and the compilers - might have thought about
it? Sure, there are occasional high-profile incidents, but in the grand
scheme of things, these UB issues are a mere blip. Buffer overflows,
incorrect use of str functions, etc., are orders of magnitude bigger
causes of problems and bugs in real-world C programs.

So here is my advice. Stop thinking about wars, or "sides". (There is
no "other side" here, since the majority of the C world do not care
about your petty concerns. They care about doing their job and getting
correct results. It is not a battle.) Stop imaging there was some
golden age of programming, back in a time before most programmers were
born and too long ago for you to remember correctly. Even if you /are/
right, it doesn't matter - that time is long gone. Stop navel-gazing
and look at the wider picture, and the future. If you really see some
kinds UB (or whatever else is bothering you at the moment) as a
practical problem, then how about trying to work /with/ compiler writers
and standards writers towards giving programmers extra choices, instead
of picking fights and annoying people so that they ignore you?

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>>As I understand it, the gcc options listed above are partly intended to
>>make this copy-and-concatenate process produce machine code that works
>>as intended. It amazes me that it actually works on several architectures.
....
>As to why it works for several architectures: Because they are all the
>same wrt. the invariants we require. However, we have disabled
>dynamic native code generation for MIPS, where the architected load
>delay slots do not satisfy these invariants (the way the jal
>instruction works on MIPS (absolute address, but works only within a
>256MB segment) would also be a hurdle).

The most recent case is the addition of control-flow protection on
AMD64 (enabled by default on recent Ubuntu). It made no changes in
Gforth necessary. The generated code I see for

: foo over + ;

in gforth-fast is

with cf-protection without cf-protection
$7FA2A4863958 over $7F19F7F5F870 noop
0x7fa2a4457701: endbr64 0x7f19f7c25b29: mov %r8,0x0(%r13)
0x7fa2a4457705: mov 0x8(%r13),%rax 0x7f19f7c25b2d: sub $0x8,%r13
0x7fa2a4457709: add $0x8,%r15 0x7f19f7c25b31: mov 0x10(%r13),%r8
0x7fa2a445770d: sub $0x8,%r13 0x7f19f7c25b35: add $0x8,%r15
0x7fa2a4457711: mov %r8,0x8(%r13) $7F19F7F5F878 +
0x7fa2a4457715: mov %rax,%r8 0x7f19f7c25b39: add $0x8,%r13
$7FA2A4863960 + 0x7f19f7c25b3d: add $0x8,%r15
0x7fa2a4457718: endbr64 0x7f19f7c25b41: add 0x0(%r13),%r8
0x7fa2a445771c: add $0x8,%r13 $7F19F7F5F880 ;s
0x7fa2a4457720: add $0x8,%r15
0x7fa2a4457724: add 0x0(%r13),%r8
$7FA2A4863968 ;s

Control flow protection means that indirect branches have to land at
endbr64 instructions. With cf-protection GCC generates an endbr64
instruction after every label whose address is taken (maybe also on
other branch targets), i.e., at the start of every primitive. Dynamic
native code generation copies the whole stuff, and as a result, those
places that can be indirectly jumped to in Gforth (e.g.,
0x7fa2a4457701) have an endbr64 instruction there. There are also
endbr64 instructions at places where Gforth does not branch to, e.g.,
0x7fa2a4457718, but on fallthrough they act as noops.

Concerning the effect on security: Gforth provides a Turing-complete
virtual machine with lot's of I/O capabilities to the user, and if an
attacker can get that far, to the attacker. It does not need dynamic
native code generation to do this, and if Gforth used switch-based
dispatch, it would also provide this virtual machine (and in the
latter case the attacker may have a slightly easier time generating
code for it). So control-flow protection does not provide any
additional security in this case. If you use Gforth, you should make
sure that attackers do not get the chance to produce code for this
virtual machine, and/or that the effects of such a break-in are
contained (e.g., by running Gforth inside an OS-level virtual
machine).

Performance (time in seconds):

sieve bubble matrix fib fft
0.121 0.075 0.041 0.056 0.024 gcc 10.3 Ubuntu default
0.118 0.075 0.040 0.050 0.020 gcc 10.3 -fcf-protection=none

The executed instructions are 3976M (default) and 3211M
(-fcf-protection=none), i.e., a factor of 1.24; but these additional
instructionshave little effect on performance, at least for these
benchmarks (for the total cycles across all of these benchmarks, a
factor 1.04). I expect that a workload with fewer indirect branch
targets will see an even smaller effect.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:

[.. on how to stop expression evaluation from leaking across
the boundaries of a function call ..]

> I think there are two separable questions here. One is what the
> mechanism does. The second is whether the mechanism should be a
> property of the function or of the invocation of that function. Or
> equivalently, should the syntax (whatever it is) be required for each
> call, or should it be invoked automatically (without additional
> syntax) every time the function is invoked.

The questions are good. I'm not sure the second question has a
single answer: in some cases it may be one, in other cases the
other. Also I'm not sure the questions are completely separable,
in that the answer to the first question might change the answer
to the second. I don't mean to say that the questions cannot
be answerable independently, only that it isn't obvious to me that
they must be.

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

> Thomas Koenig <tkoenig@netcologne.de> writes:
>
>> Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>>
>>> That's the step from tsp2.c to tsp3.c. On the bottom of that is a
>>> simple algebraic transformation:
>>>
>>> sqrt(a)<sqrt(b) => a<b (if !(a<0) && !(b<0))
>>
>> Has this been proven for all IEEE numbers and relevant
>> arithmetic on all relevant processors?
>
> For CPUs implementing IEEE FP, IIRC sqrt is one of those operations
> that are guaranteed to return the rounded result of the infinitely
> precise mathematical square root. The mathematical square root is
> monotonous for the non-negative numbers, and rounding does not
> change a monotonous function into a non-monotonous one, so for
> finite, positive numbers this monotonicity result holds.

I think the word you're looking for is monotonic, not monotonous.

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>
>>> [..if freedom in compiling were everything..]
>>> the ideal would be a programming language that defines nothing;
>>> then the compiler can compile any source program to just exit
>>> immediately, consuming the minimum of time and space.
>>>
>>> But of course that's not all there is to it, and even fans of
>>> "undefined behaviour" accept that. The problem of such a
>>> programming language is that the programmer cannot use it to
>>> express the requirements that the program has to satisfy.
>>>
>>> Standard C is such a programming language; it only specifies
>>> how "strictly conforming programs" should behave, [...]
>>
>> That statement is patently false.
>
> Please tell us where the C standard specifies how, e.g., the
> following program should behave:
>
> int main() {
> return 0;
> }

First let me ask a question. Do you think there's a difference
between that program and this one:

int main(void) {
return 0;
}

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>> Standard C is such a programming language; it only specifies
>>>> how "strictly conforming programs" should behave, [...]
>>>
>>> That statement is patently false.
>>
>> Please tell us where the C standard specifies how, e.g., the
>> following program should behave:
>>
>> int main() {
>> return 0;
>> }
>
>First let me ask a question. Do you think there's a difference
>between that program and this one:
>
> int main(void) {
> return 0;
> }

I would not expect a difference, but in any case, the arguments of
main() are not the point of this example. Choose whatever arguments
you want to provide an answer for. The result is not a "strictly
conforming program" in any case, because it terminates.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>>
>>>>> Standard C is such a programming language; it only specifies
>>>>> how "strictly conforming programs" should behave, [...]
>>>>
>>>> That statement is patently false.
>>>
>>> Please tell us where the C standard specifies how, e.g., the
>>> following program should behave:
>>>
>>> int main() {
>>> return 0;
>>> }
>>
>> First let me ask a question. Do you think there's a difference
>> between that program and this one:
>>
>> int main(void) {
>> return 0;
>> }
>
> I would not expect a difference, but in any case, the arguments of
> main() are not the point of this example. Choose whatever arguments
> you want to provide an answer for. The result is not a "strictly
> conforming program" in any case, because it terminates.

What makes you think strictly conforming programs cannot
terminate?