akbasic/tests/collision_perf.c

/**
 * @file collision_perf.c
 * @brief What the sprite collision scan costs, and what a frame costs beside it.
 *
 * This exists to settle one question with a number rather than an argument:
 * `akbasic_collision_service()` runs at the top of every interpreter *step*
 * (`src/runtime.c`), and the akgl frontend takes
 * #AKBASIC_FRONTEND_STEPS_PER_FRAME steps per rendered frame -- so a busy
 * program scans for collisions up to 256 times a frame, nearly always over
 * sprites that have not moved since the last scan. Whether that is worth
 * changing depends entirely on how the scan compares to the frame it sits
 * inside, and nobody had measured either.
 *
 * **The control row is the point.** A scan measured on its own is a number with
 * nothing to divide it by. `frame` renders what a real frame renders -- the
 * whole text grid and the sprites -- so the scan rows can be read as a fraction
 * of it. libakgl's own PERFORMANCE.md makes the same argument at length, and
 * records getting it wrong the first time by measuring queued work rather than
 * finished work.
 *
 * The harness is libakgl's, borrowed by include path rather than copied: it is
 * the house convention for a benchmark in these repositories, and a second copy
 * would be a fork.
 *
 * Labelled `perf` in CTest so `ctest -LE perf` skips it. Numbers taken at
 * `-O0`, which is what both checked-in build trees are, are not worth reading;
 * configure a RelWithDebInfo tree and run `AKGL_BENCH_SCALE=10 ctest -L perf`.
 * Budgets are report-only unless the build is optimised, which `benchutil.h`
 * enforces for exactly that reason.
 */

#include <string.h>

#include <SDL3/SDL.h>
#include <SDL3_ttf/SDL_ttf.h>

#include <akerror.h>

#include <akgl/error.h>
#include <akgl/game.h>
#include <akgl/heap.h>
#include <akgl/registry.h>
#include <akgl/renderer.h>
#include <akgl/text.h>

#include <akbasic/akgl.h>
#include <akbasic/error.h>
#include <akbasic/frontend.h>
#include <akbasic/runtime.h>
#include <akbasic/sink.h>
#include <akbasic/sprite.h>

#include "benchutil.h"

/** @brief The window a real program gets from the standalone frontend. */
#define TARGET_W	800
#define TARGET_H	600

static akbasic_Runtime RUNTIME;
static akbasic_TextSink SINK;
static akbasic_AkglSink SINKSTATE;
static akbasic_GraphicsBackend GRAPHICS;
static akbasic_AkglGraphics GRAPHICSSTATE;
static akbasic_SpriteBackend SPRITES;
static akbasic_AkglSprites SPRITESSTATE;
static TTF_Font *font = NULL;

/**
 * @brief Stand a runtime up on the real akgl devices and run @p source to completion.
 *
 * The akgl sink rather than the stdio one, because the control row has to render
 * the text layer and that is the only sink that draws.
 */
static akerr_ErrorContext AKERR_NOIGNORE *load(const char *source)
{
    PREPARE_ERROR(errctx);

    PASS(errctx, akbasic_sink_init_akgl(&SINK, &SINKSTATE, akgl_renderer, font,
					TARGET_W, TARGET_H));
    PASS(errctx, akbasic_runtime_init(&RUNTIME, &SINK));
    PASS(errctx, akbasic_graphics_init_akgl(&GRAPHICS, &GRAPHICSSTATE, akgl_renderer));
    PASS(errctx, akbasic_sprite_init_akgl(&SPRITES, &SPRITESSTATE, akgl_renderer, &GRAPHICSSTATE));
    PASS(errctx, akbasic_runtime_set_devices(&RUNTIME, &GRAPHICS, NULL, NULL, &SPRITES));
    PASS(errctx, akbasic_runtime_load(&RUNTIME, source));
    PASS(errctx, akbasic_runtime_start(&RUNTIME, AKBASIC_MODE_RUN));
    PASS(errctx, akbasic_runtime_run(&RUNTIME, 0));
    SUCCEED_RETURN(errctx);
}

/**
 * @brief A program defining @p n sprites, stacked or spread out.
 *
 * **Both arrangements are worth a row, and they measure different things.**
 * Stacked, every pair survives the bounding-box reject and pays for the
 * narrowphase -- the worst case the scan can be put in, and not a state a real
 * game sits in. Spread out, every pair is rejected on four comparisons, which is
 * what a game looks like on almost every frame. The gap between the two rows is
 * the prefilter earning its place, and libakgl's own table splits its overlap
 * and disjoint rows for the same reason.
 */
