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

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

Re: C speed

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: C speed "James R. Kuyper" <jameskuyper@verizon.net> - 2017-06-09 18:58 -0400
    Re: C speed supercat@casperkitty.com - 2017-06-09 16:21 -0700
      Re: C speed David Brown <david.brown@hesbynett.no> - 2017-06-10 19:09 +0200
        Re: C speed supercat@casperkitty.com - 2017-06-10 12:37 -0700
          Re: C speed David Brown <david.brown@hesbynett.no> - 2017-06-11 21:47 +0200
            Re: C speed Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-11 21:23 +0100
              Re: C speed supercat@casperkitty.com - 2017-06-11 13:33 -0700
                Re: C speed Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-11 23:47 +0100
              Re: C speed David Brown <david.brown@hesbynett.no> - 2017-06-12 09:12 +0200
            Re: C speed supercat@casperkitty.com - 2017-06-11 13:30 -0700
              Re: C speed David Brown <david.brown@hesbynett.no> - 2017-06-12 09:15 +0200
                Re: C speed supercat@casperkitty.com - 2017-06-12 07:14 -0700

#111911 — Re: C speed

On 06/09/2017 06:21 PM, Stefan Ram wrote:
>   Last time I looked, C was the fastest language in the
>   programming language shootout. And c, the speed of light,
>   is the fastest speed in energy transports. So, whether
>   one takes the first or the second meaning of the letter:
>   »C speed« means »the fastest speed«, »the reference speed
>   no one can hope to surpass«.

