Vuile Optimalisatiegeheimen (C voor Playdate)

Deze optimalisatietechnieken zijn vooral waardevol wanneer je zeer performante code probeert te schrijven voor zaken als emulators, grote simulaties (zoals een Factorio-achtige game), 3D-renderers, codecs, enzovoort.

1. Snelle CPU, trage Cache

Op basis van onderzoek van @StiNKz kan het model van de CPU van de Playdate als volgt worden gezien: het is een zeer snelle CPU, maar de toegang tot het geheugen is traag, vooral bij geheugen dat zich niet in de cache bevindt. Dit betekent dat als je code primair op registers opereert en niet constant grote hoeveelheden data laadt, deze waarschijnlijk razendsnel zal werken, zelfs bij veel loops en branch mis-predictions.

2. Instructiecache (Instruction Cache)

De -O3 compiler-vlag is niet noodzakelijkerwijs de snelste; -Os kan veel beter zijn. De Playdate heeft een kleine instructiecache (bij Rev A is dit slechts 4 kilobytes). Als je kerncode — bijvoorbeeld je emulator-interpreter loop, je fragment renderer of je physics engine — niet binnen deze 4 kilobytes past (voor Rev B is dit blijkbaar 16 KB), zal deze waarschijnlijk minder performant zijn dan code die sterker gecomprimeerd is (zelfs als die gecomprimeerde code meer CPU-operaties vereist).

Een voorbeeld uit de praktijk: om de prestaties van de Gameboy-emulatie te verbeteren, is de 20 KB grote emulator-core teruggebracht tot slechts 2 KB door een enorme switch table te verwijderen en deze te vervangen door compactere code met slechts enkele branches (en het gebruik van -Os). Het gedrag bleef identiek, maar de snelheid nam aanzienlijk toe.

Het is essentieel dat alleen de kerncode in deze 4 KB cache past. Zeldzame operaties (zoals opcodes die bijna nooit voorkomen of onwaarschijnlijke edge-cases in een simulatie) kunnen elders in het geheugen worden geplaatst.

Ideaal gezien wordt je kerncode door de linker op aaneengesloten adressen geplaatst. Dit kun je bereiken door attribute((section(".text.<jouw-sectie-naam-hier>"))) te gebruiken voor elke kernfunctie. Voor meer geavanceerde controle kun je een linker map gebruiken (zie volgende sectie).

3. Aangepaste Linker Map

Kopieer linkmap.ld uit de CAPI/buildsupport map naar je project en voeg de volgende regel toe aan je makefile voordat common.mk wordt geïncludeerd:

override LDSCRIPT=./link_map.ld

Hiermee kun je op een portable manier een aangepast linker-script gebruiken. Je kunt hiermee specificeren dat alle code uit bepaalde bestanden op specifieke plekken wordt geplaatst (ervan uitgaande dat je .o bestanden in build/ staan):

/* Custom code sectie (bijv. met __attribute__((section(".text.blah")))) */
*(.text.blah)

/* Alles uit foo.c */
build/foo.o(.text)
build/foo.o(.text.*)

/* Uitlijning op 32 bytes */
. = ALIGN(32);

/* Code die niet expliciet hierboven is genoemd */
*(.text)
*(.text.*)

4. Symbolen inspecteren

Gebruik het volgende commando om inzicht te krijgen in je symbolen:

nm Source/pdex.elf | sort > syms.txt

Dit genereert een lijst van alle symbolen (functies, variabelen, etc.) en hun bijbehorende adressen. Hiermee kun je eenvoudig controleren hoe groot je kerncode is en of deze in de icache past.

Voorbeeld van output (gedeelte):

00019361 t write_cart_ram_file /* <-- dit is een functie*/
00019420 t $d
00019440 t $t
00019441 t gb_error
000194dc t $d
00019500 t $t
00019501 t PGB_GameScene_menu
00019638 t $d
0001965c t $t
00019a04 t $d
00019a30 t $t
00019a31 T PGB_LibraryConfirmModal
00019a44 t $d
00019a50 t $t
00019a51 t gb_save_to_disk.isra.0
00019aa8 t $d
00019ac0 t $t
00019ac1 T __gb_write_vram
00019b10 t $t
00019b11 t PGB_GameScene_free
00019b9c t $d
00019bc0 t $t
00019bc1 T PGB_GameScene_new

