c++11 std::atomic and memory_order_relaxed

[syzygy]

I am talking about speculative stores. In your dictionary they have apparently been defined away. I suppose speculative execution does not exist, either.

Speculative stores are stores. I don't see your point.

Make a choice. Speculative stores are stores that (in some implementations) are not seen by other threads. Or they are not stores.

Either way, the fact is that "speculative stores" are being discussed in hundreds of papers, so they do exist.

Depends on the implementation. In some implementations writes are invisible to other threads until the transaction is committed (lazy versioning). In other implementations writes are visible before the transaction is committed (eager versioning). In that case the threads seeing those writes will have to be aborted if the writing transaction does not get committed.

Indeed. If a speculation cannot be corroborated by non-speculative data it will have to aborted together with all its consequences. The papers do that. Your examples don't.

In the example we are dicussing, do you have difficulty with the idea that both threads commit in a synchronised manner, thereby corroborating each other?

This synchronisation clearly is a complicating factor compared to the schemes in the papers, but there is no inherent impossibility here.

Nope. If T1 writes to X and T2 reads from X, then T2 is dependent on T1 but not the other way around. No cyclic dependency. T2 can use the result, obviously, or it should not have seen it. T2 must be rolled back if T1 is.

Well, that is exactly what I said, not? T2 cannot commit unless T1 commits. It must be sure that T1 commits before the other thread can use it (i.e. T2 can commit). You cannot use the data as long as it is speculative, and might have to be rolled back.

No, you were talking about a "dependency cycle". There is no dependency cycle between T1 and T2.

T2 is using the data, albeit speculatively. There might be a T3 using T2's data.

Of course you can say that speculative execution is not doing anything, is not using anything, is not execution. You can define away speculative execution. But the fact is that, provided in the end things get committed, real work is being done by those speculative threads. I don't see the point in your word play.

[hgm]

Make a choice. Speculative stores are stores that (in some implementations) are not seen by other threads. Or they are not stores.

Define 'seen'. If you mean by 'seen': can be used as if they are for real, then no, speculative stores must not be seen. They can be seen for what they are: speculative data.

Either way, the fact is that "speculative stores" are being discussed in hundreds of papers, so they do exist.

Well, bombs exist, and they kill you too. The point is, when you treat results of speculative stores in a way that cannot be undone, or that you don't want to undo, things are broken. 'Broken' is not the same as 'non-existent'.

In the example we are dicussing, do you have difficulty with the idea that both threads commit in a synchronised manner, thereby corroborating each other?

Define 'difficulty'. It is not difficult at all to see that this is plain wrong. You let two items of speculative data 'corroborate' each other. Speculative data cannot corroborate anything.

No, you were talking about a "dependency cycle". There is no dependency cycle between T1 and T2.

Read again:

Also in the 'dependency-aware' scheme of the second link the data forwarded to the other CPU will only be used after it is certain (and thus not speculative) that the data will be committed. When there is a dependency cycle, it will abort.

In the example you give there was no dependency cycle. So it will become clear that it is not speculative, and then it will be committed. As I said...

T2 is using the data, albeit speculatively. There might be a T3 using T2's data.

'use' is not speculate, OK? Otherwise it just peeks at it, with no irreversible effects. That is indeed not what I meant by using. Peeking at something just to conclude that you cannot use it, and have to abort, is not 'using'.

Of course you can say that speculative execution is not doing anything, is not using anything, is not execution. You can define away speculative execution. But the fact is that, provided in the end things get committed, real work is being done by those speculative threads. I don't see the point in your word play.

Concise and unambiguously expressing yourself is not 'word play'.

The point is the same point as ever: unlike all these nice but completely irrelevant papers, your 42 example 'corroborates' speculative data by other speculative data. That is broken.

[syzygy]

Make a choice. Speculative stores are stores that (in some implementations) are not seen by other threads. Or they are not stores.

Define 'seen'. If you mean by 'seen': can be used as if they are for real, then no, speculative stores must not be seen. They can be seen for what they are: speculative data.

You may define "seen" and you may make the choice.

Either way, the fact is that "speculative stores" are being discussed in hundreds of papers, so they do exist.

Well, bombs exist, and they kill you too. So they exist good.

A few comments ago they did not exist, remember? So we made some progress.

broken

Call it what you want. I have explained how the result from the opening post can arise without breaking any laws of nature. Obviously it is fair to call this result "broken" and therefore to call any compiler/hardware combination that allows it "broken". But laws of nature aren't violated (and neither is the C++11 standard, as it seems).

[hgm]

Call it what you want. I have explained how the result from the opening post can arise without breaking any laws of nature. Obviously it is fair to call this result "broken" and therefore to call any compiler/hardware combination that allows it "broken". But laws of nature aren't violated (and neither is the C++11 standard, as it seems).

It is broken, because it delivers results that are non-compliant with the standard. If that does not worry you, OK.

You are so fixated on arguing that your compiler/hardware scheme would work to produce the non-sensical 42 out of thin air, that you are completely blind to the fact that this scheme will produce outright invalid results in the vast majority of other cases.

[syzygy]

Call it what you want. I have explained how the result from the opening post can arise without breaking any laws of nature. Obviously it is fair to call this result "broken" and therefore to call any compiler/hardware combination that allows it "broken". But laws of nature aren't violated (and neither is the C++11 standard, as it seems).

