3 ms·

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 lo

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
    I think you didn't get the point. Data structure choices are dictated by requirements. The type system doesn't demand pointers. When the type system accurately represents relationships, there is no need for users of a data structure to be careful to obey rules. Operations that compile at all are correct by construction. (Anything-oriented design is code smell.) Any "fragmentation issue" is off-topic: if something is an "issue", you do something differently so it isn't anymore.
    - the-lazy-guy 4y ago
      > When the type system accurately represents relationships, there is no need for users of a data structure to be careful to obey rules. Of course. Unfortunately sticking everything into an array and pointing to things via integers instead of raw pointers doesn't provide you any help from typesystem. My whole point is that there is a huge class of datastructures and algorithms which can not be reperented in a type-safe way without automatic manual memory management. You either have to be accurate when writing your algorithms, or introduce runtime costs for validity checks. You get pretty much 0 support from your compiler (for imperative language without GC) if you are not dealing with hierarchical datastructure without backreferences. It does not really matter how you reperesent it. No language can model that at type level. You can either encapsulate it into some abstraction and prove (and/or hope) that it is implemented correctly. This is a common way to approach the problem of type-system no helping you (for example, pretty much all foundational Rust libraries are unsafe underneath to get around borrow checker; STL in C++ lives and breathes with raw pointers in the implementation of succint datastructures like maps, etc). If you can't encapsulate it fully, you try to be accurate OR use some helpers to deal with the complexity (shared and weak ptr, this raw_ptr that article is talking etc). > Any "fragmentation issue" is off-topic: if something is an "issue", you do something differently so it isn't anymore. You were selling pushing everything into an array as a solution to not using pointers. I tried to give an example why this might be not the solution that you want. Specifically in browsers. > (Anything-oriented design is code smell.) Data-oriented design is a name for what you were proposing, I just brought it up for easier reference of your point. I.e. Modelling your data as a set of tables with relations between them.

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
  I think you didn't get the point. Data structure choices are dictated by requirements. The type system doesn't demand pointers. When the type system accurately represents relationships, there is no need for users of a data structure to be careful to obey rules. Operations that compile at all are correct by construction. (Anything-oriented design is code smell.) Any "fragmentation issue" is off-topic: if something is an "issue", you do something differently so it isn't anymore.
  - the-lazy-guy 4y ago
    > When the type system accurately represents relationships, there is no need for users of a data structure to be careful to obey rules. Of course. Unfortunately sticking everything into an array and pointing to things via integers instead of raw pointers doesn't provide you any help from typesystem. My whole point is that there is a huge class of datastructures and algorithms which can not be reperented in a type-safe way without automatic manual memory management. You either have to be accurate when writing your algorithms, or introduce runtime costs for validity checks. You get pretty much 0 support from your compiler (for imperative language without GC) if you are not dealing with hierarchical datastructure without backreferences. It does not really matter how you reperesent it. No language can model that at type level. You can either encapsulate it into some abstraction and prove (and/or hope) that it is implemented correctly. This is a common way to approach the problem of type-system no helping you (for example, pretty much all foundational Rust libraries are unsafe underneath to get around borrow checker; STL in C++ lives and breathes with raw pointers in the implementation of succint datastructures like maps, etc). If you can't encapsulate it fully, you try to be accurate OR use some helpers to deal with the complexity (shared and weak ptr, this raw_ptr that article is talking etc). > Any "fragmentation issue" is off-topic: if something is an "issue", you do something differently so it isn't anymore. You were selling pushing everything into an array as a solution to not using pointers. I tried to give an example why this might be not the solution that you want. Specifically in browsers. > (Anything-oriented design is code smell.) Data-oriented design is a name for what you were proposing, I just brought it up for easier reference of your point. I.e. Modelling your data as a set of tables with relations between them.