PR #25687 opened by romainhedouin URL: https://code.ffmpeg.org/FFmpeg/FFmpeg/pulls/25687 Patch URL: https://code.ffmpeg.org/FFmpeg/FFmpeg/pulls/25687.patch
compute_default_clut() recomputed every candidate's score from scratch each time it added a color to the list. Keep the scores in an array and add only the new color's contribution. The output is unchanged. master is O^3 this PR is O^2 The result is byte-identical on 11.1M test bitmaps (exhaustive tiny ones, random sets of 1 to 256 colors, ties, regions up to 1920x1080). I've tested both with clang and GCC 16. Time per call of compute_default_clut(): | region | colors | before | after | speedup | |---|---|---|---|---| | 100x50 | 4 | 216 us | 31 us | 6.9x | | 100x50 | 16 | 638 us | 29 us | 22x | | 100x50 | 256 | 4.86 ms | 79 us | 61x | | 720x576 | 4 | 2.53 ms | 2.37 ms | 1.1x | | 720x576 | 16 | 2.63 ms | 2.02 ms | 1.3x | | 720x576 | 256 | 6.76 ms | 1.99 ms | 3.4x | Whole decode, same stream decoded repeatedly in one process: | stream | CPU before | CPU after | RAM before | RAM after | |---|---|---|---|---| | FATE sample, -compute_clut 1 (90 passes) | 2.10 s | 0.83 s | 7.82 MiB | 7.85 MiB | | FATE sample, default option (800 passes) | 1.77 s | 1.77 s | 7.91 MiB | 7.93 MiB | | 4-bit, 5 colors, no CLUT (190 passes) | 1.89 s | 1.54 s | 7.87 MiB | 7.48 MiB | | 4-bit, 16 colors, no CLUT (180 passes) | 1.95 s | 1.05 s | 7.49 MiB | 7.52 MiB | | 8-bit, 256 colors, no CLUT (60 passes) | 2.06 s | 0.32 s | 7.81 MiB | 7.65 MiB | Noticed during a review sweep of ffmpeg using an LLM. Signed-off-by: romainhedouin <[email protected]> <!-- If this PR requires new FATE test samples, attach them to the PR and list their target paths below (relative to the fate-suite root). Attached filenames must match the sample's filename: ```fate-samples # e.g. vorbis/new-sample.ogg ``` --> >From 95d898cb5eadc21b9bf21884556b11cda751748d Mon Sep 17 00:00:00 2001 From: romainhedouin <[email protected]> Date: Mon, 2 Nov 2026 01:15:39 +0100 Subject: [PATCH] avcodec/dvbsubdec: compute the clut scores incrementally compute_default_clut() recomputed the score of every candidate from scratch, summing over all 256 colours, each time a colour was added to the list: up to 256 * 256 * 256 multiply-adds per region. Keep the scores and add the contribution of the new colour instead. The output is unchanged. Noticed during a review sweep of ffmpeg using an LLM. Signed-off-by: romainhedouin <[email protected]> --- libavcodec/dvbsubdec.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/libavcodec/dvbsubdec.c b/libavcodec/dvbsubdec.c index 0256e8355d7..2426da896d1 100644 --- a/libavcodec/dvbsubdec.c +++ b/libavcodec/dvbsubdec.c @@ -673,6 +673,7 @@ static void compute_default_clut(DVBSubContext *ctx, uint8_t *clut, AVSubtitleRe uint8_t list[256] = {0}; uint8_t list_inv[256]; int counttab[256] = {0}; + int scoretab[256]; int (*counttab2)[256] = ctx->clut_count2; int count, i, x, y; ptrdiff_t stride = rect->linesize[0]; @@ -699,18 +700,15 @@ static void compute_default_clut(DVBSubContext *ctx, uint8_t *clut, AVSubtitleRe for (i = 0; i<256; i++) { counttab2[i+1][i] = 0; } + memcpy(scoretab, counttab2[0], sizeof(scoretab)); for (i = 0; i<256; i++) { int bestscore = 0; int bestv = 0; for (x = 0; x < 256; x++) { - int scorev = 0; + int scorev = scoretab[x]; if (list[x]) continue; - scorev += counttab2[0][x]; - for (y = 0; y < 256; y++) { - scorev += list[y] * counttab2[y+1][x]; - } if (scorev) { int score = 1024LL*scorev / counttab[x]; @@ -724,6 +722,8 @@ static void compute_default_clut(DVBSubContext *ctx, uint8_t *clut, AVSubtitleRe break; list [ bestv ] = 1; list_inv[ i ] = bestv; + for (x = 0; x < 256; x++) + scoretab[x] += counttab2[bestv+1][x]; } count = FFMAX(i - 1, 1); -- 2.54.0 _______________________________________________ ffmpeg-devel mailing list -- [email protected] To unsubscribe send an email to [email protected]
