6 ms·
While it's true that the difficulty of building a semantic model of pointers is mostly related to permitting optimizations, I don't think the author actually un
by jcranmer 6y ago
While it's true that the difficulty of building a semantic model of pointers is mostly related to permitting optimizations, I don't think the author actually understands how many optimizations are actually disabled by a simplistic pointers-are-integers model.
Let me give an example here. Consider these two functions:
void a() {
int x = 5;
return x;
}
void b() {
return 5;
}
In a simplistic, pointers-are-integer model, these two functions are not equivalent, and it is illegal for any compiler to transform the first into the second. This is because declaring the variable x means it must have some associated storage, which can be accessed by some unknown integer name. Any pointer which points to that integer value can then observe its value, and deleting the store to that temporary value is a potentially observable change to a legal program.
To permit this basic optimization, you need to have to some sort of rule that allows you to reason that a value whose address is never taken can never be legally accessed by a pointer. To actually effect this rule in semantics, you now have to start tracking extra metadata about what pointers can and cannot access... which is exactly the kind of model that's being criticized.
- dnautics 6y agomaybe there's a question here: If you really need the kind of performance afforded by that level of fine-grained optimization, shouldn't you instead consider emitting better code, at least in hot loops? It seems less dangerous to have the code do semantically exactly what you tell it to in the 90% case, because otherwise you can unwittingly introduce difficult-to-reason-about code. For a GP programming language, this could be possibly deployed in mission-critical code where lives are at stake.
- sanxiyn 6y agoI am not sure what the question is. Are you proposing manual marking of hot code and applying pointers-are-integers model to all code but optimizable pointer model to marked code?
- jcranmer 6y agoTo get an idea of the kind of performance degradation involved, make every variable and every pointer in your program volatile. Honestly, the actual pointer model of C is probably easier to understand than a everything-can-randomly-change-anything pointers-are-integers model. Undefined behavior gets a bit of a bad rap, and that's arguably largely because of unnecessarily gratuitous usage of it (signed integer overflow and strict aliasing being the biggies). But undefined behavior is actually a contract where the programmer promises not to do certain things. For pointers, the contract boils down to the following: * Do not violate strict aliasing (I'd call this an unnecessary rule, and it can be disabled in most compilers). * Do not read memory you haven't initialized. * Do not use memory after it's deallocated. * Do not look outside the bounds of the object you are given. * Do not look at memory you haven't been told about. There is very little reason to ever need to violate these rules. In fact, violating these rules tends to result in hard-to-reason semantics: suddenly, people can read things they shouldn't be able to, or decide to do things like execute random code.
- petergeoghegan 6y agoI agree with your points about undefined behavior. I'm pleasantly surprised that you didn't defend C's terrible strict aliasing rules. Your interpretation seems uncharitable. I imagine that you've interpreted the author's words literally, as somebody that has expert knowledge of compiler internals. Could the author really have meant to propose an "everything-can-randomly-change-anything pointers-are-integers" model?
- sanxiyn 6y agoWhat is the author's model then? I agree everything-can-randomly-change-anything interpretation is uncharitable, but then I am confused what the model is. (As you pointed out, that's the literal interpretation.) I think there is no model, and the author is just vaguely complaining they are not satisfied with status quo. But then the tone is unbelievably arrogant and deserves all the derision. By the way, I am of the opinion C's pointer model can be greatly improved to be programmer friendly, beyond getting rid of strict aliasing rule. For example, I think comparing two unrelated pointers (for sorting, lock ordering, etc.) should be well defined and not UB. But claiming "pointers are easy" is not the way to go.
- petergeoghegan 6y agoI read the article as a criticism of the strict aliasing rules in C. I think that you're attributing something to the author that they couldn't possibly believe.
- sanxiyn 6y agoThis is not a strict aliasing rule. I actually agree strict aliasing optimizations are mostly useless. (Exhibit: Rust has no strict aliasing.)
- aw1621107 6y ago> Exhibit: Rust has no strict aliasing. Isn't that arguably because Rust has even stricter aliasing rules? Not only are you not allowed to have differently-typed mutable references to the same memory, you (approximately) aren't allowed to have multiple mutable references to the same memory, period, even if they are the same type.
- sanxiyn 6y agoYes, but for most optimizations (including jcranmer's example), just "aliasing rule" is sufficient, not C's "strict aliasing rule". The gist is that pointers shouldn't be able to do out-of-bound accesses. The additional restriction that pointers should be well typed is mostly unnecessary, both in C and in Rust. Note that pointers-are-integers directly imply no restrictions whatsoever on out-of-bound accesses.
- sanxiyn 6y agoTo elaborate, the rule is roughly that if a and b are different arrays, a[i] and b[j] do not alias. If pointers-are-integers, a[b-a] and b[0] alias. In C standard, while a[b-a] and b[0] are same integers, they are not same pointers, because "a and b are different arrays" imply a[b-a] is out-of-bound access hence invalid. This is actually very reasonable. Pointers are not integers.
- agalunar 6y ago> This is because declaring the variable x means it must have some associated storage I've not read the C spec, so I may be terribly wrong here, but I'm inclined to disagree: x is not accessible outside of a() and cannot be read or modified by another part of the program, and so a compiler would be perfectly justified in not bothering to allocate storage for it. > To permit this basic optimization, you need to have to some sort of rule that allows you to reason that a value whose address is never taken can never be legally accessed by a pointer. Essentially, I'm contending that not only is the address of x never taken, it never can be taken, and therefore the optimization is safe. (In practice, if x did happen to have stack space allocated for it and you knew what location it ought to have relative to the stack pointer, you could modify x. But insofar as I'm aware, C does not guarantee many things about the layout of memory or a particular calling convention anyway, and so you shouldn't rely on this. And that isn't changed by one's model of pointers.)
- bzb5 6y agoWhat if the thread is preempted between the two lines? Another thread should be able to read and modify that variable, no?
- asdfasgasdgasdg 6y agoFor C standards before C11, C doesn't have a thread-aware memory model. The notion of threads suspending and waking up, or memory access from one thread's stack to another, does not exist in the standard, at least as far as I'm aware. The C standard also doesn't define the memory layout of the stack, so there is no standard way to acquire the address of that variable. It's easy enough to see that compilers do not actually create storage for it: https://godbolt.org/z/cfE9o5 https://godbolt.org/z/cfE9o5 In C11 there is a thread aware memory model, but still no standard way to access that location, so compilers will assume it doesn't need to be created. https://godbolt.org/z/KTz9sT https://godbolt.org/z/KTz9sT
- mhh__ 6y agoIn what language is it defined behaviour to grab a thread and start playing with its memory? The compiler can only know what the standard says and in this case it would be fair game
- TazeTSchnitzel 6y agoIn fact there are ways in C (e.g. `volatile`, though not all are portable…) to get closer to the raw integer pointers the OP seems to want… but the compiler is forced to generate worse code if you try to use them. That's probably why they're not the default. The OP's viewpoint, which seems to be a fairly popular one, seems to be something like “why can't C be as intuitive as it was in the 1970's, didn't it work fine then?” Well, it probably still does work if you're happy with the level of optimisation a 1970's C compiler would give you (-O0 maybe?), and that's a valid choice! But compilers didn't get stricter about undefined behaviour for nothing, it's key to making those “zero-cost abstractions” actually have near-zero cost.
- robotresearcher 6y ago> Any pointer which points to that integer value can then observe its value With a() as written, there's no legitimate way to obtain the address of x, so there is no such pointer. Am I wrong about this?
- sanxiyn 6y agoYes. If pointers are integers, you can cast an integer (let's say 1234) to a pointer, which happens to be the address of x. It is a legitimate way to obtain the address of x if pointers are integers, so compilers must assume this can possibly happen.
- robotresearcher 6y agoSure, but you can't know what that number is. It's almost certainly not 1234, and since it's an auto allocated var with local scope, it's probably on the stack unless it's been optimized elsewhere, so it's dynamic, and exists only for the lifetime of each run of a(). You might figure out some evil way to get it for some implementation, but I don't think the C spec gives you a reliable way. That's what I mean by 'legitimate'. Even if you modified the code of a() to pass out the address of x to a caller, they can't safely use that pointer and the actual behavior is undefined. x does not exist outside of a call to a().
- sanxiyn 6y agoI think you are right there is no reliable way, but C specification does not disallow unreliable programs. It only disallows nonconforming programs. Compilers can't optimize a() to b() under pointers-are-integers model. It may be linked to code like c(): void c() { int random = generate_random_number(); int* address = (int*)random; *address = 4; } In real machines, c() randomly overwrites memory with 4, in particular memory of x whose value will change from 5 to 4. In C abstract machine, c() randomly overwrites memory with 4, but it can never overwrite memory of x, because memory of x does not have integer address. Therefore compilers can optimize a() to b().
- dooglius 6y ago
- dooglius 6y agoYou're either coming up with a huge strawman, or you're confused about what the post means. Pointers being integers does not mean that writing garbage to any random integer you come up with has well-defined semantics. In any case, your example could be made much better by pointing out that any program could simply overwrite the stack return value; that has to be UB. > To permit this basic optimization, you need to have to some sort of rule that allows you to reason that a value whose address is never taken can never be legally accessed by a pointer This is true >To actually effect this rule in semantics, you now have to start tracking extra metadata about what pointers can and cannot access If you aren't writing to random values, you don't really need to track anything. foo(bar *) doesn't need to track anything, it's presumably part of the implicit contract that you allow foo to write to the passed in object.
- bsder 6y ago> it is illegal for any compiler to transform the first into the second. Don't know about the language spec, but compilers do this transform all the time. It is, in fact, quite infuriating if you are trying to use a debugger on the code to do a breakpoint on data change (memory change) and you can't because the value is solely held in a register. It also doesn't help that the author is writing from a C++ perspective and not a C perspective.
- saagarjha 6y agoRight, because pointers are not integers.
- deleted 6y ago[deleted]
- titzer 6y ago> In a simplistic, pointers-are-integer model, these two functions are not equivalent, In reality two functions are never and can never been equivalent--they can only be observationally equivalent. > you need to have to some sort of rule that...whose address is never taken can never be legally accessed by a pointer. Such a "rule" does exist. If the above is a C program, said C program must have undefined behavior (read: other pointer bugs) to observe x's value. Programs with pointer bugs can do insanely weird things because they break all the abstractions of programming language and expose the memory layout. The point of the article is that compilers shouldn't try to exploit undefined behavior in pursuit of more performance. The fact that you can observe optimization means that abstractions of the languages are broken. C and C++ are essentially the only languages in existence where rampant observation of optimizations is considered not a bug, but a feature. I would really recommend reading the Ertl paper [http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_201...]. It covers this really well.