The type of bitops

The type of bitops

[H. Peter Anvin]

The type of bitops is currently "int" on most, if not all, architectures
except sparc64 where it is "unsigned long".  This already has the
potential of causing failures on extremely large non-NUMA x86 boxes
(specifically if any one node contains more than 8 TiB of memory, e.g.
in an interleaved memory system.)

x86 has hardware bitmask instructions which are signed, this limits the
types to either "int" or "long".

It seems pretty clear to me at least that x86-64 really should use
"long".  However, before blindly making that change I wanted to feel
people out for what this should look like across architectures.

Moving this forward, I see a couple of possibilities:

1. We simply change the type to "long" on x86, and let this be a fully
   architecture-specific option.  This is easy, obviously.

2. Same as above, except we also define a typedef for whatever type is
   the bitops argument type (bitops_t?  bitpos_t?)

3. Change the type to "long" Linux-wide, on the logic that it should be
   the same as the general machine width across all platforms.

4. Do some macro hacks so the bitops are dependent on the size of the
   argument.

5. Introduce _long versions of the bitops.

6. Do nothing at all.


Are there any 64-bit architectures where a 64-bit argument would be very
costly?

	-hpa

The type of bitops

[H. Peter Anvin]

The type of bitops is currently "int" on most, if not all, architectures
except sparc64 where it is "unsigned long".  This already has the
potential of causing failures on extremely large non-NUMA x86 boxes
(specifically if any one node contains more than 8 TiB of memory, e.g.
in an interleaved memory system.)

x86 has hardware bitmask instructions which are signed, this limits the
types to either "int" or "long".

It seems pretty clear to me at least that x86-64 really should use
"long".  However, before blindly making that change I wanted to feel
people out for what this should look like across architectures.

Moving this forward, I see a couple of possibilities:

1. We simply change the type to "long" on x86, and let this be a fully
   architecture-specific option.  This is easy, obviously.

2. Same as above, except we also define a typedef for whatever type is
   the bitops argument type (bitops_t?  bitpos_t?)

3. Change the type to "long" Linux-wide, on the logic that it should be
   the same as the general machine width across all platforms.

4. Do some macro hacks so the bitops are dependent on the size of the
   argument.

5. Introduce _long versions of the bitops.

6. Do nothing at all.


Are there any 64-bit architectures where a 64-bit argument would be very
costly?

	-hpa

Re: The type of bitops

[Linus Torvalds]

On Mon, May 6, 2013 at 4:53 PM, H. Peter Anvin <hpa@zytor.com> wrote:
> The type of bitops is currently "int" on most, if not all, architectures
> except sparc64 where it is "unsigned long".

By "type of bitops" I assume you mean the actual bit offset.

> It seems pretty clear to me at least that x86-64 really should use
> "long".  However, before blindly making that change I wanted to feel
> people out for what this should look like across architectures.
>
> Moving this forward, I see a couple of possibilities:
>
> 1. We simply change the type to "long" on x86, and let this be a fully
>    architecture-specific option.  This is easy, obviously.

Just do this. There's no reason to overthink it, I think

> 2. Same as above, except we also define a typedef for whatever type is
>    the bitops argument type (bitops_t?  bitpos_t?)

Who would ever use it? In particular, a lot of users will use bitops
for small arrays and will have fundamentally smaller indexes. For
them, "int" or "u32" or whatever may well make sense, and the fact
that that bitops _can_ take larger bit indexes is immaterial.

> 3. Change the type to "long" Linux-wide, on the logic that it should be
>    the same as the general machine width across all platforms.

I don't think it's worth it, but I don't think anybody will care/notice.

> 4. Do some macro hacks so the bitops are dependent on the size of the
>    argument.

That sounds insane. Just *how* could the size of the argument even
matter? Seriously, there's no *difference* between a 32-bit or a
64-bit index. The code is the same, there's no possible reason to make
it be different.

The only place where the actual size of the data matters is in the
underlying bitop bitmap itse;f, and that has always been defined to be
an array of "unsigned long", and we long logn since made sure people
aren't confused about that. But the index? It's just a number, there's
no structure associated with it. Somebody might use an "unsigned char"
as the index into a bitmap, and the operations fundamentally wouldn't
care - casting the bit index it to an "int" (or a "long") doesn't
change the operation.

               Linus

Re: The type of bitops

[H. Peter Anvin]

