Kent Dickey wrote:

> In article <uiri0a$85mp$2@dont-email.me>,
> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

>>A highly relaxed memory model can be beneficial for certain workloads.

> I know a lot of people believe that statement to be true. In general, it
> is assumed to be true without proof.
<
In its most general case, relaxed order only provides a performance advantage
when the code is single threaded.
<
> I believe that statement to be false. Can you describe some of these
> workloads?
<
Relaxed memory order fails spectacularly when multiple threads are accessing
data.
<
> Kent

On 11/12/2023 4:20 PM, MitchAlsup wrote:
> Chris M. Thomasson wrote:
>
>> On 11/12/2023 2:33 PM, Kent Dickey wrote:
>>> In article <uiri0a$85mp$2@dont-email.me>,
>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>
>>>> A highly relaxed memory model can be beneficial for certain workloads.
>>>
>>> I know a lot of people believe that statement to be true.  In
>>> general, it
>>> is assumed to be true without proof.
>>>
>>> I believe that statement to be false.  Can you describe some of these
>>> workloads?
>
>> Also, think about converting any sound lock-free algorithm's finely
>> tuned memory barriers to _all_ sequential consistency... That would
>> ruin performance right off the bat... Think about it.
> <
> Assuming you are willing to accept the wrong answer fast, rather than
> the right answer later. There are very few algorithms with this property.

That does not make any sense to me. Think of a basic mutex. It basically
requires an acquire membar for the lock and a release membar for the
unlock. On SPARC that would be:

acquire = MEMBAR #LoadStore | #LoadLoad

release = MEMBAR #LoadStore | #StoreStore

Okay, fine. However, if I made them sequentially consistent, it would
require a damn #StoreLoad barrier for both acquire and release. This is
not good and should be avoided when possible.

Also, RCU prides itself with not having to use any memory barriers for
its read side. If RCU was forced to use a seq cst, basically LOCKED RMW
or MFENCE on Intel, it would completely ruin its performance.

In article <uirqj3$9q9q$1@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>On 11/12/2023 4:20 PM, MitchAlsup wrote:
>> Chris M. Thomasson wrote:
>>
>>> On 11/12/2023 2:33 PM, Kent Dickey wrote:
>>>> In article <uiri0a$85mp$2@dont-email.me>,
>>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>>
>>>>> A highly relaxed memory model can be beneficial for certain workloads.
>>>>
>>>> I know a lot of people believe that statement to be true.  In
>>>> general, it
>>>> is assumed to be true without proof.
>>>>
>>>> I believe that statement to be false.  Can you describe some of these
>>>> workloads?
>>
>>> Also, think about converting any sound lock-free algorithm's finely
>>> tuned memory barriers to _all_ sequential consistency... That would
>>> ruin performance right off the bat... Think about it.
>> <
>> Assuming you are willing to accept the wrong answer fast, rather than
>> the right answer later. There are very few algorithms with this property.
>
>That does not make any sense to me. Think of a basic mutex. It basically
>requires an acquire membar for the lock and a release membar for the
>unlock. On SPARC that would be:
>
>acquire = MEMBAR #LoadStore | #LoadLoad
>
>release = MEMBAR #LoadStore | #StoreStore
>
>Okay, fine. However, if I made them sequentially consistent, it would
>require a damn #StoreLoad barrier for both acquire and release. This is
>not good and should be avoided when possible.
>
>Also, RCU prides itself with not having to use any memory barriers for
>its read side. If RCU was forced to use a seq cst, basically LOCKED RMW
>or MFENCE on Intel, it would completely ruin its performance.

You are using the terms in the exact opposite meaning as I would understand
computer architecture.

We'll just assume 3 choices for CPU ordering:

- Sequential consistency (SC). Hardware does everything, there are no
barriers needed, ld/st instructions appear to happen in some
global order.
- Total Store Ordering (TSO) (x86). Stores appear to be done in program
order, but a CPU can peek and see its own local store results
before other CPUs can. Loads appear to be done in some total
program order (not counting hitting its own local stores).
TSO is like SC except there's effectively a store queue, and
stores can finish when placed in the queue, and the queue drains
in FIFO order. Needs no barriers, except for special cases like
Lamport's algorithm (it's easy to avoid barriers).
- Relaxed. Loads and stores are not ordered, users have to put in memory
barriers and hope they did it right.

So, a highly relaxed memory model is the ONLY model which needs barriers.
If you want to get rid of barriers, use a better memory model.

A relaxed ordering SYSTEM says rather than spending a few thousand
gates getting ordering right by hardware in the CPU, instead we're going
to require software to put in some very difficult to understand barriers.
And we're going to have a 45 page academic paper using all the greek
alphabet to describe when you need to put in barriers. Literally no one
understands all the rules, so the best bet is put in too many barriers
and wait for someone to nitpick your code and fix it for you.

[I have a theorem: there is no correct non-trivial multithreaded program
on an architecture which requires barriers for correctness.].

A very simple thought exercise shows even if Sequential Consistency
and/or TSO were slower (and I maintain they are not), but even if you
believe that, a Relaxed Ordering system WILL be slower than TSO or
Sequential for workloads which often use barriers (instructions tagged
with acquire/release are barriers). In a Relaxed ordering system, the
barriers will not be as efficient as the automatic barriers of TSO/SC
(otherwise, why not just do that?), so if barriers are executed often,
performance will be lower than hardware TSO/SC, even if there are no
contentions or any work for the barriers to do. In fact, performance
could be significantly lower.

People know this, it's why they keep trying to get rid of barriers in
their code. So get rid of all them and demand TSO ordering.

Thus, the people trapped in Relaxed Ordering Hell then push weird schemes
on everyone else to try to come up with algorithms which need fewer
barriers. It's crazy.

Relaxed Ordering is a mistake.

Kent

In article <82b3b3b710652e607dac6cec2064c90b@news.novabbs.com>,
MitchAlsup <mitchalsup@aol.com> wrote:
>Kent Dickey wrote:
>
>> In article <uiri0a$85mp$2@dont-email.me>,
>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>
>>>A highly relaxed memory model can be beneficial for certain workloads.
>
>> I know a lot of people believe that statement to be true. In general, it
>> is assumed to be true without proof.
><
>In its most general case, relaxed order only provides a performance advantage
>when the code is single threaded.

I believe a Relaxed Memory model provides a small performance improvement
ONLY to simple in-order CPUs in an MP system (if you're a single CPU,
there's nothing to order).

Relazed Memory ordering provides approximately zero performance improvement
to an OoO CPU, and in fact, might actually lower performance (depends on
how barriers are done--if done poorly, it could be a big negative).

Yes, the system designers of the world have said: let's slow down our
fastest most expensive most profitable CPUs, so we can speed up our cheapest
lowest profit CPUs a few percent, and push a ton of work onto software
developers.

It's crazy.

>> I believe that statement to be false. Can you describe some of these
>> workloads?
><
>Relaxed memory order fails spectacularly when multiple threads are accessing
>data.

Probably need to clarify with "accessing modified data".

Kent

"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>Also, think about converting any sound lock-free algorithm's finely
>tuned memory barriers to _all_ sequential consistency... That would ruin
>performance right off the bat... Think about it.

Proof by claim?

I think about several similar instances, where people went for
simple-minded hardware designs and threw the complexity over the wall
to the software people, and claimed that it was for performance; I
call that the "supercomputing attitude", and it may work in areas
where the software crisis has not yet struck[1], but is a bad attitude
in areas like general-purpose computing where it has struck.

1) People thought that they could achieve faster hardware by throwing
the task of scheduling instructions for maximum instruction-level
parallelism over to the compiler people. Several companies (in
particular, Intel, HP, and Transmeta) invested a lot of money into
this dream (and the Mill project relives this dream), but it turned
out that doing the scheduling in hardware is faster.

2) A little earlier, the Alpha designers thought that they could gain
speed by not implementing denormal numbers and by implementing
imprecise exceptions for FP operations, so that it is not possible to
implement denormal numbers through a software fixup, either. For
dealing properly with denormal numbers, you had to insert a trap
barrier right after each FP instruction, and presumably this cost a
lot of performance on early Alpha implementations. However, when I
measured it on the 21264 (released six years after the first Alpha),
the cost was like that of a nop; I guess that the trap barrier was
actually a nop on the 21264, because, as an OoO processor, the 21264
performs precise exceptions without breaking a sweat. And the 21264
is faster than the models where the trap barrier actually does
something. Meanwhile, Mitch Alsup also has posted that he can
implement fast denormal numbers with IIRC 30 extra gates (which is
probably less than what is needed for implementing the trap barrier).

