Anthony Williams wrote:
>
> BitWielder <hallsoftware@gmail.com> writes:
>
>> The draft standard in note 2 on page 6 says:
>>
>> A memory location is either an object of scalar type or a maximal
>> sequence of adjacent bit-=EF=AC=81elds all having
>> non-zero width. [Note: Various features of the language, such as
>> references and virtual functions, might
>> involve additional memory locations that are not accessible to
>> programs but are managed by the imple-
>> mentation. =E2=80=94end note ] Two threads of execution (1.10) can update a=
>> nd
>> access separate memory locations
>> without interfering with each other.
>>
>> My question then is in a multi-threaded application on an x86-based 32-
>> bit processor if the following structure must occupy 64 bits:
>>
>> struct A
>> {
>>   char x;
>>   char z;
>> };
>
> No, it need only occupy 16 bits, and I think it is required to do so.

Padding between x and z is prohibited?

Anyway, suppose the above struct ends up being used on a machine where
memory is only readable and writeable in 32-bit chunks.  Given that
the standard specifies only the behavior of a program on an abstract
machine, I believe a compiler would still be within its rights to put
x and z inside the same word, even though the compiler would have to
insert synchronization instructions to avoid having two threads try to
concurrently modify the word that x and z share.  From what I can
tell, the FCD does not define "interfere," so I take it to mean that
the observable behavior of a program must be such that it can never
appear that updates to x and z interfere with one another, even if in
the underlying hardware, access to x and z must be serialized.

> If the platform can only access 32-bit chunks but has an 8-bit char type
> then the compiler will have to use appropriate operations to ensure that
> the remaining 24-bits have not been changed by another thread when
> updating an individual char.

Unless the compiler can deduce that nothing in those 24 bits affects
observable behavior, right?

Scott

