gbdev / gbdev/rgbds

[Feature request] Rectangular packing for structs of arrays (SoA)

Open
#1,667 12 comments 0 reactions 0 assignees View on GitHub
enhancement rgbasm rgblink
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.