static void sprite_program(char *dest, size_t size, int n, bool stacked)
{
    char line[128];
    int i = 0;

    snprintf(dest, size,
	     "10 DIM P#(63)\n"
	     "20 FOR I# = 0 TO 62\n"
	     "30   P#(I#) = 255\n"
	     "40 NEXT I#\n");
    for ( i = 1; i <= n; i++ ) {
	/* 40 apart is wider than a 24x21 sprite, so no two boxes can touch. */
	int x = (stacked ? 20 : 20 + ((i - 1) * 40));

	snprintf(line, sizeof(line),
		 "%d SPRSAV P#, %d\n%d SPRITE %d, 1\n%d MOVSPR %d, %d, 20\n",
		 100 + (i * 10), i,
		 101 + (i * 10), i,
		 102 + (i * 10), i, x);
	strncat(dest, line, size - strlen(dest) - 1);
    }
}

/**
 * @brief Move sprite 1 a pixel, then scan. One full scan, no cache hit.
 *
 * The scan short-circuits when no sprite has moved since the last one, which is
 * what 255 of every 256 calls a frame do -- so a loop that only calls the scan
 * measures the short circuit and nothing else. Nudging a sprite first is what
 * makes a row mean "a scan that actually ran".
 */
static float32_t bench_nudge = 0.0f;

static akerr_ErrorContext AKERR_NOIGNORE *move_and_scan(uint16_t *mask)
{
    PREPARE_ERROR(errctx);

    bench_nudge = (bench_nudge > 0.5f ? 0.0f : 1.0f);
    PASS(errctx, SPRITES.move(&SPRITES, 1, 20.0 + (double)bench_nudge, 20.0));
    PASS(errctx, SPRITES.collisions(&SPRITES, mask));
    SUCCEED_RETURN(errctx);
}

/**
 * @brief The arrangement examples/breakout/sprites/breakout.bas actually has.
 *
 * Neither synthetic row is what that game looks like, and it is the most
 * demanding program in the repository. Two of its eight sprites are the *screen*
 * -- a captured HUD strip and a captured play field, installed as sprites because
 * a sprite is the one thing this interpreter draws for nothing -- so the field's
 * box covers everything and every moving sprite overlaps it permanently. The
 * bounding-box reject can never throw those pairs out, which puts this game
 * between the two synthetic rows rather than at the cheap end of them.
 */
static akerr_ErrorContext AKERR_NOIGNORE *bench_breakout_shaped(void)
{
    PREPARE_ERROR(errctx);
    akerr_ErrorContext *inner = NULL;
    uint16_t mask = 0;
    int iterations = bench_iterations(200000);
    int i = 0;

    PASS(errctx, load("10 GRAPHIC 1, 1\n"
		      "20 SSHAPE H$, 0, 0, 799, 59\n"
		      "30 SSHAPE F$, 0, 60, 799, 599\n"
		      "40 SSHAPE S$, 0, 0, 22, 22\n"
		      "50 SPRSAV H$, 1\n"
		      "60 SPRSAV F$, 2\n"
		      "70 SPRSAV S$, 3\n"
		      "80 SPRSAV S$, 5\n"
		      "90 SPRSAV S$, 6\n"
		      "100 SPRSAV S$, 7\n"
		      "110 SPRSAV S$, 8\n"
		      "120 FOR I# = 1 TO 8\n"
		      "130   SPRITE I#, 1\n"
		      "140 NEXT I#\n"
		      "150 MOVSPR 1, 0, 0\n"
		      "160 MOVSPR 2, 0, 60\n"
		      "170 MOVSPR 3, 300, 540\n"
		      "180 MOVSPR 5, 100, 300\n"
		      "190 MOVSPR 6, 400, 200\n"
		      "200 MOVSPR 7, 600, 400\n"
		      "210 MOVSPR 8, 200, 150\n"));

    bench_start("full scan, breakout's own layout", "call", 0.0);
    BENCH_LOOP(inner, i, iterations, move_and_scan(&mask));
    bench_stop((uint64_t)iterations);
    PASS(errctx, inner);

    /*
     * And the other path, on the same population: what the other 255 calls a
     * frame cost once the first has done the work. This row is the reason the
     * per-step cadence is affordable at all.
     */
    bench_start("cached scan, nothing moved", "call", 0.0);
    BENCH_LOOP(inner, i, iterations, SPRITES.collisions(&SPRITES, &mask));
    bench_stop((uint64_t)iterations);
    PASS(errctx, inner);
    SUCCEED_RETURN(errctx);
}

/** @brief Time the collision scan with @p n sprites live, stacked or spread. */
static akerr_ErrorContext AKERR_NOIGNORE *bench_scan(int n, bool stacked)
{
    PREPARE_ERROR(errctx);
    akerr_ErrorContext *inner = NULL;
    char source[4096];
    char name[64];
    uint16_t mask = 0;
    int iterations = bench_iterations(200000);
    int i = 0;

    memset(source, 0, sizeof(source));
    sprite_program(source, sizeof(source), n, stacked);
    PASS(errctx, load(source));

    snprintf(name, sizeof(name), "full scan, %d sprites, %s", n,
	     (stacked ? "all overlapping" : "spread out"));
    bench_start(name, "call", 0.0);
    BENCH_LOOP(inner, i, iterations, move_and_scan(&mask));
    bench_stop((uint64_t)iterations);
    PASS(errctx, inner);
    SUCCEED_RETURN(errctx);
}

