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

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

C Compilers QoI

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

Contents

  C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 13:01 +0000
    Re: C Compilers QoI mark.bluemel@gmail.com - 2017-03-14 06:16 -0700
    Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 06:42 -0700
    Re: C Compilers QoI "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-14 06:56 -0700
      Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 15:58 +0000
        Re: C Compilers QoI "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-14 09:22 -0700
        Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-14 16:54 +0000
          Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 10:24 -0700
            Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-14 17:58 +0000
              Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 14:12 -0700
                Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-14 16:34 -0500
                Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-14 17:36 -0500
                  Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 23:06 +0000
                  Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 16:20 -0700
                Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-15 02:32 +0000
                  Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-15 12:49 +0000
                  Re: C Compilers QoI supercat@casperkitty.com - 2017-03-15 11:56 -0700
                    Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-15 23:09 +0000
                      Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-16 18:17 +0000
                        Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 11:47 -0700
                          Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 07:50 +1300
                            Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 12:59 -0700
                              Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-16 21:24 +0100
                                Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 14:23 -0700
                                  Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:30 +1300
                                    Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:38 +1300
                                      Re: C Compilers QoI Gareth Owen <gwowen@gmail.com> - 2017-03-17 05:07 +0000
                                        Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 20:26 +1300
                                          Re: C Compilers QoI Gareth Owen <gwowen@gmail.com> - 2017-03-17 07:59 +0000
                                    Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 16:14 -0700
                                      Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-16 22:54 -0500
                                        Re: C Compilers QoI supercat@casperkitty.com - 2017-03-17 09:01 -0700
                                      Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-26 14:16 +1300
                                        Re: C Compilers QoI supercat@casperkitty.com - 2017-03-26 14:19 -0700
                                          Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-26 22:43 +0100
                                            Re: C Compilers QoI GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-03-27 01:28 +0200
                                            Re: C Compilers QoI supercat@casperkitty.com - 2017-03-26 22:07 -0700
                                              Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 11:28 +0100
                                                Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 07:38 -0700
                                                  Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 16:23 +0100
                                                    Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 08:55 -0700
                                                      Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 17:01 +0100
                                                        Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 10:03 -0700
                                                    Re: C Compilers QoI GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-03-27 17:58 +0200
                                          Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-27 03:54 -0700
                                            Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 08:46 -0700
                                              Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-27 17:47 +0000
                                                Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 11:48 -0700
                                                  Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 15:37 -0500
                                                    Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 14:46 -0700
                                                      Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 20:28 -0500
                                                        Re: C Compilers QoI supercat@casperkitty.com - 2017-03-28 01:18 -0700
                                                          Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-28 18:24 -0500
                                                            Re: C Compilers QoI supercat@casperkitty.com - 2017-03-29 07:40 -0700
                                                              Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-29 17:05 +0200
                                                                Re: C Compilers QoI supercat@casperkitty.com - 2017-03-29 11:07 -0700
                                                              Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-31 04:04 +0000
                                                                Re: C Compilers QoI bartc <bc@freeuk.com> - 2017-03-31 10:53 +0100
                                                                  Re: C Compilers QoI Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-31 07:35 -0700
                                                                    Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 08:07 -0700
                                                                  Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 07:54 -0700
                                                                Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 07:43 -0700
                              Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:21 +1300
                                Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:24 +1300
                        Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 22:15 +0000
                          Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-17 12:31 +0000
                        Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-16 15:24 -0700
                          Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 16:03 -0700
                          Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-17 12:39 +0000
                            Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-17 08:27 -0700
                    Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-16 01:35 +0000
                      Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 02:18 +0000
                        Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-18 00:45 +0000
                          Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-18 13:12 +0000
                            Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-18 20:31 +0000
                              Re: C Compilers QoI supercat@casperkitty.com - 2017-03-18 17:31 -0700
                      Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 09:22 -0700
            Re: C Compilers QoI Nick Bowler <nbowler@draconx.ca> - 2017-03-24 16:13 +0000
              Re: C Compilers QoI supercat@casperkitty.com - 2017-03-24 12:32 -0700
                Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-24 22:13 -0500
                  Re: C Compilers QoI supercat@casperkitty.com - 2017-03-25 13:05 -0700
                    Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 15:44 -0500
                      Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 14:51 -0700
                        Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 20:31 -0500
          Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:26 +0000
            Re: C Compilers QoI Andrew Haley <andrew29@littlepinkcloud.invalid> - 2017-03-15 12:02 -0500
    Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 15:00 +0100
      Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 07:36 -0700
        Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 15:57 +0100
        Re: C Compilers QoI Andrey Tarasevich <andreytarasevich@hotmail.com> - 2017-03-14 08:11 -0700
          Re: C Compilers QoI BGB <cr88192@hotmail.com> - 2017-03-29 23:51 -0500
      Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 15:28 +0000
        Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 21:41 +0100
    Re: C Compilers QoI Keith Thompson <kst-u@mib.org> - 2017-03-14 09:26 -0700
      Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 18:23 +0000
        Re: C Compilers QoI Keith Thompson <kst-u@mib.org> - 2017-03-14 12:05 -0700
    Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 09:35 -0700
      Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:08 +0000
        Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 10:24 -0700
          Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:34 +0000
          Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 11:55 -0700
            Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:03 +0000
              Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:06 +0000
              Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 12:10 -0700
                Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 21:14 +0000
                  Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 14:42 -0700
                  Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 14:53 -0700
                    Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 23:20 +0000
                      Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-15 02:43 +0000
    Re: C Compilers QoI jacobnavia <jacob@jacob.remcomp.fr> - 2017-03-14 19:39 +0100
      Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:10 +0000
    Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-14 19:29 +0000
    Re: C Compilers QoI Noob <root@127.0.0.1> - 2017-03-15 09:27 +0100
    Re: C Compilers QoI ed_davis2@yahoo.com - 2017-03-16 15:10 -0700
      Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 23:19 +0000

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

