145 ms·

I think undefined behavior (as a general concept) gets an unfair share of the blame here. It's notable that almost all criticism of undefined behavior in C tend

I think undefined behavior (as a general concept) gets an unfair share of the blame here. It's notable that almost all criticism of undefined behavior in C tends to focus on just two sources of UB: signed integer overflow and strict aliasing; other sources of UB just don't generate anywhere near the same vitriol [1]. Furthermore, it's notable that people don't complain about UB in Rust... which arguably has a worse issue with UB in that a) there's not even a proper documentation of what is UB in Rust, and b) the requirement that &mut x be the sole reference to x (and therefore is UB if it is not) is far more stringent than anything in C (bar maybe restrict), and I'm sure that most Rust programmers, especially newbies starting out with unsafe, don't realize that that's actually a requirement. There is a necessity for some form of UB in a C-like language, and that has to deal with pointer provenance. You see, in C, everything lives in memory, but on real hardware, you want as much to live in a register as possible. So a compiler needs to be able to have reasonable guarantees that, say, any value whose address is never taken can never be accessed with a pointer, and so can be promoted to a register. As a corollary, this requires that things like out-of-bound memory accesses, or worse, converting integers to pointers (implicating pointer provenance here) need to have UB in at least some cases, since these could in principle "accidentally" compute an address which is the same as a memory location whose address was never taken. That suggests that the problem isn't UB per se. If we look at the two canonical examples, arithmetic overflow and strict aliasing, we can see that one of the features of these things is that they have a pretty obvious well-defined semantics [2] that can be given for them, and furthermore, there's no way to access these well-defined semantics even avoiding this feature altogether. And I think it's the lack of this ability to work around UB that is the real issue with C, not UB itself. [1] For example, it is UB to pass in rand as the comparison function to qsort. I'm sure many people will not realize that before I wrote this, and even parsing the C specification to find out that this is UB is not trivial. For an interesting challenge, try giving a definition of what the behavior should be were it not UB--and no, you can't just say it's impl-defined, since that still requires you to document what the behavior is. [2] I will point out that, for arithmetic overflow, this semantics is usually wrong. There are very few times where you want <large positive number> + <large positive number> = <negative number>, and so you're mostly just swapping out an unpredictably wrong program for a predictably wrong program, which isn't really any better. However, the most common time you do want the wrapping semantics is when you want to check if the overflow happened, and this is where C's lack of any overflow-checked arithmetic option is really, really painful.

dooglius 5y ago
For [1] I would say that when the compiler does not control the standard library (e.g. most linux systems) then the compiler should treat qsort like any normal non-libc function call, it shouldn't be able to detect that I might be relying on implementation-specific guarantees. From a libc perspective, I would probably have a safe version of qsort used either on request or when NDEBUG is undefined, in which the implementation must either detect the inconsistency and abort in an implementation-defined matter, or select an ordering such that a<b in the ordering implies the existence of a finite chain a<x_1<x_2<...<x_n<b of comparison results in which each x_i is the equivalence class where the compare function said two entries were equal. I think that should be consistent with most sorting algorithms. (Whether the normal qsort should be the same as the safe version would only be needed if there were a significant-enough performance improvement.) For [2] I disagree for two reasons. For one, merely having an answer at all, rather than entering an undefined behavior is valuable; having x+y=pseudorand(x,y) would still be better than complete UB because the damage that can be done is limited. The other reason is that addition/subtraction/multiplication does actually work modulo 2^n, so if I write e.g. (a+b-c) where b can be large but b-c is known to be small, it works even if the language is technically left-associative and having the a+b first is UB. I pretty much agree with your point that the main problem is there is no way to work around UB; if there were a workaround there would be much less reason to complain. I would go a bit further and say such a workaround needs to be in the code itself to be effective, not merely a command line arg like fwrapv, so that it gets kept around when doing header inlining, LTO, copy-pasting code to other projects, etc.
- jcranmer 5y ago
  > For [1] I would say that when the compiler does not control the standard library (e.g. most linux systems) then the compiler should treat qsort like any normal non-libc function call, it shouldn't be able to detect that I might be relying on implementation-specific guarantees. I am guessing, for example, that you are not aware that every compiler will optimize `printf("Hello, world!\n");` to `puts("Hello, world!\n");`. memcpy and memset are even more heavily-optimized function calls by the compiler: for example, they don't prevent memory-to-register promotion.

dooglius 5y ago

For [1] I would say that when the compiler does not control the standard library (e.g. most linux systems) then the compiler should treat qsort like any normal non-libc function call, it shouldn't be able to detect that I might be relying on implementation-specific guarantees. From a libc perspective, I would probably have a safe version of qsort used either on request or when NDEBUG is undefined, in which the implementation must either detect the inconsistency and abort in an implementation-defined matter, or select an ordering such that a<b in the ordering implies the existence of a finite chain a<x_1<x_2<...<x_n<b of comparison results in which each x_i is the equivalence class where the compare function said two entries were equal. I think that should be consistent with most sorting algorithms. (Whether the normal qsort should be the same as the safe version would only be needed if there were a significant-enough performance improvement.) For [2] I disagree for two reasons. For one, merely having an answer at all, rather than entering an undefined behavior is valuable; having x+y=pseudorand(x,y) would still be better than complete UB because the damage that can be done is limited. The other reason is that addition/subtraction/multiplication does actually work modulo 2^n, so if I write e.g. (a+b-c) where b can be large but b-c is known to be small, it works even if the language is technically left-associative and having the a+b first is UB. I pretty much agree with your point that the main problem is there is no way to work around UB; if there were a workaround there would be much less reason to complain. I would go a bit further and say such a workaround needs to be in the code itself to be effective, not merely a command line arg like fwrapv, so that it gets kept around when doing header inlining, LTO, copy-pasting code to other projects, etc.

jcranmer 5y ago
> For [1] I would say that when the compiler does not control the standard library (e.g. most linux systems) then the compiler should treat qsort like any normal non-libc function call, it shouldn't be able to detect that I might be relying on implementation-specific guarantees. I am guessing, for example, that you are not aware that every compiler will optimize `printf("Hello, world!\n");` to `puts("Hello, world!\n");`. memcpy and memset are even more heavily-optimized function calls by the compiler: for example, they don't prevent memory-to-register promotion.