5. DTCM-acceleratie

Er is een klein geheugengebied genaamd Tightly-Coupled Memory (TCM) dat sneller is dan normaal geheugen. De stack bevindt zich in het TCM-gebied. Objecten die op de stack zijn gealloceerd, zijn daarom over het algemeen sneller dan objecten op de heap of statische variabelen.

Als je gedurende een tijdje op een bepaalde struct opereert, kan het lonen om deze via memcpy naar de stack te kopiëren, daar de operaties uit te voeren, en hem vervolgens weer terug te kopiëren.

Voorbeeld:

// Langzaam:
long_operation(&global_var);

// Sneller:
some_type copy;
memcpy(&copy, &global_var, sizeof(global_var));
long_operation(&copy);
memcpy(&global_var, &copy, sizeof(global_var));

Om twee memcpy operaties te vermijden, zou je de variabele permanent op de stack kunnen laten leven. Omdat we geen controle hebben over main, kunnen we dit niet direct doen. Een workaround is om de variabele aan het andere uiteinde van de stack te plaatsen (het lage adres, het deel dat we normaal nooit bereiken, tenzij er een stack overflow optreedt).

Je kunt __builtinframeaddress(0) gebruiken in je eventHandler op kEventInit om het hoge-adres uiteinde van de stack te bepalen, en daar vervolgens iets minder dan 10 KB van aftrekken (0x2180 is veilig bevonden) om het lage uiteinde te bereiken.

Als je iets opslaat in dit lage gebied (de dtcmmempool), blijft dit behouden tussen updates door. Plaats een canary aan het begin en einde van de dtcmmempool en controleer deze minstens één keer per update om er zeker van te zijn dat een stack overflow de pool niet heeft corrupt gemaakt.

Andere delen van het geheugen bevinden zich ook in het TCM-gebied, zoals de framebuffer van de Playdate. Je kunt data daar plaatsen voor efficiënte toegang als je onvoldoende stackruimte hebt (houd er wel rekening mee dat deze data op het scherm verschijnt als je deze rendert).

6. ITCM-acceleratie

Naast data kunnen we ook code in de TCM plaatsen. Voor Rev B is het onduidelijk of dit versnelling oplevert, maar voor Rev A is het essentieel voor efficiënte Gameboy-emulatie.

Omdat de Playdate code niet automatisch in het TCM-gebied plaatst, moet je dit handmatig kopiëren vanuit .text. Definieer deze macro in C om functies te markeren die tot de ITCM-regio behoren:

#define _itcm __attribute__((section(".itcm"))) __attribute__((short_call))

Plaats _itcm voor een functiedefinitie om deze te markeren. Voeg vervolgens dit toe aan de linker map:

__itcm_start = .;
*(.itcm)
__itcm_end = .

Dit maakt twee symbolen beschikbaar in C: één aan het begin en één aan het einde van je .itcm code. Hiermee kun je de gehele .itcm code kopiëren naar een gewenste locatie (waaronder TCM).

Belangrijke aandachtspunten:

  • Zorg dat het adres waarnaar je kopieert congruent is aan het originele adres mod 2, omdat de Cortex M7 het laagste bit van een functiepointer gebruikt om aan te geven of de code Thumb of ARM is.
  • Je kunt niet direct vanuit een functieadres kopiëren, omdat het functieadres feitelijk 1 byte na het begin van de functie ligt.

Implementatievoorbeeld:

extern char __itcm_start, __itcm_end;
char dst_itcm_region[(uintptr_t)__itcm_end - (uintptr_t)__itcm_start];
memcpy(&dst_itcm_region, &__itcm_start, &__itcm_end - &__itcm_start);

// Roep de ITCM-kopie van de functie aan
((fn_ptr_t)((void*)some_itcm_fn - __itcm_start + dst_itcm_region))(args...);

Overige overwegingen:

  • Schakel -fPIC NIET in, omdat de relocatie-tabel het werk breekt wanneer code op deze manier wordt verplaatst.
  • Gebruik het shortcall attribuut voor .itcm code (zoals in de macro), zodat een ITCM-functie die een andere ITCM-functie aanroept een relatieve jump uitvoert.
  • Elke functie buiten de .itcm regio die door .itcm code wordt aangeroepen, moet worden gemarkeerd met attribute((longcall)) om een absolute jump te forceren.
  • Flush de icache na het wijzigen of kopiëren van code via de Playdate API.

7. De Prestatieloterij (Performance Lottery)

Bij het wijzigen van code kan het voorkomen dat sommige builds significant sneller zijn dan andere (soms wel 50%), zonder duidelijk patroon. Twee prominente oorzaken zijn cache misalignment en branch prediction tables.

Cache Misalignment

De cache line size is 32 bytes. Als een functie precies op een grens van 32 bytes begint, is dit optimaal. Als een functie echter over de grens van twee cache lines heen valt, is dit nadelig. Een kleine wijziging in de code kan ervoor zorgen dat alle volgende functies verschuiven, waardoor hun adressen niet langer optimaal zijn uitgelijnd.

Oplossingen:

  • Forceer af en toe een uitlijning van 32 bytes in C met attribute((aligned(32))) of in de linker map met . = ALIGN(32);.
  • In de linker map kun je handmatig een offset toevoegen, bijv: . = ALIGN(32); . += 0xC;.
  • Gebruik de compiler-optie -falign-loops=32 om loops uit te lijnen op 32 bytes.

Branch Prediction Tables

Op de Cortex M7 CPU is er vermoedelijk een tabel met voorspellingswaarden voor 1024 unieke instructie-adressen. Als twee if-statements een veelvoud van 1024 bytes uit elkaar liggen, kan de branch predictor ze als identiek behandelen, wat leidt tot veel mispredictions.

Oplossing: Verspreid in je linker map enkele . = ALIGN(1024); . += n; instructies, waarbij n een variabele waarde tussen 0 en 1024 is. Let op: dit kost extra ruimte, dus doe dit met mate.

8. Prefetching

Prefetching kan in theorie helpen in scenario's met indirectie (bijvoorbeeld bij het itereren door een lijst van pointers int** list). Mogelijkheden zijn:

  1. De hele lijst vooraf itereren en elk element list[n] prefetchen.
  2. list[i+1] prefetchen voordat list[i] wordt bezocht.

Gebruik voor het meten van de winst van prefetching een high-precision timer in plaats van de normale FPS-meter, aangezien de verbeteringen zeer subtiel kunnen zijn.

***

Aanvullende tips en implementaties

CMake implementatie voor Linker Map

Voor gebruikers van CMake kan de volgende aanpassing in $SDKPATH/CAPI/buildsupport/playdate.cmake worden gemaakt:

if(NOT GAME_LD_MAP)
    target_link_options(${PLAYDATE_GAME_DEVICE} PUBLIC -T${SDK}/C_API/buildsupport/link_map.ld)
else()
    target_link_options(${PLAYDATE_GAME_DEVICE} PUBLIC -T${GAME_LD_MAP})
endif()

En in de CMakeLists.txt:

if (EXISTS ${CMAKE_SOURCE_DIR}/src/link_map.ld)
    file(TO_NATIVE_PATH ${CMAKE_SOURCE_DIR}/src/link_map.ld GAME_LD_MAP_PATH)
    set(GAME_LD_MAP ${GAME_LD_MAP_PATH})
endif()

Opmerkingen over Delen (Division)

Er is gemeld dat integer-divisie op de Playdate traag kan zijn. In sommige gevallen kan het vervangen van integer-divisies door float-optellingen in een tight loop voor een aanzienlijke snelheidswinst zorgen.

Een mogelijke verklaring hiervoor is niet alleen de snelheid van de operatie zelf, maar ook register allocation. De ARM CPU heeft een beperkt aantal integer-registers; door over te stappen naar floats (die eigen registers hebben), kunnen waardevolle register-slots worden vrijgemaakt.