It is broken, because it delivers results that are non-compliant with the standard. If that does not worry you, OK.

Can you give an example where it would deliver a result non-compliant with the standard? The example of the OP is compliant as far as I understand. At least, that was the assumption.

You are so fixated on arguing that your compiler/hardware scheme would work to produce the non-sensical 42 out of thin air, that you are completely blind to the fact that this scheme will produce outright invalid results in the vast majority of other cases.

I don't think so. I am assuming a compiler that knows what it is doing and is not e.g. speculatively executing divisions by zero leading to exceptions etc.

Obviously it possible to abuse speculative modes to get wrong results, like it is possible to use regular locks to deadlock a program.

Feel free to give an example.

Just to be clear "my" system commits both threads because:
- both conditions evaluate to true (yes, based on forwarded speculative values);
- assuming the speculative stores are valid, everything else is valid as well.

[hgm]

Code: Select all

int x=0, y=0;

Tread 1:
r1=x
if(r1==41) y=42;

Thread 2:
r2=y;
if(r2==42) { x=42, GlobalNuclearWar(); };

Now you speculatively store 42 in both threads. Which the other sees. So thread 2 sees its speculation confirmed, and happily goes on launching missiles. Thread 1 is not so lucky, however. It finds it speculated wrong. So it neatly restores y to 0. But since the missiles are already under way, that is not much help to thread 2...

[syzygy]

Code: Select all

int x=0, y=0;

Tread 1:
r1=x
if(r1==41) y=42;

Thread 2:
r2=y;
if(r2==42) { x=42, GlobalNuclearWar(); };

Now you speculatively store 42 in both threads. Which the other sees. So thread 2 sees its speculation confirmed, and happily goes on launching missiles. Thread 1 is not so lucky, however. It finds it speculated wrong. So it neatly restores y to 0. But since the missiles are already under way, that is not much help to thread 2...

As I wrote:

Just to be clear "my" system commits both threads because:
- both conditions evaluate to true (yes, based on forwarded speculative values);
- assuming the speculative stores are valid, everything else is valid as well.

If one of the two conditions evaluates to false, then both threads must be rolled back.

So thread 2 will not see its speculation confirmed.

But maybe you mean that once thread 2 is rolled back together with thread 1, it is already too late because thread 2 has speculatively launched some real missiles.

This same problem exists with regular transactional memory. You start a transaction, execute speculatively, and then find out that the transaction must be rolled back. If operations were performed that cannot be rolled back, you are in trouble.

To solve this:
- either allow speculation only if the compiler can see that things can be rolled back (and take finite time etc.); or
- abort the transaction once any kind of I/O takes place (or some timer runs out, if you wish to avoid deadlock).

http://researcher.ibm.com/researcher/fi ... PACT12.pdf

Causes of Transactional Execution Failures

(...)

• Jail mode violation (JMV) occur when the transaction performs irrevocable actions, that is, operations whose side-effects cannot be reversed, such as writes to device I/O address space. Irrevocable actions are detected by the kernel under a special mode called the jail mode, which will send a JMV interrupt to the owner thread of the event.

Other known problems are a lack of forward progress if transactions keep being restarted but never manage to get committed. The known solution is to limit the number of restarts (or not restart at all) and provide a fallback mode without speculation.

[hgm]

- either allow speculation only if the compiler can see that things can be rolled back (and take finite time etc.); or

Then it would just never do it. Because there is no way the compiler could see that this is the case. It cannot know what goes on in other threads, or even if there are other threads, because these could be compiled separately.

[syzygy]

- either allow speculation only if the compiler can see that things can be rolled back (and take finite time etc.); or

Then it would just never do it. Because there is no way the compiler could see that this is the case. It cannot know what goes on in other threads, or even if there are other threads, because these could be compiled separately.

The compiler does not need to look at other threads. It just needs to look at what is between the accolades in

Code: Select all

  if (r1 == 42) {   }

of the code it is compiling. If what is between the accolades is provably harmless, it can move it in front of the "if" where it can be executed speculatively. If this cannot be proven, the compiler can just leave the "if" statement as it is.

And the compiler does not need to check anything if the system ensures that transactions get aborted if they attempt to perform irrevocable actions.

What "my" system requires is that speculative dependencies between transactions are detected (such as reads of speculative values), and that cyclic dependencies between threads are permitted but must result in these threads being committed all together or not at all.

[bob]

The hardware logic for implementing this speculative execution is now being reused to implement support for transactional memory in Haswell processors. This allows the implementaiton of explicit speculative stores (i.e. by the programmer).

Can we stop the nonsense? "by the programmer" means it is NOT a hardware speculative store.

You have no clue.

http://cs.brown.edu/~mph/HerlihyM93/her ... tional.pdf
These guys are real computer scientists.

You are the one with no clue. Do you REALLY know anything about transactional memory? Do you know why it is an interesting topic? Do you know it is NOT about hardware speculation inside the CPU, but rather a tool for software to use to do transactional updates just like what we do in large database applications, without having to "lock" something every time you turn around. Transaction processing systems have had a "commit" architecture for years, all done in software. This is adding a few hardware tweaks to make it easier, NOT to make it "automatic".

Your speculation is nonsense. And until you understand what is actually being done, you will continue to spout nonsense. Speculative CPUs as you describe can not work, period. A broken compiler can certainly "excite" the 2x42 bug, but NOT speculative hardware.