[FFmpeg-devel] [PATCH] Boost FPS and performance: Optimize vertical loop for cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]

[FFmpeg-devel] [PATCH] Boost FPS and performance: Optimize vertical loop for cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]

[Chitra Dey Sarkar via ffmpeg-devel]

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*/
+    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];
+    }
+    float *array2DBlock = av_malloc(max_dim * max_dim * sizeof(float));
+    int useFallback = !array2DBlock;
+
     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);
-
-            for (i = 0; i < lv; i++)
-                data[w * i + lp] = l[i];
+
+        if (useFallback) {
+            // 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);
+
+                for (i = 0; i < lv; i++)
+                    data[w * i + lp] = l[i];
+            }
+                  }
+        else {
+            /*
+             * This array alleviates cache thrashing caused by vertical strided access across 'data'.
+             * By transposing the data outside the 'lp' loop, the inner loops gain sequential access,
+             * leading to substantial performance improvements.
+            */
+            for (int lp = 0; lp < lv; lp++)
+                for (int j = 0; j < lh; j++)
+                    array2DBlock[j * lv + lp] = data[w * lp + j];
+
+                l = line + mv;
+                for (lp = 0; lp < lh; lp++) {
+                    int i, j = 0;
+                    for (i = mv; i < lv; i += 2, j++)
+                        l[i] = array2DBlock[lp * lv + j];
+                    for (i = 1 - mv; i < lv; i += 2, j++)
+                        l[i] = array2DBlock[lp * lv + j];
+
+                    sr_1d97_float(line, mv, mv + lv);
+
+                    for (i = 0; i < lv; i++)
+                        array2DBlock[lp * lv + i] = l[i];
+                }
+
+            for (int lp = 0; lp < lv; lp++)
+                for (int j = 0; j < lh; j++)
+                    data[w * lp + j] = array2DBlock[j * lv + lp];
         }
     }
+
+    if (!useFallback)
+        av_free(array2DBlock);
 }

 static void sr_1d97_int(int32_t *p, int i0, int i1)
--
2.49.0.vfs.0.3



_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [FFmpeg-devel] [PATCH] Boost FPS and performance: Optimize vertical loop for cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]

[Michael Niedermayer]

