4 ms·
Is there a quick explanation why data races are UB in the C++ MM but not in the Java MM? Famously, Java’s String::hashCode implementation makes use of the Racy
by layer8 3y ago
Is there a quick explanation why data races are UB in the C++ MM but not in the Java MM? Famously, Java’s String::hashCode implementation makes use of the Racy Single-Check Idiom, so this is a core functionality on all supported platforms. What is the cost of Java guaranteeing defined behavior here? Or is it just that it would be costly on some non-mainstream platforms not supported by Java but supported by C++?
- bluGill 3y agoData races are generally UB because to make them defined you have to implement some form of locking on all use which is CPU expensive. With a good architecture you can make those data races impossible in the first place in most cases (not all, but most) and this is considered best practice in general: even when there is no data race, it is difficult to reason about all the possible states of your system when data is shared across threads. As such C++ has decided that data races as UB is the correct thing: in most cases the data race doesn't actually exist - the compiler just doesn't have enough information to prove it doesn't exist. When there is an exception you do have to manually add something to your code to force the synchronization, but hopefully that is rare, and when it happens you want to audit that code more anyway. I don't know how Java does data races, but often the language doesn't actually prevent data races the way you want it to. That is A=something; B=SomethingEles; can ensure A is updated before B, but will it ensure that either both A and B are both updated or neither are - which may be what you really need, and of course if you don't need that guarantee having it will slow down code that needs A until B is updated even though it doesn't care.
- layer8 3y agoIf you look up the Racy Single-Check Idiom, the point is to have defined behavior without any additional cost (aside from possible duplicate initialization). No locking, and not even volatile. At least on x86 it effectively comes for free.
- bluGill 3y agoOn X86 a lot of cases where C++ has UB the behavior could be considered fully defined since there is no optimization the compiler can do based on it being undefined and x86 guarantees memory order. On ARM you get no such guarantees and it isn't free.
- KMag 3y ago> could be considered fully defined since there is no optimization the compiler can do based on it being undefined UB means the compiler is free to perform whatever optimizations it wants. Are you really saying that no optimizations are allowed once the compiler notices UB? Michael Chastain (GDB developer, one of the few people with commit rights to the root of Google's monorepo) told me about the worst bug he ever helped a Googler debug, eventually boiling it down to: static const double y = 1.0; static const double x = 2 * y; printf("Before\n"); if (x > 0.0) { printf("x\n"); } else { printf("Not x\n"): } printf("After\n"); It was printing "Before\nAfter\n", with nothing in-between. It turns out that the value of x depended upon the initialization order of statically-scoped doubles. There was no malicious optimization in GCC that got rid of both branches, but both branches got optimized away through a series of intermediate steps where the compiler basically split the control flow graph into something equivalent to: static const double y = 1.0; static const double x = 2 * y; printf("Before\n"); if (x > 0.0) { printf("x\n"); } if (!(x > 0.0)) { printf("Not x\n"): } printf("After\n"); GCC determined that x was statically determinied and UB. In both places an optimization pass determined that the fastest choice for if(UB) is to branch over the code in question. Since it's UB, the compiler wasn't required to pick some self-consistent value for x. It's free to optimize away all if(UB) blocks to if(false) blocks. (Note that this particular case of UB is specific to floating point types and would not occur with integer types. I believe the intention of the spec is to avoid the requirement for floating point hardware to behave identically, including the state bits that affect rounding etc., to behave identically on the machine where the compiler is run and on the machine where the program is run. My naive hot take would be that this should be ID, not UB, but I'm sure the standards committee put a lot more thought into this than I have.) It wasn't some malicious or two-clever optimization. It was the emergent behavior of a series of optimizations, each one correct. Anyway, long story short, once the compiler notices UB, all optimizations are on the table. You seem to be implying that compilers need to be conservative when they detect UB. Compilers are generally recklessly aggressive in optimizing when they detect UB.
- muizelaar 3y agoCheck out the difference between LLVM's NotAtomic (C++) and Unordered (Java) here: https://llvm.org/docs/Atomics.html#notatomic https://llvm.org/docs/Atomics.html#notatomic
- layer8 3y agoOk, so it seems that the Java semantics can be expensive in cases like 64-bits-wide pointers on ARM. However, pointers (object references) in Java usually only are 32 bits wide by default, due to using a compressed pointer format.
- jcranmer 3y agoThere is general agreement that the Java 5 memory model's definition of data races is unsatisfactory. It's overly restrictive of optimizations, it doesn't quite match reality, it's utterly confusing (it's like 12 pages where the rest of the memory model is basically just 1 page). The only reason it's not UB in Java is that Java doesn't want any UB; everyone agreed that in C/C++, UB was the best way to handle data races. C++ does have a form of defined data races, though: relaxed atomics. And if you look at the history of relaxed atomics, from the moment it was first voted into the standard, there's been constant tweaking and kvetching over its unsuitability. I wouldn't recommend trying to understand relaxed atomics any more thoroughly than "you will read some value you wrote into it."
- o11c 3y agoC++ relaxed still serializes accesses to the variable itself, so it is far more useful than mere "defined data races". In particular it's useful for things like counters that always increment, or counters that decrement but which will branch and do another atomic operation when it reaches zero.
- jcranmer 3y agoI was going to mention that relaxed atomics additionally have a requirement that a read always reads the "last" write to that value, but the problem is that the temporal sense of "last" in that sentence only bears a loose resemblance to a typical programmer's sense of time in a program, so I think it may confuse more than it helps. In LLVM IR terms, the largest practical difference to users between unordered (Java) and monotonic (C relaxed) is that unordered is too weak to let an atomicrmw instruction be definable, whereas monotonic is strong enough to let it be defined. In both cases, you still have to be prepared for the possibility that a load is going to read a value that is in some sense stale. (There are a few other differences, e.g., you can reorder load unordered p/load unordered q if p and q are may-alias, but you can't if they're relaxed loads. But that's generally something that only comes up when you're writing optimization passes).
- dzaima 3y agoFar from the full story, but a note is that Java has the nice property of all possible single-operation writes being ≤8 bytes, all aligned if the VM so wants (byte, char/short, int, long, and Object are all the possible writes), whereas in C you can have larger types (structs, or larger ints (_BitInt in C2x); and with compiler extensions those can get arbitrarily misaligned). IIRC there were/are questions about write atomicity for value classes/Valhalla. And there's not much sane to define data races to anyway - String::hashCode might be "safe" with writing an 'int', but, were you to want a 64-bit hash, i.e. use a 'long', it'd be unsafe, as 64-bit types are specified to possibly tear!
- layer8 3y agoIn principle this is no different from the situation with long and double in Java, for which atomicity is not guaranteed, and word tearing can occur. It is still considered defined behavior, in the sense that you will see some combination of actually written values, and not get nasal demons.
- dzaima 3y agoAnd so Java effectively mandates at least max(32, size of Object)-bit atomic writes, while C can trivially run on 16-bit systems. I don't know if anyone's running multi-threaded software on such, but having a completely arbitrary boundary (from the point-of-view of a programmer wanting to store an integer) for what does and doesn't behave sanely is far from nice.
- plorkyeran 3y agoMy possibly-incorrect understanding is that in C++ terms, every field in Java is a relaxed atomic. In both languages this gives you very confusingly defined but not undefined behavior. A non-performance argument against Java's decision is that relaxed atomics have turned out to have much more complicated semantics than was expected in the 90s and 00s, to the extent that most code using them is probably incorrect. Java telling developers that data races are okay leads to people writing buggy code, and because it's legal you can't have something like TSan in Java to trap on data races. On the performance side, this decision inhibits some optimizations and while relaxed 32-bit atomics are free on all non-exotic hardware, that isn't the case for 64-bit atomics.
- raphlinus 3y agoIt's essentially the same as a relaxed atomic at the machine level, but it's weaker - it corresponds to "unordered" in the LLVM sense. In particular, it allows for a lot more optimization - operations can be reordered with respect to each other as long as the compiler is aware that they refer to disjoint memory locations.
- dataflow 3y agoMost of the UB in C++ could be well defined within the language if the language just did whatever the machine did (like overflows). The exceptions I can think of are (a) executing invalid code, or (b) access deallocated memory. Java can avoid both of them by taking control of both: you can't execute arbitrary pointers or read/write to arbitrary addresses within the language, and the runtime (I assume) prevents tearing of writes. (This is already guaranteed by the machine on x86, so it doesn't need to do anything there. I can only assume weaker architectures might require atomic instructions for potentially interfering writes, which seems like the cost paid here, but someone can enlighten me.) Furthermore, the GC can ensure that its operations are synchronized with your threads, so you can't interfere with it, and it doesn't pull the rug out from under you. So the end result is that there's theoretically no way to break memory safety.
- jcelerier 3y agofrom the java spec notes: > Some implementations may find it convenient to divide a single write action on a 64-bit long or double value into two write actions on adjacent 32-bit values. For efficiency's sake, this behavior is implementation-specific; an implementation of the Java Virtual Machine is free to perform writes to long and double values atomically or in two parts. > Implementations of the Java Virtual Machine are encouraged to avoid splitting 64-bit values where possible. Programmers are encouraged to declare shared 64-bit values as volatile or synchronize their programs correctly to avoid possible complications. so in practice Java behaves exactly as C++ for tearing (`volatile` in java having the same meaning than `atomic` in C++) - and if there is a powerful enough optimizer running in the back-end without access of the original semantic information it may well create the kind of UB-led optimizations that people complain about in C++
- dataflow 3y agoIs this only for numbers or also for pointers? Tearing for numbers isn't a memory safety issue, but for pointers it would mean that on a 64-bit machine with tearing, merely reassigning a variable and then calling a method on that object can execute arbitrary machine code.