6 ms·

Pointers are Easy, Optimization is Complicated

28 points by pcr910303 6y ago

a_t48 6y ago
> 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.
Taniwha 6y ago
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++)
- Sulik 6y ago
  +1
- saagarjha 6y ago
  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.
Diggsey 6y ago
> 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.
- jasonhansel 6y ago
  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.
  - mhh__ 6y ago
    It also doesn't really make sense in abstract consideration - is one address "bigger" than the other one?
    - deleted 6y ago
      [deleted]
    - jerome-jh 6y ago
      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.
- scottlamb 6y ago
  > Pointers are integers on (most) real hardware. 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-tagging-extension.html https://security.googleblog.com/2019/08/adopting-arm-memory-... [2] https://clang.llvm.org/docs/HardwareAssistedAddressSanitizerDesign.html https://clang.llvm.org/docs/HardwareAssistedAddressSanitizer...
  - Diggsey 6y ago
    There's CHERI: https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/ https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/
sanxiyn 6y ago
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.)
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 ago
  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.
  - sanxiyn 6y ago
    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?
  - jcranmer 6y ago
    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.
Sulik 6y ago
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.
- Ar-Curunir 6y ago
  That’s not true anyway today, because the assembly generated depends on the architecture, and there’s sufficient diversity there. 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.
  - Sulik 6y ago
    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.
- mhh__ 6y ago
  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.
tjalfi 6y ago
If you want PCC, you know where you can find it.
drivebycomment 6y ago
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.
- sanxiyn 6y ago
  Eh no. While I agree it won't be accepted, this is more restrictive semantics, so it doesn't cause any compatibility problem.
deleted 6y ago
[deleted]

28 points by pcr910303 6y ago

> 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.

Taniwha 6y ago

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++)

Sulik 6y ago
+1
saagarjha 6y ago
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.

Diggsey 6y ago

> 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.

jasonhansel 6y ago
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.
- mhh__ 6y ago
  It also doesn't really make sense in abstract consideration - is one address "bigger" than the other one?
  - deleted 6y ago
    [deleted]
  - jerome-jh 6y ago
    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.
scottlamb 6y ago
> Pointers are integers on (most) real hardware. 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-tagging-extension.html https://security.googleblog.com/2019/08/adopting-arm-memory-... [2] https://clang.llvm.org/docs/HardwareAssistedAddressSanitizerDesign.html https://clang.llvm.org/docs/HardwareAssistedAddressSanitizer...
- Diggsey 6y ago
  There's CHERI: https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/ https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/

sanxiyn 6y ago

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.)

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 ago
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.
- sanxiyn 6y ago
  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?
- jcranmer 6y ago
  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.

Sulik 6y ago

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.

Ar-Curunir 6y ago
That’s not true anyway today, because the assembly generated depends on the architecture, and there’s sufficient diversity there. 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.
- Sulik 6y ago
  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.
mhh__ 6y ago
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.

tjalfi 6y ago

If you want PCC, you know where you can find it.

drivebycomment 6y ago

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.

sanxiyn 6y ago
Eh no. While I agree it won't be accepted, this is more restrictive semantics, so it doesn't cause any compatibility problem.

deleted 6y ago

[deleted]