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

[Rangi42]

This idea has come up many times before:

• @pinobatch implemented rectallocate.py to allocate arrays into a "shelf", and has previously cited "Efficient Algorithms for 2-D Rectangle packing" (Discord).
• @evie-calico was looking for help with a "page-based array of structs" (Discord), which ISSOtm clarified can't yet be automatically done.
• Sono requested "sections with holes" to implement "structs in memory, but scattered" (Discord), which ISSOtm clarified as "2D packing".
• JoaoBapt requested "sparse sections" (Discord), 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" / "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.)

[Rangi42]

Pino illustrated how rectallocate.py works (Discord):

I'm making a tool to generate a RAM map containing 2D arrays, such that h and l represent row and column coordinates. Optionally it can pack several arrays into a "shelf", or a larger rectangular area with rectangles along the top and bottom.

Given this specification

shelf c040-cf7f
  array wRed[12][32]
  array wYellow[8][20]
  array wGreen[6][24]
  array wCyan[4][10]
  array wBlue[3][16]

my tool produces an allocation with an ASCII art comment

[Rangi42]

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: $c090

but 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
ENDM

That generates these symbols:

00:c080 wMapVicinity
00:c080 wMapVicinity.row0
00:c090 wActors
00:c090 wActors.row0
00:c090 wActors.class
00:c091 wActors.frame
00:c092 wActors.timers
00:c094 wActors.dx
00:c096 wActors.x
00:c098 wActors.dy
00:c09a wActors.y
00:c09c wActors.facing
00:c09d wActors.health
00:c180 wMapVicinity.row1
00:c190 wActors.row1
00:c280 wMapVicinity.row2
00:c290 wActors.row2
00:c380 wMapVicinity.row3
00:c390 wActors.row3
00:c480 wMapVicinity.row4
00:c490 wActors.row4
00:c580 wMapVicinity.row5
00:c590 wActors.row5
00:c680 wMapVicinity.row6
00:c690 wActors.row6
00:c780 wMapVicinity.row7
00:c790 wActors.row7
00:c880 wMapVicinity.row8
00:c890 wActors.row8
00:c980 wMapVicinity.row9
00:c990 wActors.row9
00:ca80 wMapVicinity.row10
00:ca90 wActors.row10
00:cb80 wMapVicinity.row11
00:cb90 wActors.row11
00:cc80 wMapVicinity.row12
00:cd80 wMapVicinity.row13
00:ce80 wMapVicinity.row14
00:cf80 wMapVicinity.row15

[Rangi42]

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: $dc58

rect_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, ""

02:d040 wRed
02:d040 wRed.row0
02:d060 wYellow
02:d060 wYellow.row0
02:d074 wCyan
02:d074 wCyan.row0
02:d140 wRed.row1
02:d160 wYellow.row1
02:d174 wCyan.row1
02:d240 wRed.row2
02:d260 wYellow.row2
02:d274 wCyan.row2
02:d340 wRed.row3
02:d360 wYellow.row3
02:d374 wCyan.row3
02:d440 wRed.row4
02:d460 wYellow.row4
02:d540 wRed.row5
02:d560 wYellow.row5
02:d640 wRed.row6
02:d660 wYellow.row6
02:d740 wRed.row7
02:d760 wYellow.row7
02:d840 wRed.row8
02:d940 wRed.row9
02:d968 wGreen
02:d968 wGreen.row0
02:da40 wRed.row10
02:da68 wGreen.row1
02:db40 wRed.row11
02:db68 wGreen.row2
02:dc58 wBlue
02:dc58 wBlue.row0
02:dc68 wGreen.row3
02:dd58 wBlue.row1
02:dd68 wGreen.row4
02:de58 wBlue.row2
02:de68 wGreen.row5

[Rangi42]

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

[pinobatch]

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).

[Rangi42]

Macros are Turing-complete. :3 I'd already implemented mergesort for a macro-pack solution to #67.

[Rangi42]

Here's rectallocate.py adapted to assembly macros: https://pastebin.com/SW15S7R8

You specify a rectangular "shelf" at a fixed address to contain your rectangular arrays, then the macros handle packing those arrays into the shelf.

shelf WRAM0, $c080, 16, 128
    rect_array wMapVicinity, 16, 16
    rect_array 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_array wGreen,  6, 24
    rect_array wCyan,   4, 10
    rect_array wYellow, 8, 20
    rect_array wBlue,   3, 16
    rect_array wRed,   12, 32
end_shelf

If you pass any argument at the end (e.g. end_shelf 1), it will print the array definitions to stdout for inspection.

If this meets people's needs, I would probably clean it up, publish it, and close this issue as not planned.

[Rangi42]

To do, allow a shelf-less rect_array WRAM0, $c080, wMyArray, 16, 16 to just immediately declare that one array.

Edit: done, although the 6-arg case is ambiguous: https://pastebin.com/yBZMNqFY

[Rangi42]

Note that the actual packing of that five-color example shrinks the gap between the top and bottom tracks (basically like defragmenting):

[Rangi42]

Regarding the ambiguous 6-arg case for the rect_array macro, the problem is that 2 of the 8 possible args are optional: type[, bank], top-left address, name, height, width[, body]. When only one is specified, how to tell which?

I see three options:

1. Combine the bank with the type arg, separated by whitespace.
   For example: rect_array WRAMX 2, $abcd, ...
2. Combine the bank with the address arg, separated by a colon.
   For example: rect_array WRAMX, 2:$abcd, ...
   (This matches the .sym file format, sort of, but users might get confused and try $2:abcd.)
3. Check the type arg to see whether the bank is required (WRAMX, VRAM, or ROMX) or forbidden (all others).
   For example: rect_array WRAMX, 2, $abcd, ...
   (The problem is, this would not work for rect_array FOO, 2, $abcd, ... where DEF FOO EQUS "WRAMX". Maybe acceptable? It could also be problematic if linker options affect which section types must/cannot be banked.)