--
* C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near
Seattle (http://cppandbeyond.com/)
* License my training materials for commercial
(http://tinyurl.com/yfzvkp9) or personal use
(http://tinyurl.com/yl5ka5p).

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

BitWielder <hallsoftware@gmail.com> writes:
>>> The draft standard in note 2 on page 6 says:
>>>
>>> A memory location is either an object of scalar type or a maximal
>>> sequence of adjacent bit-fields all having
>>> non-zero width. [Note: Various features of the language, such as
>>> references and virtual functions, might
>>> involve additional memory locations that are not accessible to
>>> programs but are managed by the imple-
>>> mentation. --end note ] Two threads of execution (1.10) can update and
>>> access separate memory locations
>>> without interfering with each other.
>>>
>>> My question then is in a multi-threaded application on an x86-based 32-
>>> bit processor if the following structure must occupy 64 bits:
>>>
>>> struct A
>>> {
>>>   char x;
>>>   char z;
>>> };

No, it doesn't have to occupy 64 bits.

However, for an A object that is potentially shared, a write to x
(e.g., a.x = 2;) must not under any circumstances cause any write to
the bits of z. Therefore, the compiler must emit program writes to x
(and z) as single-byte write instructions. If a compiler can't do
that, it must add padding between x and z.

(Note: This restriction only applies if x and z are potentially
shared. If the compiler can prove x and z aren't shared it can do such
an optimization, as it can in sequential code, based on the "as-if"
rule -- i.e., the restriction quoted above still technically applies,
but a conforming program can't tell the difference, so the compiler
can legally get away with ignoring the above restriction. However,
proving that a variable is not shared is in general very difficult,
beyond simple cases like stack-based variables to which a
pointer/reference is never taken.)


Anthony Williams wrote:
>> No, it need only occupy 16 bits,

Yes.

>> and I think it is required to do so.

No, I don't think that part is true.


On Fri, 30 Apr 2010 15:33:48 CST, Scott Meyers
<NeverRead@aristeia.com> wrote:
>Padding between x and z is prohibited?
>
>Anyway, suppose the above struct ends up being used on a machine where
>memory is only readable and writeable in 32-bit chunks.  Given that
>the standard specifies only the behavior of a program on an abstract
>machine, I believe a compiler would still be within its rights to put
>x and z inside the same word, even though the compiler would have to
>insert synchronization instructions to avoid having two threads try to
>concurrently modify the word that x and z share.

That might work, but: a) I'm not sure it actually does work, because
for example if x and z are on the same cache line you automatically
get such synchronization in the hardware already and I don't think
that's sufficient; and b) it's probably impractical for performance
reasons due to synchronization overhead.

In a real implementation the compiler would either emit single-byte
writes (>99% of the time) or else add padding (rarely, I don't know of
a specific system that doesn't have single-byte writes and wants to
support C++0x or an equivalent memory model but I believe they do
exist).

>From what I can
>tell, the FCD does not define "interfere," so I take it to mean that
>the observable behavior of a program must be such that it can never
>appear that updates to x and z interfere with one another, even if in
>the underlying hardware, access to x and z must be serialized.

Right. In particular, you don't want lost updates, where thread 1 that
is trying to write to x but is implemented by reading/writing both x
and z innocently trying to "just write back the same value for z"
clobbers thread 1 that is writing to z and can have its write
clobbered by the invented write to z on thread 1.

Herb

---
Herb Sutter   (herbsutter.wordpress.com)   (www.gotw.ca)

Convener, SC22/WG21 (C++)                  (www.gotw.ca/iso)
Architect, Visual C++                      (www.gotw.ca/microsoft)

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Herb Sutter wrote:
> However, for an A object that is potentially shared, a write to x
> (e.g., a.x = 2;) must not under any circumstances cause any write to
> the bits of z

I think this is true only if the memory is declared volatile.  For "normal"
memory, I think it suffices for there to be no *observable* writes to
the bits of z.

> On Fri, 30 Apr 2010 15:33:48 CST, Scott Meyers
>> Anyway, suppose the above struct ends up being used on a machine where
>> memory is only readable and writeable in 32-bit chunks.  Given that
>> the standard specifies only the behavior of a program on an abstract
>> machine, I believe a compiler would still be within its rights to put
>> x and z inside the same word, even though the compiler would have to
>> insert synchronization instructions to avoid having two threads try to
>> concurrently modify the word that x and z share.
>
> That might work, but: a) I'm not sure it actually does work, because
> for example if x and z are on the same cache line you automatically
> get such synchronization in the hardware already and I don't think
> that's sufficient;

I think it's clearly not.  Consider a processor with hyperthreading, where
multiple hardware threads run on a single core and thus share the same data
cache(s).  In that case, the cache coherency hardware won't prevent multiple
threads from that core from tromping on one another. Right?

Scott

--
* C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
(http://cppandbeyond.com/)
* License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
personal use (http://tinyurl.com/yl5ka5p).

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu <std-c%2B%2B@netlab.cs.rpi.edu>]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Herb Sutter wrote:

> BitWielder <hallsoftware@gmail.com> writes:
>
>> struct A
>>>> {
>>>>  char x;
>>>>  char z;
>>>> };
>>>>
>>>
> No, it doesn't have to occupy 64 bits.
>
> However, for an A object that is potentially shared, a write to x
> (e.g., a.x = 2;) must not under any circumstances cause any write to
> the bits of z. Therefore, the compiler must emit program writes to x
> (and z) as single-byte write instructions. If a compiler can't do
> that, it must add padding between x and z.
>
> (Note: This restriction only applies if x and z are potentially
> shared. If the compiler can prove x and z aren't shared it can do such
> an optimization, as it can in sequential code, based on the "as-if"
> rule -- i.e., the restriction quoted above still technically applies,
> but a conforming program can't tell the difference, so the compiler
> can legally get away with ignoring the above restriction. However,
> proving that a variable is not shared is in general very difficult,
> beyond simple cases like stack-based variables to which a
> pointer/reference is never taken.)
>

Is the last part really allowed? Because I don't think "sharing"
of variables would do. Shouldn't the structure A itself (not only
concrete variables a.x, b.x) have the same layout in any compilation
unit, in different programs, etc? Otherwise, there would never be
#include "a.h" possible.

And from this I draw a conclusion that the usage of the structure
has no influence to its layout. Right?

--
Dragan

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Tue,  4 May 2010 13:29:31 CST, Dragan Milenkovic
<dragan@plusplus.rs> wrote:
>Herb Sutter wrote:
>
>> BitWielder <hallsoftware@gmail.com> writes:
>>
>>> struct A
>>>>> {
>>>>>  char x;
>>>>>  char z;
>>>>> };
>>>>>
>>>>
>> No, it doesn't have to occupy 64 bits.
>>
>> However, for an A object that is potentially shared, a write to x
>> (e.g., a.x = 2;) must not under any circumstances cause any write to
>> the bits of z. Therefore, the compiler must emit program writes to x
>> (and z) as single-byte write instructions. If a compiler can't do
>> that, it must add padding between x and z.
>>
>> (Note: This restriction only applies if x and z are potentially
>> shared. If the compiler can prove x and z aren't shared it can do such
>> an optimization, as it can in sequential code, based on the "as-if"
>> rule -- i.e., the restriction quoted above still technically applies,
>> but a conforming program can't tell the difference, so the compiler
>> can legally get away with ignoring the above restriction. However,
>> proving that a variable is not shared is in general very difficult,
>> beyond simple cases like stack-based variables to which a
>> pointer/reference is never taken.)
>>
>
>Is the last part really allowed? Because I don't think "sharing"
>of variables would do. Shouldn't the structure A itself (not only
>concrete variables a.x, b.x) have the same layout in any compilation
>unit, in different programs, etc? Otherwise, there would never be
>#include "a.h" possible.
>
>And from this I draw a conclusion that the usage of the structure
>has no influence to its layout. Right?