[-- Attachment #1.1: Type: text/plain, Size: 4447 bytes --]

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


[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[-- Attachment #2: Type: text/plain, Size: 251 bytes --]

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [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 via ffmpeg-devel]

-----Original Message-----
From: Michael Niedermayer <michael@niedermayer.cc> 
Sent: Wednesday, May 14, 2025 9:40 AM
To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Cc: Chitra Dey Sarkar <Chitra.Dey@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



_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [FFmpeg-devel] [PATCH] Boost FPS and performance: Optimize vertical loop for cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]

[Michael Niedermayer]

[-- Attachment #1.1: Type: text/plain, Size: 5650 bytes --]

Hi

On Wed, May 14, 2025 at 06:40:03PM +0200, Michael Niedermayer wrote:
> 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

For the record: (may be interresting for others, or others may have comments too)

<michaelni> The 1D transform is made of 4 passes of lifting transforms, currently all pixels of a column are run through the first lifting step before anything runs through the 2nd. One could try to run the first through the 4th lifting step after the 2nd finishes the 3rd lifting step and the 3rd pixel of the column finishes the 2nd lifting step
<michaelni> and then do this for all pixels in a row so that the whole transform is finished for the whole first row before more than 5 rows or so have been touched
<michaelni> this _COULD_ be faster, but it needs to be tried to be sure

basically, there would be a area covering s small number of whole rows and
this area would move down by 1 or 2 rows in each iteration
above it both horizontal and vertical transforms are finished below it
its the untouched input.
as long as this sliding window fits in the cache this should outperform
anything that copyies the data around

I think its important to look into this before optimizing the code for
CPU or GPU because the structure of this is different than the transpose
based code. In fact the horizontal transform is quite unfriendly for SIMD

so the code as is in C might be to worst possible starting point for SIMD
it transforms the easy vertical transform with a transpose into a horizontal
one ...

thx

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The greatest way to live with honor in this world is to be what we pretend
to be. -- Socrates

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[-- Attachment #2: Type: text/plain, Size: 251 bytes --]

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [FFmpeg-devel] [PATCH] Boost FPS and performance: Optimize vertical loop for cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]

[Michael Niedermayer]

[-- Attachment #1.1: Type: text/plain, Size: 6183 bytes --]

On Thu, May 15, 2025 at 10:19:57PM +0200, Michael Niedermayer wrote:
> Hi
> 
> On Wed, May 14, 2025 at 06:40:03PM +0200, Michael Niedermayer wrote:
> > 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
> 
> For the record: (may be interresting for others, or others may have comments too)
> 
> <michaelni> The 1D transform is made of 4 passes of lifting transforms, currently all pixels of a column are run through the first lifting step before anything runs through the 2nd. One could try to run the first through the 4th lifting step after the 2nd finishes the 3rd lifting step and the 3rd pixel of the column finishes the 2nd lifting step
> <michaelni> and then do this for all pixels in a row so that the whole transform is finished for the whole first row before more than 5 rows or so have been touched
> <michaelni> this _COULD_ be faster, but it needs to be tried to be sure
> 
> basically, there would be a area covering s small number of whole rows and
> this area would move down by 1 or 2 rows in each iteration
> above it both horizontal and vertical transforms are finished below it
> its the untouched input.
> as long as this sliding window fits in the cache this should outperform
> anything that copyies the data around
> 
> I think its important to look into this before optimizing the code for
> CPU or GPU because the structure of this is different than the transpose
> based code. In fact the horizontal transform is quite unfriendly for SIMD
> 
> so the code as is in C might be to worst possible starting point for SIMD
> it transforms the easy vertical transform with a transpose into a horizontal
> one ...

More elaboration, i think what i wrote is still unclear

If one looks at spatial_decompose97i() in libavcodec/snow_dwt.c
thats approximately what i had in mind.
Its just one page of code

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The difference between a dictatorship and a democracy is that every 4 years
the population together is allowed to provide 1 bit of input to the government.

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[-- Attachment #2: Type: text/plain, Size: 251 bytes --]

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [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 via ffmpeg-devel]

-----Original Message-----
From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of Michael Niedermayer
Sent: Friday, May 16, 2025 2:44 AM
To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Subject: [EXTERNAL] Re: [FFmpeg-devel] [PATCH] Boost FPS and performance: Optimize vertical loop for cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]

On Thu, May 15, 2025 at 10:19:57PM +0200, Michael Niedermayer wrote:
> Hi
> 
> On Wed, May 14, 2025 at 06:40:03PM +0200, Michael Niedermayer wrote:
> > 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)
> > > +
> > >      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
> 
> For the record: (may be interresting for others, or others may have 
> comments too)
> 
> <michaelni> The 1D transform is made of 4 passes of lifting 
> transforms, currently all pixels of a column are run through the first 
> lifting step before anything runs through the 2nd. One could try to 
> run the first through the 4th lifting step after the 2nd finishes the 
> 3rd lifting step and the 3rd pixel of the column finishes the 2nd 
> lifting step <michaelni> and then do this for all pixels in a row so 
> that the whole transform is finished for the whole first row before 
> more than 5 rows or so have been touched <michaelni> this _COULD_ be 
> faster, but it needs to be tried to be sure
> 
> basically, there would be a area covering s small number of whole rows 
> and this area would move down by 1 or 2 rows in each iteration above 
> it both horizontal and vertical transforms are finished below it its 
> the untouched input.
> as long as this sliding window fits in the cache this should 
> outperform anything that copyies the data around
> 
> I think its important to look into this before optimizing the code for 
> CPU or GPU because the structure of this is different than the 
> transpose based code. In fact the horizontal transform is quite 
> unfriendly for SIMD
> 
> so the code as is in C might be to worst possible starting point for 
> SIMD it transforms the easy vertical transform with a transpose into a 
> horizontal one ...

More elaboration, i think what i wrote is still unclear

If one looks at spatial_decompose97i() in libavcodec/snow_dwt.c thats approximately what i had in mind.
Its just one page of code

==========> Acknowledged . I will look at this part of the code to see if I am able to do something similar
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

[FFmpeg-devel] [PATCH] Boost FPS and performance: Optimize vertical loop for cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]

[Chitra Dey Sarkar via ffmpeg-devel]

From d074ea81c12132e3a92211679adbe2d2cb4d5a69 Mon Sep 17 00:00:00 2001
From: ChitraDeySarkar <chdeysar@microsoft.com>
Date: Wed, 14 May 2025 11:51:35 -0700
Subject: [PATCH] Boost FPS and performance: Optimize vertical loop for
 cache-friendly access [libavcodec/jpeg2000dwt.c:dwt_decode97_float]
From: chdeysar@microsoft.com
X-Unsent: 1
To: ffmpeg-devel@ffmpeg.org

From earlier

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 of loop does not 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.

2 extra copies explanation
---------------------------
Earlier *data is malloc'd outside of the function,  without knowing LV and LH it took the largest LV*LH as its size, which is much larger than 2D Array

Earlier there were 3 loops accessing *data vertically (columnwise) , now there are 5 loops I agree. But the 5 loops are cache friendly

In the current implementation

  1.
All the loops access *data row wise but copy to 2D Array columnwise
  2.
Its might be ok to copy to 2D Array column-wise as it is smaller (fits well in CPU cache for 4 out of 5 times)
  3.
 All the inner loops are sequential and easier for prefetch and easier for compiler to apply vactorization and optimizations


I can potentially reduce the extra copies and use the fallback path  if the function is invoked with LV and LH large enough that the extra copies are not beneficial with a condition check

Overall this has shown us a lot of improvement
Please let us know if I can provide any more details. Thanks for revieing our code!

Regards
Chitra

Signed-off-by: ChitraDeySarkar <chdeysar@microsoft.com>
---
 libavcodec/jpeg2000dwt.c | 26 +++++++++++++-------------
 1 file changed, 13 insertions(+), 13 deletions(-)

diff --git a/libavcodec/jpeg2000dwt.c b/libavcodec/jpeg2000dwt.c
index 45d7897893..4de95a3bea 100644
--- a/libavcodec/jpeg2000dwt.c
+++ b/libavcodec/jpeg2000dwt.c
@@ -409,14 +409,14 @@ 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*/
-    int max_dim = 0;
+    /* Find the largest lv and lh to allocate a 2D Array*/
+    int max_dim_lv = 0 , max_dim_lh = 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];
-    }
-    float *array2DBlock = av_malloc(max_dim * max_dim * sizeof(float));
-    int useFallback = !array2DBlock;
+        max_dim_lh = FFMAX(max_dim_lh, s->linelen[lev][0]);
+        max_dim_lv = FFMAX(max_dim_lv, s->linelen[lev][1]);
+    }
+    float *array_2d_block = av_malloc(max_dim_lv * max_dim_lh * sizeof(float));
+    int useFallback = !array_2d_block;

     for (lev = 0; lev < s->ndeclevels; lev++) {
         int lh = s->linelen[lev][0],
@@ -466,30 +466,30 @@ static void dwt_decode97_float(DWTContext *s, float *t)
             */
             for (int lp = 0; lp < lv; lp++)
                 for (int j = 0; j < lh; j++)
-                    array2DBlock[j * lv + lp] = data[w * lp + j];
+                    array_2d_block[j * lv + lp] = data[w * lp + j];

                 l = line + mv;
                 for (lp = 0; lp < lh; lp++) {
                     int i, j = 0;
                     for (i = mv; i < lv; i += 2, j++)
-                        l[i] = array2DBlock[lp * lv + j];
+                        l[i] = array_2d_block[lp * lv + j];
                     for (i = 1 - mv; i < lv; i += 2, j++)
-                        l[i] = array2DBlock[lp * lv + j];
+                        l[i] = array_2d_block[lp * lv + j];

                     sr_1d97_float(line, mv, mv + lv);

                     for (i = 0; i < lv; i++)
-                        array2DBlock[lp * lv + i] = l[i];
+                        array_2d_block[lp * lv + i] = l[i];
                 }

             for (int lp = 0; lp < lv; lp++)
                 for (int j = 0; j < lh; j++)
-                    data[w * lp + j] = array2DBlock[j * lv + lp];
+                    data[w * lp + j] = array_2d_block[j * lv + lp];
         }
     }

     if (!useFallback)
-        av_free(array2DBlock);
+        av_free(array_2d_block);
 }

 static void sr_1d97_int(int32_t *p, int i0, int i1)
--
2.49.0.vfs.0.3


_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".