3) The Alpha is a rich source of examples of the supercomputer
attitude: It started out without instructions for accessing 8-bit and
16-bit data in memory. Instead, the idea was that for accessing
memory, you would use instruction sequences, and for accessing I/O
devices, the device was mapped three times or so: In one address range
you performed bytewise access, in another address range 16-bit
accesses, and in the third address range 32-bit and 64-bit accesses;
I/O driver writers had to write or modify their drivers for this
model. The rationale for that was that they required ECC for
permanent storage and that would supposedly require slow RMW accesses
for writing bytes to write-back caches. Now the 21064 and 21164 had a
write-through D-cache. That made it easy to add byte and word
accesses (BWX) in the 21164A (released 1996), but they could have done
it from the start. The 21164A is in no way slower than the 21164; it
has the same IPC and a higher clock rate.

Some people welcome and celebrate the challenges that the
supercomputer attitude poses for software, and justify it with
"performance", but as the examples above show, such claims often turn
out to be false when you actually invest effort into more capable
hardware.

Given that multi-processors come out of supercomputing, it's no
surprise that the supercomputing attitude is particularly strong
there.

But if you look at it from an architecture (i.e., hardware/software
interface) perspective, weak consistency is just bad architecture:
good architecture says what happens to the architectural state when
software performs some instruction. From that perspective sequential
consistency is architecturally best. Weaker consistency models
describe how the architecture does not provide the sequential
consistency guarantees that are so easy to describe; the weaker the
model, the more deviations it has to describe.

[1] The software crisis is that software costs are higher than
hardware costs, and supercomputing with its gigantic hardware costs
notices the software crisis much later than general-purpose computing.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Kent Dickey <kegs@provalid.com> wrote:
> We'll just assume 3 choices for CPU ordering:
>
> - Sequential consistency (SC). Hardware does everything, there are no
> barriers needed, ld/st instructions appear to happen in some
> global order.
> - Total Store Ordering (TSO) (x86). Stores appear to be done in program
> order, but a CPU can peek and see its own local store results
> before other CPUs can. Loads appear to be done in some total
> program order (not counting hitting its own local stores).
> TSO is like SC except there's effectively a store queue, and
> stores can finish when placed in the queue, and the queue drains
> in FIFO order. Needs no barriers, except for special cases like
> Lamport's algorithm (it's easy to avoid barriers).
> - Relaxed. Loads and stores are not ordered, users have to put in memory
> barriers and hope they did it right.
>
> So, a highly relaxed memory model is the ONLY model which needs barriers.

But this isn't true. Real processors aren't anywhere near as wildly
chaotic as this.

The common form of relaxed memory we see today is causally consistent
and multi-copy atomic (and cache coherent). So, all other threads see
stores to a single location in the same order, and you don't get the
extraordinary going-backwards-in-time behaviour of DEC Alpha.

> A relaxed ordering SYSTEM says rather than spending a few thousand
> gates getting ordering right by hardware in the CPU, instead we're
> going to require software to put in some very difficult to
> understand barriers.

I don't think that's really true. The reorderings we see in currently-
produced hardware are, more or less, a subset of the same reorderings
that C compilers perform. Therefore, if you see a confusing hardware
reordering in a multi-threaded C program it may well be (probably is!)
a bug (according to the C standard) *even on a TSO machine*. The only
common counter-example to this is for volatile accesses.

> A very simple thought exercise shows even if Sequential Consistency
> and/or TSO were slower (and I maintain they are not), but even if
> you believe that, a Relaxed Ordering system WILL be slower than TSO
> or Sequential for workloads which often use barriers (instructions
> tagged with acquire/release are barriers). In a Relaxed ordering
> system, the barriers will not be as efficient as the automatic
> barriers of TSO/SC (otherwise, why not just do that?),

Whyever not? They do the same thing.

Andrew.

> 1) People thought that they could achieve faster hardware by throwing
> the task of scheduling instructions for maximum instruction-level
> parallelism over to the compiler people. Several companies (in
> particular, Intel, HP, and Transmeta) invested a lot of money into
> this dream (and the Mill project relives this dream), but it turned
> out that doing the scheduling in hardware is faster.

IIRC the main argument for the Mill wasn't that it was going to be
faster but that it would give a better performance per watt by avoiding
the administrative cost of managing those hundreds of reordered
in-flight instructions, without losing too much peak performance.

The fact that performance per watt of in-order ARM cores is not really
lower than that of OOO cores suggests that the Mill wouldn't deliver on
this "promise" either.
Still, I really would like to see how it plays out in practice, instead
of having to guess.

Stefan

Kent Dickey wrote:
> In article <uirqj3$9q9q$1@dont-email.me>,
> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>> On 11/12/2023 4:20 PM, MitchAlsup wrote:
>>> Chris M. Thomasson wrote:
>>>
>>>> On 11/12/2023 2:33 PM, Kent Dickey wrote:
>>>>> In article <uiri0a$85mp$2@dont-email.me>,
>>>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>>>
>>>>>> A highly relaxed memory model can be beneficial for certain workloads.
>>>>> I know a lot of people believe that statement to be true. In
>>>>> general, it
>>>>> is assumed to be true without proof.
>>>>>
>>>>> I believe that statement to be false. Can you describe some of these
>>>>> workloads?
>>>> Also, think about converting any sound lock-free algorithm's finely
>>>> tuned memory barriers to _all_ sequential consistency... That would
>>>> ruin performance right off the bat... Think about it.
>>> <
>>> Assuming you are willing to accept the wrong answer fast, rather than
>>> the right answer later. There are very few algorithms with this property.
>> That does not make any sense to me. Think of a basic mutex. It basically
>> requires an acquire membar for the lock and a release membar for the
>> unlock. On SPARC that would be:
>>
>> acquire = MEMBAR #LoadStore | #LoadLoad
>>
>> release = MEMBAR #LoadStore | #StoreStore
>>
>> Okay, fine. However, if I made them sequentially consistent, it would
>> require a damn #StoreLoad barrier for both acquire and release. This is
>> not good and should be avoided when possible.
>>
>> Also, RCU prides itself with not having to use any memory barriers for
>> its read side. If RCU was forced to use a seq cst, basically LOCKED RMW
>> or MFENCE on Intel, it would completely ruin its performance.
>
> You are using the terms in the exact opposite meaning as I would understand
> computer architecture.
>
> We'll just assume 3 choices for CPU ordering:
>
> - Sequential consistency (SC). Hardware does everything, there are no
> barriers needed, ld/st instructions appear to happen in some
> global order.
> - Total Store Ordering (TSO) (x86). Stores appear to be done in program
> order, but a CPU can peek and see its own local store results
> before other CPUs can. Loads appear to be done in some total
> program order (not counting hitting its own local stores).
> TSO is like SC except there's effectively a store queue, and
> stores can finish when placed in the queue, and the queue drains
> in FIFO order. Needs no barriers, except for special cases like
> Lamport's algorithm (it's easy to avoid barriers).
> - Relaxed. Loads and stores are not ordered, users have to put in memory
> barriers and hope they did it right.
>
> So, a highly relaxed memory model is the ONLY model which needs barriers.
> If you want to get rid of barriers, use a better memory model.
>
> A relaxed ordering SYSTEM says rather than spending a few thousand
> gates getting ordering right by hardware in the CPU, instead we're going
> to require software to put in some very difficult to understand barriers.
> And we're going to have a 45 page academic paper using all the greek
> alphabet to describe when you need to put in barriers. Literally no one
> understands all the rules, so the best bet is put in too many barriers
> and wait for someone to nitpick your code and fix it for you.
>
> [I have a theorem: there is no correct non-trivial multithreaded program
> on an architecture which requires barriers for correctness.].
>
> A very simple thought exercise shows even if Sequential Consistency
> and/or TSO were slower (and I maintain they are not), but even if you
> believe that, a Relaxed Ordering system WILL be slower than TSO or
> Sequential for workloads which often use barriers (instructions tagged
> with acquire/release are barriers). In a Relaxed ordering system, the
> barriers will not be as efficient as the automatic barriers of TSO/SC
> (otherwise, why not just do that?), so if barriers are executed often,
> performance will be lower than hardware TSO/SC, even if there are no
> contentions or any work for the barriers to do. In fact, performance
> could be significantly lower.
>
> People know this, it's why they keep trying to get rid of barriers in
> their code. So get rid of all them and demand TSO ordering.
>
> Thus, the people trapped in Relaxed Ordering Hell then push weird schemes
> on everyone else to try to come up with algorithms which need fewer
> barriers. It's crazy.
>
> Relaxed Ordering is a mistake.
>
> Kent

