Really what is being argued here is that C pointer optimisation is difficult - and because C is designed to do stuff like coding the insides of the 'new' primitive (ie malloc) you can't make the sorts of assumptions about aliasing that you can in other languages.
I'd argue that if you don't understand that you probably shouldn't be coding in C (I'll let others argue about C++)
Coding a malloc in C is actually fairly questionable from a standards perspective. You really have to consider the entire address space to be one big object for this to really work.
> I prefer the simple and obvious pointer model. Vastly.
That's great, but then you're not writing C anymore. When you write C (or indeed, almost any language in use today) you are writing code against an abstract machine, not against real hardware.
Pointers are integers on (most) real hardware. They are indisputably not integers in the C abstract machine.
The reason for this abstract machine existing is not to enable optimizations, it's to allow the code to be portable. If there was no abstract machine, you would have to reason about the correctness of your code for each target architecture independently. With an abstract machine, you can reason that your code is correct on the abstract machine, and the compiler can do the hard work of translating that to each target architecture in a way that preserves well-defined behaviour.
Now, given that the abstract machine exists, you could ask why it is so complicated, and the answer this time is for optimizations, and also to allow the translation to the target architecture to introduce as little overhead as possible.
Agreed. The "pointers as integers" model requires (among other things) that unrelated pointers be comparable with < and >, which IIRC is undefined behavior in the C spec because it has trouble with some exotic memory models.
Since one can add to and subtract from a pointer, it is only natural to be able to compare them. And the standard clearly states pointers can be compared, although it requires the two pointers to point to the same array (or last element+1) or to the same structure.
I'm curious. Can you elaborate on "most"? The closest thing I know of to an exception is ARM's memory tagging extension stuff, [1] and I'm not sure if that qualifies because it looks like the actual checking of the tag is done by compiler-emitted assembly rather than automatically by the hardware. [2] I suppose it at least violates the idea that casting the pointer to an integer type doesn't change the value and still allows you to sort addresses via a simple <.
If pointers are integers, all pointers escape. This is not a matter of "nice to have" optimizations.
(The usual model used by compilers is that pointers are not integers, but a pointer becomes an integer when it is casted to an integer. This prevents majority of pointers that are not casted to integers from escaping, which is important.)
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.
maybe 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.
I 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?
To 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.
I 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?
What 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.
Why would you assume that the author must have a formal model? It's a short blog post.
Perhaps the author really is deserving of derision to some degree - who can say? It should not be based on a straw man that nobody could possibly believe, though.
In my experience, the model that most people railing against undefined behavior tend to end up proposing is a vague, "read-my-mind" sort of model.
Semantics are hard, and undefined behavior makes it especially so. See the voluminous threads on llvm-dev trying to pin down what "undef" actually means for an example. In the context here, the linked article is a response to someone who is describing why defining a memory model is actually more difficult than it seems. The linked article is basically saying "screw that, it doesn't have to be hard, just use the obvious model" without specifying what the obvious model actually is.
After you've been in a couple of hour-long meetings where everyone is arguing over what the "obvious" model actually says, it's painfully obvious that "obvious" isn't obvious.
My motivation is to prevent accidental UB. Let p be array of length 10. Currently, p + 15 - 10 is UB so you must parenthesize p + (15 - 10). This seems preventable and unnecessary.
Another related change I'd like to see is that &(foo * )(NULL)->bar - (foo * )NULL be made well-defined. Effectively, allowing a generalization of offset_of to be written in C/C++.
I 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.
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.
Yes, 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.
To 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.
> 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.)
For 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
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
In 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
In 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.
Yes. 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.
Sure, 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().
I 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().
I think you are taking an overly strong reading, I highly doubt the author would say that writing to stack memory is reasonable unless the address has explicitly been taken with &x
You'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.
> 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.
> 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.
To me, the philosophy of C (and even C++ before things became nuts) is that you should be able to reasonably guess the assembly code resulting from the C code, the idea being that you can write assembly code with much less typing.
These days, things seem to be moving in a more dogmatic direction with the underlying assumption that the vast majority of programmers are bad programmers.
You can predict a pseudo-assembly output for a mental model of the architecture(s) you're targeting. It doesn't have to be an exact match, register allocation and all.
You're fighting a losing battle though. You can guess what shape the assembly looks like but ultimately unless you have measured and identified somewhere where you can make progress your brain simply cannot keep in mind all the little nuances of the optimizations a compiler does.
It's worth adding that the compilers themselves aren't perfect - you can use LLVM's code to try and predict how your loop will perform (LLVM-MCA) and last time I checked it wasn't amazingly accurate.
If you don't like the current C standard and you want to change the standard, feel free to propose a change. The standard is there for a reason. If everyone adds their own extra constraints to the language, the standard falls apart and becomes useless and meaningless.
I will not be holding my breath waiting for the committee to accept this though. The chance of this being accepted seems really low, as it has serious consequences for the meaning of the large amount of existing C code.
> I find this fascinating: a "nice to have" optimzation is so obviously more important than a simple and obvious pointer model that it doesn't even need to be explained as a possible tradeoff, never mind justified as to why the tradeoff is resolved in favor of the nice-to-have optimization.
Hold up - there's also a tradeoff in assumptions you can make about well behaving code. It's _also_ an optimization in reading and internalizing the code.
58 comments
[ 2.5 ms ] story [ 116 ms ] threadI'd argue that if you don't understand that you probably shouldn't be coding in C (I'll let others argue about C++)
That's great, but then you're not writing C anymore. When you write C (or indeed, almost any language in use today) you are writing code against an abstract machine, not against real hardware.
Pointers are integers on (most) real hardware. They are indisputably not integers in the C abstract machine.
The reason for this abstract machine existing is not to enable optimizations, it's to allow the code to be portable. If there was no abstract machine, you would have to reason about the correctness of your code for each target architecture independently. With an abstract machine, you can reason that your code is correct on the abstract machine, and the compiler can do the hard work of translating that to each target architecture in a way that preserves well-defined behaviour.
Now, given that the abstract machine exists, you could ask why it is so complicated, and the answer this time is for optimizations, and also to allow the translation to the target architecture to introduce as little overhead as possible.
I'm curious. Can you elaborate on "most"? The closest thing I know of to an exception is ARM's memory tagging extension stuff, [1] and I'm not sure if that qualifies because it looks like the actual checking of the tag is done by compiler-emitted assembly rather than automatically by the hardware. [2] I suppose it at least violates the idea that casting the pointer to an integer type doesn't change the value and still allows you to sort addresses via a simple <.
[1] https://security.googleblog.com/2019/08/adopting-arm-memory-...
[2] https://clang.llvm.org/docs/HardwareAssistedAddressSanitizer...
(The usual model used by compilers is that pointers are not integers, but a pointer becomes an integer when it is casted to an integer. This prevents majority of pointers that are not casted to integers from escaping, which is important.)
Let me give an example here. Consider these two functions:
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.
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.
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?
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.
Perhaps the author really is deserving of derision to some degree - who can say? It should not be based on a straw man that nobody could possibly believe, though.
Semantics are hard, and undefined behavior makes it especially so. See the voluminous threads on llvm-dev trying to pin down what "undef" actually means for an example. In the context here, the linked article is a response to someone who is describing why defining a memory model is actually more difficult than it seems. The linked article is basically saying "screw that, it doesn't have to be hard, just use the obvious model" without specifying what the obvious model actually is.
After you've been in a couple of hour-long meetings where everyone is arguing over what the "obvious" model actually says, it's painfully obvious that "obvious" isn't obvious.
Do not even try to look; computing a pointer that points outside the object it was created from is undefined.
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.
Note that pointers-are-integers directly imply no restrictions whatsoever on out-of-bound accesses.
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.
This is technically stricter than the strict aliasing rule, isn't it? Since it also disallows aliasing through pointers of the same type?
Or am I getting concepts mixed up here, since strict aliasing is for pointers and you're talking about arrays?
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.)
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
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
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.
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?
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().
Compilers can't optimize a() to b() under pointers-are-integers model. It may be linked to code like c():
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().Unless you return a reference to an integer that's been malloc'd.
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.
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.
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_201...]. It covers this really well.
The only thing that you can predict about compiled C code is the instructions in the C abstract machine, because that’s what C targets.
It's worth adding that the compilers themselves aren't perfect - you can use LLVM's code to try and predict how your loop will perform (LLVM-MCA) and last time I checked it wasn't amazingly accurate.
I will not be holding my breath waiting for the committee to accept this though. The chance of this being accepted seems really low, as it has serious consequences for the meaning of the large amount of existing C code.
Hold up - there's also a tradeoff in assumptions you can make about well behaving code. It's _also_ an optimization in reading and internalizing the code.