/**
 * @brief What one rendered frame costs: the text layer, the sprites and a present.
 *
 * The denominator. This is the same sequence and the same order
 * `akbasic_frontend_akgl_pump()` runs, so the ratio the scan rows are read
 * against is a real one rather than an analogy.
 */
static akerr_ErrorContext AKERR_NOIGNORE *bench_frame(void)
{
    PREPARE_ERROR(errctx);
    akerr_ErrorContext *inner = NULL;
    char source[4096];
    int iterations = bench_iterations(300);
    int i = 0;

    memset(source, 0, sizeof(source));
    sprite_program(source, sizeof(source), 8, false);
    /* A screenful of text, so the sink renders what a real program's sink renders. */
    strncat(source,
	    "900 FOR R# = 0 TO 30\n"
	    "910   CHAR 1, 0, R#, \"THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG 0123456789\"\n"
	    "920 NEXT R#\n",
	    sizeof(source) - strlen(source) - 1);
    PASS(errctx, load(source));

    bench_start("one rendered frame, 8 sprites + text grid", "frame", 0.0);
    for ( i = 0; i < iterations; i++ ) {
	inner = akbasic_sink_akgl_render(&SINK);
	if ( inner != NULL ) {
	    break;
	}
	inner = akbasic_sprite_akgl_render(&SPRITES);
	if ( inner != NULL ) {
	    break;
	}
	if ( !SDL_RenderPresent(akgl_renderer->sdl_renderer) ) {
	    break;
	}
    }
    bench_stop((uint64_t)iterations);
    PASS(errctx, inner);
    SUCCEED_RETURN(errctx);
}

int main(void)
{
    PREPARE_ERROR(errctx);

    SDL_SetHint(SDL_HINT_VIDEO_DRIVER, "dummy");
    SDL_SetHint(SDL_HINT_RENDER_DRIVER, "software");

    ATTEMPT {
	CATCH(errctx, akgl_error_init());
	akgl_renderer = &akgl_default_renderer;

	FAIL_ZERO_BREAK(errctx, SDL_Init(SDL_INIT_VIDEO), AKGL_ERR_SDL,
			"Couldn't initialize SDL: %s", SDL_GetError());
	FAIL_ZERO_BREAK(errctx, TTF_Init(), AKGL_ERR_SDL,
			"Couldn't initialize SDL_ttf: %s", SDL_GetError());
	FAIL_ZERO_BREAK(errctx,
			SDL_CreateWindowAndRenderer("net/aklabs/akbasic/collision_perf",
						    TARGET_W, TARGET_H, 0,
						    &akgl_window, &akgl_renderer->sdl_renderer),
			AKGL_ERR_SDL, "Couldn't create window/renderer: %s", SDL_GetError());
	CATCH(errctx, akgl_render_2d_bind(akgl_renderer));
	CATCH(errctx, akgl_heap_init());
	CATCH(errctx, akgl_registry_init());
	akgl_camera = &akgl_default_camera;
	akgl_camera->x = 0.0f;
	akgl_camera->y = 0.0f;
	akgl_camera->w = (float)TARGET_W;
	akgl_camera->h = (float)TARGET_H;

	font = TTF_OpenFont(AKBASIC_TEST_FONT, 16);
	FAIL_ZERO_BREAK(errctx, font, AKGL_ERR_SDL,
			"Couldn't open %s: %s", AKBASIC_TEST_FONT, SDL_GetError());

	CATCH(errctx, bench_scan(0, false));
	CATCH(errctx, bench_scan(2, false));
	CATCH(errctx, bench_scan(4, false));
	CATCH(errctx, bench_scan(8, false));
	CATCH(errctx, bench_scan(8, true));
	CATCH(errctx, bench_breakout_shaped());
	CATCH(errctx, bench_frame());
	BENCH_REPORT_BREAK(errctx);
    } CLEANUP {
	if ( font != NULL ) {
	    TTF_CloseFont(font);
	}
	TTF_Quit();
	if ( akgl_window != NULL ) {
	    SDL_DestroyWindow(akgl_window);
	    akgl_window = NULL;
	}
	SDL_Quit();
    } PROCESS(errctx) {
    } HANDLE_DEFAULT(errctx) {
	LOG_ERROR_WITH_MESSAGE(errctx, "collision benchmark failed");
	return 1;
	/*
	 * FINISH_NORETURN rather than FINISH, matching src/main.c and
	 * tests/akgl_backends.c: FINISH expands a `return __err_context` that an
	 * int-returning function cannot compile even where the branch is dead.
	 */
    } FINISH_NORETURN(errctx);

    return 0;
}