I suggest something different: the ability to switch between TSO and
relaxed with non-privileged user mode instructions.

Non-concurrent code does not see the relaxed ordering, and should benefit
from extra concurrency in the Load Store Queue and cache that relaxed rules
allow, because the local core always sees its own memory as consistent.
For example, relaxed ordering allows multiple LD and ST to be in
multiple pipelines to multiple cache banks at once without regard
as to the exact order the operations are applied.

This is fine for non concurrently accessed data structures,
either non-shared data areas or shared but guarded by mutexes.

But relaxed is hard for people to reason about for concurrently accessed
lock free data structures. Now these don't just appear out of thin air so
it is reasonable for a program to emit TSO_START and TSO_END instructions.

On the other hand, almost no code is lock-free or ever will be.
So why have all the extra HW logic to support TSO if its only really
needed for this rare kind of programming.

But there is also a category of memory area that is not covered by the
above rules, one where one core thinks its memory is local and not shared
but in fact it is being accessed concurrently.

If thread T1 (say an app) on core C1 says its memory is relaxed, and calls
a subroutine passing a pointer to a value on T1's stack, and that pointer
is passed to thread T2 (a driver) on core C2 which accesses that memory,
then even if T2 declared itself to be using TSO rules it would not force
T1 on C1 obey them.

Where this approach could fail is the kind of laissez-faire sharing done
by many apps, libraries, and OS's behind the scenes in the real world.

Anton Ertl wrote:

> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>>Also, think about converting any sound lock-free algorithm's finely
>>tuned memory barriers to _all_ sequential consistency... That would ruin
>>performance right off the bat... Think about it.

> Proof by claim?

> I think about several similar instances, where people went for
> simple-minded hardware designs and threw the complexity over the wall
> to the software people, and claimed that it was for performance; I
> call that the "supercomputing attitude", and it may work in areas
> where the software crisis has not yet struck[1], but is a bad attitude
> in areas like general-purpose computing where it has struck.

> 1) People thought that they could achieve faster hardware by throwing
> the task of scheduling instructions for maximum instruction-level
> parallelism over to the compiler people. Several companies (in
> particular, Intel, HP, and Transmeta) invested a lot of money into
> this dream (and the Mill project relives this dream), but it turned
> out that doing the scheduling in hardware is faster.
<
Not faster, but easier to do with acceptable HW costs. The pipeline
is 1-3 stages longer, but HW has dynamic information that SW cannot have.
<
> 2) A little earlier, the Alpha designers thought that they could gain
> speed by not implementing denormal numbers and by implementing
> imprecise exceptions for FP operations, so that it is not possible to
> implement denormal numbers through a software fixup, either. For
<
So did I in Mc 88100--just as wrong then as it is now.
<
> dealing properly with denormal numbers, you had to insert a trap
> barrier right after each FP instruction, and presumably this cost a
> lot of performance on early Alpha implementations. However, when I
> measured it on the 21264 (released six years after the first Alpha),
> the cost was like that of a nop; I guess that the trap barrier was
> actually a nop on the 21264, because, as an OoO processor, the 21264
> performs precise exceptions without breaking a sweat. And the 21264
> is faster than the models where the trap barrier actually does
> something. Meanwhile, Mitch Alsup also has posted that he can
> implement fast denormal numbers with IIRC 30 extra gates (which is
> probably less than what is needed for implementing the trap barrier).
<
I recall saying it is about 2% of the gate count of an FMAC unit.
<
> 3) The Alpha is a rich source of examples of the supercomputer
> attitude: It started out without instructions for accessing 8-bit and
> 16-bit data in memory. Instead, the idea was that for accessing
> memory, you would use instruction sequences, and for accessing I/O
> devices, the device was mapped three times or so: In one address range
> you performed bytewise access, in another address range 16-bit
> accesses, and in the third address range 32-bit and 64-bit accesses;
> I/O driver writers had to write or modify their drivers for this
> model. The rationale for that was that they required ECC for
> permanent storage and that would supposedly require slow RMW accesses
> for writing bytes to write-back caches. Now the 21064 and 21164 had a
> write-through D-cache. That made it easy to add byte and word
> accesses (BWX) in the 21164A (released 1996), but they could have done
> it from the start. The 21164A is in no way slower than the 21164; it
> has the same IPC and a higher clock rate.

> Some people welcome and celebrate the challenges that the
> supercomputer attitude poses for software, and justify it with
> "performance", but as the examples above show, such claims often turn
> out to be false when you actually invest effort into more capable
> hardware.

> Given that multi-processors come out of supercomputing, it's no
> surprise that the supercomputing attitude is particularly strong
> there.

> But if you look at it from an architecture (i.e., hardware/software
> interface) perspective, weak consistency is just bad architecture:
> good architecture says what happens to the architectural state when
> software performs some instruction. From that perspective sequential
> consistency is architecturally best. Weaker consistency models
> describe how the architecture does not provide the sequential
> consistency guarantees that are so easy to describe; the weaker the
> model, the more deviations it has to describe.
<
The problem that the weak consistency models enabled comes from the
fact it was universal over all accesses. However the TLB can be used
to solve that problem so each access has its own model and the HW has
to perform with that model often across a multiplicity of memory
references. For my part I have 4 memory models and the CPUs switch to
the appropriate model upon detection without needing instructions. So
when the first instruction of an ATOMIC event is detected (decode),
All weaker outstanding request are allowed to complete, and all of
the ATOMIC requests are performed in sequentially consistent manner,
then afterwards the memory model is weakened, again.
<
> [1] The software crisis is that software costs are higher than
> hardware costs, and supercomputing with its gigantic hardware costs
> notices the software crisis much later than general-purpose computing.

> - anton

aph@littlepinkcloud.invalid wrote:

> Kent Dickey <kegs@provalid.com> wrote:
>> We'll just assume 3 choices for CPU ordering:
>>
>> - Sequential consistency (SC). Hardware does everything, there are no
>> barriers needed, ld/st instructions appear to happen in some
>> global order.
>> - Total Store Ordering (TSO) (x86). Stores appear to be done in program
>> order, but a CPU can peek and see its own local store results
>> before other CPUs can. Loads appear to be done in some total
>> program order (not counting hitting its own local stores).
>> TSO is like SC except there's effectively a store queue, and
>> stores can finish when placed in the queue, and the queue drains
>> in FIFO order. Needs no barriers, except for special cases like
>> Lamport's algorithm (it's easy to avoid barriers).
>> - Relaxed. Loads and stores are not ordered, users have to put in memory
>> barriers and hope they did it right.
>>
>> So, a highly relaxed memory model is the ONLY model which needs barriers.

> But this isn't true. Real processors aren't anywhere near as wildly
> chaotic as this.

> The common form of relaxed memory we see today is causally consistent
> and multi-copy atomic (and cache coherent). So, all other threads see
> stores to a single location in the same order, and you don't get the
> extraordinary going-backwards-in-time behaviour of DEC Alpha.

>> A relaxed ordering SYSTEM says rather than spending a few thousand
>> gates getting ordering right by hardware in the CPU, instead we're
>> going to require software to put in some very difficult to
>> understand barriers.
<
The control logic to perform may be that small, the state to maintain it
is at least (5×48^2)×1.2-gates.

> I don't think that's really true. The reorderings we see in currently-
> produced hardware are, more or less, a subset of the same reorderings
> that C compilers perform. Therefore, if you see a confusing hardware
> reordering in a multi-threaded C program it may well be (probably is!)
> a bug (according to the C standard) *even on a TSO machine*. The only
> common counter-example to this is for volatile accesses.
<
Andy Glew used to report that there was surprisingly few instructions
performed out-of-order on an GBOoO machine.