Right, the layout must definitely be the same.

All I was saying is that the compiler is technically allowed under
"as-if" to emit wider-than-byte read-mask-write operations that could
write (the original bits back) to nearby variabes, *if* it can prove
the variables are not shared and therefore the program can't tell the
difference.

Incidentally, for completeness, note that adjacent non-zero-length
bitfields are considered as a single variable for memory model
purposes. That is, you can protect any two named variables in the
program with different synchronization/mutexes, except if they're in
the same string of adjacent bitfields. The reasons are probably
obvious: The compiler can't in general avoid writing to one bitfield
without touching nearby bits of adjacent bitfields, because the
compiler can neither emit bit-store operations (in general, because no
processor I know of has bit-store operations and bitfields may or may
not fall on happy byte boundaries) nor add padding (by definition for
bitfields).

---
Herb Sutter   (herbsutter.wordpress.com)   (www.gotw.ca)

Convener, SC22/WG21 (C++)                  (www.gotw.ca/iso)
Architect, Visual C++                      (www.gotw.ca/microsoft)

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Herb Sutter <herb.sutter@gmail.com> writes:

> BitWielder <hallsoftware@gmail.com> writes:
>>>> The draft standard in note 2 on page 6 says:
>>>>
>>>> A memory location is either an object of scalar type or a maximal
>>>> sequence of adjacent bit-fields all having
>>>> non-zero width. [Note: Various features of the language, such as
>>>> references and virtual functions, might
>>>> involve additional memory locations that are not accessible to
>>>> programs but are managed by the imple-
>>>> mentation. --end note ] Two threads of execution (1.10) can update and
>>>> access separate memory locations
>>>> without interfering with each other.
>>>>
>>>> My question then is in a multi-threaded application on an x86-based 32-
>>>> bit processor if the following structure must occupy 64 bits:
>>>>
>>>> struct A
>>>> {
>>>>   char x;
>>>>   char z;
>>>> };
>
> No, it doesn't have to occupy 64 bits.
>
> However, for an A object that is potentially shared, a write to x
> (e.g., a.x = 2;) must not under any circumstances cause any write to
> the bits of z. Therefore, the compiler must emit program writes to x
> (and z) as single-byte write instructions. If a compiler can't do
> that, it must add padding between x and z.

> Anthony Williams wrote:
>>> No, it need only occupy 16 bits,
>
> Yes.
>
>>> and I think it is required to do so.
>
> No, I don't think that part is true.

Hmm. I can't find wording for separate members, though it would be
surprising to many if padding was allowed between consecutive members of
the same type, particularly in standard-layout types.

