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

Groups > comp.lang.c > #67778

Re: the language (and the role of Undefined Behavior therein)

Show all headers | View raw

On 8/18/15 7:19 PM, supercat@casperkitty.com wrote:
> On Saturday, December 20, 2014 at 12:36:33 PM UTC-6, James Kuyper wrote:
>> It might seem perverse to produce any other result - until you consider
>> optimizations. A shift expression could be optimized completely out of
>> the generated code, or it could be combined with another expression, and
>> the combination might be replaced by a different set of instructions
>> that is better for some reason. As long as the alternative instructions
>> have behavior that matches the standard's requirements, when it imposes
>> some, it doesn't matter what the alternative code does when the behavior
>> is undefined.
>
> A problem with that thinking is that it precludes the possibility of
>optimizing code based on a programmer's willingness to accept range of
>behaviors. Consider the following requirement and a method written in C
>to meet it:
>
>      /* Requirement 1: If n is 0 to 31, return the value of dat
>                        shifted left by n bits. */
>      uint32_t shl(uint32_t dat, uint32_t n)
>      {
>        return dat << n;
>      }
>
> Nice and simple, and compilers for many processors will be able to optimize it.  Now add one more requirement:
>
>      /* Requirement 2: If n is greater than 31, arbitrarily return either 0 or
>                        dat << (n & 31) */
>

If you are going to write your requirements to match 'common' machines 
in an attempt to optimize, you should be willing to expect that you are 
going to rely on machine dependent behavior. This is NOT the case that 
it will work naively on all machines. I seem to remember machines that 
would trap on excessive value on over sized values on register based 
shifts (I do admit it is very uncommon). If you want to be strictly 
conforming, you need to be strictly conforming.


> Feeding the simple code to vast majority of compilers written before
> 2009 would yield code meeting that requirement by default, though some
> compilers have "pedantic" or "diagnostic" modes where it would trap.
> Newer compilers, however, would require use something like one of the
> following, each of which can only yield optimal code with certain
> processors.
>
>      uint32_t shl_v1(uint32_t dat, uint32_t n) // Optimal for PC
>      {
>        return dat << (n & 31);
>      }
>      uint32_t shl_v2(uint32_t dat, uint32_t n) // Optimal for ARM
>      {
>        return (n & 255) < 32 ? dat << (n & 31) : 0;
>      }
>

My guess is that even today, as an independent function most compilers 
will do the simple thing in the original shift function. That IS the 
simplest code. You may need to separately compile the function on an 
aggressive compiler to keep it from propagating the permissions of 
undefined behavior against the callers.


> Any strictly-complaint means of writing the code will require that
> the  programmer select one of the above behaviors when n>=32, even if the
> programmer would be equally happy with either. Consequently, the effect
> of making a shift by 32 Undefined Behavior is that it will no longer be
> possible for both ARM and x86 compilers to generate the most efficient
> code meeting programmer requirements.
>
> A major key to facilitating behavior-based optimization in usable
> programs is that it should be possible to write code whose behavior is
> sufficiently constrained to meet programmer requirements, but
> loosely-enough constrained to allow a compiler some flexibility.
> Consider the following requirements/function:
>
>      /* Requirement 1: If the arithmetical values of a*b and c*d are
>                        both representable as int, return 1 if a*b > c*d
>                        and 0 otherwise. */
>      int mulcomp(int a, int b, int c, int d)
>      {
>        return a*b > c*d;
>      }
>
> Nice and simple, easy to read, and easy to optimize on a wide range of platforms.  Now add one more requirement:
>
>      /* Requirement 2: Do not negate the laws of time and causality, even if
>                        a*b or c*d is outside the range of int */
>
> Requirement 2 is just about the loosest requirement imaginable, and
> should be a "gimme". Unfortunately, since Undefined Behavior is allowed
> to negate the laws of time and causality (and on hyper-modern compilers
> it is prone to do so), it's not possible to meet requirement 1 with a
> function which is easily readable and will yield optimal code on all
> compilers. If one assumes that a long can hold the product of any two
> int values, the code could be written as:
>
>      int mulcomp(int a, int b, int c, int d)
>      {
>        return (long)a*b > (long)c*d;
>      }
>
> but that would likely be slow on many platforms--sometimes severely so.  Writing the code as

Any decent compiler will use the int*int->long multiply instruction in 
this case. It KNOWS the values are only int sized. Only a very dumb 
compiler would slow down on this, and that one would likely do the 
'right' thing on the first case.

Also, Undefined Behavior grants the implementation permission to break 
the laws of time and causality, it doesn't grant it the ability. If the 
implementers actually could break this, they are in the wrong business!

>
>      int mulcomp(int a, int b, int c, int d)
>      {
>        return (int)((unsigned)a*b) > (int)((unsigned)c*d);
>      }
>
> would work on most two's-complement platforms, but would yield
> sub-optimal performance on many DSPs. Further, the function is a lot
>less readable than the original, and ends up spending more code meeting
> what should be a "gimme" requirement than performing its primary purpose.
>

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-18 16:19 -0700
  Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-18 21:15 -0400
    Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 10:11 -0700
      Re: the language (and the role of Undefined Behavior therein) Ike Naar <ike@iceland.freeshell.org> - 2015-08-19 19:58 +0000
        Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 14:09 -0700
      Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-19 16:10 -0400
        Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 16:01 -0700
          Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-19 20:23 -0400
            Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 10:35 -0700
              Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-20 12:32 -0700
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 13:31 -0700
                Re: the language (and the role of Undefined Behavior therein) donalhambra@gmail.com - 2015-08-20 14:23 -0700
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 16:13 -0700
                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-20 17:48 -0700
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-21 01:32 -0700
                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-21 18:34 -0700
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-21 22:11 -0700
                Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-22 09:41 -0400
                Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-22 16:59 +0000
                Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-22 23:30 -0400
                Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 03:36 +0000
                Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 00:25 -0400
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 22:57 -0700
                Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 19:49 +0000
                Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-06 14:43 -0700
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 16:27 -0700
                Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 21:15 -0400
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 20:18 -0700
                Re: the language (and the role of Undefined Behavior therein) raltbos@xs4all.nl (Richard Bos) - 2015-08-22 14:37 +0000
                Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-22 19:12 -0700
                Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-22 23:38 -0400
                Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-23 20:01 -0700
                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-23 21:56 -0700
                Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-24 17:25 -0700
                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-24 18:21 -0700
                Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 22:22 -0400
                Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-25 14:31 +0000
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-25 09:22 -0700
                Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-25 18:55 +0000
                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-25 12:33 -0700
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-25 16:23 -0700
                Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 00:31 -0400
                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-24 10:32 -0700
                Re: the language (and the role of Undefined Behavior therein) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-22 23:54 -0700
                Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 03:45 +0000
                Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-07 08:11 -0700
      Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 18:46 -0400
        Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 19:04 -0700
          Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 23:40 -0400
            Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 22:48 -0700
              Re: the language (and the role of Undefined Behavior therein) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-24 00:38 -0700
  Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-18 21:22 -0400
  Re: the language (and the role of Undefined Behavior therein) Ike Naar <ike@iceland.freeshell.org> - 2015-08-20 21:44 +0000
    Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 16:48 -0700
    Re: the language (and the role of Undefined Behavior therein) Philip Lantz <prl@canterey.us> - 2015-08-20 23:41 -0700

csiph-web