>> A very simple thought exercise shows even if Sequential Consistency
>> and/or TSO were slower (and I maintain they are not), but even if
>> you believe that, a Relaxed Ordering system WILL be slower than TSO
>> or Sequential for workloads which often use barriers (instructions
>> tagged with acquire/release are barriers). In a Relaxed ordering
>> system, the barriers will not be as efficient as the automatic
>> barriers of TSO/SC (otherwise, why not just do that?),

> Whyever not? They do the same thing.

> Andrew.

EricP wrote:

> Kent Dickey wrote:
>> In article <uirqj3$9q9q$1@dont-email.me>,
>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>> On 11/12/2023 4:20 PM, MitchAlsup wrote:
>>>> Chris M. Thomasson wrote:
>>>>
>>>>> On 11/12/2023 2:33 PM, Kent Dickey wrote:
>>>>>> In article <uiri0a$85mp$2@dont-email.me>,
>>>>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>>>>
>>>>>>> A highly relaxed memory model can be beneficial for certain workloads.
>>>>>> I know a lot of people believe that statement to be true. In
>>>>>> general, it
>>>>>> is assumed to be true without proof.
>>>>>>
>>>>>> I believe that statement to be false. Can you describe some of these
>>>>>> workloads?
>>>>> Also, think about converting any sound lock-free algorithm's finely
>>>>> tuned memory barriers to _all_ sequential consistency... That would
>>>>> ruin performance right off the bat... Think about it.
>>>> <
>>>> Assuming you are willing to accept the wrong answer fast, rather than
>>>> the right answer later. There are very few algorithms with this property.
>>> That does not make any sense to me. Think of a basic mutex. It basically
>>> requires an acquire membar for the lock and a release membar for the
>>> unlock. On SPARC that would be:
>>>
>>> acquire = MEMBAR #LoadStore | #LoadLoad
>>>
>>> release = MEMBAR #LoadStore | #StoreStore
>>>
>>> Okay, fine. However, if I made them sequentially consistent, it would
>>> require a damn #StoreLoad barrier for both acquire and release. This is
>>> not good and should be avoided when possible.
>>>
>>> Also, RCU prides itself with not having to use any memory barriers for
>>> its read side. If RCU was forced to use a seq cst, basically LOCKED RMW
>>> or MFENCE on Intel, it would completely ruin its performance.
>>
>> You are using the terms in the exact opposite meaning as I would understand
>> computer architecture.
>>
>> We'll just assume 3 choices for CPU ordering:
>>
>> - Sequential consistency (SC). Hardware does everything, there are no
>> barriers needed, ld/st instructions appear to happen in some
>> global order.
>> - Total Store Ordering (TSO) (x86). Stores appear to be done in program
>> order, but a CPU can peek and see its own local store results
>> before other CPUs can. Loads appear to be done in some total
>> program order (not counting hitting its own local stores).
>> TSO is like SC except there's effectively a store queue, and
>> stores can finish when placed in the queue, and the queue drains
>> in FIFO order. Needs no barriers, except for special cases like
>> Lamport's algorithm (it's easy to avoid barriers).
>> - Relaxed. Loads and stores are not ordered, users have to put in memory
>> barriers and hope they did it right.
>>
>> So, a highly relaxed memory model is the ONLY model which needs barriers.
>> If you want to get rid of barriers, use a better memory model.
>>
>> A relaxed ordering SYSTEM says rather than spending a few thousand
>> gates getting ordering right by hardware in the CPU, instead we're going
>> to require software to put in some very difficult to understand barriers.
>> And we're going to have a 45 page academic paper using all the greek
>> alphabet to describe when you need to put in barriers. Literally no one
>> understands all the rules, so the best bet is put in too many barriers
>> and wait for someone to nitpick your code and fix it for you.
>>
>> [I have a theorem: there is no correct non-trivial multithreaded program
>> on an architecture which requires barriers for correctness.].
>>
>> A very simple thought exercise shows even if Sequential Consistency
>> and/or TSO were slower (and I maintain they are not), but even if you
>> believe that, a Relaxed Ordering system WILL be slower than TSO or
>> Sequential for workloads which often use barriers (instructions tagged
>> with acquire/release are barriers). In a Relaxed ordering system, the
>> barriers will not be as efficient as the automatic barriers of TSO/SC
>> (otherwise, why not just do that?), so if barriers are executed often,
>> performance will be lower than hardware TSO/SC, even if there are no
>> contentions or any work for the barriers to do. In fact, performance
>> could be significantly lower.
>>
>> People know this, it's why they keep trying to get rid of barriers in
>> their code. So get rid of all them and demand TSO ordering.
>>
>> Thus, the people trapped in Relaxed Ordering Hell then push weird schemes
>> on everyone else to try to come up with algorithms which need fewer
>> barriers. It's crazy.
>>
>> Relaxed Ordering is a mistake.
>>
>> Kent

> I suggest something different: the ability to switch between TSO and
> relaxed with non-privileged user mode instructions.
<
I suggest this switch between modes be done without executing any extra
instructions. I do the switches based on the address space of the access
{DRAM, MMI/O, config, ROM} and I also switch to SC when an ATOMIC event
begins.
<
> Non-concurrent code does not see the relaxed ordering, and should benefit
> from extra concurrency in the Load Store Queue and cache that relaxed rules
> allow, because the local core always sees its own memory as consistent.
> For example, relaxed ordering allows multiple LD and ST to be in
> multiple pipelines to multiple cache banks at once without regard
> as to the exact order the operations are applied.
<
I suspect SUN lost significant performance by always running TSO and
it still required barrier instructions.
<
> This is fine for non concurrently accessed data structures,
> either non-shared data areas or shared but guarded by mutexes.

> But relaxed is hard for people to reason about for concurrently accessed
> lock free data structures.
<
It is hard for people who have a completely vonNeumann thinking pattern
pattern to reason about these things, it is not hard for someone whos
entire career was spent doing multiplicity of things concurrently.
<
SW languages (and debuggers,...) teach people to think:: this happens than
that happens then something else happens. HW languages teach people to think
"crap all of this is happening at once, how do I make sense out of it".
<
In CPU design (or chip design in general) one is NEVER given the illusion
that a single <vast> state describes the moment. It is s shame the SW
did not follow similar route.
<
> Now these don't just appear out of thin air so
> it is reasonable for a program to emit TSO_START and TSO_END instructions.

> On the other hand, almost no code is lock-free or ever will be.
> So why have all the extra HW logic to support TSO if its only really
> needed for this rare kind of programming.
<
I made this exact argument to SUN circa 1993.....
<
> But there is also a category of memory area that is not covered by the
> above rules, one where one core thinks its memory is local and not shared
> but in fact it is being accessed concurrently.

> If thread T1 (say an app) on core C1 says its memory is relaxed, and calls
> a subroutine passing a pointer to a value on T1's stack, and that pointer
> is passed to thread T2 (a driver) on core C2 which accesses that memory,
> then even if T2 declared itself to be using TSO rules it would not force
> T1 on C1 obey them.

> Where this approach could fail is the kind of laissez-faire sharing done
> by many apps, libraries, and OS's behind the scenes in the real world.

So, anything written in JavaScript........

On 11/13/2023 3:49 AM, aph@littlepinkcloud.invalid wrote:
> Kent Dickey <kegs@provalid.com> wrote:
>> We'll just assume 3 choices for CPU ordering:
>>
>> - Sequential consistency (SC). Hardware does everything, there are no
>> barriers needed, ld/st instructions appear to happen in some
>> global order.
>> - Total Store Ordering (TSO) (x86). Stores appear to be done in program
>> order, but a CPU can peek and see its own local store results
>> before other CPUs can. Loads appear to be done in some total
>> program order (not counting hitting its own local stores).
>> TSO is like SC except there's effectively a store queue, and
>> stores can finish when placed in the queue, and the queue drains
>> in FIFO order. Needs no barriers, except for special cases like
>> Lamport's algorithm (it's easy to avoid barriers).
>> - Relaxed. Loads and stores are not ordered, users have to put in memory
>> barriers and hope they did it right.
>>
>> So, a highly relaxed memory model is the ONLY model which needs barriers.
>
> But this isn't true. Real processors aren't anywhere near as wildly
> chaotic as this.
>
> The common form of relaxed memory we see today is causally consistent
> and multi-copy atomic (and cache coherent). So, all other threads see
> stores to a single location in the same order, and you don't get the
> extraordinary going-backwards-in-time behaviour of DEC Alpha.
>
>> A relaxed ordering SYSTEM says rather than spending a few thousand
>> gates getting ordering right by hardware in the CPU, instead we're
>> going to require software to put in some very difficult to
>> understand barriers.
>
> I don't think that's really true. The reorderings we see in currently-
> produced hardware are, more or less, a subset of the same reorderings
> that C compilers perform. Therefore, if you see a confusing hardware
> reordering in a multi-threaded C program it may well be (probably is!)
> a bug (according to the C standard) *even on a TSO machine*. The only
> common counter-example to this is for volatile accesses.

