[Feature request] Rectangular packing for structs of arrays (SoA) #1667
Comments
Rangi42
added
enhancement
|
Pino illustrated how rectallocate.py works (Discord):
|
|
With modern RGBASM, the row-by-row allocation can be simplified with a macro. You would still need a script to calculate how to pack rectangular arrays into a larger rectangular "shelf", e.g.: $ ./pack.py c080[16][64] wActors[12][24] wMapVicinity[16][16]
wActors: $c080
wMapVicinity: $c090but once that's done, you could hard-code the addresses in macro invocations: rect_array wMapVicinity, wram0, $c080, 16, 16, ""
rect_array wActors, wram0, $c090, 12, 24, """
.class:: db
.frame:: db
.timers:: ds 2
.dx:: dw
.x:: dw
.dy:: dw
.y:: dw
.facing:: db
.health:: db
"""Here's the macro being used: MACRO rect_array
; name, section type, [bank,] top-left address, num rows, row size, first row body
DEF rect_array_num_rows_arg_idx = _NARG - 2
DEF rect_array_row_size_arg_idx = _NARG - 1
REDEF rect_array_body EQUS \<_NARG>
for rect_array_row, \<rect_array_num_rows_arg_idx>
if _NARG == 7
section "\1 row {d:rect_array_row}", \2[(\4) + rect_array_row * $100], bank[\3]
else
section "\1 row {d:rect_array_row}", \2[(\3) + rect_array_row * $100]
endc
union
if rect_array_row == 0
\1::
{rect_array_body}
assert @ - \1 <= \<rect_array_row_size_arg_idx>
nextu
endc
\1.row{d:rect_array_row}::
ds \<rect_array_row_size_arg_idx>
endu
endr
ENDMThat generates these symbols: |
|
The other example, adapted to be in banked WRAMX: $ ./pack.py d040[16][64] wRed[12][32] wYellow[8][20] wGreen[6][24] wCyan[4][10] wBlue[3][16]
wRed: $d040
wYellow: $d060
wGreen: $d968
wCyan: $d074
wBlue: $dc58rect_array wRed, wramx, 2, $d040, 12, 32, ""
rect_array wYellow, wramx, 2, $d060, 8, 20, ""
rect_array wGreen, wramx, 2, $d968, 6, 24, ""
rect_array wCyan, wramx, 2, $d074, 4, 10, ""
rect_array wBlue, wramx, 2, $dc58, 3, 16, "" |
|
Theoretically the rectallocate.py algorithm could be implemented with RGBASM macros too, allowing usage like this: shelf wram0, $c080, 16, 128
rect wMapVicinity, 16, 16
rect wActors, 12, 24, """
.class:: db
.frame:: db
.timers:: ds 2
.dx:: dw
.x:: dw
.dy:: dw
.y:: dw
.facing:: db
.health:: db
"""
end_shelf
shelf wramx, 2, $d040, 16, 64
rect wRed, 12, 32
rect wYellow, 8, 20
rect wGreen, 6, 24
rect wCyan, 4, 10
rect wBlue, 3, 16
end_shelf |
|
I'm curious as to how a macro like that would sort the rectangles by decreasing row count before packing them into the top-aligned track (which grows from low to high addresses) and the bottom-aligned track (which grows from high to low addresses). |
|
Macros are Turing-complete. :3 I'd already implemented mergesort for a macro-pack solution to #67. |
This idea has come up many times before:
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" / "parallel arrays" rarely have built-in support even in high-level programming languages (with Zig 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.)
The text was updated successfully, but these errors were encountered: