15 ms·

Pointers Are Complicated, Or: What's in a Byte? (2018)

85 points by pcr910303 6y ago

deleted 6y ago
[deleted]
deleted 6y ago
[deleted]
dang 6y ago
Discussed at the time: https://news.ycombinator.com/item?id=17604402 https://news.ycombinator.com/item?id=17604402
raphlinus 6y ago
Also potentially relevant: Ralf, or I should say, Dr. Jung, recently completed a PhD, which I'm sure will have a lot more fascinating material for those interested in this paper. I'm hoping to find time myself to read it, but I seem to spend too much time on sites like Hacker News... https://www.ralfj.de/blog/2020/09/03/phd.html https://www.ralfj.de/blog/2020/09/03/phd.html
teddyh 6y ago
It always bothered me that C, and similar languages which are termed “low level”, aren’t actually compiling to anything like the actual low level hardware anymore. The match used to be quite close in the 1980’s, but nowadays the “machine code” which is “run” by a CPU is actally a kind of virtual byte code language with an interpreter implemented in microcode inside the CPU. But this byte code has flaws: For instance, this virtual machine byte code language has little or no sense of memory caches (of any kind), out-of-order execution, branch prediction, etc. Both the compiler and the CPU knows (or could know) about these things, but the compiler has no way to communicate this to the CPU other than using this ’80s style byte code which does not have these concepts. It’s like talking about advanced mathematics using nothing but words in “The Cat in the Hat” – a rather narrow communication pipe. I’d always imagined that as parallelism rose, a new model of virtual machine would rise with it, with its own “assembly” (i.e. low level language closely tied to the machine), which would in turn be the target of a compiler of a new parallel-by-default high level language. Alas, this has not happened.
- lalaithion 6y ago
  This exact view is why https://futhark-lang.org/ https://futhark-lang.org/ is exciting to me; it's currently designed mainly for GPUs, but a lower-level CPU bytecode could be a new backend for it if CPU developers ever decide to expose it.
  - teddyh 6y ago
    Designing a high-level language first is a mistake, I think. It risks being too complex without adequate grounding in real hardware. I think this was also APL’s mistake – by being too “mathematical”, so to speak, it’s too hard to wrap one’s head around. I think it must first come from the CPU exposing these concepts, followed by increasingly better compilers taking advantage of them, and as we get more experience about what concepts we like, we can design higher-level languages around these new concepts. Chip design languages like VHDL might some day rise up from being slightly too close to the hardware to fill this role, but I certainly don’t know enough about any of these topics to have a qualified opinion.
- garaetjjte 6y ago
  So you just want VLIW architecture? It turns out it's better to have that abstract bottleneck ISA in practice, so CPU hardware can iterate microarchitectures without breaking software compatibility. Intel learned about this hard way with Itanium.
- jcranmer 6y ago
  People have had the same ideas you've had, and it's gotten as far as commercial products, but the general experience has been that "sufficiently smart compiler" tends to be very lackluster in practice. Any such effort needs to be extremely cognizant of what hardware is fundamentally good and bad at, and what compilers are fundamentally good and bad at. Let's start with branch prediction. Modern hardware branch predictors are pretty phenomenal. They can predict a basic loop with 100% accuracy (i.e., they can not only predict that the backedge is normally taken, but can predict that the loop is about to stop). In the past decade, we've seen improvements in indirect branch predictor. The classic "branch taken/branch not taken" hint is fundamentally coarser and less precise than the hardware branch predictor: it cannot take any advantage of dynamic information. Replacing the hardware branch predictor with a compiler's static branch predictor is only going to make the situation worse. Now you might be thinking of somehow encoding the branch predictor state in hardware. This runs into the issue of encoding microarchitecture in your hardware ISA. If you ever need to change microarchitecture, you face the dilemma of having to make a new, incompatible ISA, or emulating old microarchitectural details that no longer work well. MIPS got burned with this by delay slots. In general, the rule of thumb hardware designers use is "never expose your microarchitecture in your ISA." A related topic is the issue of memory size. Memory is relatively expensive compared to ALUs: we can stamp out more ALUs than we know how to fill. We have hit the limit of physics in sizing of our register files and L1 caches (electrons move at finite speed!), and the technologies we use to make them work quickly are also prohibitively power-hungry. This leads to the memory hierarchy of progressively larger, but cheaper and more efficient memories. The rule of thumb for performance engineers is that you count cycles only if you fit in L1 cache; otherwise, you're counting cache misses, since those cache misses will dwarf any cycle count savings you're likely to scrounge up.