#107165

On Monday, March 27, 2017 at 10:23:42 AM UTC-5, Bart wrote:
> > If the same machine code would be usable for the in-place and disjoint-
> > destination scenarios, would it make sense to require that the code for
> > the three-operand form check whether the destination matches one of the
> > sources and call a separate function that runs at just the same speed as
> > the three-operand form?
> 
> I don't get you. Why would x=x+y be undefined behaviour?

A compiler could not achieve efficient vectorization unless either the
pointers were declared "restrict", or the compiler generated separate
code to handle cases where some objects that are written in the loop get
read in a later iteration.  If the pointers were declared "restrict",
then accessing a location via the source pointer and then writing that
same location via the destination pointer would invoke UB.

I recognize that it can be beneficial to be able to say "add the contents
of x to y" in addition to being able to say "store the sum of x and y into
z", but it is less than helpful to have a three-operand form *require*
that all three operands be distinct.

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

#107168

On 27/03/2017 16:55, supercat@casperkitty.com wrote:
> On Monday, March 27, 2017 at 10:23:42 AM UTC-5, Bart wrote:
>>> If the same machine code would be usable for the in-place and disjoint-
>>> destination scenarios, would it make sense to require that the code for
>>> the three-operand form check whether the destination matches one of the
>>> sources and call a separate function that runs at just the same speed as
>>> the three-operand form?
>>
>> I don't get you. Why would x=x+y be undefined behaviour?
>
> A compiler could not achieve efficient vectorization unless either the
> pointers were declared "restrict", or the compiler generated separate
> code to handle cases where some objects that are written in the loop get
> read in a later iteration.  If the pointers were declared "restrict",
> then accessing a location via the source pointer and then writing that
> same location via the destination pointer would invoke UB.
>
> I recognize that it can be beneficial to be able to say "add the contents
> of x to y" in addition to being able to say "store the sum of x and y into
> z", but it is less than helpful to have a three-operand form *require*
> that all three operands be distinct.


OK. Although I have plenty of functions that take pointers such as 
(x,y,z), of which perhaps z is a destination, and I have to specify in 
the docs that x and z for example could be the same.