However, the same problem with regards memory accesses occurs with

struct XYZ
{
  char data[2];
};

And in this case, &data[1]==(&data[0]+1), so if char is 8 bits then data
is 16 bits, and I would thus expect XYZ to also be 16 bits (though
padding at the end is of course allowed).

If the hardware doesn't have 8-bit memory addressing, then either the
compiler must emit instructions to serialize access to the whole machine
word containing an 8-bit char if the rest of that word can be accessed
from another thread, or char must be promoted to the size of the machine
word (e.g. 32-bit char).

Anthony
--
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Mon,  3 May 2010 18:02:03 CST, Scott Meyers
<NeverRead@aristeia.com> wrote:
>Herb Sutter wrote:
>> However, for an A object that is potentially shared, a write to x
>> (e.g., a.x = 2;) must not under any circumstances cause any write to
>> the bits of z
>
>I think this is true only if the memory is declared volatile.

No, it's not specific to volatile. It applies to all variables -- but
like I said in the case where the compiler can prove the variable is
unshared (usually rare and difficult!) it can get away with doing a
load/mask/store that includes surrounding bits that are stored to but
only re-store the same values because a single thread in isolation
can't tell the difference.

>For "normal"
>memory, I think it suffices for there to be no *observable* writes to
>the bits of z.

I'm not sure what you mean here, but it sounds like an informal
summary of what I said in the earlier message, so I guess I agree. :)

Here's a concrete and fundamental motivating case: A program must be
able to correctly protect any two distinct named variables x and z
with different locks -- even if x and y are members of the same
struct/class, and even if they're adjacent chars. Specifically:

 // this code must be allowed and correct!

 // thread 1: use x, so take lock on mutex for x
 {
   lock_guard<mutex> g( mutX );
   a.x = 42;
 }

 // thread 2: use z, so take lock on mutex for z
 {
   lock_guard<mutex> g( mutZ );
   a.z = 42;
 }

I can't write this code correctly unless I know where all the writes
to x and z are, so I can take the right locks at the right times.
Those shared writes had better be visible in the source code, and had
better be _only_ the ones I said to perform in the source code.

If the system can silently inject writes (even of 'the same' value) to
variables never mentioned in the source code, such as writing to any
of the bits of x in thread 1 above, I have no hope of being able to
write correctly synchronized code (e.g., using separate locks for x
and z), because this wouldn't be guaranteed to be correctly
synchronized, in that thread 1 would be able to write to z without
holding the correct lock -- i.e., the compiler (or processor or cache
subsystem) would be injecting a race into my code. It had better not
ever do that.

The fundamental point is that the programmer had better be able to see
in source code all the writes to a shared variable (and all variables
are potentially shared unless the compiler can prove otherwise, which
is hard), which means that in a given piece of code the system must
never write to the bits of any program variable not mentioned in that
piece of code, otherwise the programmer can't know when to take the
right locks (or other synchronization).


>> On Fri, 30 Apr 2010 15:33:48 CST, Scott Meyers
>>> Anyway, suppose the above struct ends up being used on a machine where
>>> memory is only readable and writeable in 32-bit chunks.  Given that
>>> the standard specifies only the behavior of a program on an abstract
>>> machine, I believe a compiler would still be within its rights to put
>>> x and z inside the same word, even though the compiler would have to
>>> insert synchronization instructions to avoid having two threads try to
>>> concurrently modify the word that x and z share.
>>
>> That might work, but: a) I'm not sure it actually does work, because
>> for example if x and z are on the same cache line you automatically
>> get such synchronization in the hardware already and I don't think
>> that's sufficient;
>
>I think it's clearly not.  Consider a processor with hyperthreading, where
>multiple hardware threads run on a single core and thus share the same data
>cache(s).  In that case, the cache coherency hardware won't prevent multiple
>threads from that core from tromping on one another. Right?

Definitely it's not enough in the presence of hardware threads, which
will be long-term popular. I'm not sure it's sufficient even without
those, though.

Herb

---
Herb Sutter   (herbsutter.wordpress.com)   (www.gotw.ca)