Be sure to keep C++ std::atomic in mind... Also, std::memory_order_*

>
>> A very simple thought exercise shows even if Sequential Consistency
>> and/or TSO were slower (and I maintain they are not), but even if
>> you believe that, a Relaxed Ordering system WILL be slower than TSO
>> or Sequential for workloads which often use barriers (instructions
>> tagged with acquire/release are barriers). In a Relaxed ordering
>> system, the barriers will not be as efficient as the automatic
>> barriers of TSO/SC (otherwise, why not just do that?),
>
> Whyever not? They do the same thing.
>
> Andrew.

On 11/13/2023 11:29 AM, MitchAlsup wrote:
> EricP wrote:
>
>> Kent Dickey wrote:
>>> In article <uirqj3$9q9q$1@dont-email.me>,
>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>> On 11/12/2023 4:20 PM, MitchAlsup wrote:
>>>>> Chris M. Thomasson wrote:
>>>>>
>>>>>> On 11/12/2023 2:33 PM, Kent Dickey wrote:
>>>>>>> In article <uiri0a$85mp$2@dont-email.me>,
>>>>>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>>>>>
>>>>>>>> A highly relaxed memory model can be beneficial for certain
>>>>>>>> workloads.
>>>>>>> I know a lot of people believe that statement to be true.  In
>>>>>>> general, it
>>>>>>> is assumed to be true without proof.
>>>>>>>
>>>>>>> I believe that statement to be false.  Can you describe some of
>>>>>>> these
>>>>>>> workloads?
>>>>>> Also, think about converting any sound lock-free algorithm's
>>>>>> finely tuned memory barriers to _all_ sequential consistency...
>>>>>> That would ruin performance right off the bat... Think about it.
>>>>> <
>>>>> Assuming you are willing to accept the wrong answer fast, rather
>>>>> than the right answer later. There are very few algorithms with
>>>>> this property.
>>>> That does not make any sense to me. Think of a basic mutex. It
>>>> basically requires an acquire membar for the lock and a release
>>>> membar for the unlock. On SPARC that would be:
>>>>
>>>> acquire = MEMBAR #LoadStore | #LoadLoad
>>>>
>>>> release = MEMBAR #LoadStore | #StoreStore
>>>>
>>>> Okay, fine. However, if I made them sequentially consistent, it
>>>> would require a damn #StoreLoad barrier for both acquire and
>>>> release. This is not good and should be avoided when possible.
>>>>
>>>> Also, RCU prides itself with not having to use any memory barriers
>>>> for its read side. If RCU was forced to use a seq cst, basically
>>>> LOCKED RMW or MFENCE on Intel, it would completely ruin its
>>>> performance.
[...]
> < I suspect SUN lost significant performance by always running TSO and
> it still required barrier instructions.
[...]

Intel still requires an explicit membar for hazard pointers as-is. Sparc
in TSO mode still requires a membar for this. Spard needs a #StoreLoad
wrt the store followed by a load to another location relationship to
hold. Intel needs a LOCK'ed atomic or MFENCE to handle this.