But this is to help in writing the right code within the function (don't 
write to *z before it's done reading from *x) rather than any language 
issues.

-- 
bartc

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

#107178

On Monday, March 27, 2017 at 11:01:53 AM UTC-5, Bart wrote:
> OK. Although I have plenty of functions that take pointers such as 
> (x,y,z), of which perhaps z is a destination, and I have to specify in 
> the docs that x and z for example could be the same.
> 
> But this is to help in writing the right code within the function (don't 
> write to *z before it's done reading from *x) rather than any language 
> issues.

In this particualar scenario, the problem is that there is only one kind of
"restrict", when there are multiple levels of guarantees that could be
helpful, with stronger ones allowing more optimization but being usable in
fewer situations.  IMHO, the guarantees could be most clearly expressed by
defining various qualifiers as saying either "A programmer guarantees that
transform X would not affect code semantics in any way the programmer cares
about" or "A programmer guarantees that transform X would not affect code
semantics *even in ways the programmer wouldn't care about*".  For example,
given something like:

    void blend(float *dest, float *src)
    {
      for (int i=0; i<64; i++)
        dest[i] = (src[i] + src[i+1])/2;
    }

a compiler which read source values in advance of when they were used in
the code (e.g. processing most of the loop by reading groups of four items,
adding them, and then writing them out) would not alter semantics in any
cases of interest, but a compiler which moved later-element writes ahead
of earlier-element reads (e.g. performing the loop in reverse order) might
alter semantics.

Offering ways by which programmers could allow some optimizations without
having to allow all would increase the number of useful optimization
opportunities compilers would have.  Being able to hoist reads and defer
writes are two of the most useful optimizations for vectorization; being
able to hoist writes can also be useful in some cases, but hoisting reads
is useful even in cases where hoisting writes would break code.

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

#107167

On Mon, 27 Mar 2017 16:23:34 +0100
BartC <bc@freeuk.com> wrote:


> I don't get you. Why would x=x+y be undefined behaviour?
> 
> Anyway I'm proposing nothing except that the user interface to such 
> function allows those two forms. It's an easy way of provided useful 
> extra information to whoever has to implement them, and gives a handy 
> extra choice to the user, who doesn't need to worry about annotating 
> code with optimisation tips that may not match the actual code.

Too much fragmentation kills the efficiency of any solution like Linux systems
for example.


> (However, I've implemented both functions in my own language, with a 
> poor optimiser but more transparent code, and there was little 
> difference, perhaps 5%, between:
> 
>    add_vector(a,a,b,n);
> 
> and:
> 
>    iadd_vector(a,b,n);
> 
> Here, it's probably mostly down to the memory throughput. The test used 
> n=1 million, arrays of doubles, mostly containing 0.0, and calling each 
> 1000 times. Testing it with n=1000, and 1 million iterations to keep 
> everything in-cache, then the in-place version was 20% faster.)

You could merge both functions with only one prototype such as:

void add_vector(float *result, float *a, float *b);

If the "result" vector is NULL then the vector "a" is overwritten.

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

#107150

On Monday, March 27, 2017 at 12:19:55 AM UTC+3, supe...@casperkitty.com wrote:

> 
> I don't know FORTRAN, but I'm pretty sure it wouldn't require writing out
> the code four times to achieve the required semantics.

FYI, FORTRAN is an historical name of an old language that has very similar aliasing rules to C.
Modern variants of the languages are called Fortran.
I hardly know it either, but I think that the aliasing semantics of the serial part of the language are still the same as of C or of old Fortran/FORTRAN. But in modern Fortran (90 or later) you can sometimes write code in parallel manner (I know enough to be sure that it is possible for your example) and then aliasing rules are close to what you want.

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

#107163

On Monday, March 27, 2017 at 5:55:03 AM UTC-5, already...@yahoo.com wrote:
> FYI, FORTRAN is an historical name of an old language that has very similar aliasing rules to C.
> Modern variants of the languages are called Fortran.

Okay, noted.

> I hardly know it either, but I think that the aliasing semantics of the serial part of the language are still the same as of C or of old Fortran/FORTRAN. But in modern Fortran (90 or later) you can sometimes write code in parallel manner (I know enough to be sure that it is possible for your example) and then aliasing rules are close to what you want.

My impression was that at least in FORTRAN-77, if a function accepted
an array it was only possible to pass a reference to the start of it.
I would expect that using the same syntax in newer versions of Fortran
would have the same restriction since it allows useful optimizations,
though I wouldn't be surprised if there was also a syntax that could
use pointers in a more general way, at the cost of optimizations.

If one is using a compiler that can effectively optimize array accesses--
something that I've been told FORTRAN could do even in the 1960s--most
application fields won't get much benefit from using pointer arithmetic
beyond direct array element access.  The more general pointer arithmetic
in C serves two purposes: (1) it is needed for some kinds of low-level
programming; (2) it's simpler for a compiler to let a programmer perform
address-computation optimizations manually than for a compiler to do so
automatically.

C is great for systems programming, when used with implementations designed
for that purpose.  The easing of compiler resource constraints means that
far less is gained by having programmers do manual pointer arithmetic.  In
fact, optimal code generation will often require that compilers undo manual
optimization efforts.  For example, given:

    int n=1000;
    int *p1 = arr1,*p2 = arr2;
    do
      *p1++ += *p2++;
    while(--x);

the optimal x86-32 code would probably be equivalent to:

    int n=-1000;
    do
      (arr1+1000)[n] += (arr2+1000)[n];
    while(++n);

On many older architectures, the cost of post-increment addressing would
have been less than the cost of performing the array indexing within the
loop.  On x86-32, however, scaled index computations are free but pointer
increments aren't, so a good compiler should try to replace the former
with something like the latter.

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

#107183

supercat@casperkitty.com writes:
>On Monday, March 27, 2017 at 5:55:03 AM UTC-5, already...@yahoo.com wrote:
>> FYI, FORTRAN is an historical name of an old language that has very simil=
>ar aliasing rules to C.
>> Modern variants of the languages are called Fortran.
>
>
>On many older architectures, the cost of post-increment addressing would
>have been less than the cost of performing the array indexing within the
>loop.  On x86-32, however, scaled index computations are free but pointer
>increments aren't, so a good compiler should try to replace the former
>with something like the latter.

On the other hand, ARM64 does have post (and pre) incrementing
loads and stores.

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

#107192

On Monday, March 27, 2017 at 12:47:49 PM UTC-5, Scott Lurndal wrote:
> supercat writes:
> >On many older architectures, the cost of post-increment addressing would
> >have been less than the cost of performing the array indexing within the
> >loop.  On x86-32, however, scaled index computations are free but pointer
> >increments aren't, so a good compiler should try to replace the former
> >with something like the latter.
> 
> On the other hand, ARM64 does have post (and pre) incrementing
> loads and stores.

Some flavors of ARM do, but not all.  On Cortex-M0, floating-point
performance would trump everything else, but the best way to write
the loop with vectors of integers would probably be equivalent to

    int n=-4000;
    do
      *(float*)((char*)arr1+4000+n) += *(*float)((char*)arr2+4000+n);
    while(n+=4); 

I find it curious that Ritchie didn't define operators for byte-based
pointer arithmetic in addition to those for the ones for arithmetic
based upon pointer size (maybe ~+, ~-, and ~[]).  To be sure, source
code using the size-based operators would often be more readable, but
source code using the latter would have been a lot easier to turn into
efficient machine code on many platforms.  If a machine has addressing
modes that can add a pointer and an unscaled displacement, a compiler
for such a machine could more easily generate efficient code for

    ptrdiff_t n = 999 * sizeof (int);
    do
      arr1~[n] += arr2~[n];
    while( (n-=sizeof(int)) >= 0);

than for a form which used normal array subscripts.

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

#107212

On Mon, 27 Mar 2017 11:48:59 -0700 (PDT), supercat@casperkitty.com
wrote:

>On Monday, March 27, 2017 at 12:47:49 PM UTC-5, Scott Lurndal wrote:
>> supercat writes:
>> >On many older architectures, the cost of post-increment addressing would
>> >have been less than the cost of performing the array indexing within the
>> >loop.  On x86-32, however, scaled index computations are free but pointer
>> >increments aren't, so a good compiler should try to replace the former
>> >with something like the latter.
>> 
>> On the other hand, ARM64 does have post (and pre) incrementing
>> loads and stores.
>
>Some flavors of ARM do, but not all.  On Cortex-M0, floating-point
>performance would trump everything else, but the best way to write
>the loop with vectors of integers would probably be equivalent to
>
>    int n=-4000;
>    do
>      *(float*)((char*)arr1+4000+n) += *(*float)((char*)arr2+4000+n);
>    while(n+=4); 
>
>I find it curious that Ritchie didn't define operators for byte-based
>pointer arithmetic in addition to those for the ones for arithmetic
>based upon pointer size (maybe ~+, ~-, and ~[]).  To be sure, source
>code using the size-based operators would often be more readable, but
>source code using the latter would have been a lot easier to turn into
>efficient machine code on many platforms.  If a machine has addressing
>modes that can add a pointer and an unscaled displacement, a compiler
>for such a machine could more easily generate efficient code for
>
>    ptrdiff_t n = 999 * sizeof (int);
>    do
>      arr1~[n] += arr2~[n];
>    while( (n-=sizeof(int)) >= 0);
>
>than for a form which used normal array subscripts.


It might it a bit simpler, but that kind of strength-reduction as an
optimization technique goes back to the late fifties and the very
first Fortran compiler.

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

#107219

On Monday, March 27, 2017 at 3:37:11 PM UTC-5, robert...@yahoo.com wrote:
> On Mon, 27 Mar 2017 11:48:59 -0700 (PDT), supercat wrote:
> >I find it curious that Ritchie didn't define operators for byte-based
> >pointer arithmetic in addition to those for the ones for arithmetic
> >based upon pointer size (maybe ~+, ~-, and ~[]).  To be sure, source
> >code using the size-based operators would often be more readable, but
> >source code using the latter would have been a lot easier to turn into
> >efficient machine code on many platforms.  If a machine has addressing
> >modes that can add a pointer and an unscaled displacement, a compiler
> >for such a machine could more easily generate efficient code for
> >
> >    ptrdiff_t n = 999 * sizeof (int);
> >    do
> >      arr1~[n] += arr2~[n];
> >    while( (n-=sizeof(int)) >= 0);
> >
> >than for a form which used normal array subscripts.

> It might it a bit simpler, but that kind of strength-reduction as an
> optimization technique goes back to the late fifties and the very
> first Fortran compiler.

It does indeed, but FORTRAN uses a very restricted form of DO loop, and
early versions also restricted the forms of array subscripts.  C was
designed to facilitate single-pass compilation, but there is no way that
a compiler which sees only as far as:

    void hey(int *p1, int *p2)
    {
      int i;
      for (i=0; i<10; i++)
      {
        p1[i] = p2[i];

can know whether it should attempt strength reduction on the pointer index
computations because it would have no way of knowing whether any of the
variables involved would get modified within the loop.  By contrast, a
FORTRAN or Fortran compiler would know, having seen a similar portion of
a DO loop, that nothing would modify its equivalents of i, p1, or p2.

Applying compiler-based strength-reduction in a language with tightly
restricted loop semantics is easy.  Applying it in C is much harder, since
the language was not designed to facilitate it but instead minimize the
need for it.

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

#107240

On Mon, 27 Mar 2017 14:46:17 -0700 (PDT), supercat@casperkitty.com
wrote:

>On Monday, March 27, 2017 at 3:37:11 PM UTC-5, robert...@yahoo.com wrote:
>> On Mon, 27 Mar 2017 11:48:59 -0700 (PDT), supercat wrote:
>> >I find it curious that Ritchie didn't define operators for byte-based
>> >pointer arithmetic in addition to those for the ones for arithmetic
>> >based upon pointer size (maybe ~+, ~-, and ~[]).  To be sure, source
>> >code using the size-based operators would often be more readable, but
>> >source code using the latter would have been a lot easier to turn into
>> >efficient machine code on many platforms.  If a machine has addressing
>> >modes that can add a pointer and an unscaled displacement, a compiler
>> >for such a machine could more easily generate efficient code for
>> >
>> >    ptrdiff_t n = 999 * sizeof (int);
>> >    do
>> >      arr1~[n] += arr2~[n];
>> >    while( (n-=sizeof(int)) >= 0);
>> >
>> >than for a form which used normal array subscripts.
>
>> It might it a bit simpler, but that kind of strength-reduction as an
>> optimization technique goes back to the late fifties and the very
>> first Fortran compiler.
>
>It does indeed, but FORTRAN uses a very restricted form of DO loop, and
>early versions also restricted the forms of array subscripts.  C was
>designed to facilitate single-pass compilation, but there is no way that
>a compiler which sees only as far as:
>
>    void hey(int *p1, int *p2)
>    {
>      int i;
>      for (i=0; i<10; i++)
>      {
>        p1[i] = p2[i];
>
>can know whether it should attempt strength reduction on the pointer index
>computations because it would have no way of knowing whether any of the
>variables involved would get modified within the loop.  By contrast, a
>FORTRAN or Fortran compiler would know, having seen a similar portion of
>a DO loop, that nothing would modify its equivalents of i, p1, or p2.


While it's true that pointer aliasing is a major issue for C
optimization, there's really not an issue with applying strength
reduction in the above case.  i does not alias anything pointed to by
p1 or p2, nor do p1 or p2 themselves (the function parameters).  What
p1 and p2 do point to *can* alias, so the compiler would be hard
pressed to convert the loop into a (say) memcpy.  But converting the
above into something like the following should be no problem:


    void hey(int *p1, int *p2)
    {
      int i;
      (do-ten-times)
      {
        *p1 = *p2;
        p1++;
        p2++;
      }
    }

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

#107249

On Monday, March 27, 2017 at 8:28:09 PM UTC-5, robert...@yahoo.com wrote:
> On Mon, 27 Mar 2017 14:46:17 -0700 (PDT), supercat wrote:
> 
> >On Monday, March 27, 2017 at 3:37:11 PM UTC-5, robert...@yahoo.com wrote:
> >> On Mon, 27 Mar 2017 11:48:59 -0700 (PDT), supercat wrote:
> >It does indeed, but FORTRAN uses a very restricted form of DO loop, and
> >early versions also restricted the forms of array subscripts.  C was
> >designed to facilitate single-pass compilation, but there is no way that
> >a compiler which sees only as far as:
> >
> >    void hey(int *p1, int *p2)
> >    {
> >      int i;
> >      for (i=0; i<10; i++)
> >      {
> >        p1[i] = p2[i];

> While it's true that pointer aliasing is a major issue for C
> optimization, there's really not an issue with applying strength
> reduction in the above case.  i does not alias anything pointed to by
> p1 or p2, nor do p1 or p2 themselves (the function parameters).  What
> p1 and p2 do point to *can* alias, so the compiler would be hard
> pressed to convert the loop into a (say) memcpy.  But converting the
> above into something like the following should be no problem:
> 
>     void hey(int *p1, int *p2)
>     {
>       int i;
>       (do-ten-times)
>       {
>         *p1 = *p2;
>         p1++;
>         p2++;
>       }
>     }

If there was nothing in the loop beyond what I showed, a compiler could apply
the indicated strength reduction, but a single-pass compiler would have to
determine whether to apply strength reduction to the above code before it
could know whether there was anything beyond.  In languages which use more
tightly-controlled counting loops and pass-by-reference semantics, it would
not be necessary to see an entire loop to know that they would uphold the
invariants necessary for strength reduction.  C, however, makes no syntactic
distinction between a "for" loop which will be used only for straightforward
sequential counting and one which which might have the control variable
modified within it.

To make things even more interesting, suppose the next statement within the
loop were

        p2[i] = 0;

could the compiler reuse the address it had just computed for the earlier
p1[i] = p2[i]?  Without seeing the rest of the loop it couldn't know.  The
remainder of the loop might do something sneaky like:

        i=-1;
        p1=&i;
      }
    }

At the start of the second pass, i would be 0 and p1 will point to i.
Thus, whatever was in p2[0] would be copied to i.  If that happens to
be 42, then the assignment to p2[i] would hit p2[42].  If p2[42] exists,
behavior will be 100% defined, and a compiler will thus be required
to allow for such a possibility.

A C compiler that can see an entire loop can perform strength reduction, but
it's generally not possible to know that such things are safe unless a
compiler can see everything within a loop.  Other languages have tighter
semantics which allow for strength reduction techniques to be applied even
when a compiler can't see everything.

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

#107341

On Tue, 28 Mar 2017 01:18:54 -0700 (PDT), supercat@casperkitty.com
wrote:

>On Monday, March 27, 2017 at 8:28:09 PM UTC-5, robert...@yahoo.com wrote:
>> On Mon, 27 Mar 2017 14:46:17 -0700 (PDT), supercat wrote:
>> 
>> >On Monday, March 27, 2017 at 3:37:11 PM UTC-5, robert...@yahoo.com wrote:
>> >> On Mon, 27 Mar 2017 11:48:59 -0700 (PDT), supercat wrote:
>> >It does indeed, but FORTRAN uses a very restricted form of DO loop, and
>> >early versions also restricted the forms of array subscripts.  C was
>> >designed to facilitate single-pass compilation, but there is no way that
>> >a compiler which sees only as far as:
>> >
>> >    void hey(int *p1, int *p2)
>> >    {
>> >      int i;
>> >      for (i=0; i<10; i++)
>> >      {
>> >        p1[i] = p2[i];
>
>> While it's true that pointer aliasing is a major issue for C
>> optimization, there's really not an issue with applying strength
>> reduction in the above case.  i does not alias anything pointed to by
>> p1 or p2, nor do p1 or p2 themselves (the function parameters).  What
>> p1 and p2 do point to *can* alias, so the compiler would be hard
>> pressed to convert the loop into a (say) memcpy.  But converting the
>> above into something like the following should be no problem:
>> 
>>     void hey(int *p1, int *p2)
>>     {
>>       int i;
>>       (do-ten-times)
>>       {
>>         *p1 = *p2;
>>         p1++;
>>         p2++;
>>       }
>>     }
>
>If there was nothing in the loop beyond what I showed, a compiler could apply
>the indicated strength reduction, but a single-pass compiler would have to
>determine whether to apply strength reduction to the above code before it
>could know whether there was anything beyond. In languages which use more
>tightly-controlled counting loops and pass-by-reference semantics, it would
>not be necessary to see an entire loop to know that they would uphold the
>invariants necessary for strength reduction.  C, however, makes no syntactic
>distinction between a "for" loop which will be used only for straightforward
>sequential counting and one which which might have the control variable
>modified within it.
>
>To make things even more interesting, suppose the next statement within the
>loop were
>
>        p2[i] = 0;
>
>could the compiler reuse the address it had just computed for the earlier
>p1[i] = p2[i]?  Without seeing the rest of the loop it couldn't know.  The
>remainder of the loop might do something sneaky like:
>
>        i=-1;
>        p1=&i;
>      }
>    }
>
>At the start of the second pass, i would be 0 and p1 will point to i.
>Thus, whatever was in p2[0] would be copied to i.  If that happens to
>be 42, then the assignment to p2[i] would hit p2[42].  If p2[42] exists,
>behavior will be 100% defined, and a compiler will thus be required
>to allow for such a possibility.
>
>A C compiler that can see an entire loop can perform strength reduction, but
>it's generally not possible to know that such things are safe unless a
>compiler can see everything within a loop.  Other languages have tighter
>semantics which allow for strength reduction techniques to be applied even
>when a compiler can't see everything.


It's 2017. single pass compilers for C or C++ are not very relevant.
For the same effort as doing one you could do a Clang or gcc port.

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

#107390

On Tuesday, March 28, 2017 at 6:24:07 PM UTC-5, robert...@yahoo.com wrote:
> It's 2017. single pass compilers for C or C++ are not very relevant.
> For the same effort as doing one you could do a Clang or gcc port.

Many aspects of C seem stuck with the requirement for single-pass compilation.
For example, even though the convention for a long time had been to pass
arrays followed by their size, C99 requires that a function which processes
multi-dimensional VLA to accept the length first.

Further, my point was that I found it curious that C didn't include a set
of pointer arithmetic operators (e.g. ~+, ~-, and ~[]) that were byte-based
rather than object-based, since such operators would have made it possible
for programmers and compilers to perform strength reduction with the kinds
of compilers that were in use back then.  If C's "for" loops had the kind of
limited semantics of FORTRAN's DO loops, even single-pass-plus-backpatch
compilers could have performed such strength reduction automatically, but
since they don't, byte-based operators could have helped.

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

#107392

On 29/03/17 16:40, supercat@casperkitty.com wrote:
> On Tuesday, March 28, 2017 at 6:24:07 PM UTC-5, robert...@yahoo.com wrote:
>> It's 2017. single pass compilers for C or C++ are not very relevant.
>> For the same effort as doing one you could do a Clang or gcc port.
> 
> Many aspects of C seem stuck with the requirement for single-pass compilation.
> For example, even though the convention for a long time had been to pass
> arrays followed by their size, C99 requires that a function which processes
> multi-dimensional VLA to accept the length first.
> 

C requires things to be declared before use.  To determine the type of a
multi-dimensional array, all but one of the dimensions must be declared
before the type can be known.

This has nothing to do with single-pass compilation (though it would
make it /easier/ to make a single-pass compiler, it is perfectly
possible to have a single-pass compiler for a language where things are
declared shortly after they are really needed.  Pascal is an example of
such a language).

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

#107411

On Wednesday, March 29, 2017 at 10:05:45 AM UTC-5, David Brown wrote:
> C requires things to be declared before use.  To determine the type of a
> multi-dimensional array, all but one of the dimensions must be declared
> before the type can be known.

At what point is the value of an array-size expression actually *used*?
From what I can tell, it is only used if code needs to compute its size,
either for purposes of sizeof or pointer arithmetic.  Since the size of
a VLA is not a compile-time constant, the compiler won't need to know
the size of an array until the code using it starts executing.

Thus, the code:

   int processArray(float dat[rows][cols], int rows, int cols)
   {
     for (r=0; r<rows; r++)
       for (c=0; c<cols; c++)
         dat[r][c]+=1.0;
   }

would be equivalent to:

   int processArray(float *__arg1, int x, int y)
   {
     float (*dat)[cols] = (float (*)[cols])__arg1;

     for (r=0; r<rows; r++)
       for (c=0; c<cols; c++)
         dat[r][c]+=1.0;
   }

except that the former might allow a compiler to warn if an attempt is made
to pass a pointer of a array with improper dimensions while the latter would
provide no such opportunity.

Also, out of curiosity, how do compilers handle situations like:

   int foo(int *p, int arr[][* // Compiler has gotten this far

where the next thing could be either ] or a p]?  Do they use normal scanning
as though the expect an expression, and then kludge into the error-reporting
code so it doesn't squawk in the case where an unexpected ] occurs while
processing a unary * which is the only token within a [] pair, or do they
look ahead when they encounter a [ to see if the next two tokens are *], or
what?

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

#107531

supercat@casperkitty.com wrote:
> 
> Further, my point was that I found it curious that C didn't include a set
> of pointer arithmetic operators (e.g. ~+, ~-, and ~[]) that were byte-based
> rather than object-based, since such operators would have made it possible
> for programmers and compilers to perform strength reduction with the kinds
> of compilers that were in use back then.

For program writen in pointer style such operators would be
almost of no use, after all normal case is to go to next 
element.  And if needed programmer could define pointers
as char * and use casts when dereferencing.  AFAICS with naive
compilers programmer was supposed to choose between array style
and pointer style.  So nonoptimizing compiler would have almost
no opportunity to perform useful strength reduction.  OTOH
by not having such operators compiler can be smaller, which
was important at that time.

Take into account that in early C days people started looking
at relative frequencies of various operations.  And when
something is rare enough it is not worth optimizing.

-- 
                              Waldek Hebisch

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

#107537

On 31/03/2017 05:04, antispam@math.uni.wroc.pl wrote:
> supercat@casperkitty.com wrote:
>>
>> Further, my point was that I found it curious that C didn't include a set
>> of pointer arithmetic operators (e.g. ~+, ~-, and ~[]) that were byte-based
>> rather than object-based, since such operators would have made it possible
>> for programmers and compilers to perform strength reduction with the kinds
>> of compilers that were in use back then.
>
> For program writen in pointer style such operators would be
> almost of no use, after all normal case is to go to next
> element.

In that case you'd be looking at ++ and --, not adding or subtracting an 
arbitrary offset to a pointer.

   And if needed programmer could define pointers
> as char * and use casts when dereferencing.  AFAICS with naive
> compilers programmer was supposed to choose between array style
> and pointer style.  So nonoptimizing compiler would have almost
> no opportunity to perform useful strength reduction.  OTOH
> by not having such operators compiler can be smaller, which
> was important at that time.
>
> Take into account that in early C days people started looking
> at relative frequencies of various operations.  And when
> something is rare enough it is not worth optimizing.

It would be reasonable to have had a choice between byte and element 
offset. And it's useful from the time to time: if you have an int* 
pointing to the start of a struct, then it would be convenient to make 
use of a generic byte offset to access some particular member.

Especially if the int members are not aligned, then you can't convert 
the byte offset to an element offset (by dividing the offset by 4 or 8).

Also, if subtracting two pointers of type T*, sometimes you need an 
offset in bytes compatible with subtracting two U* pointers. (Eg. offset 
between two struct members of different types.)

Now you'd have to use (p-q)*sizeof(*p). In fact, what happens at the 
moment is that (p-q), which has a natural byte offset at machine level, 
has to be divided by sizeof (*p) to get the element offset, then you 
have to multiply by sizeof(*p) to get back the byte offset! These ought 
to be cancel out, but that optimisation has to be done.

You can convert to and from char*, but it's messy.

-- 
bartc

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

#107538

On Friday, March 31, 2017 at 10:53:38 AM UTC+1, Bart wrote:
> On 31/03/2017 05:04, antispam@math.uni.wroc.pl wrote:
> > supercat@casperkitty.com wrote:
> >>
>
> It would be reasonable to have had a choice between byte and element 
> offset. And it's useful from the time to time: if you have an int* 
> pointing to the start of a struct, then it would be convenient to make 
> use of a generic byte offset to access some particular member.
> 
> Especially if the int members are not aligned, then you can't convert 
> the byte offset to an element offset (by dividing the offset by 4 or 8).
> 
What you really need is a bit buffer description language so that you can
pull out the integer, regardless of offset, width, or encoding. 

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

#107541

On Friday, March 31, 2017 at 9:36:14 AM UTC-5, Malcolm McLean wrote:
> On Friday, March 31, 2017 at 10:53:38 AM UTC+1, Bart wrote:
> > Especially if the int members are not aligned, then you can't convert 
> > the byte offset to an element offset (by dividing the offset by 4 or 8).
> > 
> What you really need is a bit buffer description language so that you can
> pull out the integer, regardless of offset, width, or encoding.

If C is to be viewed as a language for writing portable programs, rather than
as a language which can be implemented on a variety of systems to allow people
to write programs for them, it's long overdue for such a feature.

If there were e.g. a type "32-bit integer, stored with 8 bits in each of 4
consecutive bytes, big-endian", then such a type could be implemented on
any system that can run C, a compiler's code to use such a type could easily
be at least as efficient as the code a programmer would have to write to
work around its absence.  Further, in many cases it would be easier for a
compiler to generate decent code to work with such types than it would be
for a compiler to recognize all the ways programmers might try to work around
their absence and generate decent code for those.

For example, on a 32-bit platform which has an instruction to reverse the
bytes in a  32-bit value, would it be easier to generate good code for:

    uint32be_t *x;
    ...
    *x+=1;

or for

    char *x;
    ...
    uint32_t temp = (x[3]<<24)|(x[2]<<16)|(x[1]<<8)|(x[0]);
    temp+=1;
    x[3]=(uint8_t)(temp>>24);
    x[2]=(uint8_t)(temp>>16);
    x[1]=(uint8_t)(temp>>8);
    x[0]=(uint8_t)(temp);

Existence of such types would not throw 36-bit platforms under the bus, but
would instead make it easier for people to write things like JPG decoders
in a way which could work with such platforms as well as octet-based ones.

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

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

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

csiph-web