[FFmpeg-devel] [EXTERNAL] Re: [PATCH] Boost FPS and performance: Optimize vertical loop for cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]
Chitra Dey Sarkar
Chitra.Dey at microsoft.com
Wed May 14 20:42:23 EEST 2025
-----Original Message-----
From: Michael Niedermayer <michael at niedermayer.cc>
Sent: Wednesday, May 14, 2025 9:40 AM
To: FFmpeg development discussions and patches <ffmpeg-devel at ffmpeg.org>
Cc: Chitra Dey Sarkar <Chitra.Dey at microsoft.com>
Subject: [EXTERNAL] Re: [FFmpeg-devel] [PATCH] Boost FPS and performance: Optimize vertical loop for cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]
Hi Chitra
On Wed, May 14, 2025 at 03:55:59AM +0000, Chitra Dey Sarkar via ffmpeg-devel wrote:
> Original Implementation:
> ---------------------------------
> In the original implementation, the "VER_SD" section processes image data stored in *data using strided memory access in a vertical fashion This leads to inefficient memory access patterns and cache thrashing due to non-sequential data access across multiple inner loops.
>
> Proposed Refactor:
> ---------------------------------
> The proposed refactor replaces this by allocating a cache-friendly 2D array buffer. This change eliminates strided memory access across the three inner loops, significantly improving cache locality and reducing cache thrashing.
>
> Additionally, the data is transposed outside the lp loop, which allows for efficient per-line access and write-back to the l buffer, further optimizing performance.
>
> Performance improvements
> -------------------------------------------------------
> This change results in a substantial performance improvement Sharing
> the FPS data benchmarked on our end for the file 'Tears of Steel'
> using HandBrake
>
> Device / CPU Model Official FPS Optimized FPS % Improvement
> Surface Laptop 11 (10-core X1P64100, L2: 36MB) 3.18 6.15 +93%
> Surface Laptop 11(10-core X1P64100, L2: 36MB) 5.16 7.31 +41%
> Surface Laptop 11 (10-core X1P64100, L2: 36MB) 5.57 9.21 +65%
> AMD Ryzen + NVIDIA RTX 4060 Laptop (12C/24T) 9.97 11.22 +12%
> Mac Mini Apple M4 Chip 9.00 12.00 +30%
>
> ----------------------------------------------------------------------
> ---------------------------------
> ---
> libavcodec/jpeg2000dwt.c | 72
> +++++++++++++++++++++++++++++++---------
> 1 file changed, 57 insertions(+), 15 deletions(-)
>
> diff --git a/libavcodec/jpeg2000dwt.c b/libavcodec/jpeg2000dwt.c index
> 9ee8122658..45d7897893 100644
> --- a/libavcodec/jpeg2000dwt.c
> +++ b/libavcodec/jpeg2000dwt.c
> @@ -409,6 +409,15 @@ static void dwt_decode97_float(DWTContext *s, float *t)
> /* position at index O of line range [0-5,w+5] cf. extend function */
> line += 5;
>
> + /* Find the largest lv and lv to allocate a 2D Array*/
lv and lv ?
you mean lv anf lh ?
> + int max_dim = 0;
> + for (lev = 0; lev < s->ndeclevels; lev++) {
> + if (s->linelen[lev][0] > max_dim) max_dim = s->linelen[lev][0];
> + if (s->linelen[lev][1] > max_dim) max_dim =
> + s->linelen[lev][1];
FFMAX()
> + }
> + float *array2DBlock = av_malloc(max_dim * max_dim * sizeof(float));
> + int useFallback = !array2DBlock;
also is this supposed to be max_dim_h * max_dim_v ?
> +
> for (lev = 0; lev < s->ndeclevels; lev++) {
> int lh = s->linelen[lev][0],
> lv = s->linelen[lev][1],
> @@ -431,23 +440,56 @@ static void dwt_decode97_float(DWTContext *s, float *t)
> for (i = 0; i < lh; i++)
> data[w * lp + i] = l[i];
> }
> -
> - // VER_SD
> - l = line + mv;
> - for (lp = 0; lp < lh; lp++) {
> - int i, j = 0;
> - // copy with interleaving
> - for (i = mv; i < lv; i += 2, j++)
> - l[i] = data[w * j + lp];
> - for (i = 1 - mv; i < lv; i += 2, j++)
> - l[i] = data[w * j + lp];
> -
> - sr_1d97_float(line, mv, mv + lv);
this should be run linewise not columnwise if you dont understand what i mean here, please say so and ill elaborate
But basically both vertical and horizontal transforms should be done with row based implementations
The code before loads and safes each column (which is bad) your code adds an efficient transpose and then copies each row
Theres a ton of unneeded copying here, i think the data in your implementation now is copied 4 times for each vertical transform pass
But iam very happy to see a patch submission from Microsoft! :)
thx
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
"I am not trying to be anyone's saviour, I'm trying to think about the future and not be sad" - Elon Musk
--------------------
Hi Michael,
Thanks so much for getting back! I'll quickly implement the first 3 comments
For the last comment is there a way for me to reach you on regular email to elaborate the proposed change more with a better explanation.
The 'git-send-email' was not good way for me to provide a detailed explanation for what I was trying to achieve
Additionally I can add more people from my group.
Comment from Michael
---------------------------------
this should be run linewise not columnwise
if you dont understand what i mean here, please say so and ill elaborate
But basically both vertical and horizontal transforms should be done with row based implementations
The code before loads and safes each column (which is bad)
- Yes we would like to learn more 😊. I am always happy to understand the details behind what is going on here and appreciate your explanations
Issue
---------------------------------
for (i = mv; i < lv; i += 2, j++)
l[i] = data[w * j + lp];
- VER_SD is running vertically at the moment with j being incremented in the innermost loop.
With w=4096 , we access data[4096] , data[8192] , data[12288] which touches a new cacheline in every single iteration of the inner- loop and causes cache thrashing (The next iteration cannot use the previous cacheline)
In our profiling on the newest Surface 11 devices with ~36M L2 cache we observed this loop to be a bottleneck costing ~4-5 FPS on these devices. We observed this on Mac M2 and M4 devices too.
Chitra's comments
------------------------------------
The proposed fix saves each column in 2D array in reverse. Inner loops are sequential, but the performance benefit is also coming from the size of 2DArray
In my profiling here are the real time-values
LV : 108, 215 , 429 , 857 ,1714
LH : 256 , 512 , 1024 , 2048 , 4096
W : 4096
Original code the size of *data = 1714 * 4096 * sizeof(float) = 26MB
In cache-blocking with the 2D Array I am intentionally transposing *data in a 2D array but 2DArray is much smaller and fits in CPU cache and no need to access DRAM.
Here are the sizes of 2DArray
LV LH Memory for Array2DBlock
108 256 ~0.1 MB
215 512 ~0.4 MB
429 1024 ~1.6 MB
857 2048 ~6.7 MB
1714 4096 ~26 MB
Overall logic
------------------------------
The overall logic is not impacted . I do not change the contents of l[i] even though it gets populated through the 2D Array
sr_1d97_float using *line should not be impacted
I have validated the CRC of the output file for transcoding the first 1500 frames of tears of Steel with and without this change and I am also happy to do a Demo if that is an option.
Please let us know what you think . Thanks for revieing our code!
Regards
Chitra
More information about the ffmpeg-devel
mailing list