5 ms·

Except for the fact that one leads to undefined behavior and the other doesn't. This is a massive difference.

bombela 1y ago
This might not seem obvious. So allow me an attempt at expanding a bit. The difference is that a dangling raw pointer to the heap will point to anything that can be modified at any time. But indexing a dynamic array guarantees that every elements is always well formed and safe to use.
- loeg 1y ago
  It's true that the array approach cannot suffer from type confusion.
loeg 1y ago
Non-UB data structure corruption and other incorrect behavior isn't like, super obviously better than UB corruption and other incorrect behavior.
- conradludgate 1y ago
  The obvious upside is that it's so much easier to debug when there's no UB. Debugging UB is never enjoyable.
  - deleted 1y ago
    [deleted]
  - jpc0 1y ago
    It’s pretty common to implement graphs in terms of arrays, not because of indices but because of cache locality. So your “UB” and “non-UB” code would look effectively identical to the CPU and would take the same amount of debugging. The reality is whether an index was tombstones and referenced or “deallocated” and referenced it is still a programmer fault that is a bug that the compiler could not catch
    - IshKebab 1y ago
      > So your “UB” and “non-UB” code would look effectively identical to the CPU and would take the same amount of debugging. Said the person who has never had to debug serious UB...
  - loeg 1y ago
    The practical ramifications are often similar, even if UB can in theory do anything.
  - nullc 1y ago
    not sure I agree. UB has the benefit that there are a lot of tools like valgrind, memcheck, and various compiler features to detect it both statically and at runtime. And when you hit UB it is certainly an error. Non-UB errors have no such powerful tools, only what application specific tests or assertions you create. I've seen plenty of cases where people went and turned signed types into unsigned because signed overflow is undefined, but it had the real effect of turning easily detected and diagnosed issues into much harder to find bugs.
    - loeg 1y ago
      Also like, it's not universally true that UB bugs (broad class of problems) are all harder to debug than non-UB bugs (another broad class of problems). Null pointer dereferences are UB, and among the easiest class of problem to debug.
- burntsushi 1y ago
  Ummm. Yeah it is. I'm sure you can come up with some cases where the impact of the bugs is roughly equivalent, but generally speaking, UB is a terrible class of bug. For example, if the aho-corasick crate accidentally tries to look up a dangling state node, you'll get a panic. But if this were UB instead, that could easily lead to a security problem or just pretty much anything... because behavior is undefined. So generally speaking, yes, this is absolutely a major difference and it matters in practice. You even have other people in this thread saying this technique is used in C for this exact reason. Leaving out this very obvious difference and pretending like these are the same thing is extremely misleading.
  - jakobnissen 1y ago
    Author here. In scientific computing, there isn't much of a security implication of UB, and the most dangerous kind of error are when your program silently computes the wrong thing. And that is especially likely when you use indices manually. You could say that UB enables all behaviour, including silently wrong answers, and you'd be right. But it's more likely to crash your program and therefore be caught. Most importantly, the comparison to a raw pointer is not relevant. My blog post states that integers come with zero safety (as in: preventing bugs, not risk of UB) and zero language support and that is true. My blog post compares Rust with GC languages, not with raw pointer arithmetic. And it's clear that, when you compare to using GC references, manual indices are horribly unsafe.
    - zozbot234 1y ago
      For the record, I completely agree that using GC is appropriate for problems that deal with possibly-cyclic general graphs, and maybe even wrt. DAG structures whenever one wishes to maximize throughput and the use of simpler refcounting would involve heavy overhead. (This is a well-known pitfall wrt. languages like Swift, that enforce pervasive use of atomic reference counting.) Since the use of "pluggable" GC in C-like or Rust-like languages is still uncommon, this generally means resorting to a language which happens to inherently rely on GC, such as Golang.
    - burntsushi 1y ago

This might not seem obvious. So allow me an attempt at expanding a bit. The difference is that a dangling raw pointer to the heap will point to anything that can be modified at any time. But indexing a dynamic array guarantees that every elements is always well formed and safe to use.

loeg 1y ago
It's true that the array approach cannot suffer from type confusion.

loeg 1y ago

Non-UB data structure corruption and other incorrect behavior isn't like, super obviously better than UB corruption and other incorrect behavior.

conradludgate 1y ago
The obvious upside is that it's so much easier to debug when there's no UB. Debugging UB is never enjoyable.
- deleted 1y ago
  [deleted]
- jpc0 1y ago
  It’s pretty common to implement graphs in terms of arrays, not because of indices but because of cache locality. So your “UB” and “non-UB” code would look effectively identical to the CPU and would take the same amount of debugging. The reality is whether an index was tombstones and referenced or “deallocated” and referenced it is still a programmer fault that is a bug that the compiler could not catch
  - IshKebab 1y ago
    > So your “UB” and “non-UB” code would look effectively identical to the CPU and would take the same amount of debugging. Said the person who has never had to debug serious UB...
- loeg 1y ago
  The practical ramifications are often similar, even if UB can in theory do anything.
- nullc 1y ago
  not sure I agree. UB has the benefit that there are a lot of tools like valgrind, memcheck, and various compiler features to detect it both statically and at runtime. And when you hit UB it is certainly an error. Non-UB errors have no such powerful tools, only what application specific tests or assertions you create. I've seen plenty of cases where people went and turned signed types into unsigned because signed overflow is undefined, but it had the real effect of turning easily detected and diagnosed issues into much harder to find bugs.
  - loeg 1y ago
    Also like, it's not universally true that UB bugs (broad class of problems) are all harder to debug than non-UB bugs (another broad class of problems). Null pointer dereferences are UB, and among the easiest class of problem to debug.
burntsushi 1y ago
Ummm. Yeah it is. I'm sure you can come up with some cases where the impact of the bugs is roughly equivalent, but generally speaking, UB is a terrible class of bug. For example, if the aho-corasick crate accidentally tries to look up a dangling state node, you'll get a panic. But if this were UB instead, that could easily lead to a security problem or just pretty much anything... because behavior is undefined. So generally speaking, yes, this is absolutely a major difference and it matters in practice. You even have other people in this thread saying this technique is used in C for this exact reason. Leaving out this very obvious difference and pretending like these are the same thing is extremely misleading.
- jakobnissen 1y ago
  Author here. In scientific computing, there isn't much of a security implication of UB, and the most dangerous kind of error are when your program silently computes the wrong thing. And that is especially likely when you use indices manually. You could say that UB enables all behaviour, including silently wrong answers, and you'd be right. But it's more likely to crash your program and therefore be caught. Most importantly, the comparison to a raw pointer is not relevant. My blog post states that integers come with zero safety (as in: preventing bugs, not risk of UB) and zero language support and that is true. My blog post compares Rust with GC languages, not with raw pointer arithmetic. And it's clear that, when you compare to using GC references, manual indices are horribly unsafe.
  - zozbot234 1y ago
    For the record, I completely agree that using GC is appropriate for problems that deal with possibly-cyclic general graphs, and maybe even wrt. DAG structures whenever one wishes to maximize throughput and the use of simpler refcounting would involve heavy overhead. (This is a well-known pitfall wrt. languages like Swift, that enforce pervasive use of atomic reference counting.) Since the use of "pluggable" GC in C-like or Rust-like languages is still uncommon, this generally means resorting to a language which happens to inherently rely on GC, such as Golang.
  - burntsushi 1y ago