0x09 6y ago
The article doesn't touch on this, but in C pointer types are also the only kind that can be invalidated without any apparent change to their value: void *x = malloc(...); free(x); if(x); // undefined behavior Note that this isn't about dereferencing x after free, which is understandably not valid. Rather the standard specifies that any use of the pointer's value itself is undefined after being used as an argument to free, even though syntactically free could not have altered that. This special behavior is also specifically applied to FILE* pointers after fclose() has been called on them. If there is some historical reason / architecture that could explain this part of the specification I would be interested to hear the rationale, this has been present in mostly the same wording since C89.
- jcranmer 6y ago
  My gut instinct is as follows: void *x = malloc(...); void *y = malloc(...); assert(x != y); // standard guarantees this [1] Yet it's fairly reasonable that: void *x = malloc(...); free(x); void *y = malloc(...); // malloc reused x's allocation here. So, in effect, guaranteeing that the results of two mallocs can never alias each other, while allowing the implementation to reuse freed memory, requires semantically adjusting the value of a pointer to a unique, unaddressable value. [1] I think, but I'm not sure which versions of C/C++ added this guarantee
  - asveikau 6y ago
    I feel like you should not need to carve out extra language in the standard to explain this. It's very clear that following *x is undefined after free(x). It's also clear from any reasonable understanding of malloc that x's numeric value might collide with a later allocation coincidentally. Why should that make "if (x)" undefined? It's true that the result of "if (x == y)" would depend on coincidences lining up and you should not rely on either one. Calling any evaluation of x "undefined" seems much more extreme than that though.
    - jcranmer 6y ago
      At first glance, it does some like an unnecessarily gratuitous instance of undefined behavior. However... what could you actually meaningfully do with a pointer to freed memory anyways? You clearly can't dereference it. The only pointers you can compare it to are other pointers to the now-freed object (cross-object pointer comparisons are UB in C) and NULL. But if you were going to compare it to NULL, it's presumably to guard against a dereference, so you'd end up UB anyways if you didn't overwrite it to NULL in the first place, at which point it's not being compared with anything anymore.
saagarjha 6y ago
In addition to all the things mentioned above, there's also another kind of byte: structure padding. Nobody really knows how to deal with it, and it has extremely strange rules–it's kind of uninitialized in some cases, but you can give it a value sometimes…and sometimes you can't, or not in any way that sticks. It's truly strange stuff, and its exact nature is still being worked out.
- nwmcsween 6y ago
  Pack your structs to not have padding? The probable reason it sometimes works is purely how the compiler decides to do the copy. Anything that relies on implicit padding is horribly broken software.
  - saagarjha 6y ago
    I think you might be misunderstanding my comment, I’m not complaining about struct padding causing issues in my code, I’m saying the standard is wishy-washy about it. This can be problematic when you are doing things like memcpying a structure, or trying to zero it out before sending it somewhere else. (And, FWIW, there is no standard way to disable struct padding, and doing so will likely generate slower code anyways.)
    - nwmcsween 6y ago
      How is the standard not explicit? copying with padding doesn't need to copy the padding at all or can if it's faster, memcpy is a intrinsic the compiler can copy whatever it deems wrt padding.
      - saagarjha 6y ago
        Because there are certain cases in C11 where padding can be legally observed because it is defined to be set to zero–brace initialization, for example. It is unclear what happens in this case when you do anything with the memory other than read it (for example, storing to a structure member, based on the current reading of the standard, may make padding indeterminate again–plus, is "memcpy" a "read"?). See here for some of the questions raised: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1793.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1793.pdf
stephc_int13 6y ago
I read the article and I am not convinced by the author arguments. He is talking about edge cases. I've been using C and C++ for over 20 years now, for both low level and high level stuff, and I never needed to know about those edge cases. And I think you don't want to know about them, you don't need to know about them to write good code. Nitpicking about edge cases tradeoffs made by compiler designers and language standards decades ago is like attacking under the belt, in my opinion.
- pwdisswordfish4 6y ago
  The point isn’t that anyone would want to write code like this. It’s to define rules that establish what the language implementation is allowed to assume about pointers when performing optimisations, and consequently, what operations code is allowed to perform without running into UB. The best way to study such rules is with edge cases like this. It’s like a trolley problem in a way. The situation may be unlikely, but better have an answer for it ready instead of replying ‘how dare you ask such questions’.
- SubjectToChange 6y ago
  Can you clarify what you disagree with in the article? The author wasn't saying programmers need to understand all the complexities of pointers to write good code, nor was he saying anything about the quality of those languages. Also, it is incredibility defensive to accuse the author of "attacking under the belt" when his observation wasn't aimed at any specific language.
  - stephc_int13 6y ago
    From my opinion, this is a way to try and push the adoption of Rust by shading an unpleasant light on the current contender : C/C++ An other way to say is that this is propaganda.
    - steveklabnik 6y ago
      That doesn’t make sense, given: > Both parts of this statement are false, at least in languages with unsafe features like Rust or C: The two languages share these features, which is the whole reason this is being written in the first place.