On 11/12/2023 9:54 PM, Kent Dickey wrote:
> In article <82b3b3b710652e607dac6cec2064c90b@news.novabbs.com>,
> MitchAlsup <mitchalsup@aol.com> wrote:
>> Kent Dickey wrote:
>>
>>> In article <uiri0a$85mp$2@dont-email.me>,
>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>
>>>> A highly relaxed memory model can be beneficial for certain workloads.
>>
>>> I know a lot of people believe that statement to be true. In general, it
>>> is assumed to be true without proof.
>> <
>> In its most general case, relaxed order only provides a performance advantage
>> when the code is single threaded.
>
> I believe a Relaxed Memory model provides a small performance improvement
> ONLY to simple in-order CPUs in an MP system (if you're a single CPU,
> there's nothing to order).
>
> Relazed Memory ordering provides approximately zero performance improvement
> to an OoO CPU, and in fact, might actually lower performance (depends on
> how barriers are done--if done poorly, it could be a big negative).
>
> Yes, the system designers of the world have said: let's slow down our
> fastest most expensive most profitable CPUs, so we can speed up our cheapest
> lowest profit CPUs a few percent, and push a ton of work onto software
> developers.
>
> It's crazy.
>
>>> I believe that statement to be false. Can you describe some of these
>>> workloads?
>> <
>> Relaxed memory order fails spectacularly when multiple threads are accessing
>> data.
>
> Probably need to clarify with "accessing modified data".
>
> Kent

Huh? So, C++ is crazy for allowing for std::memory_order_relaxed to even
exist? I must be misunderstanding you point here. Sorry if I am. ;^o

Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
> On 11/13/2023 3:49 AM, aph@littlepinkcloud.invalid wrote:
>>
>> I don't think that's really true. The reorderings we see in currently-
>> produced hardware are, more or less, a subset of the same reorderings
>> that C compilers perform. Therefore, if you see a confusing hardware
>> reordering in a multi-threaded C program it may well be (probably is!)
>> a bug (according to the C standard) *even on a TSO machine*. The only
>> common counter-example to this is for volatile accesses.
>
> Be sure to keep C++ std::atomic in mind... Also, std::memory_order_*

Maybe I wasn't clear enough. If you use std::atomic and
std::memory_order_* in such a way that there are no data races, your
concurrent program will be fine on both TSO and relaxed memory
ordering. If you try to fix data races with volatile instead of
std::atomic and std::memory_order_*, that'll mostly fix things on a
TSO machine, but not on a machine with relaxed memory ordering.

(For pedants: Mostly, but not completely, even on TSO, e.g. Dekker's
Algorithm, which needs something stronger.)

Because of this, the assertion that programming a non-TSO machine is
"harder" doesn't IMO stand up, at least in C programs, because the
same data-race bugs can manifest themselves as either compiler
optimizations or hardware reorderings. And a compiler can, at least in
theory, can do things that are far weirder than any memory system
does.

Andrew.

On 11/14/2023 2:25 AM, aph@littlepinkcloud.invalid wrote:
> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>> On 11/13/2023 3:49 AM, aph@littlepinkcloud.invalid wrote:
>>>
>>> I don't think that's really true. The reorderings we see in currently-
>>> produced hardware are, more or less, a subset of the same reorderings
>>> that C compilers perform. Therefore, if you see a confusing hardware
>>> reordering in a multi-threaded C program it may well be (probably is!)
>>> a bug (according to the C standard) *even on a TSO machine*. The only
>>> common counter-example to this is for volatile accesses.
>>
>> Be sure to keep C++ std::atomic in mind... Also, std::memory_order_*
>
> Maybe I wasn't clear enough.

Well, I think I was being a bit too dense here and missed your main
point. Sorry.

> If you use std::atomic and
> std::memory_order_* in such a way that there are no data races, your
> concurrent program will be fine on both TSO and relaxed memory
> ordering.

Agreed.

> If you try to fix data races with volatile instead of
> std::atomic and std::memory_order_*, that'll mostly fix things on a
> TSO machine, but not on a machine with relaxed memory ordering.
>
> (For pedants: Mostly, but not completely, even on TSO, e.g. Dekker's
> Algorithm, which needs something stronger.)

Indeed, it does.

> Because of this, the assertion that programming a non-TSO machine is
> "harder" doesn't IMO stand up, at least in C programs, because the
> same data-race bugs can manifest themselves as either compiler
> optimizations or hardware reorderings. And a compiler can, at least in
> theory, can do things that are far weirder than any memory system
> does.

On 2023-11-13, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
> On 11/13/2023 11:29 AM, MitchAlsup wrote:
>> EricP wrote:
>>
>>> Kent Dickey wrote:
>>>> In article <uirqj3$9q9q$1@dont-email.me>,
>>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>>> On 11/12/2023 4:20 PM, MitchAlsup wrote:
>>>>>> Chris M. Thomasson wrote:
>>>>>>
>>>>>>> On 11/12/2023 2:33 PM, Kent Dickey wrote:
>>>>>>>> In article <uiri0a$85mp$2@dont-email.me>,
>>>>>>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>>>>>>
>>>>>>>>> A highly relaxed memory model can be beneficial for certain
>>>>>>>>> workloads.
>>>>>>>> I know a lot of people believe that statement to be true.  In
>>>>>>>> general, it
>>>>>>>> is assumed to be true without proof.
>>>>>>>>
>>>>>>>> I believe that statement to be false.  Can you describe some of
>>>>>>>> these
>>>>>>>> workloads?
>>>>>>> Also, think about converting any sound lock-free algorithm's
>>>>>>> finely tuned memory barriers to _all_ sequential consistency...
>>>>>>> That would ruin performance right off the bat... Think about it.
>>>>>> <
>>>>>> Assuming you are willing to accept the wrong answer fast, rather
>>>>>> than the right answer later. There are very few algorithms with
>>>>>> this property.
>>>>> That does not make any sense to me. Think of a basic mutex. It
>>>>> basically requires an acquire membar for the lock and a release
>>>>> membar for the unlock. On SPARC that would be:
>>>>>
>>>>> acquire = MEMBAR #LoadStore | #LoadLoad
>>>>>
>>>>> release = MEMBAR #LoadStore | #StoreStore
>>>>>
>>>>> Okay, fine. However, if I made them sequentially consistent, it
>>>>> would require a damn #StoreLoad barrier for both acquire and
>>>>> release. This is not good and should be avoided when possible.
>>>>>
>>>>> Also, RCU prides itself with not having to use any memory barriers
>>>>> for its read side. If RCU was forced to use a seq cst, basically
>>>>> LOCKED RMW or MFENCE on Intel, it would completely ruin its
>>>>> performance.
> [...]
>> < I suspect SUN lost significant performance by always running TSO and
>> it still required barrier instructions.
> [...]
>
> Intel still requires an explicit membar for hazard pointers as-is. Sparc
> in TSO mode still requires a membar for this. Spard needs a #StoreLoad
> wrt the store followed by a load to another location relationship to
> hold. Intel needs a LOCK'ed atomic or MFENCE to handle this.
I think that Apple M1 requires, too. I has problems wihout membar.

--

7-77-777, Evil Sinner!
https://www.linkedin.com/in/branimir-maksimovic-6762bbaa/

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>I have written a microbenchmark for measuring how memory dependencies
>affect the performance of various microarchitectures. You can find it
>along with a description and results on
><http://www.complang.tuwien.ac.at/anton/memdep/>.

I have now added parameter combinations for detecting something that I
currently call memory renaming: If the microarchitecture can overlap
independent accesses to the same memory location (analogous to
register renaming).

Does anybody know if there is a commonly-used term for this feature?
I would also be interested in a commonly-used term for bypassing the
store buffer in store-to-load forwarding (as we see in Zen3 and Tiger
Lake).

Concerning memory renaming, it turns out that Intel added it in
Nehalem, and AMD added it between K10 and Excavator (probably in the
Bulldozer). ARM has not implemented this in any microarchitecture I
have measured (up to Cortex-A76), and Apple has it in Firestorm (M1
P-core), but not in Icestorm (M1 E-Core).

One interesting benefit of memory renaming is that when you are bad at
register allocation, and keep local variables in memory (or virtual
machine registers, or virtual machine stack items), independent
computations that use the same local variable still can execute in
parallel. Say, stuff like

a = b[1]; c = a+1;
a = b[2]; d = a-1;

The hardware can execute them in parallel, even if a is located in
memory.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Anton Ertl wrote:

> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>I have written a microbenchmark for measuring how memory dependencies
>>affect the performance of various microarchitectures. You can find it
>>along with a description and results on
>><http://www.complang.tuwien.ac.at/anton/memdep/>.

> I have now added parameter combinations for detecting something that I
> currently call memory renaming: If the microarchitecture can overlap
> independent accesses to the same memory location (analogous to
> register renaming).

> Does anybody know if there is a commonly-used term for this feature?
<
I use the term Conditional Cache, I have heard others call it a Memory
Reorder Buffer.
<
> I would also be interested in a commonly-used term for bypassing the
> store buffer in store-to-load forwarding (as we see in Zen3 and Tiger
> Lake).
<
Store-to-Load-Forwarding is the only term I know here.
<
> Concerning memory renaming, it turns out that Intel added it in
> Nehalem, and AMD added it between K10 and Excavator (probably in the
> Bulldozer). ARM has not implemented this in any microarchitecture I
> have measured (up to Cortex-A76), and Apple has it in Firestorm (M1
> P-core), but not in Icestorm (M1 E-Core).

> One interesting benefit of memory renaming is that when you are bad at
> register allocation,
<
Or bad at alias analysis...
<
< and keep local variables in memory (or virtual
> machine registers, or virtual machine stack items), independent
> computations that use the same local variable still can execute in
> parallel. Say, stuff like

> a = b[1]; c = a+1;
> a = b[2]; d = a-1;

> The hardware can execute them in parallel, even if a is located in
> memory.
<
And why not, they are independent containers.

> - anton

In article <u5mcnayk1ZSP1s74nZ2dnZfqnPqdnZ2d@supernews.com>,
<aph@littlepinkcloud.invalid> wrote:
>Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>> On 11/13/2023 3:49 AM, aph@littlepinkcloud.invalid wrote:
>>>
>>> I don't think that's really true. The reorderings we see in currently-
>>> produced hardware are, more or less, a subset of the same reorderings
>>> that C compilers perform. Therefore, if you see a confusing hardware
>>> reordering in a multi-threaded C program it may well be (probably is!)
>>> a bug (according to the C standard) *even on a TSO machine*. The only
>>> common counter-example to this is for volatile accesses.
>>
>> Be sure to keep C++ std::atomic in mind... Also, std::memory_order_*
>
>Maybe I wasn't clear enough. If you use std::atomic and
>std::memory_order_* in such a way that there are no data races, your
>concurrent program will be fine on both TSO and relaxed memory
>ordering. If you try to fix data races with volatile instead of
>std::atomic and std::memory_order_*, that'll mostly fix things on a
>TSO machine, but not on a machine with relaxed memory ordering.

What you are saying is:

As long as you fully analyze your program, ensure all multithreaded accesses
are only through atomic variables, and you label every access to an
atomic variable properly (although my point is: exactly what should that
be??), then there is no problem.

If you assume you've already solved the problem, then you find the
problem is solved! Magic!

What I'm arguing is: the CPU should behave as if memory_order_seq_cst
is set on all accesses with no special trickery. This acquire/release
nonsense is all weakly ordered brain damage. The problem is on weakly
ordered CPUs, performance definitely does matter in terms of getting this
stuff right, but that's their problem. Being weakly ordered makes them
slower when they have to execute barriers for correctness, but it's the
barriers themselves that are the slow down, not ordering the requests
properly.

If the CPU takes ownership of ordering, then the only rule is: you just
have to use atomic properly (even then, you can often get away with
volatile for most producer/consumer cases), and these subtypes for all
accesses don't matter for correctness or performance.

It also would be nice if multithreaded programs could be written in C99,
or pre-C++11. It's kinda surprising we've only been able to write threaded
programs for about 10 years.

Kent

On 11/15/2023 12:32 PM, Kent Dickey wrote:
> In article <u5mcnayk1ZSP1s74nZ2dnZfqnPqdnZ2d@supernews.com>,
> <aph@littlepinkcloud.invalid> wrote:
>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>> On 11/13/2023 3:49 AM, aph@littlepinkcloud.invalid wrote:
>>>>
>>>> I don't think that's really true. The reorderings we see in currently-
>>>> produced hardware are, more or less, a subset of the same reorderings
>>>> that C compilers perform. Therefore, if you see a confusing hardware
>>>> reordering in a multi-threaded C program it may well be (probably is!)
>>>> a bug (according to the C standard) *even on a TSO machine*. The only
>>>> common counter-example to this is for volatile accesses.
>>>
>>> Be sure to keep C++ std::atomic in mind... Also, std::memory_order_*
>>
>> Maybe I wasn't clear enough. If you use std::atomic and
>> std::memory_order_* in such a way that there are no data races, your
>> concurrent program will be fine on both TSO and relaxed memory
>> ordering. If you try to fix data races with volatile instead of
>> std::atomic and std::memory_order_*, that'll mostly fix things on a
>> TSO machine, but not on a machine with relaxed memory ordering.
>
> What you are saying is:
>
> As long as you fully analyze your program, ensure all multithreaded accesses
> are only through atomic variables, and you label every access to an
> atomic variable properly (although my point is: exactly what should that
> be??), then there is no problem.
>
> If you assume you've already solved the problem, then you find the
> problem is solved! Magic!
>
> What I'm arguing is: the CPU should behave as if memory_order_seq_cst
> is set on all accesses with no special trickery. This acquire/release
> nonsense is all weakly ordered brain damage.

Huh? Just because you have a problem with memory ordering, does not mean
that all std::memory_order_* should default to seq_cst! You are being
radically obtuse here. Is as if you have no idea about what you are
writing about.

[...]

Kent Dickey wrote:

> In article <u5mcnayk1ZSP1s74nZ2dnZfqnPqdnZ2d@supernews.com>,
> <aph@littlepinkcloud.invalid> wrote:
>>Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>> On 11/13/2023 3:49 AM, aph@littlepinkcloud.invalid wrote:
>>>>
>>>> I don't think that's really true. The reorderings we see in currently-
>>>> produced hardware are, more or less, a subset of the same reorderings
>>>> that C compilers perform. Therefore, if you see a confusing hardware
>>>> reordering in a multi-threaded C program it may well be (probably is!)
>>>> a bug (according to the C standard) *even on a TSO machine*. The only
>>>> common counter-example to this is for volatile accesses.
>>>
>>> Be sure to keep C++ std::atomic in mind... Also, std::memory_order_*
>>
>>Maybe I wasn't clear enough. If you use std::atomic and
>>std::memory_order_* in such a way that there are no data races, your
>>concurrent program will be fine on both TSO and relaxed memory
>>ordering. If you try to fix data races with volatile instead of
>>std::atomic and std::memory_order_*, that'll mostly fix things on a
>>TSO machine, but not on a machine with relaxed memory ordering.

> What you are saying is:

> As long as you fully analyze your program, ensure all multithreaded accesses
> are only through atomic variables, and you label every access to an
> atomic variable properly (although my point is: exactly what should that
> be??), then there is no problem.

> If you assume you've already solved the problem, then you find the
> problem is solved! Magic!

> What I'm arguing is: the CPU should behave as if memory_order_seq_cst
> is set on all accesses with no special trickery.
<
Should appear as if.....not behave as if.
<
> This acquire/release
> nonsense is all weakly ordered brain damage.
<
Agreed ...
<
> The problem is on weakly
> ordered CPUs, performance definitely does matter in terms of getting this
> stuff right, but that's their problem.
<
Not necessarily !! If you have a weakly ordered machine and start doing
something ATOMIC, the processor can switch to sequential consistency upon
the detection of the ATOMIC event starting (LL for example) stay SC until
the ATOMIC even is done, then revert back to weakly ordered as it pleases.
The single threaded code gets is performance while the multithreaded code
gets is SC (as Lamport demonstrated was necessary).
<
> Being weakly ordered makes them
> slower when they have to execute barriers for correctness, but it's the
> barriers themselves that are the slow down, not ordering the requests
> properly.
<
But You see, doing it my way gets rid of the MemBar instructions but not
their necessary effects. In addition, in my model, every access within
an ATOMIC event is SC not just a MemBar at the front and end.
<
> If the CPU takes ownership of ordering, then the only rule is: you just
> have to use atomic properly (even then, you can often get away with
> volatile for most producer/consumer cases), and these subtypes for all
> accesses don't matter for correctness or performance.
<
But a CPU is not in a position to determine Memory Order, the (multiplicity
of) memory controllers do, the CPUs just have to figure out how to put up with
the imposed order based on the kind of things the CPU is doing at that instant.
<
> It also would be nice if multithreaded programs could be written in C99,
> or pre-C++11. It's kinda surprising we've only been able to write threaded
> programs for about 10 years.
<
I wrote multithreaded programs on an 8085.....
<
> Kent

On 11/15/2023 12:56 PM, MitchAlsup wrote:
> Kent Dickey wrote:
>
>> In article <u5mcnayk1ZSP1s74nZ2dnZfqnPqdnZ2d@supernews.com>,
>>  <aph@littlepinkcloud.invalid> wrote:
>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>> On 11/13/2023 3:49 AM, aph@littlepinkcloud.invalid wrote:
>>>>>
>>>>> I don't think that's really true. The reorderings we see in currently-
>>>>> produced hardware are, more or less, a subset of the same reorderings
>>>>> that C compilers perform. Therefore, if you see a confusing hardware
>>>>> reordering in a multi-threaded C program it may well be (probably is!)
>>>>> a bug (according to the C standard) *even on a TSO machine*. The only
>>>>> common counter-example to this is for volatile accesses.
>>>>
>>>> Be sure to keep C++ std::atomic in mind... Also, std::memory_order_*
>>>
>>> Maybe I wasn't clear enough. If you use std::atomic and
>>> std::memory_order_* in such a way that there are no data races, your
>>> concurrent program will be fine on both TSO and relaxed memory
>>> ordering. If you try to fix data races with volatile instead of
>>> std::atomic and std::memory_order_*, that'll mostly fix things on a
>>> TSO machine, but not on a machine with relaxed memory ordering.
>
>> What you are saying is:
>
>> As long as you fully analyze your program, ensure all multithreaded
>> accesses
>> are only through atomic variables, and you label every access to an
>> atomic variable properly (although my point is: exactly what should that
>> be??), then there is no problem.
>
>> If you assume you've already solved the problem, then you find the
>> problem is solved!  Magic!
>
>> What I'm arguing is: the CPU should behave as if memory_order_seq_cst
>> is set on all accesses with no special trickery.
> <
> Should appear as if.....not behave as if.
> <
>>                                                  This acquire/release
>> nonsense is all weakly ordered brain damage.
> <
> Agreed ...
> <

Why do you "seem" to think its brain damage? Knowing how to use them
properly is a good thing.

>>                                               The problem is on weakly
>> ordered CPUs, performance definitely does matter in terms of getting this
>> stuff right, but that's their problem.
> <
> Not necessarily !! If you have a weakly ordered machine and start doing
> something ATOMIC, the processor can switch to sequential consistency upon
> the detection of the ATOMIC event starting (LL for example) stay SC until
> the ATOMIC even is done, then revert back to weakly ordered as it pleases.
> The single threaded code gets is performance while the multithreaded code
> gets is SC (as Lamport demonstrated was necessary).
> <
>>                                         Being weakly ordered makes them
>> slower when they have to execute barriers for correctness, but it's the
>> barriers themselves that are the slow down, not ordering the requests
>> properly.
> <
> But You see, doing it my way gets rid of the MemBar instructions but not
> their necessary effects. In addition, in my model, every access within
> an ATOMIC event is SC not just a MemBar at the front and end.
> <
>> If the CPU takes ownership of ordering, then the only rule is: you just
>> have to use atomic properly (even then, you can often get away with
>> volatile for most producer/consumer cases), and these subtypes for all
>> accesses don't matter for correctness or performance.
> <
> But a CPU is not in a position to determine Memory Order, the
> (multiplicity of) memory controllers do, the CPUs just have to figure
> out how to put up with
> the imposed order based on the kind of things the CPU is doing at that
> instant.
> <
>> It also would be nice if multithreaded programs could be written in C99,
>> or pre-C++11.  It's kinda surprising we've only been able to write
>> threaded
>> programs for about 10 years.
> <
> I wrote multithreaded programs on an 8085.....
> <
>> Kent

In article <uiu4t5$t4c2$2@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>On 11/12/2023 9:54 PM, Kent Dickey wrote:
>> In article <82b3b3b710652e607dac6cec2064c90b@news.novabbs.com>,
>> MitchAlsup <mitchalsup@aol.com> wrote:
>>> Kent Dickey wrote:
>>>
>>>> In article <uiri0a$85mp$2@dont-email.me>,
>>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>
>>>>> A highly relaxed memory model can be beneficial for certain workloads.
>>>
>>>> I know a lot of people believe that statement to be true. In general, it
>>>> is assumed to be true without proof.
>>> <
>>> In its most general case, relaxed order only provides a performance advantage
>>> when the code is single threaded.
>>
>> I believe a Relaxed Memory model provides a small performance improvement
>> ONLY to simple in-order CPUs in an MP system (if you're a single CPU,
>> there's nothing to order).
>>
>> Relazed Memory ordering provides approximately zero performance improvement
>> to an OoO CPU, and in fact, might actually lower performance (depends on
>> how barriers are done--if done poorly, it could be a big negative).
>>
>> Yes, the system designers of the world have said: let's slow down our
>> fastest most expensive most profitable CPUs, so we can speed up our cheapest
>> lowest profit CPUs a few percent, and push a ton of work onto software
>> developers.
>>
>> It's crazy.
>>
>>>> I believe that statement to be false. Can you describe some of these
>>>> workloads?
>>> <
>>> Relaxed memory order fails spectacularly when multiple threads are accessing
>>> data.
>>
>> Probably need to clarify with "accessing modified data".
>>
>> Kent
>
>Huh? So, C++ is crazy for allowing for std::memory_order_relaxed to even
>exist? I must be misunderstanding you point here. Sorry if I am. ;^o

You have internalized weakly ordered memory, and you're having trouble
seeing beyond it.

CPUs with weakly ordered memory are the ones that need all those flags.
Yes, you need the flags if you want to use those CPUs. I'm pointing out:
we could all just require better memory ordering and get rid of all this
cruft. Give the flag, don't give the flag, the program is still correct
and works properly.

It's like FP denorms--it's generally been decided the hardware cost
to implement it is small, so hardware needs to support it at full speed.
No need to write code in a careful way to avoid denorms, to use funky CPU-
specific calls to turn on flush-to-0, etc., it just works, we move on to
other topics. But we still have flush-to-0 calls available--but you don't
need to bother to use them. In my opinion, memory ordering is much more
complex for programmers to handle. I maintain it's actually so
complex most people cannot get it right in software for non-trivial
interactions. I've found many hardware designers have a very hard time
reasoning about this as well when I report bugs (since the rules are so
complex and poorly described). There are over 100 pages describing memory
ordering in the Arm Architectureal Reference Manual, and it is very
complex (Dependency through registers and memory; Basic Dependency;
Address Dependency; Data Dependency; Control Dependency; Pick Basic
dependency; Pick Address Dependency; Pick Data Dependency; Pick
Control Dependency, Pick Dependency...and this is just from the definition
of terms). It's all very abstract and difficult to follow. I'll be
honest: I do not understand all of these rules, and I don't care to.
I know how to implement a CPU, so I know what they've done, and that's
much simpler to understand. But writing a threaded application is much
more complex than it should be for software.

The cost to do TSO is some out-of-order tracking structures need to get
a little bigger, and some instructions have to stay in queues longer
(which is why they may need to get bigger), and allow re-issuing loads
which now have stale data. The difference between TSO and Sequential
Consistency is to just disallow loads seeing stores queued before they
write to the data cache (well, you can speculatively let loads happen,
but you need to be able to walk it back, which is not difficult). This
is why I say the performance cost is low--normal code missing caches and
not being pestered by other CPUs can run at the same speed. But when
other CPUs begin pestering us, the interference can all be worked out as
efficiently as possible using hardware, and barriers just do not
compete.

Kent

On 11/15/2023 1:09 PM, Kent Dickey wrote:
> In article <uiu4t5$t4c2$2@dont-email.me>,
> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>> On 11/12/2023 9:54 PM, Kent Dickey wrote:
>>> In article <82b3b3b710652e607dac6cec2064c90b@news.novabbs.com>,
>>> MitchAlsup <mitchalsup@aol.com> wrote:
>>>> Kent Dickey wrote:
>>>>
>>>>> In article <uiri0a$85mp$2@dont-email.me>,
>>>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>>>
>>>>>> A highly relaxed memory model can be beneficial for certain workloads.
>>>>
>>>>> I know a lot of people believe that statement to be true. In general, it
>>>>> is assumed to be true without proof.
>>>> <
>>>> In its most general case, relaxed order only provides a performance advantage
>>>> when the code is single threaded.
>>>
>>> I believe a Relaxed Memory model provides a small performance improvement
>>> ONLY to simple in-order CPUs in an MP system (if you're a single CPU,
>>> there's nothing to order).
>>>
>>> Relazed Memory ordering provides approximately zero performance improvement
>>> to an OoO CPU, and in fact, might actually lower performance (depends on
>>> how barriers are done--if done poorly, it could be a big negative).
>>>
>>> Yes, the system designers of the world have said: let's slow down our
>>> fastest most expensive most profitable CPUs, so we can speed up our cheapest
>>> lowest profit CPUs a few percent, and push a ton of work onto software
>>> developers.
>>>
>>> It's crazy.
>>>
>>>>> I believe that statement to be false. Can you describe some of these
>>>>> workloads?
>>>> <
>>>> Relaxed memory order fails spectacularly when multiple threads are accessing
>>>> data.
>>>
>>> Probably need to clarify with "accessing modified data".
>>>
>>> Kent
>>
>> Huh? So, C++ is crazy for allowing for std::memory_order_relaxed to even
>> exist? I must be misunderstanding you point here. Sorry if I am. ;^o
>
> You have internalized weakly ordered memory, and you're having trouble
> seeing beyond it.

Really? Don't project yourself on me. Altering all of the memory
barriers of a finely tuned lock-free algorithm to seq_cst is VERY bad.

>
> CPUs with weakly ordered memory are the ones that need all those flags.
> Yes, you need the flags if you want to use those CPUs. I'm pointing out:
> we could all just require better memory ordering and get rid of all this
> cruft. Give the flag, don't give the flag, the program is still correct
> and works properly.

Huh? Just cruft? wow. Just because it seems hard for you does not mean
we should eliminate it. Believe it or not there are people out there
that know how to use memory barriers. I suppose you would use seq_cst to
load each node of a lock-free stack iteration in a RCU read-side region.
This is terrible! Realy bad, bad, BAD! Afaicvt, it kind a, sort a, seems
like you do not have all that much experience with them. Humm...

>
> It's like FP denorms--it's generally been decided the hardware cost
> to implement it is small, so hardware needs to support it at full speed.
> No need to write code in a careful way to avoid denorms, to use funky CPU-
> specific calls to turn on flush-to-0, etc., it just works, we move on to
> other topics. But we still have flush-to-0 calls available--but you don't
> need to bother to use them. In my opinion, memory ordering is much more
> complex for programmers to handle. I maintain it's actually so
> complex most people cannot get it right in software for non-trivial
> interactions. I've found many hardware designers have a very hard time
> reasoning about this as well when I report bugs (since the rules are so
> complex and poorly described). There are over 100 pages describing memory
> ordering in the Arm Architectureal Reference Manual, and it is very
> complex (Dependency through registers and memory; Basic Dependency;
> Address Dependency; Data Dependency; Control Dependency; Pick Basic
> dependency; Pick Address Dependency; Pick Data Dependency; Pick
> Control Dependency, Pick Dependency...and this is just from the definition
> of terms). It's all very abstract and difficult to follow. I'll be
> honest: I do not understand all of these rules, and I don't care to.
> I know how to implement a CPU, so I know what they've done, and that's
> much simpler to understand. But writing a threaded application is much
> more complex than it should be for software.
>
> The cost to do TSO is some out-of-order tracking structures need to get
> a little bigger, and some instructions have to stay in queues longer
> (which is why they may need to get bigger), and allow re-issuing loads
> which now have stale data. The difference between TSO and Sequential
> Consistency is to just disallow loads seeing stores queued before they
> write to the data cache (well, you can speculatively let loads happen,
> but you need to be able to walk it back, which is not difficult). This
> is why I say the performance cost is low--normal code missing caches and
> not being pestered by other CPUs can run at the same speed. But when
> other CPUs begin pestering us, the interference can all be worked out as
> efficiently as possible using hardware, and barriers just do not
> compete.

Having access to fine grain memory barriers is a very good thing. Of
course we can use C++ right now and make everything seq_cst, but that is
moronic. Why would you want to use seq_cst everywhere when you do not
have to? There are rather massive performance implications.

Are you thinking about a magic arch that we cannot use right now?