[RFC,BZ,#17943] Use long for int_fast8_t

  Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?

It is definitely slower with division, following code is 25% slower on
haswell with char than when you use long.

There is question what about other architectures and atomic operations,
are byte ones better than int?

int main ()
{
  int i;
  char x = 32;
  for (i=0; i<1000000000; i++)
    x = 11 * x + 5 + x / 3;
  return x;
}




	* sysdeps/generic/stdint.h: Use long int for int_fast8_t
  

On Sun, 8 Feb 2015, Ondřej Bílka wrote:

> Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
> 
> It is definitely slower with division, following code is 25% slower on
> haswell with char than when you use long.

 It may boil down to the choice of instructions produced made by the 
compiler.  I can hardly imagine 8-bit division to be slower than 64-bit 
one on a processor that implements subword integer arithmetic.

> There is question what about other architectures and atomic operations,
> are byte ones better than int?
> 
> int main ()
> {
>   int i;
>   char x = 32;
>   for (i=0; i<1000000000; i++)
>     x = 11 * x + 5 + x / 3;
>   return x;
> }

 On Intel Atom for example division latencies are as follows[1]:

		latency	throughput
IDIV r/m8	   33	    32
IDIV r/m16	   42	    41
IDIV r/m32	   57	    56
IDIV r/m64	  197	   196

I'd expect the ratio of elapsed times for the corresponding data widths 
and a manual division algorithm used with processors that have no hardware 
divider to be similar.  There is no latency difference between individual 
data widths AFAICT for multiplication or general ALU operations.

 For processors that do have a hardware divider implementing word 
calculation only I'd expect either a constant latency or again, a decrease 
in operation time depending on the actual width of significant data 
contained in operands.

 For example the M14Kc MIPS32 processor has an RTL configuration option to 
include either an area-efficient or a high-performance MDU 
(multiply/divide unit).  The area-efficient MDU has a latency of 33 clocks 
for unsigned division (signed division adds up to 2 clocks for sign 
reversal).  The high-performance MDU reduces the latency as follows[2]:

"Divide operations are implemented with a simple 1-bit-per-clock iterative 
algorithm.  An early-in detection checks the sign extension of the 
dividend (rs) operand.  If rs is 8 bits wide, 23 iterations are skipped. 
For a 16-bit-wide rs, 15 iterations are skipped, and for a 24-bit-wide rs, 
7 iterations are skipped.  Any attempt to issue a subsequent MDU 
instruction while a divide is still active causes an IU pipeline stall 
until the divide operation has completed."

As it happens automatically there is no benefit from using a narrower data 
type, and the lack of subword arithmetic operations means that using such 
a type will require a truncation operation from time to time for 
multiplication or general ALU operations.

> --- a/sysdeps/generic/stdint.h
> +++ b/sysdeps/generic/stdint.h
> @@ -87,12 +87,13 @@ typedef unsigned long long int	uint_least64_t;
>  /* Fast types.  */
>  
>  /* Signed.  */
> -typedef signed char		int_fast8_t;
>  #if __WORDSIZE == 64
> +typedef long int		int_fast8_t;
>  typedef long int		int_fast16_t;
>  typedef long int		int_fast32_t;
>  typedef long int		int_fast64_t;
>  #else
> +typedef int			int_fast8_t;
>  typedef int			int_fast16_t;
>  typedef int			int_fast32_t;
>  __extension__

 So I find the choice of types above to be already questionable for a 
generic header.  By default I'd expect fast data types to have the same 
width as their fixed-width counterparts for the large benefit they provide 
with most architectures that do implement subword arithmetic weighed 
against the small loss they will likely incur with architectures that only 
implement word arithmetic.  Then individual ports could override the 
defaults as they see fit.

 At this point the discussion is however I believe moot though -- there 
will have been relocatable objects out there with data embedded using 
these types already so the ABI has been set and I don't see a way of 
changing it without breaking binary compatibility.

 References:

[1] "Intel 64 and IA-32 Architectures Optimization Reference Manual", 
    Intel Corporation, Order Number: 248966-020, November 2009, Table 12-2 
    "Intel Atom Microarchitecture Instructions Latency Data", p. 12-21

[2] "MIPS32 M14Kc Processor Core Datasheet", Revision 01.00, MIPS 
    Technologies, Inc., Document Number: MD00672, November 2, 2009, 
    Subsection "High-Performance MDU", p. 6

  Maciej
  

On Mon, Feb 9, 2015 at 5:36 AM, Maciej W. Rozycki <macro@linux-mips.org> wrote:
> On Sun, 8 Feb 2015, Ondřej Bílka wrote:
>
>> Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
>>
>> It is definitely slower with division, following code is 25% slower on
>> haswell with char than when you use long.
>
>  It may boil down to the choice of instructions produced made by the
> compiler.  I can hardly imagine 8-bit division to be slower than 64-bit
> one on a processor that implements subword integer arithmetic.
>
>> There is question what about other architectures and atomic operations,
>> are byte ones better than int?
>>
>> int main ()
>> {
>>   int i;
>>   char x = 32;
>>   for (i=0; i<1000000000; i++)
>>     x = 11 * x + 5 + x / 3;
>>   return x;
>> }
>
>  On Intel Atom for example division latencies are as follows[1]:
>
>                 latency throughput
> IDIV r/m8          33       32
> IDIV r/m16         42       41
> IDIV r/m32         57       56
> IDIV r/m64        197      196
>
> I'd expect the ratio of elapsed times for the corresponding data widths
> and a manual division algorithm used with processors that have no hardware
> divider to be similar.  There is no latency difference between individual
> data widths AFAICT for multiplication or general ALU operations.
>
>  For processors that do have a hardware divider implementing word
> calculation only I'd expect either a constant latency or again, a decrease
> in operation time depending on the actual width of significant data
> contained in operands.
>
>  For example the M14Kc MIPS32 processor has an RTL configuration option to
> include either an area-efficient or a high-performance MDU
> (multiply/divide unit).  The area-efficient MDU has a latency of 33 clocks
> for unsigned division (signed division adds up to 2 clocks for sign
> reversal).  The high-performance MDU reduces the latency as follows[2]:
>
> "Divide operations are implemented with a simple 1-bit-per-clock iterative
> algorithm.  An early-in detection checks the sign extension of the
> dividend (rs) operand.  If rs is 8 bits wide, 23 iterations are skipped.
> For a 16-bit-wide rs, 15 iterations are skipped, and for a 24-bit-wide rs,
> 7 iterations are skipped.  Any attempt to issue a subsequent MDU
> instruction while a divide is still active causes an IU pipeline stall
> until the divide operation has completed."
>
> As it happens automatically there is no benefit from using a narrower data
> type, and the lack of subword arithmetic operations means that using such
> a type will require a truncation operation from time to time for
> multiplication or general ALU operations.
>
>> --- a/sysdeps/generic/stdint.h
>> +++ b/sysdeps/generic/stdint.h
>> @@ -87,12 +87,13 @@ typedef unsigned long long int    uint_least64_t;
>>  /* Fast types.  */
>>
>>  /* Signed.  */
>> -typedef signed char          int_fast8_t;
>>  #if __WORDSIZE == 64
>> +typedef long int             int_fast8_t;
>>  typedef long int             int_fast16_t;
>>  typedef long int             int_fast32_t;
>>  typedef long int             int_fast64_t;
>>  #else
>> +typedef int                  int_fast8_t;
>>  typedef int                  int_fast16_t;
>>  typedef int                  int_fast32_t;
>>  __extension__
>
>  So I find the choice of types above to be already questionable for a
> generic header.  By default I'd expect fast data types to have the same
> width as their fixed-width counterparts for the large benefit they provide
> with most architectures that do implement subword arithmetic weighed
> against the small loss they will likely incur with architectures that only
> implement word arithmetic.  Then individual ports could override the
> defaults as they see fit.
>
>  At this point the discussion is however I believe moot though -- there
> will have been relocatable objects out there with data embedded using
> these types already so the ABI has been set and I don't see a way of
> changing it without breaking binary compatibility.
>
>  References:
>
> [1] "Intel 64 and IA-32 Architectures Optimization Reference Manual",
>     Intel Corporation, Order Number: 248966-020, November 2009, Table 12-2
>     "Intel Atom Microarchitecture Instructions Latency Data", p. 12-21

This manual is very old and Intel Atom Microarchitecture has been
replaced by Silvermont Microarchitecture.

> [2] "MIPS32 M14Kc Processor Core Datasheet", Revision 01.00, MIPS
>     Technologies, Inc., Document Number: MD00672, November 2, 2009,
>     Subsection "High-Performance MDU", p. 6
>
>   Maciej
  

On Mon, 9 Feb 2015, H.J. Lu wrote:

> > [1] "Intel 64 and IA-32 Architectures Optimization Reference Manual",
> >     Intel Corporation, Order Number: 248966-020, November 2009, Table 12-2
> >     "Intel Atom Microarchitecture Instructions Latency Data", p. 12-21
> 
> This manual is very old and Intel Atom Microarchitecture has been
> replaced by Silvermont Microarchitecture.

 Maybe, I picked whatever I had handy.  That doesn't change the fact this 
silicon is out there.  There's older yet x86 silicon in the field where 
the divider has a similar characteristic.

 As I say for a generic header you need to weigh the balance -- except 
that the ABI has been set, so there's little if anything we can do, apart 
from new architecture additions that can get their overrides right from 
the beginning.

  Maciej
  

On Sun, 8 Feb 2015, Ondřej Bílka wrote:

> Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
> 
> It is definitely slower with division, following code is 25% slower on
> haswell with char than when you use long.

Well, there are trade-offs with space in that if you use more cache for a 
larger type then that could make things slower; it's not automatically 
the case that a type that's faster for individual operations makes 
programs faster if it's used.

In any case, we need to be very wary of changing the size or alignment or 
C++ name mangling of any exported type in a public header, even if it 
doesn't affect existing executables / shared libraries because the type 
isn't involved in the ABIs of existing glibc functions.

In the present case, GCC knows about these types for each target, both so 
as to ensure <stdint.h> is available for freestanding compilations, and to 
provide the Fortran C bindings.  So if you did use different types for new 
glibc configurations, the GCC ports for those targets would also need to 
know.

This patch doesn't change inttypes.h.  If it passed testing, I suppose 
that means we are missing a testcase that all the inttypes.h format macros 
do work with the corresponding types (such a test would mainly be that the 
testcase builds OK with -Wformat -Werror rather than for the runtime 
execution).
  

On Sun, Feb 08, 2015 at 12:04:26PM +0100, Ondřej Bílka wrote:
> Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
> 
> It is definitely slower with division, following code is 25% slower on
> haswell with char than when you use long.

This claim is nonsense. It's a compiler bug. If the 8-bit divide
instruction is slow, then the compiler should use 32-bit or 64-bit
divide instructions to divide 8-bit types. (Note: there's actually no
such thing as a division of 8-byte types; formally, they're promoted
to int, so it's the compiler being stupid if it generates a slow 8-bit
divide instruction for operands that are formally int!) There's no
reason to use a different type for the _storage_.

The only legigimate reason to change the int_fast types is when the
_storage_ in certain sizes is slow to access.

Rich
  

On 09/02/15 13:36, Maciej W. Rozycki wrote:
> On Sun, 8 Feb 2015, Ondřej Bílka wrote:
> 
>> Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
>>
>> It is definitely slower with division, following code is 25% slower on
>> haswell with char than when you use long.
> 
>  It may boil down to the choice of instructions produced made by the 
> compiler.  I can hardly imagine 8-bit division to be slower than 64-bit 
> one on a processor that implements subword integer arithmetic.
> 
>> There is question what about other architectures and atomic operations,
>> are byte ones better than int?
>>
>> int main ()
>> {
>>   int i;
>>   char x = 32;
>>   for (i=0; i<1000000000; i++)
>>     x = 11 * x + 5 + x / 3;
>>   return x;
>> }
> 
>  On Intel Atom for example division latencies are as follows[1]:
> 
> 		latency	throughput
> IDIV r/m8	   33	    32
> IDIV r/m16	   42	    41
> IDIV r/m32	   57	    56
> IDIV r/m64	  197	   196
> 
> I'd expect the ratio of elapsed times for the corresponding data widths 
> and a manual division algorithm used with processors that have no hardware 
> divider to be similar.  There is no latency difference between individual 
> data widths AFAICT for multiplication or general ALU operations.
> 
>  For processors that do have a hardware divider implementing word 
> calculation only I'd expect either a constant latency or again, a decrease 
> in operation time depending on the actual width of significant data 
> contained in operands.
> 
>  For example the M14Kc MIPS32 processor has an RTL configuration option to 
> include either an area-efficient or a high-performance MDU 
> (multiply/divide unit).  The area-efficient MDU has a latency of 33 clocks 
> for unsigned division (signed division adds up to 2 clocks for sign 
> reversal).  The high-performance MDU reduces the latency as follows[2]:
> 
> "Divide operations are implemented with a simple 1-bit-per-clock iterative 
> algorithm.  An early-in detection checks the sign extension of the 
> dividend (rs) operand.  If rs is 8 bits wide, 23 iterations are skipped. 
> For a 16-bit-wide rs, 15 iterations are skipped, and for a 24-bit-wide rs, 
> 7 iterations are skipped.  Any attempt to issue a subsequent MDU 
> instruction while a divide is still active causes an IU pipeline stall 
> until the divide operation has completed."
> 
> As it happens automatically there is no benefit from using a narrower data 
> type, and the lack of subword arithmetic operations means that using such 
> a type will require a truncation operation from time to time for 
> multiplication or general ALU operations.
> 
>> --- a/sysdeps/generic/stdint.h
>> +++ b/sysdeps/generic/stdint.h
>> @@ -87,12 +87,13 @@ typedef unsigned long long int	uint_least64_t;
>>  /* Fast types.  */
>>  
>>  /* Signed.  */
>> -typedef signed char		int_fast8_t;
>>  #if __WORDSIZE == 64
>> +typedef long int		int_fast8_t;
>>  typedef long int		int_fast16_t;
>>  typedef long int		int_fast32_t;
>>  typedef long int		int_fast64_t;
>>  #else
>> +typedef int			int_fast8_t;
>>  typedef int			int_fast16_t;
>>  typedef int			int_fast32_t;
>>  __extension__

On AArch64 there's nothing to be gained in terms of performance from
using a 64-bit type over a 32-bit type when both can hold the required
range of values.  In fact, it's likely to make things slower, since
multiply and divide operations will most likely take longer.

So on AArch64 int_fast8_t, int_fast16_t and int_fast32_t should all map
to int, not long.

R.

> 
>  So I find the choice of types above to be already questionable for a 
> generic header.  By default I'd expect fast data types to have the same 
> width as their fixed-width counterparts for the large benefit they provide 
> with most architectures that do implement subword arithmetic weighed 
> against the small loss they will likely incur with architectures that only 
> implement word arithmetic.  Then individual ports could override the 
> defaults as they see fit.
> 
>  At this point the discussion is however I believe moot though -- there 
> will have been relocatable objects out there with data embedded using 
> these types already so the ABI has been set and I don't see a way of 
> changing it without breaking binary compatibility.
> 
>  References:
> 
> [1] "Intel 64 and IA-32 Architectures Optimization Reference Manual", 
>     Intel Corporation, Order Number: 248966-020, November 2009, Table 12-2 
>     "Intel Atom Microarchitecture Instructions Latency Data", p. 12-21
> 
> [2] "MIPS32 M14Kc Processor Core Datasheet", Revision 01.00, MIPS 
>     Technologies, Inc., Document Number: MD00672, November 2, 2009, 
>     Subsection "High-Performance MDU", p. 6
> 
>   Maciej
>
  

On Mon, Feb 09, 2015 at 01:13:24PM -0500, Rich Felker wrote:
> On Sun, Feb 08, 2015 at 12:04:26PM +0100, Ondřej Bílka wrote:
> > Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
> > 
> > It is definitely slower with division, following code is 25% slower on
> > haswell with char than when you use long.
> 
> This claim is nonsense. It's a compiler bug. If the 8-bit divide
> instruction is slow, then the compiler should use 32-bit or 64-bit
> divide instructions to divide 8-bit types. (Note: there's actually no
> such thing as a division of 8-byte types; formally, they're promoted
> to int, so it's the compiler being stupid if it generates a slow 8-bit
> divide instruction for operands that are formally int!) There's no
> reason to use a different type for the _storage_.
> 
That is also nonsense, you cannot get same speed as 32bit instruction
without having 8bit instruction with same performance.

Compiler must add extra truncation instructions to get correct result
which slows it down, otherwise it gets wrong result for cases like (128+128)%3
  

On Wed, Feb 11, 2015 at 02:34:09PM +0100, Ondřej Bílka wrote:
> On Mon, Feb 09, 2015 at 01:13:24PM -0500, Rich Felker wrote:
> > On Sun, Feb 08, 2015 at 12:04:26PM +0100, Ondřej Bílka wrote:
> > > Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
> > > 
> > > It is definitely slower with division, following code is 25% slower on
> > > haswell with char than when you use long.
> > 
> > This claim is nonsense. It's a compiler bug. If the 8-bit divide
> > instruction is slow, then the compiler should use 32-bit or 64-bit
> > divide instructions to divide 8-bit types. (Note: there's actually no
> > such thing as a division of 8-byte types; formally, they're promoted
> > to int, so it's the compiler being stupid if it generates a slow 8-bit
> > divide instruction for operands that are formally int!) There's no
> > reason to use a different type for the _storage_.
> > 
> That is also nonsense, you cannot get same speed as 32bit instruction
> without having 8bit instruction with same performance.
> 
> Compiler must add extra truncation instructions to get correct result
> which slows it down, otherwise it gets wrong result for cases like (128+128)%3

The additional need to truncate can arise when using 32-bit types on a
64-bit arch, but normally you defer this truncation for until storage
(in which case it's usually automatic), promotion, or division (in
which case it's hopefully dominated by the time to divide). If your
concern is the need to truncate before division/remainder operations,
I think that cost is dwarfed by the added cache/memory pressure of
wasting half your space.

Rich
  

On 11/02/15 13:34, Ondřej Bílka wrote:
> On Mon, Feb 09, 2015 at 01:13:24PM -0500, Rich Felker wrote:
>> On Sun, Feb 08, 2015 at 12:04:26PM +0100, Ondřej Bílka wrote:
>>> Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
>>>
>>> It is definitely slower with division, following code is 25% slower on
>>> haswell with char than when you use long.
>>
>> This claim is nonsense. It's a compiler bug. If the 8-bit divide
>> instruction is slow, then the compiler should use 32-bit or 64-bit
>> divide instructions to divide 8-bit types. (Note: there's actually no
>> such thing as a division of 8-byte types; formally, they're promoted
>> to int, so it's the compiler being stupid if it generates a slow 8-bit
>> divide instruction for operands that are formally int!) There's no
>> reason to use a different type for the _storage_.
>>
> That is also nonsense, you cannot get same speed as 32bit instruction
> without having 8bit instruction with same performance.
> 
> Compiler must add extra truncation instructions to get correct result
> which slows it down, otherwise it gets wrong result for cases like (128+128)%3
> 

Only if the intermediate result (128+128) is assigned directly to a
variable with less precision than int.  Otherwise the whole expression
is calculated with int precision.

R.
  

On 11/02/15 18:26, Richard Earnshaw wrote:
> On 11/02/15 13:34, Ondřej Bílka wrote:
>> On Mon, Feb 09, 2015 at 01:13:24PM -0500, Rich Felker wrote:
>>> On Sun, Feb 08, 2015 at 12:04:26PM +0100, Ondřej Bílka wrote:
>>>> Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
>>>>
>>>> It is definitely slower with division, following code is 25% slower on
>>>> haswell with char than when you use long.
>>>
>>> This claim is nonsense. It's a compiler bug. If the 8-bit divide
>>> instruction is slow, then the compiler should use 32-bit or 64-bit
>>> divide instructions to divide 8-bit types. (Note: there's actually no
>>> such thing as a division of 8-byte types; formally, they're promoted
>>> to int, so it's the compiler being stupid if it generates a slow 8-bit
>>> divide instruction for operands that are formally int!) There's no
>>> reason to use a different type for the _storage_.
>>>
>> That is also nonsense, you cannot get same speed as 32bit instruction
>> without having 8bit instruction with same performance.
>>
>> Compiler must add extra truncation instructions to get correct result
>> which slows it down, otherwise it gets wrong result for cases like (128+128)%3
>>
> 
> Only if the intermediate result (128+128) is assigned directly to a
> variable with less precision than int. 

Or, of course, if an explicit cast is applied to the intermediate result.


> Otherwise the whole expression
> is calculated with int precision.
> 
> R.
>
  

On Wed, Feb 11, 2015 at 06:26:01PM +0000, Richard Earnshaw wrote:
> On 11/02/15 13:34, Ondřej Bílka wrote:
> > On Mon, Feb 09, 2015 at 01:13:24PM -0500, Rich Felker wrote:
> >> On Sun, Feb 08, 2015 at 12:04:26PM +0100, Ondřej Bílka wrote:
> >>> Hi, as in bugzilla entry what is rationale of using char as int_fast8_t?
> >>>
> >>> It is definitely slower with division, following code is 25% slower on
> >>> haswell with char than when you use long.
> >>
> >> This claim is nonsense. It's a compiler bug. If the 8-bit divide
> >> instruction is slow, then the compiler should use 32-bit or 64-bit
> >> divide instructions to divide 8-bit types. (Note: there's actually no
> >> such thing as a division of 8-byte types; formally, they're promoted
> >> to int, so it's the compiler being stupid if it generates a slow 8-bit
> >> divide instruction for operands that are formally int!) There's no
> >> reason to use a different type for the _storage_.
> >>
> > That is also nonsense, you cannot get same speed as 32bit instruction
> > without having 8bit instruction with same performance.
> > 
> > Compiler must add extra truncation instructions to get correct result
> > which slows it down, otherwise it gets wrong result for cases like (128+128)%3
> > 
> 
> Only if the intermediate result (128+128) is assigned directly to a
> variable with less precision than int.  Otherwise the whole expression
> is calculated with int precision.

I read it as an example with small numbers that's not directly
applicable with the C type ranges. If we're actually talking about the
value 128 in C then of course 128+128 is not subject to truncation.

Rich