On 05/06/2013 05:51 PM, Linus Torvalds wrote:
> 
>> 4. Do some macro hacks so the bitops are dependent on the size of the
>>    argument.
> 
> That sounds insane. Just *how* could the size of the argument even
> matter? Seriously, there's no *difference* between a 32-bit or a
> 64-bit index. The code is the same, there's no possible reason to make
> it be different.
> 

The only reason on x86 would be to avoid the REX prefix.  Hardly worth
it, though.

	-hpa

Re: The type of bitops

[Linus Torvalds]

On Mon, May 6, 2013 at 6:36 PM, H. Peter Anvin <hpa@zytor.com> wrote:
>>
>> That sounds insane. Just *how* could the size of the argument even
>> matter? Seriously, there's no *difference* between a 32-bit or a
>> 64-bit index. The code is the same, there's no possible reason to make
>> it be different.
>>
>
> The only reason on x86 would be to avoid the REX prefix.  Hardly worth
> it, though.

Hmm. You *might* be able to do it by simply turning the inline
functions into statement expressions, and letting the compiler do the
types as it will. Use "(nr)+0" to make sure that the type is at least
"int", and then "Ir" as the asm constraint.

A quick test seems to imply that this works:

  #define test_bit(nr, addr) \
    ({ int oldbit; \
        asm volatile("bt %2,%1\n\t" \
                "sbb %0,%0" \
                : "=r" (oldbit) \
                : "m" (*(unsigned long *)(addr)), \
                 "Ir" ((nr)+0)); \
    oldbit; })

  int test(int idx1, long idx2, void *addr)
  {
    return test_bit(idx1, addr) + test_bit(idx2, addr);
  }

and I get

    ...
    bt %edi,(%rdx)
    ...
    bt %rsi,(%rdx)
    ...

for the int/long index respectively. So if the argument is an 'int',
it will avoid the rex prefix.

And I tested that using a "char" index does indeed do the right thing too:

    movsbl %dil,%eax
    bt     %eax,(%rcx)

so that all seems surmountable.Whether it really matters, I dunno.

                 Linus

Re: The type of bitops

[Linus Torvalds]

On Mon, May 6, 2013 at 6:36 PM, H. Peter Anvin <hpa@zytor.com> wrote:
>>
>> That sounds insane. Just *how* could the size of the argument even
>> matter? Seriously, there's no *difference* between a 32-bit or a
>> 64-bit index. The code is the same, there's no possible reason to make
>> it be different.
>>
>
> The only reason on x86 would be to avoid the REX prefix.  Hardly worth
> it, though.

Hmm. You *might* be able to do it by simply turning the inline
functions into statement expressions, and letting the compiler do the
types as it will. Use "(nr)+0" to make sure that the type is at least
"int", and then "Ir" as the asm constraint.

A quick test seems to imply that this works:

  #define test_bit(nr, addr) \
    ({ int oldbit; \
        asm volatile("bt %2,%1\n\t" \
                "sbb %0,%0" \
                : "=r" (oldbit) \
                : "m" (*(unsigned long *)(addr)), \
                 "Ir" ((nr)+0)); \
    oldbit; })

  int test(int idx1, long idx2, void *addr)
  {
    return test_bit(idx1, addr) + test_bit(idx2, addr);
  }

and I get

    ...
    bt %edi,(%rdx)
    ...
    bt %rsi,(%rdx)
    ...

for the int/long index respectively. So if the argument is an 'int',
it will avoid the rex prefix.

And I tested that using a "char" index does indeed do the right thing too:

    movsbl %dil,%eax
    bt     %eax,(%rcx)

so that all seems surmountable.Whether it really matters, I dunno.

                 Linus

Re: The type of bitops

[Andy Lutomirski]

On 05/06/2013 05:51 PM, Linus Torvalds wrote:
> The only place where the actual size of the data matters is in the
> underlying bitop bitmap itse;f, and that has always been defined to be
> an array of "unsigned long", and we long logn since made sure people
> aren't confused about that. But the index? It's just a number, there's
> no structure associated with it. Somebody might use an "unsigned char"
> as the index into a bitmap, and the operations fundamentally wouldn't
> care - casting the bit index it to an "int" (or a "long") doesn't
> change the operation.

The one and only time I tried to use this, I thought this was odd.  Long
has a different size on 32 vs 64 bit architectures, and bit ops seem
like they'd want to be the same size everywhere so you can allocate the
appropriate number of bits.  (Also, if you only want 32 bits, you have
to do some evil cheating, and I don't trust casting int* to long* on
big-endian architectures.)

