[Feature request] Rectangular packing for structs of arrays (SoA)
- Dominant language
- C++
- Stars
- 1.6k
- Forks
- 193
- Avg merge
- 22h 17m
- Merged PRs (30d)
- 26
Description
This idea has come up many times before:
- @pinobatch implemented [rectallocate.py](https://github.com/pinobatch/numism/blob/main/hike-gb/tools/rectallocate.py) to allocate arrays into a "shelf", and has previously cited "[Efficient Algorithms for 2-D Rectangle packing](https://cgi.csc.liv.ac.uk/~epa/)" ([Discord](https://discord.com/channels/303217943234215948/790920525253836912/881882186117177354)).
- @evie-calico was looking for help with a "page-based array of structs" ([Discord](https://discord.com/channels/303217943234215948/790920525253836912/881863274445029416)), which ISSOtm clarified can't yet be automatically done.
- Sono requested "sections with holes" to implement "structs in memory, but scattered" ([Discord](https://discord.com/channels/303217943234215948/303217943234215948/1338572583301546054)), which ISSOtm clarified as "2D packing".
- JoaoBapt requested "sparse sections" ([Discord](https://discord.com/channels/303217943234215948/790920525253836912/1350420525100433479)), which ax6 rephrased as "2D memory packing", prompting this issue to be created.
I'm citing those previous Discord chats because they discuss some of the possibilities for how such a thing could work, and highlight the pitfalls of doing so ("the two alternatives are a bodge or an over-complicated and over-specialized "correct" solution").
It's possible that RGBDS may never get a built-in solution to this problem: I too would like to avoid over-complicated and over-specialized solutions. And maybe there isn't one; "[structures of arrays](https://en.wikipedia.org/wiki/AoS_and_SoA)" / "[parallel arrays](https://en.wikipedia.org/wiki/Parallel_array)" rarely have built-in support even in high-level programming languages (with [Zig](https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-in-userland-40m0) being one example that does). This issue exists to iron out a sufficiently-general solution if possible (and just to record/remember that the user demand exists.)
Contributor guide
Research direction
Start by reading rectallocate.py and the linked discussions about shelf allocation, page-based arrays, sparse sections, and 2D memory packing. Compare the alternatives and constraints raised there; the work is done when the project has agreed on a sufficiently general approach, or documented that no built-in solution is appropriate.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100