4 ms·

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 yo

by 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
      If you thought I was hustling something-oriented design, you missed the point. And, if you think that a type system can be no help with some family of data structures, it can only because you are unfamiliar with powerful type systems. Rust coders rely on the compiler to protect them from themselves. C++ coders rely on the type system and libraries in the same way. The language is powerful enough to enable building libraries that can only be used correctly; or that it is much more work to use incorrectly, so no one is tempted.

by ncmncm 4y ago

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
    If you thought I was hustling something-oriented design, you missed the point. And, if you think that a type system can be no help with some family of data structures, it can only because you are unfamiliar with powerful type systems. Rust coders rely on the compiler to protect them from themselves. C++ coders rely on the type system and libraries in the same way. The language is powerful enough to enable building libraries that can only be used correctly; or that it is much more work to use incorrectly, so no one is tempted.