3 ms·

How would this work for a hierarchical structure like a B-tree? Also: If, say, 30% of your system is pointers and you have them "spread all over the place", wo

How would this work for a hierarchical structure like a B-tree? Also: If, say, 30% of your system is pointers and you have them "spread all over the place", wouldn't moving are your pointers to a central location result in pointers "spread all over" two different places. "Cache oblivious" systems organize B-trees and related so related objects are close together in memory. It seems like a system with bits of things relating to each other scattered about would have to just use some ad-hoc similarity measure to minimize cache hits.

yellowapple 6y ago
You could encode the item's location in the tree into the handle itself, though this assumes that the tree will never be rebalanced while that handle remains active. This is basically (from what I understand) how hierarchal triangular meshes (HTM) works. The "coordinate" is a number describing the location of a coordinate's triangle within a larger triangle within a larger triangle within a larger triangle and so on until you get to an octahedron.
stephc_int13 6y ago
I don't like to use tree or linked-list, I prefer arrays and hash tables. I haven't found many problems that couldn't be solved with simple arrays or hash maps. Same thing about recursive functions, I never use them.
- chrisseaton 6y ago
  How would you for example represent a program in memory with simple arrays and hash maps, where most people would use a tree or graph?
  - stephc_int13 6y ago
    Do you mean an AST?
    - chrisseaton 6y ago
      AST, CST, CFG, DFG, PDG, or any other data structure for representing a program. But I can't imagine it being done with a simple array or a hash map. The all end in T or G! How would you approach that with your way of doing things? I guess if you work on game engines this is a relevant problem? Or if not maybe a graphics data structure like a BSP? How do you do that without trees? Or a NPC navigation data structure? How do you do that without graphs?
      - stephc_int13 6y ago
        BSP is a pretty outdated algorithm in the game engine space. I very often use spatial hashing instead of quad-trees or octrees. I rarely write interpreters but from memory a simple stack can go a long way. Scenes are stored as flat arrays of components (ECS style) Navigation (path finding) is very dependent on the internal level architecture, many tricks can be used to avoid trees or complex computations.
        codetrotter 6y ago
        Just wanted to say thank you for this comment. It led me to this paper http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf which introduced some new ideas to me alongside of concepts that I were familiar with so it’s been generally easy but useful reading so far :)
        chrisseaton 6y ago
        You probably know more than me but I don't really get how you can go from text source code to a stack without going through a tree or with recursion!
        stephc_int13 6y ago
        https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm
      - 6y ago
  - munchbunny 6y ago
    Sometimes a tree or graph really is the right way, but if you want memory locality, you could have an array of nodes and an array of edges that reference the nodes by index. That’s effectively what the author is proposing (pooling), rather than allocating all of the nodes and edges individually.
snicker7 6y ago
I don't think this advice is suppose to apply to /actual/ data structures. Rather, it applies to "business-logic objects" (e.g. video game entities or whatever).
psykotic 6y ago
> How would this work for a hierarchical structure like a B-tree? For something like B-trees you want to make a distinction between internal and external references. Internal references ("child pointers") can just be 32-bit indices into an array of fixed-size items (each the size of a cache line or a multiple thereof) or even naked pointers if you don't mind the inefficiency on 64-bit platforms. Depending on the requirements, external references are often best represented as some kind of handle with explicit registration. This is especially helpful if you need to manage the lifetime for persistent B-trees (where different trees can share subtrees) since the external reference handles serve as GC roots, so you require them to be explicitly registered while the internal references are owned by the B-tree heap and can therefore be direct while still being traceable or refcountable; this also works well for dealing with reclamation in a concurrent system. So, you almost always want to distinguish internal vs external references, and handles are primarily a solution candidate for external references.

yellowapple 6y ago

You could encode the item's location in the tree into the handle itself, though this assumes that the tree will never be rebalanced while that handle remains active. This is basically (from what I understand) how hierarchal triangular meshes (HTM) works. The "coordinate" is a number describing the location of a coordinate's triangle within a larger triangle within a larger triangle within a larger triangle and so on until you get to an octahedron.

stephc_int13 6y ago

I don't like to use tree or linked-list, I prefer arrays and hash tables. I haven't found many problems that couldn't be solved with simple arrays or hash maps. Same thing about recursive functions, I never use them.

chrisseaton 6y ago
How would you for example represent a program in memory with simple arrays and hash maps, where most people would use a tree or graph?
- stephc_int13 6y ago
  Do you mean an AST?
  - chrisseaton 6y ago
    AST, CST, CFG, DFG, PDG, or any other data structure for representing a program. But I can't imagine it being done with a simple array or a hash map. The all end in T or G! How would you approach that with your way of doing things? I guess if you work on game engines this is a relevant problem? Or if not maybe a graphics data structure like a BSP? How do you do that without trees? Or a NPC navigation data structure? How do you do that without graphs?
    - stephc_int13 6y ago
      BSP is a pretty outdated algorithm in the game engine space. I very often use spatial hashing instead of quad-trees or octrees. I rarely write interpreters but from memory a simple stack can go a long way. Scenes are stored as flat arrays of components (ECS style) Navigation (path finding) is very dependent on the internal level architecture, many tricks can be used to avoid trees or complex computations.
      - codetrotter 6y ago
        Just wanted to say thank you for this comment. It led me to this paper http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf which introduced some new ideas to me alongside of concepts that I were familiar with so it’s been generally easy but useful reading so far :)
      - chrisseaton 6y ago
        You probably know more than me but I don't really get how you can go from text source code to a stack without going through a tree or with recursion!
        stephc_int13 6y ago
        https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm
    - 6y ago
- munchbunny 6y ago
  Sometimes a tree or graph really is the right way, but if you want memory locality, you could have an array of nodes and an array of edges that reference the nodes by index. That’s effectively what the author is proposing (pooling), rather than allocating all of the nodes and edges individually.

snicker7 6y ago

I don't think this advice is suppose to apply to /actual/ data structures. Rather, it applies to "business-logic objects" (e.g. video game entities or whatever).

psykotic 6y ago

> How would this work for a hierarchical structure like a B-tree? For something like B-trees you want to make a distinction between internal and external references. Internal references ("child pointers") can just be 32-bit indices into an array of fixed-size items (each the size of a cache line or a multiple thereof) or even naked pointers if you don't mind the inefficiency on 64-bit platforms. Depending on the requirements, external references are often best represented as some kind of handle with explicit registration. This is especially helpful if you need to manage the lifetime for persistent B-trees (where different trees can share subtrees) since the external reference handles serve as GC roots, so you require them to be explicitly registered while the internal references are owned by the B-tree heap and can therefore be direct while still being traceable or refcountable; this also works well for dealing with reclamation in a concurrent system. So, you almost always want to distinguish internal vs external references, and handles are primarily a solution candidate for external references.