Would offering a u32* option make sense?

--Andy

Re: The type of bitops

[Andy Lutomirski]

On 05/06/2013 05:51 PM, Linus Torvalds wrote:
> The only place where the actual size of the data matters is in the
> underlying bitop bitmap itse;f, and that has always been defined to be
> an array of "unsigned long", and we long logn since made sure people
> aren't confused about that. But the index? It's just a number, there's
> no structure associated with it. Somebody might use an "unsigned char"
> as the index into a bitmap, and the operations fundamentally wouldn't
> care - casting the bit index it to an "int" (or a "long") doesn't
> change the operation.

The one and only time I tried to use this, I thought this was odd.  Long
has a different size on 32 vs 64 bit architectures, and bit ops seem
like they'd want to be the same size everywhere so you can allocate the
appropriate number of bits.  (Also, if you only want 32 bits, you have
to do some evil cheating, and I don't trust casting int* to long* on
big-endian architectures.)

Would offering a u32* option make sense?

--Andy

Re: The type of bitops

[H. Peter Anvin]

On 05/07/2013 04:17 PM, Andy Lutomirski wrote:
> 
> The one and only time I tried to use this, I thought this was odd.  Long
> has a different size on 32 vs 64 bit architectures, and bit ops seem
> like they'd want to be the same size everywhere so you can allocate the
> appropriate number of bits.  (Also, if you only want 32 bits, you have
> to do some evil cheating, and I don't trust casting int* to long* on
> big-endian architectures.)
> 
> Would offering a u32* option make sense?
> 

Honestly, the only thing that makes sense on bigendian architectures is
either byte-by-byte elements or counting bit numbers from the MSB, but
that is serious water under the bridge at this point...

	-hpa

Re: The type of bitops

[H. Peter Anvin]

On 05/07/2013 04:17 PM, Andy Lutomirski wrote:
> 
> The one and only time I tried to use this, I thought this was odd.  Long
> has a different size on 32 vs 64 bit architectures, and bit ops seem
> like they'd want to be the same size everywhere so you can allocate the
> appropriate number of bits.  (Also, if you only want 32 bits, you have
> to do some evil cheating, and I don't trust casting int* to long* on
> big-endian architectures.)
> 
> Would offering a u32* option make sense?
> 

Honestly, the only thing that makes sense on bigendian architectures is
either byte-by-byte elements or counting bit numbers from the MSB, but
that is serious water under the bridge at this point...

	-hpa

Re: The type of bitops

[Andy Lutomirski]

On Tue, May 7, 2013 at 4:18 PM, H. Peter Anvin <hpa@zytor.com> wrote:
> On 05/07/2013 04:17 PM, Andy Lutomirski wrote:
>>
>> The one and only time I tried to use this, I thought this was odd.  Long
>> has a different size on 32 vs 64 bit architectures, and bit ops seem
>> like they'd want to be the same size everywhere so you can allocate the
>> appropriate number of bits.  (Also, if you only want 32 bits, you have
>> to do some evil cheating, and I don't trust casting int* to long* on
>> big-endian architectures.)
>>
>> Would offering a u32* option make sense?
>>
>
> Honestly, the only thing that makes sense on bigendian architectures is
> either byte-by-byte elements or counting bit numbers from the MSB, but
> that is serious water under the bridge at this point...

Sure... but would some important data structure that only need 32 bits
get shorter if there were 32-bit bitops?

--Andy

Re: The type of bitops

[Andy Lutomirski]

On Tue, May 7, 2013 at 4:18 PM, H. Peter Anvin <hpa@zytor.com> wrote:
> On 05/07/2013 04:17 PM, Andy Lutomirski wrote:
>>
>> The one and only time I tried to use this, I thought this was odd.  Long
>> has a different size on 32 vs 64 bit architectures, and bit ops seem
>> like they'd want to be the same size everywhere so you can allocate the
>> appropriate number of bits.  (Also, if you only want 32 bits, you have
>> to do some evil cheating, and I don't trust casting int* to long* on
>> big-endian architectures.)
>>
>> Would offering a u32* option make sense?
>>
>
> Honestly, the only thing that makes sense on bigendian architectures is
> either byte-by-byte elements or counting bit numbers from the MSB, but
> that is serious water under the bridge at this point...

Sure... but would some important data structure that only need 32 bits
get shorter if there were 32-bit bitops?

--Andy