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

Groups > comp.lang.c > #70649 > unrolled thread

Re: What's the best hashing function?

Back to article view | Back to comp.lang.c

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: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 09:35 -0700
    Re: What's the best hashing function? "D. Aaron Sawyer" <aaron@110.net> - 2015-09-16 14:22 -0300
      Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 10:59 -0700
        Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 19:44 +0100
          Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 12:32 -0700
            Re: What's the best hashing function? Bartc <bc@freeuk.com> - 2015-09-16 20:40 +0100
              Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-16 13:11 -0700
              Re: What's the best hashing function? "James Harris" <james.harris.1@gmail.com> - 2015-09-16 21:16 +0100
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 13:47 -0700
                  Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:14 -0700
                Re: What's the best hashing function? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-16 18:08 -0500
                  Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-17 00:13 +0100
                  Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-20 01:13 -0700
            Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-16 13:10 -0700
            Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 22:17 +0100
              Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:33 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:48 -0700
                  Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:58 -0700
                    Re: What's the best hashing function? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-16 18:13 -0500
                    Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 16:29 -0700
                    Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-17 10:17 +0200
                      Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-17 08:53 -0700
                      Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-17 11:29 -0700
                        Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 10:07 +0200
                          Re: What's the best hashing function? Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 09:20 +0100
                          Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 09:25 -0700
                            Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 19:45 +0200
                              Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 11:47 -0700
                                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 21:49 +0200
                                  Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 14:50 -0700
                                    Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-19 00:23 -0700
                                    Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-19 11:13 +0200
                                      Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-19 11:03 +0100
                                        Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-19 12:38 +0200
                                      Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-21 11:29 -0700
                                        Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-22 10:23 +0200
                                          Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-22 02:31 -0700
                                            Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-22 11:28 -0700
                                          Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-22 11:18 -0700
                  Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-17 10:24 +0200
                    Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 01:48 -0700
                      Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 01:56 -0700
                      Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 02:09 -0700
              Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-16 14:49 -0700
                Re: What's the best hashing function? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-16 21:56 +0000
                Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 23:37 +0100
          Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 13:02 -0700
            Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 21:57 +0100
              Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 14:16 -0700
            Re: What's the best hashing function? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-16 21:57 +0000
              Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 16:20 -0700

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#70776

On 16/09/15 23:58, fir wrote:
> W dniu środa, 16 września 2015 23:48:38 UTC+2 użytkownik fir
> napisał:
>> ((though c has also iirc some undefined parts that are not
>> justified by different platform behaviours - those maybe should be
>> just defined))
>> 
> 
> small example on this above here is a question if this famous
> undefined behaviour
> 
> foo(a(), b(), c());

That is not undefined behaviour - you are thinking of unspecified
behaviour.  There is a huge difference.

With /undefined/ behaviour, the compiler can do anything.  The compiler
has no obligation to make sense of it.  If the compiler can see that
something is always undefined behaviour, then it might give a warning -
but often it is not able to do so, and often you only sometimes get
undefined behaviour.

Take for example division by 0.  Division of integers in C is
well-defined, and matches typical cpu hardware divide instructions,
except in the case of dividing by 0.  Different cpus will do different
things - perhaps cause a trap, perhaps return a value of 0, perhaps set
a flag in the cpu's flag register.  If C (i.e., the C standards) were to
define the behaviour of division by 0, then compilers would generally
have to add extra code to check it as a special case.  But since it is
undefined behaviour, the compiler can assume (or pretend) that you would
never run the division code with 0, so it's fine to use the fastest
hardware instruction.