85 points by pcr910303 6y ago

deleted 6y ago

[deleted]

deleted 6y ago

[deleted]

dang 6y ago

Discussed at the time: https://news.ycombinator.com/item?id=17604402 https://news.ycombinator.com/item?id=17604402

raphlinus 6y ago

Also potentially relevant: Ralf, or I should say, Dr. Jung, recently completed a PhD, which I'm sure will have a lot more fascinating material for those interested in this paper. I'm hoping to find time myself to read it, but I seem to spend too much time on sites like Hacker News... https://www.ralfj.de/blog/2020/09/03/phd.html https://www.ralfj.de/blog/2020/09/03/phd.html

teddyh 6y ago

It always bothered me that C, and similar languages which are termed “low level”, aren’t actually compiling to anything like the actual low level hardware anymore. The match used to be quite close in the 1980’s, but nowadays the “machine code” which is “run” by a CPU is actally a kind of virtual byte code language with an interpreter implemented in microcode inside the CPU. But this byte code has flaws: For instance, this virtual machine byte code language has little or no sense of memory caches (of any kind), out-of-order execution, branch prediction, etc. Both the compiler and the CPU knows (or could know) about these things, but the compiler has no way to communicate this to the CPU other than using this ’80s style byte code which does not have these concepts. It’s like talking about advanced mathematics using nothing but words in “The Cat in the Hat” – a rather narrow communication pipe. I’d always imagined that as parallelism rose, a new model of virtual machine would rise with it, with its own “assembly” (i.e. low level language closely tied to the machine), which would in turn be the target of a compiler of a new parallel-by-default high level language. Alas, this has not happened.

lalaithion 6y ago
This exact view is why https://futhark-lang.org/ https://futhark-lang.org/ is exciting to me; it's currently designed mainly for GPUs, but a lower-level CPU bytecode could be a new backend for it if CPU developers ever decide to expose it.
- teddyh 6y ago
  Designing a high-level language first is a mistake, I think. It risks being too complex without adequate grounding in real hardware. I think this was also APL’s mistake – by being too “mathematical”, so to speak, it’s too hard to wrap one’s head around. I think it must first come from the CPU exposing these concepts, followed by increasingly better compilers taking advantage of them, and as we get more experience about what concepts we like, we can design higher-level languages around these new concepts. Chip design languages like VHDL might some day rise up from being slightly too close to the hardware to fill this role, but I certainly don’t know enough about any of these topics to have a qualified opinion.
garaetjjte 6y ago
So you just want VLIW architecture? It turns out it's better to have that abstract bottleneck ISA in practice, so CPU hardware can iterate microarchitectures without breaking software compatibility. Intel learned about this hard way with Itanium.
jcranmer 6y ago
People have had the same ideas you've had, and it's gotten as far as commercial products, but the general experience has been that "sufficiently smart compiler" tends to be very lackluster in practice. Any such effort needs to be extremely cognizant of what hardware is fundamentally good and bad at, and what compilers are fundamentally good and bad at. Let's start with branch prediction. Modern hardware branch predictors are pretty phenomenal. They can predict a basic loop with 100% accuracy (i.e., they can not only predict that the backedge is normally taken, but can predict that the loop is about to stop). In the past decade, we've seen improvements in indirect branch predictor. The classic "branch taken/branch not taken" hint is fundamentally coarser and less precise than the hardware branch predictor: it cannot take any advantage of dynamic information. Replacing the hardware branch predictor with a compiler's static branch predictor is only going to make the situation worse. Now you might be thinking of somehow encoding the branch predictor state in hardware. This runs into the issue of encoding microarchitecture in your hardware ISA. If you ever need to change microarchitecture, you face the dilemma of having to make a new, incompatible ISA, or emulating old microarchitectural details that no longer work well. MIPS got burned with this by delay slots. In general, the rule of thumb hardware designers use is "never expose your microarchitecture in your ISA." A related topic is the issue of memory size. Memory is relatively expensive compared to ALUs: we can stamp out more ALUs than we know how to fill. We have hit the limit of physics in sizing of our register files and L1 caches (electrons move at finite speed!), and the technologies we use to make them work quickly are also prohibitively power-hungry. This leads to the memory hierarchy of progressively larger, but cheaper and more efficient memories. The rule of thumb for performance engineers is that you count cycles only if you fit in L1 cache; otherwise, you're counting cache misses, since those cache misses will dwarf any cycle count savings you're likely to scrounge up.

0x09 6y ago