I first wrote C code not long after K&R 1 was first published. At that 
time, someone told me that Fortran compilers were much better at 
optimization than C compilers. According to him, this wasn't just 
because people had been working on improving Fortran compilers a lot 
longer than they'd been working on improving C compilers (which, at that 
time, was certainly true). It was also supposedly because certain 
features of C (including it's heavy use of pointers) made it much more 
difficult to optimize.
I never felt the need to prove or disprove that claim, so I've no idea 
whether it was true at that time.

A decade or so later, someone told me the same thing again. I pointed 
out to him that the "Fortran" compiler he was using ran f2c to convert 
Fortran code to C code, and then used a C compiler to actually create 
the object files. He seemed somewhat deflated after he confirmed what I 
was saying.

[toc] | [next] | [standalone]

#111912

On Friday, June 9, 2017 at 5:59:03 PM UTC-5, James R. Kuyper wrote:
> I first wrote C code not long after K&R 1 was first published. At that 
> time, someone told me that Fortran compilers were much better at 
> optimization than C compilers. According to him, this wasn't just 
> because people had been working on improving Fortran compilers a lot 
> longer than they'd been working on improving C compilers (which, at that 
> time, was certainly true). It was also supposedly because certain 
> features of C (including it's heavy use of pointers) made it much more 
> difficult to optimize.

C was designed to maximize the quality of code that can be produced by a
skilled programmer using a simple compiler.  Since a simple compiler would
have no reason to care about, e.g., whether something is a pointer to the
start of an array versus a pointer to an element in the middle, the
language offers no means of indicating such things.

In many cases, a compiler that is allowed to make certain assumptions about
pointers would be allowed to produce much more efficient code than one which
cannot.  For example, given code like:

    void test(double arr1[], double arr2[], double scale)
    {
      for (int i=0; i<1000; i++)
        arr1[i] = arr2[i] * scale;
    }

If a compiler knew that arr1 was the pointer to the start of an array, and
that arr2 was a pointer to the start of a (not necessarily different) array,
it could vectorize the loop, or have 10 CPU cores each process 100 elements
of it, or do all sorts of wonderful things.  Unfortunately, C provides no
way for the programmer to allow such optimizations without having to write
a separate version of the code to handle the case where the values should
be scaled "in place".

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

#111932

On 10/06/17 01:21, supercat@casperkitty.com wrote:
> On Friday, June 9, 2017 at 5:59:03 PM UTC-5, James R. Kuyper wrote:
>> I first wrote C code not long after K&R 1 was first published. At that
>> time, someone told me that Fortran compilers were much better at
>> optimization than C compilers. According to him, this wasn't just
>> because people had been working on improving Fortran compilers a lot
>> longer than they'd been working on improving C compilers (which, at that
>> time, was certainly true). It was also supposedly because certain
>> features of C (including it's heavy use of pointers) made it much more
>> difficult to optimize.
> 
> C was designed to maximize the quality of code that can be produced by a
> skilled programmer using a simple compiler.  Since a simple compiler would
> have no reason to care about, e.g., whether something is a pointer to the
> start of an array versus a pointer to an element in the middle, the
> language offers no means of indicating such things.
> 
> In many cases, a compiler that is allowed to make certain assumptions about
> pointers would be allowed to produce much more efficient code than one which
> cannot.  For example, given code like:
> 
>      void test(double arr1[], double arr2[], double scale)
>      {
>        for (int i=0; i<1000; i++)
>          arr1[i] = arr2[i] * scale;
>      }
> 
> If a compiler knew that arr1 was the pointer to the start of an array, and
> that arr2 was a pointer to the start of a (not necessarily different) array,
> it could vectorize the loop, or have 10 CPU cores each process 100 elements
> of it, or do all sorts of wonderful things.  Unfortunately, C provides no
> way for the programmer to allow such optimizations without having to write
> a separate version of the code to handle the case where the values should
> be scaled "in place".
> 

The compiler /does/ know that arr1 and arr2 point to the start of arrays 
of at least 1000 elements.  If they did not do so, the rest of the code 
would be undefined behaviour - and the compiler knows you did not write 
undefined behaviour.

This is a fine example of the advantages of C's undefined behaviour concept.

(And you can use "restrict" if you want to tell the compiler that they 
are independent arrays.)

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

#111935

On Saturday, June 10, 2017 at 12:09:48 PM UTC-5, David Brown wrote:
> On 10/06/17 01:21, supercat wrote:
> >      void test(double arr1[], double arr2[], double scale)
> >      {
> >        for (int i=0; i<1000; i++)
> >          arr1[i] = arr2[i] * scale;
> >      }
> The compiler /does/ know that arr1 and arr2 point to the start of arrays 
> of at least 1000 elements.  If they did not do so, the rest of the code 
> would be undefined behaviour - and the compiler knows you did not write 
> undefined behaviour.

How does it know that, exactly?  The declaration is equivalent to:

     void test(double *arr1, double *arr2, double scale)

and the pointers are allowed to point at arbitrary locations within any
array of doubles large enough to have 1000 accessible items at and beyond
the indicated addresses.
 
> This is a fine example of the advantages of C's undefined behaviour concept.

It may be a fine example of something, but I'm not sure I'd call it any kind
of "advantage".  If any compiler writer would optimize on the basis of it
having undefined behavior, I'd say it's an example of why C should have
an explicit syntax to indicate that something is the start of an array.
While most such functions would not typically be used to duplicate a growing
pattern, nothing in the Standard would prohibit the function as written from
being used for that purpose.

> (And you can use "restrict" if you want to tell the compiler that they 
> are independent arrays.)

That would require what would generally be needless code duplication to
handle the situation where code needs to scale an array "in place".  While there may be some systems where a loop using the same source and destination
pointer could be faster than one using separate pointers to the same object,
on many systems the same machine code should be usable for both purposes.

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

#111977

On 10/06/17 21:37, supercat@casperkitty.com wrote:
> On Saturday, June 10, 2017 at 12:09:48 PM UTC-5, David Brown wrote:
>> On 10/06/17 01:21, supercat wrote:
>>>       void test(double arr1[], double arr2[], double scale)
>>>       {
>>>         for (int i=0; i<1000; i++)
>>>           arr1[i] = arr2[i] * scale;
>>>       }
>> The compiler /does/ know that arr1 and arr2 point to the start of arrays
>> of at least 1000 elements.  If they did not do so, the rest of the code
>> would be undefined behaviour - and the compiler knows you did not write
>> undefined behaviour.
> 
> How does it know that, exactly?  The declaration is equivalent to:
> 
>       void test(double *arr1, double *arr2, double scale)
> 
> and the pointers are allowed to point at arbitrary locations within any
> array of doubles large enough to have 1000 accessible items at and beyond
> the indicated addresses.

Fair enough - it knows that the pointers point to the start of 
/subarrays/ of at least 1000 elements.  Does that make you feel better? 
The compiler can do the same kind of vectorisation.  Being a pointer to 
the /start/ of an array rather than some part in the middle of it makes 
no difference.

>   
>> This is a fine example of the advantages of C's undefined behaviour concept.
> 
> It may be a fine example of something, but I'm not sure I'd call it any kind
> of "advantage".  If any compiler writer would optimize on the basis of it
> having undefined behavior, I'd say it's an example of why C should have
> an explicit syntax to indicate that something is the start of an array.

I think it would be nice if C had a better way of treating arrays, and 
was able to describe them explicitly.  I don't see how it would make a 
difference here, however.

> While most such functions would not typically be used to duplicate a growing
> pattern, nothing in the Standard would prohibit the function as written from
> being used for that purpose.
> 
>> (And you can use "restrict" if you want to tell the compiler that they
>> are independent arrays.)
> 
> That would require what would generally be needless code duplication to
> handle the situation where code needs to scale an array "in place".  While there may be some systems where a loop using the same source and destination
> pointer could be faster than one using separate pointers to the same object,
> on many systems the same machine code should be usable for both purposes.
> 

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

#111980

David Brown <david.brown@hesbynett.no> writes:

> On 10/06/17 21:37, supercat@casperkitty.com wrote:
>> On Saturday, June 10, 2017 at 12:09:48 PM UTC-5, David Brown wrote:
>>> On 10/06/17 01:21, supercat wrote:
>>>>       void test(double arr1[], double arr2[], double scale)
>>>>       {
>>>>         for (int i=0; i<1000; i++)
>>>>           arr1[i] = arr2[i] * scale;
>>>>       }
>>> The compiler /does/ know that arr1 and arr2 point to the start of arrays
>>> of at least 1000 elements.  If they did not do so, the rest of the code
>>> would be undefined behaviour - and the compiler knows you did not write
>>> undefined behaviour.
>>
>> How does it know that, exactly?  The declaration is equivalent to:
>>
>>       void test(double *arr1, double *arr2, double scale)
>>
>> and the pointers are allowed to point at arbitrary locations within any
>> array of doubles large enough to have 1000 accessible items at and beyond
>> the indicated addresses.
>
> Fair enough - it knows that the pointers point to the start of
> /subarrays/ of at least 1000 elements.  Does that make you feel
> better? The compiler can do the same kind of vectorisation.  Being a
> pointer to the /start/ of an array rather than some part in the middle
> of it makes no difference.

Is this always the case?  In languages were the compiler knows that the
pointer is to the start of an array (and this may be a pointer generated
internally -- the language may not have pointers as such) the compiler
may be able to assume things about alignment that could be helpful for
optimisation (particularly vectorisation).

<snip>
-- 
Ben.

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

#111982

On Sunday, June 11, 2017 at 3:23:22 PM UTC-5, Ben Bacarisse wrote:
> Is this always the case?  In languages were the compiler knows that the
> pointer is to the start of an array (and this may be a pointer generated
> internally -- the language may not have pointers as such) the compiler
> may be able to assume things about alignment that could be helpful for
> optimisation (particularly vectorisation).

If a compiler knows that arr1 is the start of one array and arr2 is the start
of a (not necessarily different) array, then it will be entitled to assume
that for any *unequal* integer values i and j, nothing that is accessed as
arr1[i] will also be accessed as arr2[j].  That's a *very* useful assumption
for vectorization.

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

#111984

supercat@casperkitty.com writes:

> On Sunday, June 11, 2017 at 3:23:22 PM UTC-5, Ben Bacarisse wrote:
>> Is this always the case?  In languages were the compiler knows that the
>> pointer is to the start of an array (and this may be a pointer generated
>> internally -- the language may not have pointers as such) the compiler
>> may be able to assume things about alignment that could be helpful for
>> optimisation (particularly vectorisation).
>
> If a compiler knows that arr1 is the start of one array and arr2 is the start
> of a (not necessarily different) array, then it will be entitled to assume
> that for any *unequal* integer values i and j, nothing that is accessed as
> arr1[i] will also be accessed as arr2[j].  That's a *very* useful assumption
> for vectorization.

'restrict' will do that in C, though that makes a rather more general
guarantee.

-- 
Ben.

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

#111994

On 11/06/17 22:23, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 10/06/17 21:37, supercat@casperkitty.com wrote:
>>> On Saturday, June 10, 2017 at 12:09:48 PM UTC-5, David Brown wrote:
>>>> On 10/06/17 01:21, supercat wrote:
>>>>>       void test(double arr1[], double arr2[], double scale)
>>>>>       {
>>>>>         for (int i=0; i<1000; i++)
>>>>>           arr1[i] = arr2[i] * scale;
>>>>>       }
>>>> The compiler /does/ know that arr1 and arr2 point to the start of arrays
>>>> of at least 1000 elements.  If they did not do so, the rest of the code
>>>> would be undefined behaviour - and the compiler knows you did not write
>>>> undefined behaviour.
>>>
>>> How does it know that, exactly?  The declaration is equivalent to:
>>>
>>>       void test(double *arr1, double *arr2, double scale)
>>>
>>> and the pointers are allowed to point at arbitrary locations within any
>>> array of doubles large enough to have 1000 accessible items at and beyond
>>> the indicated addresses.
>>
>> Fair enough - it knows that the pointers point to the start of
>> /subarrays/ of at least 1000 elements.  Does that make you feel
>> better? The compiler can do the same kind of vectorisation.  Being a
>> pointer to the /start/ of an array rather than some part in the middle
>> of it makes no difference.
> 
> Is this always the case?  In languages were the compiler knows that the
> pointer is to the start of an array (and this may be a pointer generated
> internally -- the language may not have pointers as such) the compiler
> may be able to assume things about alignment that could be helpful for
> optimisation (particularly vectorisation).
> 

I'd be loath to say it is /always/ the case - but I think it is likely
to be so in most cases in C.  I suppose a compiler could give an array a
larger alignment than an element of an array, but it seems unlikely in
practice - certainly not for doubles.  It may be that sometimes it will
know that the real array is at higher alignment - but the compiler will
not know that merely from knowing a pointer is to the start of the array.

If you want to tell the compiler more about alignment to help
vectorisation, there are standard C methods (such as using unions or
_Alignas), and implementation-specific methods (such as gcc's aligned
attribute) that are probably much more useful when you are targeting
specific types of optimisation.

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

#111981

On Sunday, June 11, 2017 at 2:47:42 PM UTC-5, David Brown wrote:
> On 10/06/17 21:37, supercat wrote:
> >>>       void test(double arr1[], double arr2[], double scale)
> >>>       {
> >>>         for (int i=0; i<1000; i++)
> >>>           arr1[i] = arr2[i] * scale;
> >>>       }
> > ... the pointers are allowed to point at arbitrary locations within any
> > array of doubles large enough to have 1000 accessible items at and beyond
> > the indicated addresses.
> 
> Fair enough - it knows that the pointers point to the start of 
> /subarrays/ of at least 1000 elements.  Does that make you feel better? 
> The compiler can do the same kind of vectorisation.  Being a pointer to 
> the /start/ of an array rather than some part in the middle of it makes 
> no difference.

Given:

   double arr[1001];
   arr[0] = 1.0;
   test(arr+1, arr, 2.0);

the generated code would be required by the Standard to use the value
computed for arr[1] when computing arr[2], use that value when computing
arr[3], etc.  If the compiler were to read arr[0..3] into registers,
scale them, and write them to arr[1..4], then the values for arr[2..4]
would be wrong, as would every single array element thereafter.  The
only way a compiler could legitimately vectorize the above function would
be if it started by testing the relationship between the two pointers and
then handled the partial-overlap cases specially.

> I think it would be nice if C had a better way of treating arrays, and 
> was able to describe them explicitly.  I don't see how it would make a 
> difference here, however.

It makes a huge difference if compilers are required to make all of the
operations behave as though they're performed sequentially in cases where
overlapping pointers might reveal the actual operation sequence.

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

#111995

On 11/06/17 22:30, supercat@casperkitty.com wrote:
> On Sunday, June 11, 2017 at 2:47:42 PM UTC-5, David Brown wrote:
>> On 10/06/17 21:37, supercat wrote:
>>>>>       void test(double arr1[], double arr2[], double scale)
>>>>>       {
>>>>>         for (int i=0; i<1000; i++)
>>>>>           arr1[i] = arr2[i] * scale;
>>>>>       }
>>> ... the pointers are allowed to point at arbitrary locations within any
>>> array of doubles large enough to have 1000 accessible items at and beyond
>>> the indicated addresses.
>>
>> Fair enough - it knows that the pointers point to the start of 
>> /subarrays/ of at least 1000 elements.  Does that make you feel better? 
>> The compiler can do the same kind of vectorisation.  Being a pointer to 
>> the /start/ of an array rather than some part in the middle of it makes 
>> no difference.
> 
> Given:
> 
>    double arr[1001];
>    arr[0] = 1.0;
>    test(arr+1, arr, 2.0);
> 
> the generated code would be required by the Standard to use the value
> computed for arr[1] when computing arr[2], use that value when computing
> arr[3], etc.  If the compiler were to read arr[0..3] into registers,
> scale them, and write them to arr[1..4], then the values for arr[2..4]
> would be wrong, as would every single array element thereafter.  The
> only way a compiler could legitimately vectorize the above function would
> be if it started by testing the relationship between the two pointers and
> then handled the partial-overlap cases specially.

All true - but all pretty much irrelevant.  If you are writing code
where the independence of the arrays makes a difference, you use
"restrict", and you don't call the function with overlapping arrays.  It
is of no benefit to the compiler or the programmer to have information
specifically about the pointers being to the start of an array.

> 
>> I think it would be nice if C had a better way of treating arrays, and 
>> was able to describe them explicitly.  I don't see how it would make a 
>> difference here, however.
> 
> It makes a huge difference if compilers are required to make all of the
> operations behave as though they're performed sequentially in cases where
> overlapping pointers might reveal the actual operation sequence.
> 

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

#112015

On Monday, June 12, 2017 at 2:15:45 AM UTC-5, David Brown wrote:
> All true - but all pretty much irrelevant.  If you are writing code
> where the independence of the arrays makes a difference, you use
> "restrict", and you don't call the function with overlapping arrays.  It
> is of no benefit to the compiler or the programmer to have information
> specifically about the pointers being to the start of an array.

I already acknowledged that it would be possible to add restrict *if one
wanted to needlessly duplicate the code to handle the case of scaling an
array in place*.

[toc] | [prev] | [standalone]

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

csiph-web