ATBG: Reordering optimizations

Last time on the Coverity Development Testing Blog’s continuing series Ask The Bug Guys I discussed whether it was a good idea to remove a lock which protects an integer field. My conclusion was that it is not, because the lock prevents many potentially confusing optimizations. This week I follow up on that episode with an example where eliding locks on volatile reads and writes permits a surprising result.


As always, if you have questions about a bug you’ve found in a C, C++, C# or Java program that you think would make a good episode of ATBG, please send your question along with a small reproducer of the problem to TheBugGuys@Coverity.com. We cannot promise to answer every question or solve every problem, but we’ll take a selection of the best questions that we can answer and address them on the dev testing blog every couple of weeks.

Advertisements

25 thoughts on “ATBG: Reordering optimizations

  1. I seem to remember that the Java memory model wouldn’t allow this re-ordering. Is C#’s notion of “volatile” closer to that of C than that of Java then?

    • No the JMM behaves identically here.

      A volatile read has acquire semantics, and a volatile write has release semantics, basically this means that you can’t move anything *before* a volatile read and can’t move anything *past* a volatile write.

      But the converse is perfectly fine, what this means is that

      volatile write
      normal write
      normal read
      

      can be reordered to (assuming the single threaded behavior would be identical)

      normal write
      normal read
      volatile write
      

      while

      normal write
      normal read
      volatile read
      

      can be changed to

      volatile read
      normal write
      normal read
      

      If you want stronger guarantees you’ll have to put bidirectional memory barriers in place yourself – or use a lock

  2. You just made me curious enough to read through the JMM specification again (it’s been a long time) and try to prove my intuition. I believe the reordering would be invalid in Java by the following argument:

    Let us reduce the problematic program to four actions:
    w.q: Write to q
    r.r: Read from r
    w.r: Write to r
    r.q: Read from q

    All of these actions are synchronization actions according to 17.4.2, since they are volatile reads and writes. According to 17.4.4, the synchronization order of an execution is a total order over all synchronization actions that is consistent with the program order of each thread. That means w.q must come before r.r in the synchronization order, and w.r must come before r.q.

    However, that means all valid synchronization orders start with either w.r or w.q. And by 17.4.4,

    “A write to a volatile variable v synchronizes-with all subsequent reads of v by any thread (where “subsequent” is defined according to the synchronization order). ”

    Since the synchronizes-with relation implies the happens-before relation, and that in turn guarantees that the read will observe the write, we will always read either r or q as true.

    I think the effort needed already to reason about such a simple example proves Eric’s point though: Just use locks and be happy that you don’t have to think about these fine details. Locks already leave you with enough to worry about 🙂

    • Thanks for the analysis. FYI the C# specification says very clearly that an implementation is not required to make a consistent ordering of volatile accesses as observed from different threads. Interesting that Java requires a consistent total order.

      • Is C# specification stated this way because of x86 memory ordering?

        I don’t remember of a processor with memory ordering stronger than x86, so, for Java to be stronger the compiler probably needs to emit a lot of mfences.

        Is it possible to do the “mfence” in C# without locks?

          • Is the decision of when to introduce memory fences a function of the architecture, or of the processor? From what I can tell, the “volatile read” and “volatile write” behaviors are designed to guard the object identified by a reference stored in a field, rather than the field itself; the fact that a variable is volatile does not expedite stores to the variable itself (unlike in C), but rather ensures that it is delayed until after all previous stores (volatile or not) have completed. Likewise, the fact that a variable is volatile does not ensure that a read of that variable will yield current data, but to the contrary ensures that it won’t see a value written after a write fence unless all subsequent reads are sure to see all data written before it. I wouldn’t think a processor design would require that particular usage pattern when different situations require different kinds of memory barriers.

          • The initial intention of the volatile specifier in C was to facilitate communicating with memory-mapped devices – you certainly don’t want the compiler changing the meaning of your code by, for example, writing to the “execute command” port before it finishes writing the command to be executed.

            Using volatile in C as an attempt to provide safe multithreading is, and has always been, flawed, since it does absolutely nothing to prevent the processor from reordering your accesses (it’s just assumed that the processor won’t sabotage itself in cases where you’re actually writing to and reading from a memory-mapped device).

            C# seems to inherit this definition, and hence using volatile in any case other than controlling a memory-mapped device means you’re probably doing it wrong. Considering how often you’d typically use managed code to do low-level talking to memory-mapped devices, I’m of the opinion that that was a mistake. At least in Java it’s actually useful for something, even if that something is also usually a bad idea.

          • No, C# volatile is very different from C volatile, in that C# volatile was designed with multi-threaded scenarios in mind. The semantics of volatile in C# are that reads and writes are special events that must be observed to be ordered in certain ways with respect to other special events such as: entering a lock, leaving a lock, throwing an exception, starting a thread, and so on. See the C# specification for details.

            In C, you’re correct, volatile means nothing with respect to threads unless your particular compiler vendor makes it mean something.

        • x86 actually gives stronger guarantees than the JMM demands in many regards and is in general a horrible fit to the memory models of modern languages (JMM and C++’s memory_order_seq_cst at least), complete ordering overkill. You can very efficiently implement the JMM on processors with weaker ordering guarantees (so basically everything; the new ARMv8 ISA was apparently explicitly designed to work well with the JMM and similar models and is more similar to ia64 [itanium] than x86)

          If you’re interested in the JMM and how that works together with many different ISAs I suggest http://g.oswego.edu/dl/jmm/cookbook.html

    • “All of these actions are synchronization actions according to 17.4.2, since they are volatile reads and writes. According to 17.4.4, the synchronization order of an execution is a total order over all synchronization actions”

      No you’re mixing different things up here. We are only interested in synchronization actions and (important!) what they synchronize with! This is handled in 17.4.4:
      “A write to a volatile variable v (§8.3.1.4) synchronizes-with all subsequent reads *of v* (focus mine) by any thread”
      but as you see it does not synchronize with reads of other variables.

      17.4.5 goes on with happens-before relationships but that again only specifies:
      “A write to a volatile field (§8.3.1.4) happens-before every subsequent read of that field.”

      So my reading of the JMM says that there’s nothing stopping you from doing the reorderings here.

      • > but as you see it does not synchronize with reads of other variables.

        True, but I never used this statement with reads and writes of different variables, so the objection does not apply.

        > We are only interested in synchronization actions and (important!) what they synchronize with.

        We definitely are interested in that – it’s how we determine whether the writes are guaranteed to be visible to the reads. But the very rule you cited says that the synchronizes-with relation is influenced by the synchronization order:

        “A write to a volatile variable v (§8.3.1.4) synchronizes-with all subsequent reads of v by any thread (where “subsequent” is defined *according to the synchronization order*)” (emphasis mine this time)

        So the synchronization order determines whether a volatile write synchronizes-with a volatile read from the same variable. I reasoned about the synchronization order to show that for either r or q, the write must be ordered before the read, which (according to the rule above) induces the synchronizes-with relationship that we are interested in.

        If I am mixing things up, please tell me exactly where. I’m not an expert on the JMM so it’s very well possible that I misunderstood something, but if so I don’t see it at the moment.

        • True, but I never used this statement with reads and writes of different variables, so the objection does not apply.

          It looks to me like you were, here:


          That means w.q must come before r.r in the synchronization order, and w.r must come before r.q.

          My understanding of the Java memory model concurs with voo’s. But then I’ve never used volatile (in any language) because locks are so much easier to reason about, and therefore safer.

          • I see now where you are coming from. Of course you cannot apply the rule in question directly to my statement you quoted above, because it concerns orderings between reads and writes to *different* variables.

            But that’s not what I intended to say. I left out an important step in between because I thought it was too simple to spell out. Let’s do this in slow motion, starting from the statement you quoted:

            1. “That means w.q must come before r.r in the synchronization order, and w.r must come before r.q.”

            2. “However, that means all valid synchronization orders start with either w.r or w.q.” (They can’t start with r.r or r.q because that would conflict with 1)

            3. (missing from the original argument): If the syncrhonization order starts with w.r, then it orders w.r before r.r. If the order starts with w.q, then it orders w.q before r.q.

            4. (also missing): From 2 and 3 follows: The synchronization order either orders w.r before r.r, or it orders w.q before r.q.

            At this point it should be obvious how the rule in question applies.

        • Mhm on a second reading of the spec I think you are right about *volatile* reads/writes. I.e. you can’t reorder volatile reads and writes, *but* you can do so for normal read/writes.

          That means
          st/ld # can be reordered with respect to next volatile store if non- volatile
          volatile ld
          st/ld # can not be reordered
          respectively
          st/ld # can never be reordered with respect to next volatile store
          volatile st
          st/ld # can be reordered if non-volatile

          • I’m glad we agree now on the volatile reorderings :). As for re-ordering non-volatile relative to volatile, I somehow don’t want to dive back into the specs right now to see what exactly is legal and what isn’t, but I agree that non-volatile reads/writes can be re-ordered past volatile ones in some situations.

        • What prevents the write to q to be moved below the read to r? What in the standard prevents this:

          static void MethodOne()
          {
          q = true;
          if (!GetR())
          s = true;
          }

          from being optimized to this?:

          static void MethodOne()
          {
          if (!GetR())
          s = true;
          q = true;
          }

  3. I wish there were a nice easy way for a program to specify that a group of threads should be confined to running in such fashion as to have a stronger memory model (e.g. on some machines, being limited to running on the two “halves” of a hyper-threaded core that share an L1 cache). The cost of the full memory barriers associated with locks is going to increase as machines add more and more cores, and it would seem that in an increasing number of cases, running a task on one core with no memory barriers could take less CPU time than dividing it among multiple cores (especially if the other cores have something else useful they can be doing).

    Otherwise, how much would efficiency be hurt if generated code barred volatile reads from being sequenced before volatile writes on the same thread (if nothing else, by adding a barrier in any case where one might not already exist)? I would think the cost would be less than having to add locks which would otherwise not be be required.

    • I would think this would be a rare case, and that programmers should and do strive mightily to ensure that it is a rare case.

      Best practise is to cut down the amount of shared data between threads as much as possible, regardless of what synchronisation mechanism is used. Your desired feature would only see use when that wasn’t possible for some reason.

      In which case I personally would, yeah, just give up write it in one thread for simplicity’s sake.

      • The C# version of “volatile” is designed around the idea that code will write many values (which need not be volatile), then write one “data ready” indication (perhaps a reference to the values just written). Other code will read the “data ready” indication (using a volatile read) and, if data is ready, read the data. This approach requires one write barrier when setting an arbitrary number of items, and one read barrier when examining them.

        An alternative approach, and the one used by some other systems, would be to include a write barrier after storing each item, and before reading each item. Only the last item written and first item read would need the barrier, but including the barrier (especially when writing) only on those items where it was needed could be tricky. The C# volatile model tries to avoid the need to make such determination. Unfortunately, it is ineffective in scenarios which don’t fit the “bunch of non-volatile variables guarded by volatile readiness indicator”.

        I’d suggest that the right approach for a programmer who wants to think about memory barriers is to not use volatile variables at all, but instead specify memory barriers everyplace a cause-and-effect relationship is required. If a language wants to provide a way of easing that burden, it should have a “volatile” keyword which can ensure that all memory barriers necessary to maintain cause and effect relationships among volatile variables will be included. In addition to the existing barriers, it should include a read barrier before any volatile read which could possibly follow a volatile write (as opposed to another read), and a write barrier after any volatile write which could be followed by a volatile read without another intervening volatile write. Such an option could I think be perfectly compatible with C# (nothing ever promises that memory barriers won’t be inserted), and would greatly reduce the likelihood of Heisenbugs associated with `volatile` variables.

        • The C# version of “volatile” is designed around the idea that code will write many values (which need not be volatile), then write one “data ready” indication (perhaps a reference to the values just written). Other code will read the “data ready” indication (using a volatile read) and, if data is ready, read the data. This approach requires one write barrier when setting an arbitrary number of items, and one read barrier when examining them.

          But the non-volatile reads and writes can be re-ordered around the volatile one, so this surely is not safe. The reader thread is not guaranteed to see all the written values.

          If I wished to pass many values from one thread to another, I would put them all in an immutable object, and lock the reference to that object.

          • Actually they do IF
            – No writes (of regular variables) can be moved to after a volatile write
            – No reads (of regular variables) can be moved to before a volatile read

            –> This is the whole idea of a memory barrier. AFAIK the volatile will add half-barriers like that (see comments above. I didn’t read the C# spec for volatiles myself)

          • The .NET memory model has no such thing as volatile reads and volatile writes. Instead it has reads, writes, thread-global read barriers, thread-global write barriers, and thread-global read/write barriers. No distinction is made between reads and writes which should be affected by a memory barrier, and those which should not. A memory model in which “ordinary” reads and writes could not affected by some form of memory barrier would compel the use of volatile reads and writes even for immutable objects–thus defeating one of the reasons for using immutable objects in the first place; memory models differ, though, in the kinds of ordering that can be imposed upon normal reads and writes.

  4. Mfences, the servants of the Incoherent Ones.

    Really, such articles make me to recall Lovecraft’s stories. Because a man thinks of a world as regular and sensible, but then he looks through the borders of ordered space, and sees chaos and madness. And the unholy demon prince Arm-eleven-toth.

    And a comment above has this gem: “the right approach for a programmer who wants to think about memory barriers is…” Why would a C# programmer want to think about memory barriers? In fact, why would any high-level programming language user want to think about them? That stuff belongs to those who write optimizers, or automatic paralellization tools (in fact, our department has been working on such a project, http://ops.rsu.ru/en/about.shtml, for some time but thankfully, I am not a part of it), or something like this.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s