The article doesn't touch on this, but in C pointer types are also the only kind that can be invalidated without any apparent change to their value: void *x = malloc(...); free(x); if(x); // undefined behavior Note that this isn't about dereferencing x after free, which is understandably not valid. Rather the standard specifies that any use of the pointer's value itself is undefined after being used as an argument to free, even though syntactically free could not have altered that. This special behavior is also specifically applied to FILE* pointers after fclose() has been called on them. If there is some historical reason / architecture that could explain this part of the specification I would be interested to hear the rationale, this has been present in mostly the same wording since C89.

jcranmer 6y ago
My gut instinct is as follows: void *x = malloc(...); void *y = malloc(...); assert(x != y); // standard guarantees this [1] Yet it's fairly reasonable that: void *x = malloc(...); free(x); void *y = malloc(...); // malloc reused x's allocation here. So, in effect, guaranteeing that the results of two mallocs can never alias each other, while allowing the implementation to reuse freed memory, requires semantically adjusting the value of a pointer to a unique, unaddressable value. [1] I think, but I'm not sure which versions of C/C++ added this guarantee
- asveikau 6y ago
  I feel like you should not need to carve out extra language in the standard to explain this. It's very clear that following *x is undefined after free(x). It's also clear from any reasonable understanding of malloc that x's numeric value might collide with a later allocation coincidentally. Why should that make "if (x)" undefined? It's true that the result of "if (x == y)" would depend on coincidences lining up and you should not rely on either one. Calling any evaluation of x "undefined" seems much more extreme than that though.
  - jcranmer 6y ago
    At first glance, it does some like an unnecessarily gratuitous instance of undefined behavior. However... what could you actually meaningfully do with a pointer to freed memory anyways? You clearly can't dereference it. The only pointers you can compare it to are other pointers to the now-freed object (cross-object pointer comparisons are UB in C) and NULL. But if you were going to compare it to NULL, it's presumably to guard against a dereference, so you'd end up UB anyways if you didn't overwrite it to NULL in the first place, at which point it's not being compared with anything anymore.

saagarjha 6y ago

In addition to all the things mentioned above, there's also another kind of byte: structure padding. Nobody really knows how to deal with it, and it has extremely strange rules–it's kind of uninitialized in some cases, but you can give it a value sometimes…and sometimes you can't, or not in any way that sticks. It's truly strange stuff, and its exact nature is still being worked out.

nwmcsween 6y ago
Pack your structs to not have padding? The probable reason it sometimes works is purely how the compiler decides to do the copy. Anything that relies on implicit padding is horribly broken software.
- saagarjha 6y ago
  I think you might be misunderstanding my comment, I’m not complaining about struct padding causing issues in my code, I’m saying the standard is wishy-washy about it. This can be problematic when you are doing things like memcpying a structure, or trying to zero it out before sending it somewhere else. (And, FWIW, there is no standard way to disable struct padding, and doing so will likely generate slower code anyways.)
  - nwmcsween 6y ago
    How is the standard not explicit? copying with padding doesn't need to copy the padding at all or can if it's faster, memcpy is a intrinsic the compiler can copy whatever it deems wrt padding.
    - saagarjha 6y ago
      Because there are certain cases in C11 where padding can be legally observed because it is defined to be set to zero–brace initialization, for example. It is unclear what happens in this case when you do anything with the memory other than read it (for example, storing to a structure member, based on the current reading of the standard, may make padding indeterminate again–plus, is "memcpy" a "read"?). See here for some of the questions raised: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1793.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1793.pdf

stephc_int13 6y ago

I read the article and I am not convinced by the author arguments. He is talking about edge cases. I've been using C and C++ for over 20 years now, for both low level and high level stuff, and I never needed to know about those edge cases. And I think you don't want to know about them, you don't need to know about them to write good code. Nitpicking about edge cases tradeoffs made by compiler designers and language standards decades ago is like attacking under the belt, in my opinion.

pwdisswordfish4 6y ago
The point isn’t that anyone would want to write code like this. It’s to define rules that establish what the language implementation is allowed to assume about pointers when performing optimisations, and consequently, what operations code is allowed to perform without running into UB. The best way to study such rules is with edge cases like this. It’s like a trolley problem in a way. The situation may be unlikely, but better have an answer for it ready instead of replying ‘how dare you ask such questions’.
SubjectToChange 6y ago
Can you clarify what you disagree with in the article? The author wasn't saying programmers need to understand all the complexities of pointers to write good code, nor was he saying anything about the quality of those languages. Also, it is incredibility defensive to accuse the author of "attacking under the belt" when his observation wasn't aimed at any specific language.
- stephc_int13 6y ago
  From my opinion, this is a way to try and push the adoption of Rust by shading an unpleasant light on the current contender : C/C++ An other way to say is that this is propaganda.
  - steveklabnik 6y ago
    That doesn’t make sense, given: > Both parts of this statement are false, at least in languages with unsafe features like Rust or C: The two languages share these features, which is the whole reason this is being written in the first place.