4 ms·

Probably, you rarely see these errors because you have never been a part of team making a comparably complex system which is used literally by billions of peopl

Probably, you rarely see these errors because you have never been a part of team making a comparably complex system which is used literally by billions of people and being exploited by multiple hackers. Also trying to implement certain algorithms and datastructures _efficiently_ often unfortunately calls for raw pointers. And writing the most used web browser certainly calls for trying to optimize things. If you think differently, please tell me how you would implement something as simple as a mutable tree, where each knows about it's parent.

ncmncm 4y ago
There is a substantive difference between "rarely" and "never". The principle about trees, if you must use one -- they are very slow to walk -- is that you either use it, or mutate it, not both at the same time. Generally, instead of pointers to nodes as native objects, it is much better to have all the nodes in a more array-like container, and represent edges with indices. Then none own any others, and you can visit all the nodes, if you must, without following any edges at all. (Graphs, likewise.) You might keep all the nodes with one property in one vector, and the rest in a different one. If they have some unique identifier, that could be their index. Doing whatever your freshman Data Structures class taught, forever, is no way to code for a multi-billion dollar company.
- notacoward 4y ago
  > no way to code for a multi-billion dollar company ...because people coding for multi-billion dollar companies usually need to deal with concurrency if not outright parallelism. So people working at such companies don't code like first-year CS students (avoiding the sexist term) under an outdated curriculum. The real way to fail in that kind of environment is to keep giving advice suited only to a now-purely-pedagogical model of computation as a single sequential stream.
  - ncmncm 4y ago
    > "avoiding the sexist term" Sexist term... "freshman"? You reveal that you had no intention of engaging honestly.
    - deleted 4y ago
      [deleted]
    - deleted 4y ago
      [deleted]
- the-lazy-guy 4y ago
  Thanks for the excursion into data oriented design. Now think about the fact that API provided by browser to JS is actually stateful. And you have to make a lot of things mutable. That is an external constraint that a lot of things in the browser world are formulated as a mutable OO-model. Also think about the fact that storing everything in a vector means that you get a massive fragmentation issues if your use pattern (which is dictated by actual downloaded content) for some reason requires allocating N items and then freeing 0.9N. Also think about the fact that whenever your array overflows and you need to resize it, you have to a) make a massive allocation from the OS, which might be quite janky because large allocations usually incur context switch + TLB misses for new pages b) you temporary use 2x memory. Also note the fact that if you reference everything by index, you effecitevly have a raw pointer. The only win here is that it is guaranteed to point to the right kind of memory, but you may very well reference a newely allocated node in the same spot. It is easy to preach "the right" approach until you meet real world.
  - ncmncm 4y ago
    The win is that one entity owns all the nodes, and does not need to follow edges to manage them. Edges are just edges; what else you imagine about them is on you. (CS grads do love their pointers!) If size varies much, a deque-like structure would work better than a naïve vector. You can always do the dumb thing if you are in a hurry, but then you have a dumb thing.
    - the-lazy-guy 4y ago
      I think you didn't get the point. If you represent references between objects as integers, you are back to having no help from compiler in case you keep a reference (index) longer than the object exists in a sensible state. This works fine for immutable data structures where you usually can ensure that you have no dangling references at build time. With mutable data structures you are back to use-after-free if you are not accurate. This time no sanitizer will help you to detect it. Now you have to invent some smart pointers to help you (like the MiraclePtr described in the article). The fact that all objects are owned by the same holder doesn't help you at all. Deque-like data-structure obviously has 2 memory references on each access instead of one with regulare pointers or with indices into a vectos. Didn't you want to have a more efficient datastructure? You didn't address the fragmentation issue either. Just to clarify things: I am not saying that using data oriented design is bad in any way. I am saying that proposal to use it specifically to prevent memory issues in self-referential mutable data-structures is nonsense.

ncmncm 4y ago

There is a substantive difference between "rarely" and "never". The principle about trees, if you must use one -- they are very slow to walk -- is that you either use it, or mutate it, not both at the same time. Generally, instead of pointers to nodes as native objects, it is much better to have all the nodes in a more array-like container, and represent edges with indices. Then none own any others, and you can visit all the nodes, if you must, without following any edges at all. (Graphs, likewise.) You might keep all the nodes with one property in one vector, and the rest in a different one. If they have some unique identifier, that could be their index. Doing whatever your freshman Data Structures class taught, forever, is no way to code for a multi-billion dollar company.

notacoward 4y ago
> no way to code for a multi-billion dollar company ...because people coding for multi-billion dollar companies usually need to deal with concurrency if not outright parallelism. So people working at such companies don't code like first-year CS students (avoiding the sexist term) under an outdated curriculum. The real way to fail in that kind of environment is to keep giving advice suited only to a now-purely-pedagogical model of computation as a single sequential stream.
- ncmncm 4y ago
  > "avoiding the sexist term" Sexist term... "freshman"? You reveal that you had no intention of engaging honestly.
  - deleted 4y ago
    [deleted]
  - deleted 4y ago
    [deleted]
the-lazy-guy 4y ago
Thanks for the excursion into data oriented design. Now think about the fact that API provided by browser to JS is actually stateful. And you have to make a lot of things mutable. That is an external constraint that a lot of things in the browser world are formulated as a mutable OO-model. Also think about the fact that storing everything in a vector means that you get a massive fragmentation issues if your use pattern (which is dictated by actual downloaded content) for some reason requires allocating N items and then freeing 0.9N. Also think about the fact that whenever your array overflows and you need to resize it, you have to a) make a massive allocation from the OS, which might be quite janky because large allocations usually incur context switch + TLB misses for new pages b) you temporary use 2x memory. Also note the fact that if you reference everything by index, you effecitevly have a raw pointer. The only win here is that it is guaranteed to point to the right kind of memory, but you may very well reference a newely allocated node in the same spot. It is easy to preach "the right" approach until you meet real world.
- ncmncm 4y ago
  The win is that one entity owns all the nodes, and does not need to follow edges to manage them. Edges are just edges; what else you imagine about them is on you. (CS grads do love their pointers!) If size varies much, a deque-like structure would work better than a naïve vector. You can always do the dumb thing if you are in a hurry, but then you have a dumb thing.
  - the-lazy-guy 4y ago
    I think you didn't get the point. If you represent references between objects as integers, you are back to having no help from compiler in case you keep a reference (index) longer than the object exists in a sensible state. This works fine for immutable data structures where you usually can ensure that you have no dangling references at build time. With mutable data structures you are back to use-after-free if you are not accurate. This time no sanitizer will help you to detect it. Now you have to invent some smart pointers to help you (like the MiraclePtr described in the article). The fact that all objects are owned by the same holder doesn't help you at all. Deque-like data-structure obviously has 2 memory references on each access instead of one with regulare pointers or with indices into a vectos. Didn't you want to have a more efficient datastructure? You didn't address the fragmentation issue either. Just to clarify things: I am not saying that using data oriented design is bad in any way. I am saying that proposal to use it specifically to prevent memory issues in self-referential mutable data-structures is nonsense.