Convener, SC22/WG21 (C++)                  (www.gotw.ca/iso)
Architect, Visual C++                      (www.gotw.ca/microsoft)

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Herb Sutter wrote:
>
> On Mon,  3 May 2010 18:02:03 CST, Scott Meyers
> <NeverRead@aristeia.com> wrote:
>>
>> Herb Sutter wrote:
>>>
>>> However, for an A object that is potentially shared, a write to x
>>> (e.g., a.x = 2;) must not under any circumstances cause any write to
>>> the bits of z
>>
>> I think this is true only if the memory is declared volatile.
>
> No, it's not specific to volatile. It applies to all variables -- but
> like I said in the case where the compiler can prove the variable is
> unshared (usually rare and difficult!) it can get away with doing a
> load/mask/store that includes surrounding bits that are stored to but
> only re-store the same values because a single thread in isolation
> can't tell the difference.

But this isn't the same as "not under any circumstances [causing] any
write to the bits of z." If z's bits are volatile, however, the
load/mask/store is not permitted at all, IMO.  Consider the disaster
that would ensue with that technique if z was memory-mapped.

>> For "normal"
>> memory, I think it suffices for there to be no *observable* writes to
>> the bits of z.
>
> I'm not sure what you mean here, but it sounds like an informal
> summary of what I said in the earlier message, so I guess I agree. :)

I think you do, too :-)

Scott

--
* C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near
Seattle (http://cppandbeyond.com/)
* License my training materials for commercial
(http://tinyurl.com/yfzvkp9) or personal use
(http://tinyurl.com/yl5ka5p).

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

The draft standard in note 2 on page 6 says:

A memory location is either an object of scalar type or a maximal
sequence of adjacent bit-=EF=AC=81elds all having
non-zero width. [Note: Various features of the language, such as
references and virtual functions, might
involve additional memory locations that are not accessible to
programs but are managed by the imple-
mentation. =E2=80=94end note ] Two threads of execution (1.10) can update a=
nd
access separate memory locations
without interfering with each other.

My question then is in a multi-threaded application on an x86-based 32-
bit processor if the following structure must occupy 64 bits:

struct A
{
   char x;
   char z;
};

The idea being that the last note in the says that two threads of
execution can update and access separate memory location *without
interfering with each other*.  On x86 32-bit processors, I believe
memory is written to 32-bits at a time, so if one wanted to modify 1
byte, the CPU must read the other 3 bytes, set the 1 byte and write
that back to memory.  Or am I mistaken about x86 32-bit processors?
If I am not mistaken, am I interpreting the standard correctly?

Thanks for the help in understanding.

Kevin Hall


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

BitWielder <hallsoftware@gmail.com> writes:

> The draft standard in note 2 on page 6 says:
>
> A memory location is either an object of scalar type or a maximal
> sequence of adjacent bit-=EF=AC=81elds all having
> non-zero width. [Note: Various features of the language, such as
> references and virtual functions, might
> involve additional memory locations that are not accessible to
> programs but are managed by the imple-
> mentation. =E2=80=94end note ] Two threads of execution (1.10) can update a=
> nd
> access separate memory locations
> without interfering with each other.
>
> My question then is in a multi-threaded application on an x86-based 32-
> bit processor if the following structure must occupy 64 bits:
>
> struct A
> {
>    char x;
>    char z;
> };

No, it need only occupy 16 bits, and I think it is required to do so.

> The idea being that the last note in the says that two threads of
> execution can update and access separate memory location *without
> interfering with each other*.  On x86 32-bit processors, I believe
> memory is written to 32-bits at a time, so if one wanted to modify 1
> byte, the CPU must read the other 3 bytes, set the 1 byte and write
> that back to memory.  Or am I mistaken about x86 32-bit processors?
> If I am not mistaken, am I interpreting the standard correctly?

You are mistaken about the x86 processors --- they can access single
bytes. It will of course require the cache line to be passed back and
forth, but this does not affect addressability.

If the platform can only access 32-bit chunks but has an 8-bit char type
then the compiler will have to use appropriate operations to ensure that
the remaining 24-bits have not been changed by another thread when
updating an individual char.

Anthony
--
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]