From d074ea81c12132e3a92211679adbe2d2cb4d5a69 Mon Sep 17 00:00:00 2001
From: ChitraDeySarkar <chdey...@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: chdey...@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 <chdey...@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-requ...@ffmpeg.org with subject "unsubscribe".
