We are now departing the land of type-checked programming. Thank you for understanding.
I want to flatten a deep tree of struct / struct-of-array / array-of-structs, being the data model of a game or simulation. In C, I suspect a deep struct tree lacking pointers would be allocated as a single chunk of memory, as per a pre-order DFS traversal, i.e. in order of members as written in the struct def.
Now, instead of letting structs define the memory layout, I want what to use something similar to structs (let's call them nested concepts) to exist only as a hierarchical representation of a program's concepts, but not dictating the memory layout.
We can then use custom indexing functions to decide the memory layout at runtime, without changing this hierarchical blueprint of concepts. User code also remains unchanged. We are only changing the order of data within a large array.
The reason is to be able do on-the-fly generation of a large variety of data layouts for a given program, and from these, select the best-performing for a given set of criteria. The data layout that emerges as the winner will be the one which most accurately reflects the type of data access which the program's instructions engage in.
(There exist cases where making copies of data to improve locality of reference, results in better performance, but for this question, we'll ignore this... maybe a future concern.)
Proposed Implementation
Custom indexing functions provide the memory layout for read and write, and this can be highly variable (see below). This is however automatable, and much less tedious than modifying structs by hand all the time -- never mind that every time we change structs, we also have to change struct accesses throughout the codebase.
Assuming(!) these indexing functions adhere to the same interface / function arguments signature, they are then switchable per run of the program, meaning we can test the performance of many different layouts without needing to change user code (game or simulation logic).
Consider a program precisely-defined in terms of its data and the exact number of members (primitives, structs and arrays) instantiable at runtime. It can thus pre-allocate a uniformly-typed array or buffer (sequence of bytes or words, in my case a massive buffer of signed 32-bit integers) big enough to accommodate any layout of its concepts (ignore padding, alignment for now).
Flattening can be achieved by a variety of indexing schemes, including but not limited to:
- linear 1D indexing
- row-major or column-major 2D, 3D etc.
- post or pre order DFS or BFS
- Morton or Hilbert curves
Flattening can also be partial, more on this below.
Naturally, choice of indexing method depends on the sorts of arrays involved at different depths within the overall data model:
- spatial data benefits from Hilbert curves.
- DFS or BFS when we want to preserve some specific walk ordering.
- arrays which don't benefit from a particular special ordering, use cheap linear indexing.
In the concepts definitions, we'd hint at the type of data involved, thereby selecting the ideal indexing scheme for each array.
(An obvious consequence of this method is that by foregoing regular old struct definition and access, we lose all type-checking when accessing the data in this flat buffer. Sobeit.)
Where I'm getting stuck: Flattening Schemes
Flattening, combinatorically, presents a challenge.
Flattening can be partial (semi-flattening). For example:
- One can truncate the tree to a certain depth from the bottom up: leaf structs and primitives are pulled from depth 4 to depth 3.
- One can splice/remove from the tree AT a certain depth, e.g. in a depth 4 tree with depths [0..3], we can assign everything at depth 2 up one level, to depth 1, thereby removing depth 2 entirely (why, I would't know, but it is logically possible.)
Furthermore, one can choose at every depth of the tree, whether arrays are to be allocated inline / interleaved within that "struct" or moved up one or more levels, or to the root.
What I need
Right now the above is the best way I can describe the jumble in my head with regards to potential implementation.
The relationship between indexing methods and flattening / interleaving is difficult to consider as a single, unified whole. Flattening could be considered another part of the indexing scheme, although not really... indexing is dynamic / handled at runtime in predictable way by a limited number of indexing functions, such as those mentioned above, which keep things at the same depth within the tree and simply decides their ordering within that "flat" sub-array. Whereas flattening is more about where (offset) in the overall array various sub-arrays (or struct or primitive members) start. One is dynamic, the other is more static, I'd tend to store the latter in a static offset table. So there seems to be a distinction here.
I need some kind of comprehensive guidance that allows me to systematically work through this problem, including which approaches are worth implementing in terms of flattening, and which aren't. This is especially true where we may do partial flattening, or where we have arrays existing at multiple depths (for example: graph -> nodes[] where each node also has -> neighbours[]), i.e. non-homogenous multi-dimensional arrays, where each dimension represents a different data type. It is conceivable that all nodes neighbours could be placed either into the graph's sub-array after the nodes or into the global array space. Which is more intelligent to do? Probably the former? Is this a matter of heuristics? Brute-force random selection aside, I feel as if only dynamic analysis of program instructions could propose "good" data layouts.
It's also not clear whether I'm blind to other sizeable aspects of this problem space? Please advise.