With /unspecified/ behaviour, the compiler gets plenty of freedom, but
the final results should be correct and well-defined.  So typically
things like ordering (between sequence points) are unspecified.  So the
compiler is free to pick the order in which it calculated a(), b() and
c() here.  It is also free to change that order - you can have a loop
with foo(a(), b(), c()) in which the order changes during that loop (if
the compiler thinks it's a good idea).  This can make an enormous
difference to the compiler's ability to optimise code.

This is different from /implementation defined/ behaviour, in which the
compiler should pick one and only one way to define the behaviour,
document it, and be consistent about it.  The size of an "int", for
example, is implementation defined (with a defined minimum range).  But
the programmer can rely on the behaviour being consistent for that
particular compiler version and target (and possibly the given compiler
flags).

> 
> has a sense (good reason) to be undefined? I doubt if this is
> undefined becouse of varance of platforms, if so what is a reason?
> 

Usually something is given "undefined behaviour" in the standard because
there is no good choice that would work well across a range of
platforms, and there is no good reason for a programmer to want a
particular behaviour, so the standards make it undefined in order to
give the compiler freedom to generate fast code for the behaviours that
programmers actually want.

> probably it shopuld be just defined in strightforward way: a() is
> called, b(0 is called, c() is called - then foo() is called
> 

That order would make sense for traditional Pascal calling conventions
(push the first argument first), but not for traditional C calling
conventions (push the last argument first).  And any fixed order would
greatly reduce compiler optimisations.

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

#70829

David Brown <david.brown@hesbynett.no> writes:
[...]
> Take for example division by 0.  Division of integers in C is
> well-defined, and matches typical cpu hardware divide instructions,
> except in the case of dividing by 0.

INT_MIN / -1 also has undefined behavior on systems where
INT_MIN < -INT_MAX.  It's easy to forget that integer division
can overflow.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#70842

On Thursday, September 17, 2015 at 3:18:07 AM UTC-5, David Brown wrote:
> ......................................................  But since it is
> undefined behaviour, the compiler can assume (or pretend) that you would
> never run the division code with 0, so it's fine to use the fastest
> hardware instruction.

Better yet, a compiler may infer that the code will never be executed with
a divisor of zero.  Thus, given

    void x(int a)
    {
      if (a != 0) printf("You typed %d!\n");
      a = 1/a;
    }

not only would a compiler be allowed to rewrite the function to call the
printf unconditionally, but there are some people who invest a lot of effort
in making compilers perform such rewrites on the theory that it makes code
more "efficient" [IMHO, far greater efficiency gains could be achieved far
more safely in other ways].

Historically, it used to be safe to allow things like arithmetic overflow to
occur if one knew all plausible "natural" consequences on the platform one was
using, and if a program's requirements would be met for any of them.  For the
99% of programs whose requirements were:

    1. Given valid input, yield correct output.
    2. Don't launch nuclear missiles when given invalid input.

it was generally safe to assume that the second would be met by default.  Such
a viewpoint is alas no longer safe, since compilers that determine that
certain inputs will trigger Undefined Behavior may omit code which would have
limited the consequences of such behavior but failed to prevent it entirely.

> Usually something is given "undefined behaviour" in the standard because
> there is no good choice that would work well across a range of
> platforms, and there is no good reason for a programmer to want a
> particular behaviour, so the standards make it undefined in order to
> give the compiler freedom to generate fast code for the behaviours that
> programmers actually want.

C89 classified as UB any action for which some implementations might
conceivably trap.  I don't think the authors foresaw the possibility that
implementations might use UB as a license to violate laws of time and
causality.

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

#70867

On 17/09/15 20:29, supercat@casperkitty.com wrote:
> On Thursday, September 17, 2015 at 3:18:07 AM UTC-5, David Brown wrote:
>> ......................................................  But since it is
>> undefined behaviour, the compiler can assume (or pretend) that you would
>> never run the division code with 0, so it's fine to use the fastest
>> hardware instruction.
> 
> Better yet, a compiler may infer that the code will never be executed with
> a divisor of zero.  Thus, given
> 
>     void x(int a)
>     {
>       if (a != 0) printf("You typed %d!\n");
>       a = 1/a;
>     }
> 
> not only would a compiler be allowed to rewrite the function to call the
> printf unconditionally, but there are some people who invest a lot of effort
> in making compilers perform such rewrites on the theory that it makes code
> more "efficient" [IMHO, far greater efficiency gains could be achieved far
> more safely in other ways].
> 

When greater efficiency gains can be achieved in other ways, compiler
writers try to do that as well.

> Historically, it used to be safe to allow things like arithmetic overflow to
> occur if one knew all plausible "natural" consequences on the platform one was
> using, and if a program's requirements would be met for any of them.  For the
> 99% of programs whose requirements were:
> 
>     1. Given valid input, yield correct output.
>     2. Don't launch nuclear missiles when given invalid input.
> 
> it was generally safe to assume that the second would be met by default.  Such
> a viewpoint is alas no longer safe, since compilers that determine that
> certain inputs will trigger Undefined Behavior may omit code which would have
> limited the consequences of such behavior but failed to prevent it entirely.
> 
>> Usually something is given "undefined behaviour" in the standard because
>> there is no good choice that would work well across a range of
>> platforms, and there is no good reason for a programmer to want a
>> particular behaviour, so the standards make it undefined in order to
>> give the compiler freedom to generate fast code for the behaviours that
>> programmers actually want.
> 
> C89 classified as UB any action for which some implementations might
> conceivably trap.  I don't think the authors foresaw the possibility that
> implementations might use UB as a license to violate laws of time and
> causality.
> 

If a program has undefined behaviour, it has a mistake, and the compiler
can do what it wants when that happens.  This also means that the
compiler can assume that it will not happen, and generate code on that
basis.  So in the "x(int a)" function above, the compiler can assume
that "a" is never zero, and optimise on that basis.

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

#70869

On 18/09/15 09:07, David Brown wrote:

<snip>

>
> If a program has undefined behaviour, it has a mistake

Not necessarily. The UB may be perfectly deliberate. For example:

unsigned char *v = (unsigned char *)0xb8000000UL + 80 * r + 2 * c;
*v = 'A';

is undefined, and on many systems it would be a mistake, but a lot of us 
have written very similar code to that, quite deliberately, with a very 
definite purpose in mind, that this UB facilitated rather neatly.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#70895

On Friday, September 18, 2015 at 3:07:36 AM UTC-5, David Brown wrote:
> When greater efficiency gains can be achieved in other ways, compiler
> writers try to do that as well.

Unfortunately, the aforementioned style of "optimization" impairs many other
opportunities for efficiency.

> If a program has undefined behaviour, it has a mistake, and the compiler
> can do what it wants when that happens.  This also means that the
> compiler can assume that it will not happen, and generate code on that
> basis.  So in the "x(int a)" function above, the compiler can assume
> that "a" is never zero, and optimise on that basis.

Suppose you are tasked with writing a function which performs exactly like
the following in all defined cases, but is is also required to either core
dump or yield an arbitrary value in cases where the line marked with a *
overflows.

    int maxdiff(int *base, unsigned int n)
    {
      int ret = INT_MIN;
      while(n--)
      {
        int delta = base[1]-base[0]; /// *** THIS LINE
        if (delta > ret)
          ret = delta;
        base+=2;
      }
      return ret;
    }

There are a few ways I know of to change the above code so as to meet the
aforementioned requirements, but I don't know of any way which would meet
the requirements and yet not incur a significant (greater than 25%) speed
penalty on at least some systems.

To my mind, a good language should make it possible for a programmer to
express three different semantics:

1. If the value is outside the range of "int", wrap it

2. Use the arithmetically correct value, even if it exceeds the range of "int"

3. If the value is outside the range of "int", wrap it or not as convenient

A programmer who doesn't care whether the value wraps or not shouldn't be
required to write code which forces the compiler to make it wrap or forces
the compiler to handle the result in arithmetically-correct fashion.  I
would suggest that in many cases, the optimizations that would be facilitated
if programmers could afford to let compilers wrap when convenient would be
far more useful than the kinds of optimizations that would be precluded by
that.  The examples I've generally seen given as to why compilers need full
"freedom of Undefined Behavior" would generally work just as well if out-
of-range computations could yield a "partially indeterminate result" [meaning
that given `int i=INT_MAX; i++;` every rvalue conversion of i could,
independently, yield a value that behaves as any number (not necessarily representable in any type) that is congruent to INT_MAX+1 mod 2^INT_BITS].

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

#70901

On 18/09/15 18:25, supercat@casperkitty.com wrote:
> On Friday, September 18, 2015 at 3:07:36 AM UTC-5, David Brown wrote:
>> When greater efficiency gains can be achieved in other ways, compiler
>> writers try to do that as well.
> 
> Unfortunately, the aforementioned style of "optimization" impairs many other
> opportunities for efficiency.
> 

Can you give a concrete example?

>> If a program has undefined behaviour, it has a mistake, and the compiler
>> can do what it wants when that happens.  This also means that the
>> compiler can assume that it will not happen, and generate code on that
>> basis.  So in the "x(int a)" function above, the compiler can assume
>> that "a" is never zero, and optimise on that basis.
> 
> Suppose you are tasked with writing a function which performs exactly like
> the following in all defined cases, but is is also required to either core
> dump or yield an arbitrary value in cases where the line marked with a *
> overflows.

Most (all?) C compilers would simply use the processors most obvious
instructions for the calculations of delta.  Whether that causes a core
dump or an incorrect value on overflow is up to the hardware.  (It may,
possibly, cause some other undefined behaviour on overflow - perhaps a
program crash without a core dump.  You have no way to specify that
behaviour in C.  So if you absolutely require a core dump, write code
that asks for that specifically on the OS you are using.)

> 
>     int maxdiff(int *base, unsigned int n)
>     {
>       int ret = INT_MIN;
>       while(n--)
>       {
>         int delta = base[1]-base[0]; /// *** THIS LINE
>         if (delta > ret)
>           ret = delta;
>         base+=2;
>       }
>       return ret;
>     }
> 
> There are a few ways I know of to change the above code so as to meet the
> aforementioned requirements, but I don't know of any way which would meet
> the requirements and yet not incur a significant (greater than 25%) speed
> penalty on at least some systems.

I can't make sense of that.  As far as I can see, the code will already
fulfil the requirements (with the modification I gave above).

> 
> To my mind, a good language should make it possible for a programmer to
> express three different semantics:
> 
> 1. If the value is outside the range of "int", wrap it

That is one reasonable way to handle out-of-range values for int.  C
specifically does not handle them this way, in order to give maximal
flexibility to the compiler.  Languages such as Java /do/ specify
wrapping behaviour on ints - that requires two's complement integers.

> 
> 2. Use the arithmetically correct value, even if it exceeds the range of "int"

That makes no sense.  If the value is out of range, you can't use it.
If you need to use ranges beyond those of int, make an appropriate cast.

> 
> 3. If the value is outside the range of "int", wrap it or not as convenient

That is pretty much the behaviour of C compilers - they generally ignore
the possibility of the calculation going out of range, and use
instructions that work correctly when you are in range.  The compiler is
allowed to do that precisely because the behaviour is undefined as far
as C is concerned.

> 
> A programmer who doesn't care whether the value wraps or not shouldn't be
> required to write code which forces the compiler to make it wrap or forces
> the compiler to handle the result in arithmetically-correct fashion.  I
> would suggest that in many cases, the optimizations that would be facilitated
> if programmers could afford to let compilers wrap when convenient would be
> far more useful than the kinds of optimizations that would be precluded by
> that.  The examples I've generally seen given as to why compilers need full
> "freedom of Undefined Behavior" would generally work just as well if out-
> of-range computations could yield a "partially indeterminate result" [meaning
> that given `int i=INT_MAX; i++;` every rvalue conversion of i could,
> independently, yield a value that behaves as any number (not necessarily 
> representable in any type) that is congruent to INT_MAX+1 mod
> 2^INT_BITS].
> 

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

#70905

On Friday, September 18, 2015 at 12:45:15 PM UTC-5, David Brown wrote:
> Can you give a concrete example?

The code below.

> Most (all?) C compilers would simply use the processors most obvious
> instructions for the calculations of delta.  Whether that causes a core
> dump or an incorrect value on overflow is up to the hardware.  (It may,
> possibly, cause some other undefined behaviour on overflow - perhaps a
> program crash without a core dump.  You have no way to specify that
> behaviour in C.  So if you absolutely require a core dump, write code
> that asks for that specifically on the OS you are using.)

Most C compilers will do that, but the Standard allows C compilers to
infer that programs will never receive inputs that would trigger Undefined
Behavior, and some compilers very aggressively try to remove any code which
would only be relevant in such cases, even if such code would otherwise have
preventing the program from doing something unacceptable.

> >     int maxdiff(int *base, unsigned int n)
> >     {
> >       int ret = INT_MIN;
> >       while(n--)
> >       {
> >         int delta = base[1]-base[0]; /// *** THIS LINE
> >         if (delta > ret)
> >           ret = delta;
> >         base+=2;
> >       }
> >       return ret;
> >     }

Given e.g.

    int main(void)
    {
      int a[2];
      scanf("%d %d", a, a+1);
      if (a[0] > -2000000000 || a[1] < 2000000000)
        printf("WOW");
      return maxdiff(a, 1) > 0;
    }

a compiler could legitimately decide that the printf should be made
unconditional since any inputs which would cause the "if" test to be false
would cause Undefined Behavior in the "maxdiff" call.  I don't think that
compilers are *yet* sophisticated enough to make that particular inference
given the above code, but I don't think it's safe to assume that compilers
won't make such inferences given that some people are investing a lot of
effort into making them do precisely that.

There are a lot of scenarios such as graphics decoding where programs will
receive input from untrustworthy sources, and they must ensure that the
effect of malformed or maliciously-crafted output will be limited to the
production of harmless garbage output, but there is no particular requirement
as to how the values in that output should be computed.  A good language
should avoid forcing programmers or executable code to invest a large
amount of effort to limit the consequences of malformed input in cases where
the platform's natural way of handling such inputs would satisfy requirements.

> I can't make sense of that.  As far as I can see, the code will already
> fulfil the requirements (with the modification I gave above).

On most compilers, it will, but I know of no clean and efficient way to write
the code in such a way that an implementation would not be allowed to launch
nuclear missiles in the event that two array values differed by more than
INT_MAX.

> 1. If the value is outside the range of "int", wrap it

One could avoid UB by writing the code as "(int)(long)(p[0]-p[1])) > ret";
that would be required to either yield a value or raise an implementation-
defined signal, and either course of action would meet requirements, but on
some platforms casting the result of the subtraction to "int" before the
compare could add considerable expense.  Optimal machine code on the TMS
320C50 would be three cycles per iteration without the cast to "int", but
optimal code with the cast would be five cycles per iteration, adding an
extra 66% overhead.  I'm not sure if the compiler would find the optimal
code, but it it couldn't find that it could still do the job in six cycles
without the cast, and eight with, meaning the cast would add 33% overhead.

> > 2. Use the arithmetically correct value, even if it exceeds the range of "int"
> 
> That makes no sense.  If the value is out of range, you can't use it.
> If you need to use ranges beyond those of int, make an appropriate cast.

The code could easily modified to use the arithmetically-correct result, even
when it exceeds the range of "int", by adding a cast to "long" or "long long".
On some platforms, that would be very expensive, but on others it would be
cheaper than wrapping arithmetic.

> > 
> > 3. If the value is outside the range of "int", wrap it or not as convenient
> 
> That is pretty much the behaviour of C compilers - they generally ignore
> the possibility of the calculation going out of range, and use
> instructions that work correctly when you are in range.  The compiler is
> allowed to do that precisely because the behaviour is undefined as far
> as C is concerned.

That's the behavior of most C compilers, but you neglect a fourth behavior,
which some compilers aggressively pursue:

4. Assume that no inputs will be received which would cause overflow, and
   use such inferences to eliminate "dead code" elsewhere.

There are many cases where almost every behavior except #4 would be
acceptable but I know of no way to prevent #4 without writing the code in
such a way as to force #1 or #2.

Also, there are many cases where it's necessary that overflows be detected,
but the exact semantics of the trapping aren't terribly important.  If there
were a standard means by which code could say "I need to determine if any
overflows occur within this block of code, and I don't care exactly how much
of the code executes if an overflow occurs", it would often be possible for a
compiler to support such semantics much more cheaply than it would be able
to support the strict-overflow-checking semantics offered by some other
languages, or run "manual" overflow-checking code which was written using
existing features of the C language in a way that would avoid Undefined
Behavior.  If C wants to compete against Java, it should make it easier to
write robust code which is more performant than comparably-robust code in
Java.  Well-designed semantics could achieve that.

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

#70906

On 18/09/15 20:47, supercat@casperkitty.com wrote:
> On Friday, September 18, 2015 at 12:45:15 PM UTC-5, David Brown wrote:
>> Can you give a concrete example?
> 
> The code below.
> 
>> Most (all?) C compilers would simply use the processors most obvious
>> instructions for the calculations of delta.  Whether that causes a core
>> dump or an incorrect value on overflow is up to the hardware.  (It may,
>> possibly, cause some other undefined behaviour on overflow - perhaps a
>> program crash without a core dump.  You have no way to specify that
>> behaviour in C.  So if you absolutely require a core dump, write code
>> that asks for that specifically on the OS you are using.)
> 
> Most C compilers will do that, but the Standard allows C compilers to
> infer that programs will never receive inputs that would trigger Undefined
> Behavior, and some compilers very aggressively try to remove any code which
> would only be relevant in such cases, even if such code would otherwise have
> preventing the program from doing something unacceptable.
> 
>>>     int maxdiff(int *base, unsigned int n)
>>>     {
>>>       int ret = INT_MIN;
>>>       while(n--)
>>>       {
>>>         int delta = base[1]-base[0]; /// *** THIS LINE
>>>         if (delta > ret)
>>>           ret = delta;
>>>         base+=2;
>>>       }
>>>       return ret;
>>>     }
> 
> Given e.g.
> 
>     int main(void)
>     {
>       int a[2];
>       scanf("%d %d", a, a+1);
>       if (a[0] > -2000000000 || a[1] < 2000000000)
>         printf("WOW");
>       return maxdiff(a, 1) > 0;
>     }
> 
> a compiler could legitimately decide that the printf should be made
> unconditional since any inputs which would cause the "if" test to be false
> would cause Undefined Behavior in the "maxdiff" call.  I don't think that
> compilers are *yet* sophisticated enough to make that particular inference
> given the above code, but I don't think it's safe to assume that compilers
> won't make such inferences given that some people are investing a lot of
> effort into making them do precisely that.

Your claim was that "the aforementioned style of optimization impairs
many other opportunities for efficiency".  Do you have any examples that
demonstrate this claim, or that make it at all reasonable?

> 
> There are a lot of scenarios such as graphics decoding where programs will
> receive input from untrustworthy sources, and they must ensure that the
> effect of malformed or maliciously-crafted output will be limited to the
> production of harmless garbage output, but there is no particular requirement
> as to how the values in that output should be computed.  A good language
> should avoid forcing programmers or executable code to invest a large
> amount of effort to limit the consequences of malformed input in cases where
> the platform's natural way of handling such inputs would satisfy requirements.
> 
>> I can't make sense of that.  As far as I can see, the code will already
>> fulfil the requirements (with the modification I gave above).
> 
> On most compilers, it will, but I know of no clean and efficient way to write
> the code in such a way that an implementation would not be allowed to launch
> nuclear missiles in the event that two array values differed by more than
> INT_MAX.

It's easy - don't pass two values that would go outside the range.  If
you think that might be a possibility, use a "long" or "long long".  If
you have to write something that is so portable that you can't be sure
that "long long" is actually longer than "int", and you have to use a
bit of tests on signs and values before the subtraction.

Or you accept that garbage in means garbage out.

> 
>> 1. If the value is outside the range of "int", wrap it
> 
> One could avoid UB by writing the code as "(int)(long)(p[0]-p[1])) > ret";

No, that would not work - the casts are in the wrong places.

	if ((((long) p[0]) - p[1]) > INT_MAX) {
		ret = INT_MAX;
	} else {
		delta = base[1] - base[0];
		if (delta > ret) ret = delta;
	}

(I hope I haven't made a mistake there myself...)


> that would be required to either yield a value or raise an implementation-
> defined signal, and either course of action would meet requirements, but on
> some platforms casting the result of the subtraction to "int" before the
> compare could add considerable expense.  Optimal machine code on the TMS
> 320C50 would be three cycles per iteration without the cast to "int", but
> optimal code with the cast would be five cycles per iteration, adding an
> extra 66% overhead.  I'm not sure if the compiler would find the optimal
> code, but it it couldn't find that it could still do the job in six cycles
> without the cast, and eight with, meaning the cast would add 33% overhead.
> 

I don't see why the compiler could not reduce this all to a subtraction
and a check for overflow - or on a DSP like the TMS perhaps a saturating
operation could be used.

And of course since the requirement was to allow an arbitrary value in
the case of overflow, there is no need to make such checks - just write
the simple code and let the compiler use a simple subtraction.

And again, you have given no hint as to why you think disabling the
compiler's ability to use undefined behaviour for optimisation hinders
it from doing other optimisations that you feel are more valid.

>>> 2. Use the arithmetically correct value, even if it exceeds the range of "int"
>>
>> That makes no sense.  If the value is out of range, you can't use it.
>> If you need to use ranges beyond those of int, make an appropriate cast.
> 
> The code could easily modified to use the arithmetically-correct result, even
> when it exceeds the range of "int", by adding a cast to "long" or "long long".
> On some platforms, that would be very expensive, but on others it would be
> cheaper than wrapping arithmetic.

No, it could not use longer than int - it is storing the value in an int
variable.  You asked for "delta" to be int, so that's what you get.  The
compiler does not get to arbitrarily change types.

> 
>>>
>>> 3. If the value is outside the range of "int", wrap it or not as convenient
>>
>> That is pretty much the behaviour of C compilers - they generally ignore
>> the possibility of the calculation going out of range, and use
>> instructions that work correctly when you are in range.  The compiler is
>> allowed to do that precisely because the behaviour is undefined as far
>> as C is concerned.
> 
> That's the behavior of most C compilers, but you neglect a fourth behavior,
> which some compilers aggressively pursue:
> 
> 4. Assume that no inputs will be received which would cause overflow, and
>    use such inferences to eliminate "dead code" elsewhere.

And that is perfectly reasonable.  Garbage in, garbage out.  The
compiler can't do better than that, so why should it limit the speed of
the code for good input in order to try to make a little less mess when
given bad input?  It is the programmer's responsibility to either give
the function good input, or to write the function to check its inputs.

> 
> There are many cases where almost every behavior except #4 would be
> acceptable but I know of no way to prevent #4 without writing the code in
> such a way as to force #1 or #2.

If #4 is not acceptable, the function is not properly specified.

> 
> Also, there are many cases where it's necessary that overflows be detected,
> but the exact semantics of the trapping aren't terribly important.  If there
> were a standard means by which code could say "I need to determine if any
> overflows occur within this block of code, and I don't care exactly how much
> of the code executes if an overflow occurs", it would often be possible for a
> compiler to support such semantics much more cheaply than it would be able
> to support the strict-overflow-checking semantics offered by some other
> languages, or run "manual" overflow-checking code which was written using
> existing features of the C language in a way that would avoid Undefined
> Behavior.  If C wants to compete against Java, it should make it easier to
> write robust code which is more performant than comparably-robust code in
> Java.  Well-designed semantics could achieve that.
> 

So now you want the compiler to guess when you want to check for
overflows, and guess what you consider acceptable implementations, and
guess where you want to make this extra effort?  There are languages
that will do that sort of overflow checking (and indeed there are
compiler switches for gcc that will help you do it in C, at least on
some platforms).  But languages that do such checking are a lot slower
than C because of such hand-holding.  In C, you do the checking yourself
when you need it (it's not hard), which you rarely do.

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

#70910

On Friday, September 18, 2015 at 2:49:35 PM UTC-5, David Brown wrote:
> It's easy - don't pass two values that would go outside the range.  If
> you think that might be a possibility, use a "long" or "long long".  If
> you have to write something that is so portable that you can't be sure
> that "long long" is actually longer than "int", and you have to use a
> bit of tests on signs and values before the subtraction.

Input is coming from untrusted sources, and may or may not contain values
whose differences would exceed "int" range.  Evaluating whether the input
contains any such pairs of values would on many machines take longer than
finding the maximum difference given inputs that did not contain such
values.

On almost any hardware platform, **in the absence of compiler inferences
about array contents**, the optimal implementation of the original code,
which would meet requirements when given valid input, would also meet the
stated requirements when given invalid input.  Thus, code which meets the
stated requirements should be able to run just as fast on almost any
platform as code which only had to meet the requirements when given valid
input.

> Or you accept that garbage in means garbage out.

I accept that garbage data in means garbage data out.  What I find far less
acceptable is the idea that garbage data in should result in unbounded
arbitrary behavior, or that convincing a compiler to impose even the loosest
of bounds on the program of a behavior when given invalid input should
add significantly to the required complexity, code size, or execution time
in cases where a less-aggressively-optimizing compiler would naturally emit
code meeting requirements.


> 
> > 
> >> 1. If the value is outside the range of "int", wrap it
> > 
> > One could avoid UB by writing the code as "(int)(long)(p[0]-p[1])) > ret";
> 
> No, that would not work - the casts are in the wrong places.

Correct would be "(int)((long)p[0]-p[1]) > ret".  The cast to "long" needs
to be before the addition, the cast back to "int" [to enforce wrapping
behavior] needs to be before the comparison.

> I don't see why the compiler could not reduce this all to a subtraction
> and a check for overflow - or on a DSP like the TMS perhaps a saturating
> operation could be used.

On the TMS3205x, loading the accumulator with p[0] and subtracting p[1] when
they contain 32767 and -32767, respectively, would result in the accumulator
holding +65534.  Since the accumulator is 32 bits, there is no overflow.
To make that value be interpreted as 0xFFFFFFFE, it would be necessary to
store it to memory and then reload it using sign extension.

> And of course since the requirement was to allow an arbitrary value in
> the case of overflow, there is no need to make such checks - just write
> the simple code and let the compiler use a simple subtraction.

If the compiler makes no inferences about array contents, that will indeed
suffice.  My point is that writing the code in such a fashion as to
prevent improper inferences requires that the program write it in a way
that will perform needlessly slowly on at least some machines.

> And again, you have given no hint as to why you think disabling the
> compiler's ability to use undefined behaviour for optimisation hinders
> it from doing other optimisations that you feel are more valid.

It forces programmers to write code which denies compilers the ability
not only to make false inferences which would never be compatible with
program requirements, but also the ability to make other optimizations.

If the programmer writes the comparison as "(int)((long)p[0]-p[1])>ret",
that will force a TMS320C50 compiler to generate code which is slower
than the optimal code that would meet requirements.  If the programmer
writes the comparison as "(long)(p[0]-p[1])>ret" that would force an
8086 compiler to generate code which is a lot slower than the optimal
code that would meet requirements.

A major key to optimization is that in cases where multiple behaviors
would be equally acceptable, an optimizer can select the behavior which
yields the most efficient code.  If one of the requirements of a program
is that behavior must be at least loosely constrained, then any program
which meets such a requirement must prevent any optimizer that could
exploit UB from having a chance to do *anything*.

> No, it could not use longer than int - it is storing the value in an int
> variable.  You asked for "delta" to be int, so that's what you get.  The
> compiler does not get to arbitrarily change types.

Because int overflow is Undefined Behavior, a compiler is allowed to use an
over-sized register to hold an "int" variable, and is under no obligation to
clip the value of such register when storing the result of a computation on
"int" values.

> And that is perfectly reasonable.  Garbage in, garbage out.  The
> compiler can't do better than that, so why should it limit the speed of
> the code for good input in order to try to make a little less mess when
> given bad input?  It is the programmer's responsibility to either give
> the function good input, or to write the function to check its inputs.

Writing the loop in such a way as to avoid UB will cause it to run more
slowly on some systems.  If a programmer doesn't care what value the code
returns when given invalid input, why should the programmer have to select
one of two ways of evaluating such input, rather than letting the compiler
choose?

In cases where programs must accept input from untrusted sources (which, in
some problem domains, is nearly all cases) I could see great usefulness for
a code-analysis tool which could say "If this value will never need to
process "foo" values greater than 4000, adding an early-exit check here
could save considerable code downstream".  I see far less usefulness for
UB-based dead code elimination.  Nearly any kind of UB-based optimization
could be achieved by adding e.g. "__FWD_ASSUME(someVariable <= 5000)" at some
point in the code before the UB would occrred; having a code-analysis tool
which would use UB to suggest places to add such directives would be very
useful if one ran it at times when one was willing to examine the
assumptions and confirm their correctness.  Having every compilation search
for places where assumptions could be useful and apply them silently will
be slower than having normal builds simply use the directives which show
where such assumptions should be used.

> > There are many cases where almost every behavior except #4 would be
> > acceptable but I know of no way to prevent #4 without writing the code in
> > such a way as to force #1 or #2.
> 
> If #4 is not acceptable, the function is not properly specified.

What do you mean?  If I don't care about whether a compiler does #1 or #2,
or sometimes does #1 and sometimes does #2, why should that mean I must be
willing to accept #4?

> So now you want the compiler to guess when you want to check for
> overflows, and guess what you consider acceptable implementations, and
> guess where you want to make this extra effort?  There are languages
> that will do that sort of overflow checking (and indeed there are
> compiler switches for gcc that will help you do it in C, at least on
> some platforms).  But languages that do such checking are a lot slower
> than C because of such hand-holding.  In C, you do the checking yourself
> when you need it (it's not hard), which you rarely do.

Adding efficient trapped-overflow semantics would require extending the
language.  In cases where applications are not allowed to yield seemingly-
valid-but-wrong output in case of overflow, however, there is a such a huge
performance gulf between what can be achieved in optimized machine code
versus what can be achieved in C that I would think such extensions would
add considerable value.  Overflow checking adds considerable overhead in
managed .NET languages like C#, but .NET code generators can make use of
the processor overflow flag which is unavailable to C code.  I don't see
how C can hope to compete with C# for applications where untrapped overflows
are unacceptable if there's no clean and efficient way for C code to detect
overflows.

Suppose one is tasked with writing the following function:

    int sum(int *data, unsigned n);
    // Return the total of 'n' items from *data if the partial sums of all
    //   combinations of items would fit within "int".
    // Return INT_MIN if the total of the items does not fit within "int".
    // Return INT_MIN or the correct total (arbitrary choice) if the total
    //   fits within "int" but the partial sums of some combinations
    //   of items do not.

Is there any way one could write that in C which would be anywhere near as
fast as an optimized machine-code version on x86 or ARM7-TDMI?  On x86,
the loop without unrolling would be something like:

lp:
    add eax,[ecx+edi]
    jo  oops
    sub ecx,4 // Assume ecx is initialized to (n-1)*4
    jae lp

Overflow checking adds one branch not taken to the cost of the loop.  On
ARM7-TDMI, unrolling the loop 4x would yield something like:

lp: ; 
    ldrmia r0,{r4,r5,r6,r7}
    add    r1,r1,r4
    addno  r1,r1,r5 ; Only do this add if no overflow from previous one
    addno  r1,r1,r6 ; Only do this add if no overflow from previous one
    addno  r1,r1,r7 ; Only do this add if no overflow from previous one
    addno  r2,r2,#1 ; Arrange for loop counter to hit 0x80000000 at end
    bno    lp

Zero extra overhead compared to the cost of computing the sum without
overflow detection.

Can you offer any proposed way to write the a function meeting the stated
requirements such that the inner loop is less than twice as slow as optimal
machine code?

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

#70916

On Friday, September 18, 2015 at 10:50:29 PM UTC+1, supe...@casperkitty.com wrote:
> 
> Can you offer any proposed way to write the a function meeting the 
> stated requirements such that the inner loop is less than twice 
> as slow as optimal machine code?
>
1) The input is coming from untrusted sources. So what do 
the values represent? What is being counted? Sanity test
them first, shortly after reading.
2) If that's not acceptable, here's my output from the
following

int *t = malloc(1000000 * sizeof(int));
	for (i = 0; i < 1000000; i++)
		t[i] = (rand() % 2) ? INT_MIN : INT_MAX;

	tick = clock();
	for (i = 0; i < 100;i++)
	sx = maxdiffi(t, 1000000);
	tock = clock();
	printf("Integer %g %d\n", (double)(tock - tick), sx);

	double d;
	tick = clock();
	for (i = 0; i < 100; i++)
		d = maxdiffd(t, 1000000);
	tock = clock();
	printf("Integer %g %g\n", (double)(tock - tick), d);

	getchar();
	return;
	

int maxdiffi(int *x, int N)
{
	int i;
	double answer = INT_MIN;

	for (i = 0; i < N; i += 2)
	{
		if (x[i] - x[i + 1] > answer)
			answer = x[i] - x[i + 1];
	}

	return answer;
}

double maxdiffd(int *x, int N)
{
	int i;
	double answer = -DBL_MAX;

	for (i = 0; i < N; i += 2)
	{
		if ( (double) x[i] - x[i + 1] > answer)
			answer = (double) x[i] - x[i + 1];
	}

	return answer;
}

Output:
Integer 148 1
Double 141 4.297497e-4

Compile with full optimisation and the optimiser optimises the
test out to make the results meaningless (I can defeat it, 
but the basic principle is that flops aren't much slower
than integer operations these days).

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

#70918

On 18/09/15 23:50, supercat@casperkitty.com wrote:
> On Friday, September 18, 2015 at 2:49:35 PM UTC-5, David Brown wrote:
>> It's easy - don't pass two values that would go outside the range.  If
>> you think that might be a possibility, use a "long" or "long long".  If
>> you have to write something that is so portable that you can't be sure
>> that "long long" is actually longer than "int", and you have to use a
>> bit of tests on signs and values before the subtraction.
> 
> Input is coming from untrusted sources, and may or may not contain values
> whose differences would exceed "int" range.  Evaluating whether the input
> contains any such pairs of values would on many machines take longer than
> finding the maximum difference given inputs that did not contain such
> values.
> 
> On almost any hardware platform, **in the absence of compiler inferences
> about array contents**, the optimal implementation of the original code,
> which would meet requirements when given valid input, would also meet the
> stated requirements when given invalid input.  Thus, code which meets the
> stated requirements should be able to run just as fast on almost any
> platform as code which only had to meet the requirements when given valid
> input.
> 

In other words, you are happy to accept garbage in means garbage out.
So you write code that ignores what happens if there actually is an
overflow and underfined behaviour, and the compiler generates code that
does exactly what you want.  So what exactly is your problem?

In theory, a compiler could change your code from:

	delta = base[1] - base[0];

to

	if (subtraction_will_overflow(base[1], base[0])) {
		launch_missiles();
	} else {
		delta = base[1] - base[0];
	}

(Compiling with "-fsanitize-signed-integer-overflow" in gcc will give
you that, albeit with slightly less dramatic consequences.)

But the whole point of such behaviour being undefined is that the
compiler does not have to make any special treatment for it, and can
simply ignore the possibility - thus (assuming a non-malicious compiler)
you get what you want here.

>> Or you accept that garbage in means garbage out.
> 
> I accept that garbage data in means garbage data out.  What I find far less
> acceptable is the idea that garbage data in should result in unbounded
> arbitrary behavior, or that convincing a compiler to impose even the loosest
> of bounds on the program of a behavior when given invalid input should
> add significantly to the required complexity, code size, or execution time
> in cases where a less-aggressively-optimizing compiler would naturally emit
> code meeting requirements.
> 

You have not given the slightest evidence for your claim that compilers
would make code that is more complex, bigger or slower because of
undefined behaviour optimisations.  It is complete nonsense as far as I
can see.

It is true that there is no bound on what the compiler can do when faced
with undefined behaviour - but that is precisely so that it can simplify
and optimise code on the assumption that such behaviour does not happen.

And if you want bounds on the behaviour even for invalid inputs, then
check the validity of the inputs and avoid undefined behaviour.  In many
cases, that is the correct way to deal with the possibility - in other
cases, garbage in, garbage out is okay.

> 
>>
>>>
>>>> 1. If the value is outside the range of "int", wrap it
>>>
>>> One could avoid UB by writing the code as "(int)(long)(p[0]-p[1])) > ret";
>>
>> No, that would not work - the casts are in the wrong places.
> 
> Correct would be "(int)((long)p[0]-p[1]) > ret".  The cast to "long" needs
> to be before the addition, the cast back to "int" [to enforce wrapping
> behavior] needs to be before the comparison.

No, that's still wrong.  The cast to long needs to be before the
subtraction (there being no addition here).  But you can't cast the
result back to int - there is no wrapping behaviour, and if the
subtraction would have overflowed when done as ints, then it will also
overflow (and be undefined behaviour) when the result is cast from long
back to int.  You need to do the comparison as long, and explicitly
limit the value to INT_MAX before putting it back to an int.

> 
>> I don't see why the compiler could not reduce this all to a subtraction
>> and a check for overflow - or on a DSP like the TMS perhaps a saturating
>> operation could be used.
> 
> On the TMS3205x, loading the accumulator with p[0] and subtracting p[1] when
> they contain 32767 and -32767, respectively, would result in the accumulator
> holding +65534.  Since the accumulator is 32 bits, there is no overflow.
> To make that value be interpreted as 0xFFFFFFFE, it would be necessary to
> store it to memory and then reload it using sign extension.

So what?  Having the value 0x0000fffe (for +65534, out of range for a
16-bit int) in the accumulator is no better and no worse than having
0xfffffffe (for -2, the result of 32767 - -32767 if you have 16-bit
wrapped two's complement arithmetic).  Signed ints in C don't wrap on
overflow, except by luck - the overflow behaviour is undefined.  One
incorrect value is as good as another.

> 
>> And of course since the requirement was to allow an arbitrary value in
>> the case of overflow, there is no need to make such checks - just write
>> the simple code and let the compiler use a simple subtraction.
> 
> If the compiler makes no inferences about array contents, that will indeed
> suffice.  My point is that writing the code in such a fashion as to
> prevent improper inferences requires that the program write it in a way
> that will perform needlessly slowly on at least some machines.

A compiler is not going to suspect that code might have undefined
behaviour for some inputs, and generate special slow code to detect that
and cause odd behaviour - it ignores the possibility of the undefined
behaviour happening.  It is only if it knows a code path /always/ leads
to undefined behaviour that it can use that information - and it does so
by simplifying and eliminated such code paths.

> 
>> And again, you have given no hint as to why you think disabling the
>> compiler's ability to use undefined behaviour for optimisation hinders
>> it from doing other optimisations that you feel are more valid.
> 
> It forces programmers to write code which denies compilers the ability
> not only to make false inferences which would never be compatible with
> program requirements, but also the ability to make other optimizations.

You are making this up.  Show an example of what you are thinking, in
which it is reasonable to suspect that a compiler might generate bigger
or slower code because of undefined behaviour optimisations.  Or show an
example of code in which the programmer must write extra code in order
to ensure correct behaviour with valid inputs, because the compiler
might make such optimisations.  I have seen nothing remotely convincing
from you as yet.

> 
> If the programmer writes the comparison as "(int)((long)p[0]-p[1])>ret",
> that will force a TMS320C50 compiler to generate code which is slower
> than the optimal code that would meet requirements.

As shown above, it would also be wrong.

And on the TMS, as I understand it, the conversion to long comes free
here - but that's a coincidence of that target.

But the programmer could simply write the code as it was originally
written, without any extra checks, and it will work as intended (i.e.,
valid results for valid inputs, arbitrary result for invalid inputs).

>  If the programmer
> writes the comparison as "(long)(p[0]-p[1])>ret" that would force an
> 8086 compiler to generate code which is a lot slower than the optimal
> code that would meet requirements.

True, but irrelevant as noted above.

If the programmer intends the code to give a best effort answer on
invalid input (which would be an INT_MAX return), then he cannot avoid
having a cast and a check like this.  But that would be a change to the
specification of the function, and require a corresponding change to the
implementation.

> 
> A major key to optimization is that in cases where multiple behaviors
> would be equally acceptable, an optimizer can select the behavior which
> yields the most efficient code.  

Yes.

> If one of the requirements of a program
> is that behavior must be at least loosely constrained, then any program
> which meets such a requirement must prevent any optimizer that could
> exploit UB from having a chance to do *anything*.

If you have requirements for your code, you need to write code that
fulfils those requirements.  That is the basis for programming.  If
there are situations (such as invalid input) for which there are no
particular requirements, then it does not matter if those lead to
undefined behaviour - and you let the compiler's optimiser take
advantage of that freedom to pick the most efficient code.

> 
>> No, it could not use longer than int - it is storing the value in an int
>> variable.  You asked for "delta" to be int, so that's what you get.  The
>> compiler does not get to arbitrarily change types.
> 
> Because int overflow is Undefined Behavior, a compiler is allowed to use an
> over-sized register to hold an "int" variable, and is under no obligation to
> clip the value of such register when storing the result of a computation on
> "int" values.

Correct.  But any time it uses that value for other purposes, the value
is likely to be clipped at that time.  Or the compiler can continue to
assume that it does not need clipped, and ignore the possibility of it
having a value that is not compatible with a plain int.  After all, that
situation only occurs for undefined behaviour, and can be safely ignored.

> 
>> And that is perfectly reasonable.  Garbage in, garbage out.  The
>> compiler can't do better than that, so why should it limit the speed of
>> the code for good input in order to try to make a little less mess when
>> given bad input?  It is the programmer's responsibility to either give
>> the function good input, or to write the function to check its inputs.
> 
> Writing the loop in such a way as to avoid UB will cause it to run more
> slowly on some systems.

Absolutely true.  But your specification said you didn't care about the
result for invalid inputs, so undefined behaviour is fine - there is no
need to avoid it.  You only need to write code to avoid the undefined
behaviour if you want to handle invalid inputs in a controlled manner.

> If a programmer doesn't care what value the code
> returns when given invalid input, why should the programmer have to select
> one of two ways of evaluating such input, rather than letting the compiler
> choose?

I think you are completely confused here.  See my paragraph above.

> 
> In cases where programs must accept input from untrusted sources (which, in
> some problem domains, is nearly all cases) I could see great usefulness for
> a code-analysis tool which could say "If this value will never need to
> process "foo" values greater than 4000, adding an early-exit check here
> could save considerable code downstream".  I see far less usefulness for
> UB-based dead code elimination.  Nearly any kind of UB-based optimization
> could be achieved by adding e.g. "__FWD_ASSUME(someVariable <= 5000)" at some
> point in the code before the UB would occrred; having a code-analysis tool
> which would use UB to suggest places to add such directives would be very
> useful if one ran it at times when one was willing to examine the
> assumptions and confirm their correctness.  Having every compilation search
> for places where assumptions could be useful and apply them silently will
> be slower than having normal builds simply use the directives which show
> where such assumptions should be used.

Are you seriously worried about the /compilation/ speed of doing such
undefined behaviour analysis and optimisation?  It will be negligible in
almost all cases.  Run-time speed is a relevant concern (though
undefined behaviour optimisation will usually improve that, and never
make it worse).

> 
>>> There are many cases where almost every behavior except #4 would be
>>> acceptable but I know of no way to prevent #4 without writing the code in
>>> such a way as to force #1 or #2.
>>
>> If #4 is not acceptable, the function is not properly specified.
> 
> What do you mean?  If I don't care about whether a compiler does #1 or #2,
> or sometimes does #1 and sometimes does #2, why should that mean I must be
> willing to accept #4?

#4, whose definition you snipped, was to assume that that there are no
inputs which would lead to undefined behaviour.  That is always a valid
assumption.  If you want to make your function have particular behaviour
in the face of inputs that are not valid in the normal sense, then you
need to treat them explicitly in the code - in effect, you make all
inputs "valid" by determining what the output will be for those inputs.
 Therefore, if you think #4 is not acceptable to you, it is because you
haven't properly specified your function.

> 
>> So now you want the compiler to guess when you want to check for
>> overflows, and guess what you consider acceptable implementations, and
>> guess where you want to make this extra effort?  There are languages
>> that will do that sort of overflow checking (and indeed there are
>> compiler switches for gcc that will help you do it in C, at least on
>> some platforms).  But languages that do such checking are a lot slower
>> than C because of such hand-holding.  In C, you do the checking yourself
>> when you need it (it's not hard), which you rarely do.
> 
> Adding efficient trapped-overflow semantics would require extending the
> language.  In cases where applications are not allowed to yield seemingly-
> valid-but-wrong output in case of overflow, however, there is a such a huge
> performance gulf between what can be achieved in optimized machine code
> versus what can be achieved in C that I would think such extensions would
> add considerable value.

The cases where this is relevant, and actually lead to a significant
(and measured) cost in run-time, are rare.  But I agree that they do
happen.  There are several approaches to dealing with this:

1. The programmer can write code that is correct (such as by casting to
long or long long), and rely on the compiler to generate optimal code.
Compilers can often do a good job here - especially on modern platforms
such as x86-64 where doing the calculations in 64-bit longs is not going
to be slower than doing it in 32-bit int).

2. The compiler can add support on some platforms, such as "-ftrapv" on
gcc for some cpus.

3. The compiler can provide extensions to aid such tasks, such as
__buildin_add_overflow() in gcc.

4. You can use inline assembly.

5. You can petition the C standards committee to add support for
overflow checking to the C standards.


>  Overflow checking adds considerable overhead in
> managed .NET languages like C#, but .NET code generators can make use of
> the processor overflow flag which is unavailable to C code.  I don't see
> how C can hope to compete with C# for applications where untrapped overflows
> are unacceptable if there's no clean and efficient way for C code to detect
> overflows.

I don't think C proponents are particularly worried about speed
comparisons with C#, even though JIT tools are improving.  And to the
extent that this is any problem, C compiler implementations can help
even without changes to the language.

> 
> Suppose one is tasked with writing the following function:
> 
>     int sum(int *data, unsigned n);
>     // Return the total of 'n' items from *data if the partial sums of all
>     //   combinations of items would fit within "int".
>     // Return INT_MIN if the total of the items does not fit within "int".
>     // Return INT_MIN or the correct total (arbitrary choice) if the total
>     //   fits within "int" but the partial sums of some combinations
>     //   of items do not.
> 
> Is there any way one could write that in C which would be anywhere near as
> fast as an optimized machine-code version on x86 or ARM7-TDMI?  On x86,
> the loop without unrolling would be something like:
> 
> lp:
>     add eax,[ecx+edi]
>     jo  oops
>     sub ecx,4 // Assume ecx is initialized to (n-1)*4
>     jae lp
> 
> Overflow checking adds one branch not taken to the cost of the loop.  On
> ARM7-TDMI, unrolling the loop 4x would yield something like:
> 
> lp: ; 
>     ldrmia r0,{r4,r5,r6,r7}
>     add    r1,r1,r4
>     addno  r1,r1,r5 ; Only do this add if no overflow from previous one
>     addno  r1,r1,r6 ; Only do this add if no overflow from previous one
>     addno  r1,r1,r7 ; Only do this add if no overflow from previous one
>     addno  r2,r2,#1 ; Arrange for loop counter to hit 0x80000000 at end
>     bno    lp
> 
> Zero extra overhead compared to the cost of computing the sum without
> overflow detection.
> 
> Can you offer any proposed way to write the a function meeting the stated
> requirements such that the inner loop is less than twice as slow as optimal
> machine code?
> 

All you are saying here is that there are some functions that current C
compilers cannot optimise as well as hand-written assembly.  There is
nothing new in that, and it has no bearing on anything we have been
discussing.  Yes, there are still situations where hand-written assembly
code can be the best choice for maximal speed.

Having said that, I'd be curious to see what the code with gcc's
__buildin_add_overflow() looked like here, but I don't have gcc 5.0
installed at the moment.

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

#70921

David Brown <david.brown@hesbynett.no> writes:
<snip>
> Compiling with "-fsanitize-signed-integer-overflow" in gcc will give
> you that,

  -fsanitize=signed-integer-overflow

There is some not inconsiderable cost of course.

<snip>
-- 
Ben.

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

#70923

On 19/09/15 12:03, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> <snip>
>> Compiling with "-fsanitize-signed-integer-overflow" in gcc will give
>> you that,
> 
>   -fsanitize=signed-integer-overflow
> 
> There is some not inconsiderable cost of course.
> 

I don't doubt that - the sanitize options are for debugging aids, and
come at a cost.

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

#71023

On Saturday, September 19, 2015 at 4:13:45 AM UTC-5, David Brown wrote:
> In other words, you are happy to accept garbage in means garbage out.
> So you write code that ignores what happens if there actually is an
> overflow and underfined behaviour, and the compiler generates code that
> does exactly what you want.  So what exactly is your problem?

The problem is that if the program's requirements specify that maliciously-
crafted inputs may yield essentially-arbitrary outputs, but are required
not to allow the creator of those inputs to take over the machine, the only
way for the programmer to ensure that the compiler's generated code will
meet those requirements is for the SOURCE CODE to demand that the compiler
perform additional operations which will have no effect the programmer cares
about beyond preventing the compiler from making unwanted inferences about
the program's input.

It will often be possible for a programmer to choose additional operations
which will have no effect on *some* platforms, but for any choice the
programmer makes there will be other platforms where such operations do have
a cost.

> (Compiling with "-fsanitize-signed-integer-overflow" in gcc will give
> you that, albeit with slightly less dramatic consequences.)

Not merely less dramatic.  When the flag is specified, the code will meet
requirements perfectly, since there will be no way the generated code could
call launch_missiles() while abiding by the compiler's specified behavior.

There are two difficulties with such a compiler option:

1. There is no standardized means by which source code can refuse compilation
   if a compiler configuration would not meet requirements; it would be very
   easy for changes in a build system to cause compilation options to get
   lost, yielding a program that seems to work but could could be vulnerable
   to security exploits.

> But the whole point of such behaviour being undefined is that the
> compiler does not have to make any special treatment for it, and can
> simply ignore the possibility - thus (assuming a non-malicious compiler)
> you get what you want here.

The problem is that there's no standard way to force compilers to merely
ignore the possibility, and hyper-modern philosophy suggests that compilers
should "optimize" away any *user-written* code to handle inputs that the
compiler determines would cause Undefined Behavior anyway, even if the
effect of such omission is to convert what would otherwise be a benign
behavior (e.g. overflow yielding an arbitrary value) into a dangerous one.
For example, on a 32-bit machine, consider the code:

    int32_t foo(int32_t x, int *array, uint32_t array_size, uint16_t req_size)
    {
      if (req_size < array_size)
        do_something(x, array, req_size);
      return x*req_size;
    }
    #define ARR_SIZE 16384
    int arr[ARR_SIZE];
    void bar(int req_size)
    {       
      foo(65536, arr, ARR_SIZE, req_size);
    }

The most efficient implementation for the above would probably, correctly,
reject a request where req_size was greater than 16383.  Suppose, however,
that ARR_SIZE were increased to 32768.  According to hyper-modern philosophy,
increasing the array size to 32768 should eliminate the need for the bounds
check because any value of req_size over 32767 will trigger arithmetic
overflow in the computation of the return value (which is ignored anyway).
Would you approve of the compiler omitting the bounds check there?

> You have not given the slightest evidence for your claim that compilers
> would make code that is more complex, bigger or slower because of
> undefined behaviour optimisations.  It is complete nonsense as far as I
> can see.

Many programs are required to not let the creators of maliciously-crafted
inputs take over the machine.  That is hardly an obscure requirement.

If compilers are allowed to use arithmetic overflow as an excuse to bypass
code that would otherwise prevent maliciously-crafted inputs from taking
over the machine, then there will never be any situations where a non-broken
program which is bound by the above requirement could receive input that
would cause overflow.  I'm not quite sure what value there is in having an
optimizer which is only effective on broken programs.

> And if you want bounds on the behaviour even for invalid inputs, then
> check the validity of the inputs and avoid undefined behaviour.  In many
> cases, that is the correct way to deal with the possibility - in other
> cases, garbage in, garbage out is okay.

Code to checking whether inputs would cause overflow is often more
expensive and complicated than code to handle the non-overflow cases.  If
the only requirement in case of overflow is to avoid exposing any security
weaknesses, having sufficient restrictions on the actions of the compiler
that that the programmer could omit such checking from the source code
would result in a program which was easier to write, easier for humans to
read, and would allow a compiler to make *useful* optimizations in non-
broken programs that meet requirements.

> No, that's still wrong.  The cast to long needs to be before the
> subtraction (there being no addition here).  But you can't cast the
> result back to int - there is no wrapping behaviour, and if the
> subtraction would have overflowed when done as ints, then it will also
> overflow (and be undefined behaviour) when the result is cast from long
> back to int.  You need to do the comparison as long, and explicitly
> limit the value to INT_MAX before putting it back to an int.

Coercing an out-of-range "long" to "int" is required to either yield an
implementation-defined value or raise an implementation-defined signal.
The Standard allows no other behavior.

> So what?  Having the value 0x0000fffe (for +65534, out of range for a
> 16-bit int) in the accumulator is no better and no worse than having
> 0xfffffffe (for -2, the result of 32767 - -32767 if you have 16-bit
> wrapped two's complement arithmetic).  Signed ints in C don't wrap on
> overflow, except by luck - the overflow behaviour is undefined.  One
> incorrect value is as good as another.

My point is that there's no way to grant permission for the compiler to
use 65534 or -2 at its convenience without also granting permission for
the compiler to bypass security checks elsewhere in the code.

> A compiler is not going to suspect that code might have undefined
> behaviour for some inputs, and generate special slow code to detect that
> and cause odd behaviour - it ignores the possibility of the undefined
> behaviour happening.  It is only if it knows a code path /always/ leads
> to undefined behaviour that it can use that information - and it does so
> by simplifying and eliminated such code paths.

The problem is that there's no way of knowing what inferences a compiler
will and will not be able to make.  Consider the example above with req_size.
Looking at the code for "foo", how obvious would you say the security risk
is?

> ..........................Show an example of what you are thinking, in
> which it is reasonable to suspect that a compiler might generate bigger
> or slower code because of undefined behaviour optimisations.  Or show an
> example of code in which the programmer must write extra code in order
> to ensure correct behaviour with valid inputs, because the compiler
> might make such optimisations.  I have seen nothing remotely convincing
> from you as yet.

You state that programmers should add code to validate inputs, even when
a program could meet requirements without such code if compilers could offer
loose guarantees about their behavior in cases of arithmetic overflow.

> And on the TMS, as I understand it, the conversion to long comes free
> here - but that's a coincidence of that target.

On the TMS320C50 and C2xx processors, there are times when computations on
32-bit values are much cheaper than operations on on 16-bit values, and
there are times when 16-bit values are much cheaper.  A programmer who cast
things at precisely the same time as the compiler would in generating code
which ignored the possibility of overflow could probably write a source file
that would be just as efficient without ever invoking Undefined Behavior,
but a compiler will generally know more than a programmer about when values
should get converted.  If in the evaluation of an expression it will be
necessary to spill the accumulator out to memory and later reload it, it
will be faster to save 16 bits and load them back with sign extension than
to save and restore 32 bits, but if a compiler could just leave a value in
the primary or secondary accumulator that would be more efficient than
requiring the compiler to generate code to sign-extend the bottom half of
the accumulator.

> But the programmer could simply write the code as it was originally
> written, without any extra checks, and it will work as intended (i.e.,
> valid results for valid inputs, arbitrary result for invalid inputs).

On most compilers it would work 100% of the time.  IMHO, there should be
a means by which code could specify that a compiler must either generate
code where that will work 100% of the time, or refuse compilation if it
is unable to do so.  Allowing compilers to produce code where overflows
can have unbounded consequences means programmers cannot make use of what
you acknowledge is natural platform behavior.

> > If one of the requirements of a program
> > is that behavior must be at least loosely constrained, then any program
> > which meets such a requirement must prevent any optimizer that could
> > exploit UB from having a chance to do *anything*.
> 
> If you have requirements for your code, you need to write code that
> fulfils those requirements.  That is the basis for programming.  If
> there are situations (such as invalid input) for which there are no
> particular requirements, then it does not matter if those lead to
> undefined behaviour - and you let the compiler's optimiser take
> advantage of that freedom to pick the most efficient code.

If code receives input from possibly-malicious sources, there will often
be inputs for which application requirements are extremely minimal, but
unfortunately C doesn't have any means of granting compilers the freedom
to do *almost* anything without granting the freedom to do *absolutely*
everything.

I would suggest that curtailing compiler freedom in case of overflow back
slightly, from "absolutely anything" to "almost anything", would minimally
affect the performance of any program whose behavior needed to be bounded
even when fed maliciously-crafted inputs, but the benefit to programmers
of being able to safely write the sort of code you seem to think they can
write anyway would be huge.

> Correct.  But any time it uses that value for other purposes, the value
> is likely to be clipped at that time.  Or the compiler can continue to
> assume that it does not need clipped, and ignore the possibility of it
> having a value that is not compatible with a plain int.  After all, that
> situation only occurs for undefined behaviour, and can be safely ignored.

If I were writing a normative specification for integer overflow (with a
requirement that every compiler must either honor the spec or declare a
macro which programs could use to refuse compilation if they rely upon
such behavior), I would expressly allow for the possibility that integer
overflow yields a Partially-Indeterminate Value, which would behave as an
infinitely-long integer type whose upper bits could change arbitrarily at
any time.  I would further specify that *implicit* coercion of such a value
to an integer type would not need to clip the value, but that an *explicit*
typecast would be required to clip it.

Thus, given (assume int is 32 bits, and two's-complement math)

    int x=y+z; // Assume all values are integers
    long long l1 = x;
    if (x > 23) foo(1);
    if (x > 30) foo(2);
    long long l2 = (long long)x;
    if (x > 40) foo(3);
    if (x > 50) foo(4);
   
the first assignment would store into "l1" a value where bits 0-31 matched
those of x, bits 32-63 were unspecified, and higher bits were Indeterminate.
The second assignment would assign bits 0-31 to match x, 32-63 unspecified
values, and all higher bits the same value as bit 63.

Thus, the first two comparisons would not be required to yield consistent
values, but the third and fourth ones would.

> Absolutely true.  But your specification said you didn't care about the
> result for invalid inputs, so undefined behaviour is fine - there is no
> need to avoid it.  You only need to write code to avoid the undefined
> behaviour if you want to handle invalid inputs in a controlled manner.

Unfortunately, there's no middle ground between "rigidly-controlled manner"
and "let creators of maliciously-crafted data take over the machine".

> Are you seriously worried about the /compilation/ speed of doing such
> undefined behaviour analysis and optimisation?  It will be negligible in
> almost all cases.  Run-time speed is a relevant concern (though
> undefined behaviour optimisation will usually improve that, and never
> make it worse).

I have a friend who's a C++ developer who misses the shorter build times of
his Amiga projects.  The projects had a lot less code, but were running on a
machine that's less than 1/1000 as fast as a modern one.  I'm not sure just
how much time is spent on which phases of program analysis, but the kinds
of optimization at issue have a higher algorithmic complexity than most of
the other things compilers have to do.

> #4, whose definition you snipped, was to assume that that there are no
> inputs which would lead to undefined behaviour.  That is always a valid
> assumption.  If you want to make your function have particular behaviour
> in the face of inputs that are not valid in the normal sense, then you
> need to treat them explicitly in the code - in effect, you make all
> inputs "valid" by determining what the output will be for those inputs.
>  Therefore, if you think #4 is not acceptable to you, it is because you
> haven't properly specified your function.

Perhaps I should have worded it "Make unbounded inferences based on the
premise that the program will never receive inputs which will lead to
Undefined Behavior".  Does that help?

> 1. The programmer can write code that is correct (such as by casting to
> long or long long), and rely on the compiler to generate optimal code.
> Compilers can often do a good job here - especially on modern platforms
> such as x86-64 where doing the calculations in 64-bit longs is not going
> to be slower than doing it in 32-bit int).

What if one wishes to write code which will run optimally on either a 32-bit
or 64-bit platform?  If there's one way of writing the code which will run
optimally on a 32-bit platform but sub-optimally on a 64-bit platform, and
another which will run optimally on a 64-bit platform but sub-optimally on
a 32-bit platform, should a programmer who wants optimal behavior have
to write separate programs for each?

> 2. The compiler can add support on some platforms, such as "-ftrapv" on
> gcc for some cpus.

That would be fine *if* there were a standard means for source code to
specify its behavioral requirements, such that compilers would be allowed
to reject programs whose requirements they couldn't meet, but would not be
allowed to generate an executable whose behavior didn't meet those
requirements unless it generated a diagnostic (the normal requirement for
a compiler "rejecting" a program).

> 3. The compiler can provide extensions to aid such tasks, such as
> __buildin_add_overflow() in gcc.

I would suggest that the need for overflow checking is sufficiently non-
obscure that there should be language support for it.  Further, extensions
such as described would force a compiler to generate code with rigidly-
defined behavior.  Suppose one is tasked with writing a function which
behaves like whichever of the following is faster:

    int sum3(int x, int y, int z)
    {
      long sum = (long)x+y+z;
      if (sum < INT_MIN || sum > INT_MAX)
        return INT_MIN;
      return sum;
    }

    int sum3(int x, int y, int z)
    {
      long sum = (long)x+y;
      if (sum < INT_MIN || sum > INT_MAX)
        return INT_MIN;
      sum+=z;
      if (sum < INT_MIN || sum > INT_MAX)
        return INT_MIN;
      return sum;
    }

I don't think there's any way to tell the compiler to use whichever form
is faster.  If the function gets inlined, it's entirely possible that which
form would be faster may depend upon the invocation context.

> 4. You can use inline assembly.

A good compiler should often be able to produce code which can outperform
in-line assembly, given that a compiler knows more about its register usage.
In a case where code which uses 6 registers could be an instruction shorter
than code which uses 5, either form might be better depending upon whether
use of the sixth register would require adding code to save/restore its
value elsewhere.  

> 5. You can petition the C standards committee to add support for
> overflow checking to the C standards.

Not sure how to gain any sort of audience.

> >  Overflow checking adds considerable overhead in
> > managed .NET languages like C#, but .NET code generators can make use of
> > the processor overflow flag which is unavailable to C code.  I don't see
> > how C can hope to compete with C# for applications where untrapped overflows
> > are unacceptable if there's no clean and efficient way for C code to detect
> > overflows.
> 
> I don't think C proponents are particularly worried about speed
> comparisons with C#, even though JIT tools are improving.  And to the
> extent that this is any problem, C compiler implementations can help
> even without changes to the language.

C and C++ have lost a lot of market share to other languages.  Is there
any reason besides performance that C or C++ should even be considered as
a language for PC application development?

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

#71069

On 21/09/15 20:29, supercat@casperkitty.com wrote:
> On Saturday, September 19, 2015 at 4:13:45 AM UTC-5, David Brown wrote:
>> In other words, you are happy to accept garbage in means garbage out.
>> So you write code that ignores what happens if there actually is an
>> overflow and underfined behaviour, and the compiler generates code that
>> does exactly what you want.  So what exactly is your problem?
> 
> The problem is that if the program's requirements specify that maliciously-
> crafted inputs may yield essentially-arbitrary outputs, but are required
> not to allow the creator of those inputs to take over the machine, the only
> way for the programmer to ensure that the compiler's generated code will
> meet those requirements is for the SOURCE CODE to demand that the compiler
> perform additional operations which will have no effect the programmer cares
> about beyond preventing the compiler from making unwanted inferences about
> the program's input.

You are changing the specifications yet again.  Now the functions
response to inputs with out-of-range differences should be something
specific and very definitely /not/ arbitrary - it must somehow be
something that does not allow the user to take over the machine.  That
is an impossible specification as it stands - there is not enough
information for a programmer to write such code, let alone for a
compiler to guess what you mean.

So you must fall back to giving a specification for exactly what will
happen when the function is called, with the specifications covering all
possible inputs.  For example, you might say that if the differences are
outside the range of int, then the result will be INT_MAX.  You might
say it should an int, but don't care what int - in which case the
simple, naive program with no checking will give you appropriate code on
any sane compiler (just because the behaviour is undefined, does not
mean that the compiler /must/ generate nasal daemons).  Whether you are
happy to accept such a reasonable implementation of the undefined
behaviour, or whether you insist on avoiding any undefined behaviour, is
up to you.


The /real/ problem here, is that you apparently do not understand the
basics of software design.  If you want a function that will do
something, then step one is to decide what it will do - give it a
complete specification covering all inputs that you want to handle in a
given way.  Regardless of what language you are using, and what the
standards might say about behaviours, the function's behaviour will be
undefined for all other inputs - that's what writing a specification
means.  Then once you have the specification, step two is to write code
that tells the compiler how to generate that function - on the
assumption that the inputs match those given in the specification.


> 
> It will often be possible for a programmer to choose additional operations
> which will have no effect on *some* platforms, but for any choice the
> programmer makes there will be other platforms where such operations do have
> a cost.
> 
>> (Compiling with "-fsanitize-signed-integer-overflow" in gcc will give
>> you that, albeit with slightly less dramatic consequences.)
> 
> Not merely less dramatic.  When the flag is specified, the code will meet
> requirements perfectly, since there will be no way the generated code could
> call launch_missiles() while abiding by the compiler's specified behavior.

Your specification at the time when I wrote it allowed for the
possibility of launching missiles given unreasonable input values.  It
is extremely difficult to discuss a problem when you change
specifications several times in every post.

> 
> There are two difficulties with such a compiler option:
> 
> 1. There is no standardized means by which source code can refuse compilation
>    if a compiler configuration would not meet requirements; it would be very
>    easy for changes in a build system to cause compilation options to get
>    lost, yielding a program that seems to work but could could be vulnerable
>    to security exploits.

It is a /debugging/ option, to help figure out why your code is not
doing what you think it should.  It is not an option to use in released
code.  You should write correct code, according to the specifications
you have, then there will be no problem.

> 
>> But the whole point of such behaviour being undefined is that the
>> compiler does not have to make any special treatment for it, and can
>> simply ignore the possibility - thus (assuming a non-malicious compiler)
>> you get what you want here.
> 
> The problem is that there's no standard way to force compilers to merely
> ignore the possibility, and hyper-modern philosophy suggests that compilers
> should "optimize" away any *user-written* code to handle inputs that the
> compiler determines would cause Undefined Behavior anyway, even if the
> effect of such omission is to convert what would otherwise be a benign
> behavior (e.g. overflow yielding an arbitrary value) into a dangerous one.

That is bollocks.  Complete nonsense.

Compilers can optimise away code if it could only occur after undefined
behaviour.

So if you write this:

void foo1(int* p) {
	if (!p) {
		printf("Error!");
		return;
	}
	*p = 0x1234;
}

The code is fine - the function will print "Error!" if foo is called
with the null pointer.

But if you write this:

void foo2(int* p) {
	*p = 0x1234;
	if (!p) {
		printf("Error!");
		return;
	}
}

Then the compiler can freely omit the test and printf call, as it knows
you don't actually care if p is 0.

This second case comes as a surprise to some people, especially as it is
an optimisation technique that has become more common in compilers in
recent years, but it is perfectly valid.  The error is clearly in the
source code - if you write bad source code, you cannot expect the
compiler to magically turn it into good object code.  And you cannot
expect the compiler to somehow make judgements about what is "less
dangerous" or "more dangerous" output code.  The compiler just does what
you tell it to do.
	

> For example, on a 32-bit machine, consider the code:
> 
>     int32_t foo(int32_t x, int *array, uint32_t array_size, uint16_t req_size)
>     {
>       if (req_size < array_size)
>         do_something(x, array, req_size);
>       return x*req_size;
>     }
>     #define ARR_SIZE 16384
>     int arr[ARR_SIZE];
>     void bar(int req_size)
>     {       
>       foo(65536, arr, ARR_SIZE, req_size);
>     }
> 
> The most efficient implementation for the above would probably, correctly,
> reject a request where req_size was greater than 16383.  Suppose, however,
> that ARR_SIZE were increased to 32768.  According to hyper-modern philosophy,
> increasing the array size to 32768 should eliminate the need for the bounds
> check because any value of req_size over 32767 will trigger arithmetic
> overflow in the computation of the return value (which is ignored anyway).
> Would you approve of the compiler omitting the bounds check there?

This is finally getting to the point where something might be
controversial.  The compiler could reasonably omit the bounds check -
but I would hope it was able to issue a diagnostic message if it did so
(assuming the appropriate warning flags).  Quick tests with gcc 4.9 show
that while that compiler will omit unnecessary tests that come after
undefined behaviour, it does not omit such tests that come before
undefined behaviour.

Note, however, that the reason for all this is the bug in your code.  If
the compiler omitted the test on reg_size, it is guilty of being
unhelpful in aiding your debugging, not of generating incorrect code.  I
believe compilers should be as helpful as possible in helping the
programmer track bugs - /that/ is why I would be unhappy if it silently
removed the test.

> 
>> You have not given the slightest evidence for your claim that compilers
>> would make code that is more complex, bigger or slower because of
>> undefined behaviour optimisations.  It is complete nonsense as far as I
>> can see.

It is still complete nonsense, and you still have given no evidence to
this claim.

> 
> Many programs are required to not let the creators of maliciously-crafted
> inputs take over the machine.  That is hardly an obscure requirement.

If you don't make that requirement in the specification of the function,
then it is obscure.  And since most functions are internal, rather than
directly facing external input, then for most functions it is not a
sensible requirement.

> 
> If compilers are allowed to use arithmetic overflow as an excuse to bypass
> code that would otherwise prevent maliciously-crafted inputs from taking
> over the machine, then there will never be any situations where a non-broken
> program which is bound by the above requirement could receive input that
> would cause overflow.  I'm not quite sure what value there is in having an
> optimizer which is only effective on broken programs.

If your code is correct, there is no problem.  The optimiser works best
on correct code.

Remember, we are talking about code which has defined behaviour for some
inputs, and undefined behaviour for others.  The optimiser simply
assumes that you will never give the function an input value for which
the behaviour is undefined.  So as long as you have written your
function to work in a predictable and defined way for all the inputs
that it will be given, then the optimiser produces smaller and faster
code using that assumption.

If you write incorrect function code that has undefined behaviour for
some possible inputs, or incorrect calling code that calls the function
with invalid inputs, then that is the fault of the programmer - not the
compiler.


<snip>

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

#71079

On Tuesday, September 22, 2015 at 9:23:23 AM UTC+1, David Brown wrote:
> 
> So you must fall back to giving a specification for exactly what will
> happen when the function is called, with the specifications covering all
> possible inputs.  For example, you might say that if the differences are
> outside the range of int, then the result will be INT_MAX.  You might
> say it should an int, but don't care what int - in which case the
> simple, naive program with no checking will give you appropriate code on
> any sane compiler (just because the behaviour is undefined, does not
> mean that the compiler /must/ generate nasal daemons).  Whether you are
> happy to accept such a reasonable implementation of the undefined
> behaviour, or whether you insist on avoiding any undefined behaviour, is
> up to you.
>
A sane complier could raise a signal that interrupts normal processing and
calls a special handler which reports that an arithmetical overflow has
occurred. An attacker could potentially have access to that routine and 
insert his own hook, calling arbitrary machine code of his devising.

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

#71106

On Tuesday, September 22, 2015 at 4:31:23 AM UTC-5, Malcolm McLean wrote:
> A sane complier could raise a signal that interrupts normal processing and
> calls a special handler which reports that an arithmetical overflow has
> occurred. An attacker could potentially have access to that routine and 
> insert his own hook, calling arbitrary machine code of his devising.

In what cases would an attacker be able to attach arbitrary machine code of
his devising to an interrupt handler without already having the means of
executing arbitrary machine code of his devising in other ways.

I would like to see, as a normative C Standard, a standardized pair of
macros such that if the first is invoked before "main()" and the second is
executed at the start of "main()", would direct that in the absence of
code or external action which configures them otherwise, any trap handlers
associated with overflow, divide by zero, etc. or any of the non-critical
forms of UB listed in Appendix L, will be configured in a fashion which
will prevent any critical form of UB.  On systems without traps, or on
systems where traps are by default already configured in such fashion, the
macros would be empty.  Systems which cannot achieve the indicated guarantees
should either leave the macros undefined or define them in such a fashion
that programs including them will not compile.

In some cases there is value in allowing for the possibility that a program
might be executed with traps pre-configured to behave in a way not envisioned
by the C Standard, and allowing for that means that the Standard cannot
impose any rigid requirements, but there would also be great value in
allowing programs to specify that certain actions must have bounded
consequences.

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

#71105

On Tuesday, September 22, 2015 at 3:23:23 AM UTC-5, David Brown wrote:
> On 21/09/15 20:29, supercat wrote:
> > The problem is that if the program's requirements specify that maliciously-
> > crafted inputs may yield essentially-arbitrary outputs, but are required
> > not to allow the creator of those inputs to take over the machine, the only
> > way for the programmer to ensure that the compiler's generated code will
> > meet those requirements is for the SOURCE CODE to demand that the compiler
> > perform additional operations which will have no effect the programmer cares
> > about beyond preventing the compiler from making unwanted inferences about
> > the program's input.
> 
> You are changing the specifications yet again.  Now the functions
> response to inputs with out-of-range differences should be something
> specific and very definitely /not/ arbitrary - it must somehow be
> something that does not allow the user to take over the machine.  That
> is an impossible specification as it stands - there is not enough
> information for a programmer to write such code, let alone for a
> compiler to guess what you mean.

Appendix L of the C11 Standard is not particularly well-written, but it
expresses the basic concept that programs which are "analyzable" should
separate Undefined Behavior into "critical" and "non-critical" forms, with
the intention that the occurrence of actions which trigger non-critical
forms of undefined behaviors (such as integer overflow or accessing a
scalar variable with indeterminate value) should not entitle the compiler to
invoke critical forms.  Appendix L fails to sufficiently delineate what
range of actions should or should not be allowable to allow a programmer
to know whether a piece of code could trigger critical UB given invalid
input [e.g. given:

    unsigned char foo[5000];

    void blah(uint16_t x, uint16_t y)
    {
      int32_t z = x*y;
      if (z >= 0 && z < 5000) foo[z] = 6;
    }

it's unclear whether blah(42950,50000) would entitle a compiler to write to
foo[-131071], which would be Critical Undefined Behavior, or how the code
would need to be written to ensure that couldn't happen.  Note that even if
overflow is required to have no effect beyond yielding Indeterminate Value,
and every rvalue conversion of an Indeterminate Value is required to have no
effect beyond yielding another Indeterminate Value, and comparisons with
Indeterminate Values yield an Unspecified result, the above code could
generate a write to foo[-131071]; for Appendix-L Analyzability to be useful,
there needs to be some defined process for converting an Indeterminate Value
to an Unspecified Value, such that it would not be possible for the compiler
to simultaneously regard "z" as holding 4294836225 (which is greater than
zero) and -131071 (which is less than 5000).

> You might
> say it should an int, but don't care what int - in which case the
> simple, naive program with no checking will give you appropriate code on
> any sane compiler (just because the behaviour is undefined, does not
> mean that the compiler /must/ generate nasal daemons).  

If like me you do not believe that any SANE compiler would trigger arbitrary
and unpredictable behaviors, would that imply that you would consider some
of the trends in hyper-modern compiler philosophy to be INSANE?

>                                                         Whether you are
> happy to accept such a reasonable implementation of the undefined
> behaviour, or whether you insist on avoiding any undefined behaviour, is
> up to you.

I suspect I would be happy to accept the behaviors you would consider to be
sane.  I think our point of disagreement is that current compiler philosophy
believes that in those cases where the Standard imposes no requirements,
compilers should seek out any behavior that would be more "efficient" without
regard for whether it would satisfy application requirements which might have
been met by more commonplace behaviors.
 
> The /real/ problem here, is that you apparently do not understand the
> basics of software design.  If you want a function that will do
> something, then step one is to decide what it will do - give it a
> complete specification covering all inputs that you want to handle in a
> given way.  Regardless of what language you are using, and what the
> standards might say about behaviours, the function's behaviour will be
> undefined for all other inputs - that's what writing a specification
> means.  Then once you have the specification, step two is to write code
> that tells the compiler how to generate that function - on the
> assumption that the inputs match those given in the specification.

In the design of logic circuitry, if one specifies a list of cases when an
output must be high, and a list of cases when it must be low, the expected
normal behavior of a logic compiler is to yield the simplest circuitry
which, for any other combination of inputs, will make the output high or
make it low, without causing the circuit to catch fire, draw substantial
extra current, or doing anything else bizarre.  In some cases, the amount
of circuitry required to ensure that the circuit will produce a high or low
output without drawing excessive requirement will be greater than if
drawing excessive current was a valid behavior when given unspecified
inputs, but I don't think many designers would suggest that a good tool
shouldn't waste circuitry handling such cases.

> Your specification at the time when I wrote it allowed for the
> possibility of launching missiles given unreasonable input values.  It
> is extremely difficult to discuss a problem when you change
> specifications several times in every post.

A requirement that a program must not perform some specific behavior even
when given even maliciously-crafted invalid input, and a requirement that
a program must not grant the authors of maliciously-crafted input the
ability to have a program execute arbitrary code on their behalf, are pretty
much equivalent; any program which fails the latter requirement would, if
given input which was crafted to execute code to perform the forbidden
action, would perform the forbidden action.

> It is a /debugging/ option, to help figure out why your code is not
> doing what you think it should.  It is not an option to use in released
> code.  You should write correct code, according to the specifications
> you have, then there will be no problem.

You suggested that semantics suitable for programs that must not produce
seemingly-valid-but-wrong output in case of overflow (but would be allowed
to abnormally terminate) exist in the form of -fsanitize.  If it is
necessary that release code offer such semantics, how would you suggest
that could be done without bloating the main-line of the code with logic
to detect all possible overflows?

Given a requirement that overflows must be reported if they would cause a
numerically-incorrect result, but may arbitrarily be reported or not in
cases where the result would end up being numerically correct anyhow, the
optimal code to meet that requirement may be dependent upon CPU register
spillage, which is something a compiler will know about and a programmer
won't.  In many cases, performing computations using oversized values may
be cheaper than checking for overflow after every step, but only when
registers are sufficiently plentiful to allow such usage.  If it becomes
necessary to save/restore registers, checking whether a register is within
range of int32, trapping if not, and otherwise just storing the bottom
half and later reloading with sign extension may be faster than having to
save/restore all 64 bits.  Compilers will know a lot more about what
such optimizations would be useful than programmers could ever hope to, but
only if there exist a behavioral specification which provides that allows
compilers to freely select whether computations that exceed the range of
their integer type should yield arithmetically-correct results anyway, or
whether they should trap.

> This is finally getting to the point where something might be
> controversial.  The compiler could reasonably omit the bounds check -
> but I would hope it was able to issue a diagnostic message if it did so
> (assuming the appropriate warning flags).  Quick tests with gcc 4.9 show
> that while that compiler will omit unnecessary tests that come after
> undefined behaviour, it does not omit such tests that come before
> undefined behaviour.

I'm not sure how I see how it's useful to have the compiler omit the code
automatically and also emit warnings.  Either:

1. The code is correct, but the number of substitutions is small enough
   that once a programmer has read the warnings they won't pose too much
   of a distraction on future builds, in which case there probably won't
   have been enough optimizations to have much value.

2. The code is correct, and to avoid having massive numbers of warnings
   the programmer will immediately adds a directive to indicate that
   the apparent behavior is desired, in which case the value of having the
   compiler apply its inferences to code generation before the programmer
   adds the directive will be limited.

3. The code is incorrect, in which case having the compiler apply its
   inferences to code generation will be counter-productive.

In what situation is there significant value in having a compiler both warn
about what it perceives as dead code and eliminate it?

> Note, however, that the reason for all this is the bug in your code.  If
> the compiler omitted the test on reg_size, it is guilty of being
> unhelpful in aiding your debugging, not of generating incorrect code.  I
> believe compilers should be as helpful as possible in helping the
> programmer track bugs - /that/ is why I would be unhappy if it silently
> removed the test.

The purpose of code is to *meet requirements*.  A good language should allow
programmers to formulate a program meeting their requirements in a way which
is concise, readable, and *focused on those requirements that are unique to
their application*.  If more than 10% of the programs in a language will
need to meet some requirement, and if meeting the requirement "manually"
would be expensive, those factors should be taken as a strong indication
that the language should strive to minimize the amount of user-written code
necessary to meet those requirements.

> > Many programs are required to not let the creators of maliciously-crafted
> > inputs take over the machine.  That is hardly an obscure requirement.
> 
> If you don't make that requirement in the specification of the function,
> then it is obscure.  And since most functions are internal, rather than
> directly facing external input, then for most functions it is not a
> sensible requirement.

In cases where the amount of machine code required to make a function safe
against unsanitized data would be significant, it's often good to have
separate functions for sanitized and unsanitized inputs.  Absent a compelling
performance difference, however, I'd suggest that it's better to have a
policy that code should be made "safe" by default.

> > If compilers are allowed to use arithmetic overflow as an excuse to bypass
> > code that would otherwise prevent maliciously-crafted inputs from taking
> > over the machine, then there will never be any situations where a non-broken
> > program which is bound by the above requirement could receive input that
> > would cause overflow.  I'm not quite sure what value there is in having an
> > optimizer which is only effective on broken programs.
> 
> If your code is correct, there is no problem.  The optimiser works best
> on correct code.

If in a correct program, no combination of inputs will produce UB, then what
inferences could an UB-based optimizer ever manage to draw about the inputs
to a correct program?

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

#70778

On 16/09/15 23:48, fir wrote:
> W dniu środa, 16 września 2015 23:33:49 UTC+2 użytkownik fir
> napisał:
>> W dniu środa, 16 września 2015 23:17:24 UTC+2 użytkownik Ben
>> Bacarisse napisał:
>>> fir <profesor.fir@gmail.com> writes: <snip>
>>>>>>> On 2015.09.16 13:35, fir wrote:
>>>>>>>> I encountered recently some example like this, Though i
>>>>>>>> not tested it
>>>>>>>> 
>>>>>>>> its in jave i dont know what >>> means
>>>>>>>> 
>>>>>>>> /** Robert Jenkins' 96 bit Mix Function. */ private
>>>>>>>> static int mix(int a, int b, int c) { a=a-b;  a=a-c;
>>>>>>>> a=a^(c >>> 13); b=b-c;  b=b-a;  b=b^(a << 8); c=c-a;
>>>>>>>> c=c-b;  c=c^(b >>> 13); a=a-b;  a=a-c;  a=a^(c >>>
>>>>>>>> 12); b=b-c;  b=b-a;  b=b^(a << 16); c=c-a;  c=c-b;
>>>>>>>> c=c^(b >>> 5); a=a-b;  a=a-c;  a=a^(c >>> 3); b=b-c;
>>>>>>>> b=b-a;  b=b^(a << 10); c=c-a;  c=c-b;  c=c^(b >>> 15); 
>>>>>>>> return c; }
>>> <snip>
>>>> so in short it means it is inpossible to revrite it to c?
>>> 
>>> No, that's not it at all.  It should be obvious that a C re-write
>>> is possible.  The only question is how much effort do you want to
>>> put in to make the code have *exactly* the same semantics on
>>> *every* conforming C implementation.  The answer is none,
>>> because, ironically, the original Jenkins hash function was
>>> written C.  The Java re-write has been forced to use signed
>>> integers (presumably it's old Java) and has therefore has altered
>>> the semantics (though probably not at the bit-level).  Anyway, 
>>> just use the original C version.
>>> 
>>> Or even use one of the newer hash function he's designed like: 
>>> http://www.burtleburtle.net/bob/hash/spooky.html
>>> 
>> 
>> aa-h, okay though if this particular example has its easy
>> correspondent doesnt probably neccessary mean that all code that
>> uses signed or unsigned shifts on negative integers can be
>> revritten (and thats a bit worry - they should gave at least all
>> those intrinsics in gcc if x86 supports it (and x86 afaik supports
>> a wide wariety of shifts)
>> 
>> I vote for gcc intrinsics for all the x86 usable assembly to use
>> (intrinsics should be probably standard term in c, as its great
>> usability (not necessary 'portab;e' 9avaliable on all c targets,
>> but as a platform dependant parts of stdlib or something (who said
>> stdlib must be all portable) ) **
>> 
>> (** it all untill ev some more organisation will be done, as im not
>> great fan of clib at all, but intrinsics are at least extreamly
>> usable 'patch' for platforms (or seems so))
> 
> this is word on c standard (that maybe those people who care much
> about standard should be interested maybe on this topic) ->
> 
> it is okay that c is designed to work on so wide variety of platforms
> and thus has so many undefined parts ((though c has also iirc some
> undefined parts that are not justified by different platform
> behaviours - those maybe should be just defined))
> 
> but if so c should also probably standarize some platform dependant
> parts by some groups of platforms 9it seems so), for example if the
> talk is x86 platform or alike, there is need of standarisation those
> outa-core-standard parts across gcc-vs-clang or what else; becouse if
> no it is practically silly (behaviours that could be
> agreed/coordinated on platforms are not..
> 

There are far too many different platforms and targets for C for this to
make sense.  And these days, C is a minor (but vitally important)
language on x86, especially with Windows - while it is the biggest
choice by far on embedded systems.  So gcc supports some 30+ target
processors, and they have no interest in trying to make intrinsics for
all opcodes on all platforms.  There is already a way to handle that -
it's called assembly, with gcc inline assembly for mixing it with C code.

For many targets, gcc /does/ have intrinsics for some of the most
commonly needed opcodes that are not easily expressed in C.  Thus there
are intrinsics for a lot of SIMD stuff on x86, or atomic access
instructions.

> - this leads admittedly to some c variants, like c-x86 c-something
> other , but better that than nothing (probably))
> 
> 

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web