* [PATCH 0/2] drm/amd/display: optimize reserved time candidates handling
@ 2025-08-24 18:23 Kuan-Wei Chiu
2025-08-24 18:23 ` [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort() Kuan-Wei Chiu
2025-08-24 18:23 ` [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N) Kuan-Wei Chiu
0 siblings, 2 replies; 9+ messages in thread
From: Kuan-Wei Chiu @ 2025-08-24 18:23 UTC (permalink / raw)
To: austin.zheng, jun.lei, harry.wentland, sunpeng.li, siqueira,
alexander.deucher, christian.koenig, airlied, simona
Cc: zaeem.mohamed, wenjing.liu, chiahsuan.chung, Natanel.Roizenman,
Daniel.Sa, jserv, amd-gfx, dri-devel, linux-kernel, Kuan-Wei Chiu
Optimize the handling of reserved time candidates by replacing the
custom bubble sort with the kernel's standard sort() and rewriting
duplicate removal with a linear-time fast/slow pointer method. The
changes improve sorting from O(N^2) to O(N log N) and duplicate removal
from O(N^2) to O(N), reducing computational overhead and eliminating
hand-rolled implementations, while correctness has been verified with
simple unit tests.
Kuan-Wei Chiu (2):
drm/amd/display: Optimize reserved time candidates sorting using
standard sort()
drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)
.../dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c | 41 ++++++++++---------
1 file changed, 21 insertions(+), 20 deletions(-)
--
2.34.1
^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort()
2025-08-24 18:23 [PATCH 0/2] drm/amd/display: optimize reserved time candidates handling Kuan-Wei Chiu
@ 2025-08-24 18:23 ` Kuan-Wei Chiu
2025-09-08 17:05 ` Alex Hung
2025-08-24 18:23 ` [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N) Kuan-Wei Chiu
1 sibling, 1 reply; 9+ messages in thread
From: Kuan-Wei Chiu @ 2025-08-24 18:23 UTC (permalink / raw)
To: austin.zheng, jun.lei, harry.wentland, sunpeng.li, siqueira,
alexander.deucher, christian.koenig, airlied, simona
Cc: zaeem.mohamed, wenjing.liu, chiahsuan.chung, Natanel.Roizenman,
Daniel.Sa, jserv, amd-gfx, dri-devel, linux-kernel, Kuan-Wei Chiu
Replace the custom bubble sort used for sorting reserved time
candidates in with the kernel's standard sort() helper. The previous
code had O(N^2) time complexity, while the generic kernel sort runs in
O(N log N). This improves efficiency and removes the need for a local
sorting implementation, while keeping functionality unchanged.
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Compile test only.
.../dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c | 23 +++++++++++--------
1 file changed, 13 insertions(+), 10 deletions(-)
diff --git a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
index e763c8e45da8..2b13a5e88917 100644
--- a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
+++ b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
@@ -2,19 +2,21 @@
//
// Copyright 2024 Advanced Micro Devices, Inc.
+#include <linux/sort.h>
+
#include "dml2_pmo_factory.h"
#include "dml2_pmo_dcn3.h"
-static void sort(double *list_a, int list_a_size)
+static int cmp_double(const void *a, const void *b)
{
- // For all elements b[i] in list_b[]
- for (int i = 0; i < list_a_size - 1; i++) {
- // Find the first element of list_a that's larger than b[i]
- for (int j = i; j < list_a_size - 1; j++) {
- if (list_a[j] > list_a[j + 1])
- swap(list_a[j], list_a[j + 1]);
- }
- }
+ double da = *(const double *)a;
+ double db = *(const double *)b;
+
+ if (da < db)
+ return -1;
+ if (da > db)
+ return 1;
+ return 0;
}
static double get_max_reserved_time_on_all_planes_with_stream_index(struct display_configuation_with_meta *config, unsigned int stream_index)
@@ -634,7 +636,8 @@ bool pmo_dcn3_init_for_pstate_support(struct dml2_pmo_init_for_pstate_support_in
// Finally sort the array of candidates
sort(pmo->scratch.pmo_dcn3.reserved_time_candidates[stream_index],
- pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index]);
+ pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index],
+ sizeof(double), cmp_double, NULL);
remove_duplicates(pmo->scratch.pmo_dcn3.reserved_time_candidates[stream_index],
&pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index]);
--
2.34.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)
2025-08-24 18:23 [PATCH 0/2] drm/amd/display: optimize reserved time candidates handling Kuan-Wei Chiu
2025-08-24 18:23 ` [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort() Kuan-Wei Chiu
@ 2025-08-24 18:23 ` Kuan-Wei Chiu
2025-09-08 17:10 ` Alex Hung
1 sibling, 1 reply; 9+ messages in thread
From: Kuan-Wei Chiu @ 2025-08-24 18:23 UTC (permalink / raw)
To: austin.zheng, jun.lei, harry.wentland, sunpeng.li, siqueira,
alexander.deucher, christian.koenig, airlied, simona
Cc: zaeem.mohamed, wenjing.liu, chiahsuan.chung, Natanel.Roizenman,
Daniel.Sa, jserv, amd-gfx, dri-devel, linux-kernel, Kuan-Wei Chiu
Replace the previous O(N^2) implementation of remove_duplicates() in
with a O(N) version using a fast/slow pointer approach. The new version
keeps only the first occurrence of each element and compacts the array
in place, improving efficiency without changing functionality.
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Verified correctness using the following simple unit test:
double arr1[] = {1,1,2,2,3}; int size1=5;
remove_duplicates(arr1,&size1);
assert(size1==3 && arr1[0]==1 && arr1[1]==2 && arr1[2]==3);
double arr2[] = {1,2,3}; int size2=3;
remove_duplicates(arr2,&size2);
assert(size2==3 && arr2[0]==1 && arr2[1]==2 && arr2[2]==3);
double arr3[] = {5,5,5,5}; int size3=4;
remove_duplicates(arr3,&size3);
assert(size3==1 && arr3[0]==5);
double arr4[] = {}; int size4=0;
remove_duplicates(arr4,&size4);
assert(size4==0);
.../dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c | 18 ++++++++----------
1 file changed, 8 insertions(+), 10 deletions(-)
diff --git a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
index 2b13a5e88917..5100e0e7af42 100644
--- a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
+++ b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
@@ -50,18 +50,16 @@ static void set_reserved_time_on_all_planes_with_stream_index(struct display_con
static void remove_duplicates(double *list_a, int *list_a_size)
{
- int cur_element = 0;
- // For all elements b[i] in list_b[]
- while (cur_element < *list_a_size - 1) {
- if (list_a[cur_element] == list_a[cur_element + 1]) {
- for (int j = cur_element + 1; j < *list_a_size - 1; j++) {
- list_a[j] = list_a[j + 1];
- }
- *list_a_size = *list_a_size - 1;
- } else {
- cur_element++;
+ int j = 0;
+
+ for (int i = 1; i < *list_a_size; i++) {
+ if (list_a[j] != list_a[i]) {
+ j++;
+ list_a[j] = list_a[i];
}
}
+
+ *list_a_size = j + 1;
}
static bool increase_mpc_combine_factor(unsigned int *mpc_combine_factor, unsigned int limit)
--
2.34.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort()
2025-08-24 18:23 ` [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort() Kuan-Wei Chiu
@ 2025-09-08 17:05 ` Alex Hung
2025-09-08 17:35 ` Christian König
0 siblings, 1 reply; 9+ messages in thread
From: Alex Hung @ 2025-09-08 17:05 UTC (permalink / raw)
To: Kuan-Wei Chiu, austin.zheng, jun.lei, harry.wentland, sunpeng.li,
siqueira, alexander.deucher, christian.koenig, airlied, simona
Cc: zaeem.mohamed, wenjing.liu, chiahsuan.chung, Natanel.Roizenman,
Daniel.Sa, jserv, amd-gfx, dri-devel, linux-kernel
On 8/24/25 12:23, Kuan-Wei Chiu wrote:
> Replace the custom bubble sort used for sorting reserved time
> candidates in with the kernel's standard sort() helper. The previous
> code had O(N^2) time complexity, while the generic kernel sort runs in
> O(N log N). This improves efficiency and removes the need for a local
> sorting implementation, while keeping functionality unchanged.
>
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> Compile test only.
>
> .../dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c | 23 +++++++++++--------
> 1 file changed, 13 insertions(+), 10 deletions(-)
>
> diff --git a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> index e763c8e45da8..2b13a5e88917 100644
> --- a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> +++ b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> @@ -2,19 +2,21 @@
> //
> // Copyright 2024 Advanced Micro Devices, Inc.
>
> +#include <linux/sort.h>
> +
Thanks for working on this, but this file is shared with another OS and
it is not possible to replace sort function with Linux-only sort.
> #include "dml2_pmo_factory.h"
> #include "dml2_pmo_dcn3.h"
>
> -static void sort(double *list_a, int list_a_size)
> +static int cmp_double(const void *a, const void *b)
> {
> - // For all elements b[i] in list_b[]
> - for (int i = 0; i < list_a_size - 1; i++) {
> - // Find the first element of list_a that's larger than b[i]
> - for (int j = i; j < list_a_size - 1; j++) {
> - if (list_a[j] > list_a[j + 1])
> - swap(list_a[j], list_a[j + 1]);
> - }
> - }
> + double da = *(const double *)a;
> + double db = *(const double *)b;
> +
> + if (da < db)
> + return -1;
> + if (da > db)
> + return 1;
> + return 0;
> }
>
> static double get_max_reserved_time_on_all_planes_with_stream_index(struct display_configuation_with_meta *config, unsigned int stream_index)
> @@ -634,7 +636,8 @@ bool pmo_dcn3_init_for_pstate_support(struct dml2_pmo_init_for_pstate_support_in
>
> // Finally sort the array of candidates
> sort(pmo->scratch.pmo_dcn3.reserved_time_candidates[stream_index],
> - pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index]);
> + pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index],
> + sizeof(double), cmp_double, NULL);
>
> remove_duplicates(pmo->scratch.pmo_dcn3.reserved_time_candidates[stream_index],
> &pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index]);
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)
2025-08-24 18:23 ` [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N) Kuan-Wei Chiu
@ 2025-09-08 17:10 ` Alex Hung
2025-09-08 17:58 ` Aurabindo Pillai
2025-09-09 9:10 ` Kuan-Wei Chiu
0 siblings, 2 replies; 9+ messages in thread
From: Alex Hung @ 2025-09-08 17:10 UTC (permalink / raw)
To: Kuan-Wei Chiu, austin.zheng, jun.lei, harry.wentland, sunpeng.li,
siqueira, alexander.deucher, christian.koenig, airlied, simona,
Aurabindo Pillai
Cc: zaeem.mohamed, wenjing.liu, chiahsuan.chung, Natanel.Roizenman,
Daniel.Sa, jserv, amd-gfx, dri-devel, linux-kernel
On 8/24/25 12:23, Kuan-Wei Chiu wrote:
> Replace the previous O(N^2) implementation of remove_duplicates() in
> with a O(N) version using a fast/slow pointer approach. The new version
> keeps only the first occurrence of each element and compacts the array
> in place, improving efficiency without changing functionality.
>
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> Verified correctness using the following simple unit test:
>
> double arr1[] = {1,1,2,2,3}; int size1=5;
> remove_duplicates(arr1,&size1);
> assert(size1==3 && arr1[0]==1 && arr1[1]==2 && arr1[2]==3);
>
> double arr2[] = {1,2,3}; int size2=3;
> remove_duplicates(arr2,&size2);
> assert(size2==3 && arr2[0]==1 && arr2[1]==2 && arr2[2]==3);
>
> double arr3[] = {5,5,5,5}; int size3=4;
> remove_duplicates(arr3,&size3);
> assert(size3==1 && arr3[0]==5);
>
> double arr4[] = {}; int size4=0;
> remove_duplicates(arr4,&size4);
> assert(size4==0);
>
> .../dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c | 18 ++++++++----------
> 1 file changed, 8 insertions(+), 10 deletions(-)
>
> diff --git a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> index 2b13a5e88917..5100e0e7af42 100644
> --- a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> +++ b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> @@ -50,18 +50,16 @@ static void set_reserved_time_on_all_planes_with_stream_index(struct display_con
>
> static void remove_duplicates(double *list_a, int *list_a_size)
> {
> - int cur_element = 0;
> - // For all elements b[i] in list_b[]
> - while (cur_element < *list_a_size - 1) {
> - if (list_a[cur_element] == list_a[cur_element + 1]) {
> - for (int j = cur_element + 1; j < *list_a_size - 1; j++) {
> - list_a[j] = list_a[j + 1];
> - }
> - *list_a_size = *list_a_size - 1;
> - } else {
> - cur_element++;
> + int j = 0;
> +
> + for (int i = 1; i < *list_a_size; i++) {
> + if (list_a[j] != list_a[i]) {
> + j++;
> + list_a[j] = list_a[i];
> }
> }
> +
> + *list_a_size = j + 1;
A corner case needs fixing:
When input *list_a_size is zero, it will be updated to 1, unlike the
original code. Maybe a early return when *list_a_size is zero?
Hi Aurabindo,
Do you have other comments or other concerns?
> }
>
> static bool increase_mpc_combine_factor(unsigned int *mpc_combine_factor, unsigned int limit)
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort()
2025-09-08 17:05 ` Alex Hung
@ 2025-09-08 17:35 ` Christian König
2025-09-09 9:09 ` Kuan-Wei Chiu
0 siblings, 1 reply; 9+ messages in thread
From: Christian König @ 2025-09-08 17:35 UTC (permalink / raw)
To: Alex Hung, Kuan-Wei Chiu, austin.zheng, jun.lei, harry.wentland,
sunpeng.li, siqueira, alexander.deucher, airlied, simona
Cc: zaeem.mohamed, wenjing.liu, chiahsuan.chung, Natanel.Roizenman,
Daniel.Sa, jserv, amd-gfx, dri-devel, linux-kernel
On 08.09.25 19:05, Alex Hung wrote:
>
>
> On 8/24/25 12:23, Kuan-Wei Chiu wrote:
>> Replace the custom bubble sort used for sorting reserved time
>> candidates in with the kernel's standard sort() helper. The previous
>> code had O(N^2) time complexity, while the generic kernel sort runs in
>> O(N log N). This improves efficiency and removes the need for a local
>> sorting implementation, while keeping functionality unchanged.
>>
>> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
>> ---
>> Compile test only.
>>
>> .../dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c | 23 +++++++++++--------
>> 1 file changed, 13 insertions(+), 10 deletions(-)
>>
>> diff --git a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
>> index e763c8e45da8..2b13a5e88917 100644
>> --- a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
>> +++ b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
>> @@ -2,19 +2,21 @@
>> //
>> // Copyright 2024 Advanced Micro Devices, Inc.
>> +#include <linux/sort.h>
>> +
>
> Thanks for working on this, but this file is shared with another OS and it is not possible to replace sort function with Linux-only sort.
That's not a valid argument. Linux code must be solely written for Linux, you can't reject a valid patch because it breaks sharing code with other operating systems.
Regards,
Christian.
>
>> #include "dml2_pmo_factory.h"
>> #include "dml2_pmo_dcn3.h"
>> -static void sort(double *list_a, int list_a_size)
>> +static int cmp_double(const void *a, const void *b)
>> {
>> - // For all elements b[i] in list_b[]
>> - for (int i = 0; i < list_a_size - 1; i++) {
>> - // Find the first element of list_a that's larger than b[i]
>> - for (int j = i; j < list_a_size - 1; j++) {
>> - if (list_a[j] > list_a[j + 1])
>> - swap(list_a[j], list_a[j + 1]);
>> - }
>> - }
>> + double da = *(const double *)a;
>> + double db = *(const double *)b;
>> +
>> + if (da < db)
>> + return -1;
>> + if (da > db)
>> + return 1;
>> + return 0;
>> }
>> static double get_max_reserved_time_on_all_planes_with_stream_index(struct display_configuation_with_meta *config, unsigned int stream_index)
>> @@ -634,7 +636,8 @@ bool pmo_dcn3_init_for_pstate_support(struct dml2_pmo_init_for_pstate_support_in
>> // Finally sort the array of candidates
>> sort(pmo->scratch.pmo_dcn3.reserved_time_candidates[stream_index],
>> - pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index]);
>> + pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index],
>> + sizeof(double), cmp_double, NULL);
>> remove_duplicates(pmo->scratch.pmo_dcn3.reserved_time_candidates[stream_index],
>> &pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index]);
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)
2025-09-08 17:10 ` Alex Hung
@ 2025-09-08 17:58 ` Aurabindo Pillai
2025-09-09 9:10 ` Kuan-Wei Chiu
1 sibling, 0 replies; 9+ messages in thread
From: Aurabindo Pillai @ 2025-09-08 17:58 UTC (permalink / raw)
To: Alex Hung, Kuan-Wei Chiu, austin.zheng, jun.lei, harry.wentland,
sunpeng.li, siqueira, alexander.deucher, christian.koenig,
airlied, simona
Cc: zaeem.mohamed, wenjing.liu, chiahsuan.chung, Natanel.Roizenman,
Daniel.Sa, jserv, amd-gfx, dri-devel, linux-kernel
On 9/8/25 1:10 PM, Alex Hung wrote:
>
>
> On 8/24/25 12:23, Kuan-Wei Chiu wrote:
>> Replace the previous O(N^2) implementation of remove_duplicates() in
>> with a O(N) version using a fast/slow pointer approach. The new version
>> keeps only the first occurrence of each element and compacts the array
>> in place, improving efficiency without changing functionality.
>>
>> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
>> ---
>> Verified correctness using the following simple unit test:
>>
>> double arr1[] = {1,1,2,2,3}; int size1=5;
>> remove_duplicates(arr1,&size1);
>> assert(size1==3 && arr1[0]==1 && arr1[1]==2 && arr1[2]==3);
>>
>> double arr2[] = {1,2,3}; int size2=3;
>> remove_duplicates(arr2,&size2);
>> assert(size2==3 && arr2[0]==1 && arr2[1]==2 && arr2[2]==3);
>>
>> double arr3[] = {5,5,5,5}; int size3=4;
>> remove_duplicates(arr3,&size3);
>> assert(size3==1 && arr3[0]==5);
>>
>> double arr4[] = {}; int size4=0;
>> remove_duplicates(arr4,&size4);
>> assert(size4==0);
>>
>> .../dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c | 18 ++++++++----------
>> 1 file changed, 8 insertions(+), 10 deletions(-)
>>
>> diff --git a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/
>> dml2_pmo_dcn3.c b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/
>> dml2_pmo/dml2_pmo_dcn3.c
>> index 2b13a5e88917..5100e0e7af42 100644
>> --- a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/
>> dml2_pmo_dcn3.c
>> +++ b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/
>> dml2_pmo_dcn3.c
>> @@ -50,18 +50,16 @@ static void
>> set_reserved_time_on_all_planes_with_stream_index(struct display_con
>> static void remove_duplicates(double *list_a, int *list_a_size)
>> {
>> - int cur_element = 0;
>> - // For all elements b[i] in list_b[]
>> - while (cur_element < *list_a_size - 1) {
>> - if (list_a[cur_element] == list_a[cur_element + 1]) {
>> - for (int j = cur_element + 1; j < *list_a_size - 1; j++) {
>> - list_a[j] = list_a[j + 1];
>> - }
>> - *list_a_size = *list_a_size - 1;
>> - } else {
>> - cur_element++;
>> + int j = 0;
>> +
>> + for (int i = 1; i < *list_a_size; i++) {
>> + if (list_a[j] != list_a[i]) {
>> + j++;
>> + list_a[j] = list_a[i];
>> }
>> }
>> +
>> + *list_a_size = j + 1;
>
> A corner case needs fixing:
>
> When input *list_a_size is zero, it will be updated to 1, unlike the
> original code. Maybe a early return when *list_a_size is zero?
>
> Hi Aurabindo,
>
> Do you have other comments or other concerns?
Patch looks good with the early return added. Only nit is the
description wording - an extraneous 'in' is present.
--
Thanks & Regards,
Aurabindo Pillai
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort()
2025-09-08 17:35 ` Christian König
@ 2025-09-09 9:09 ` Kuan-Wei Chiu
0 siblings, 0 replies; 9+ messages in thread
From: Kuan-Wei Chiu @ 2025-09-09 9:09 UTC (permalink / raw)
To: Christian König
Cc: Alex Hung, austin.zheng, jun.lei, harry.wentland, sunpeng.li,
siqueira, alexander.deucher, airlied, simona, zaeem.mohamed,
wenjing.liu, chiahsuan.chung, Natanel.Roizenman, Daniel.Sa, jserv,
amd-gfx, dri-devel, linux-kernel
On Mon, Sep 08, 2025 at 07:35:08PM +0200, Christian König wrote:
> On 08.09.25 19:05, Alex Hung wrote:
> >
> >
> > On 8/24/25 12:23, Kuan-Wei Chiu wrote:
> >> Replace the custom bubble sort used for sorting reserved time
> >> candidates in with the kernel's standard sort() helper. The previous
> >> code had O(N^2) time complexity, while the generic kernel sort runs in
> >> O(N log N). This improves efficiency and removes the need for a local
> >> sorting implementation, while keeping functionality unchanged.
> >>
> >> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> >> ---
> >> Compile test only.
> >>
> >> .../dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c | 23 +++++++++++--------
> >> 1 file changed, 13 insertions(+), 10 deletions(-)
> >>
> >> diff --git a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> >> index e763c8e45da8..2b13a5e88917 100644
> >> --- a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> >> +++ b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> >> @@ -2,19 +2,21 @@
> >> //
> >> // Copyright 2024 Advanced Micro Devices, Inc.
> >> +#include <linux/sort.h>
> >> +
> >
> > Thanks for working on this, but this file is shared with another OS and it is not possible to replace sort function with Linux-only sort.
>
> That's not a valid argument. Linux code must be solely written for Linux, you can't reject a valid patch because it breaks sharing code with other operating systems.
>
Hi Alex and Christian,
Thanks for your feedback.
Based on the discussion, I plan to keep this patch in my v2.
Regards,
Kuan-Wei
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)
2025-09-08 17:10 ` Alex Hung
2025-09-08 17:58 ` Aurabindo Pillai
@ 2025-09-09 9:10 ` Kuan-Wei Chiu
1 sibling, 0 replies; 9+ messages in thread
From: Kuan-Wei Chiu @ 2025-09-09 9:10 UTC (permalink / raw)
To: Alex Hung
Cc: austin.zheng, jun.lei, harry.wentland, sunpeng.li, siqueira,
alexander.deucher, christian.koenig, airlied, simona,
Aurabindo Pillai, zaeem.mohamed, wenjing.liu, chiahsuan.chung,
Natanel.Roizenman, Daniel.Sa, jserv, amd-gfx, dri-devel,
linux-kernel
On Mon, Sep 08, 2025 at 11:10:30AM -0600, Alex Hung wrote:
>
>
> On 8/24/25 12:23, Kuan-Wei Chiu wrote:
> > Replace the previous O(N^2) implementation of remove_duplicates() in
> > with a O(N) version using a fast/slow pointer approach. The new version
> > keeps only the first occurrence of each element and compacts the array
> > in place, improving efficiency without changing functionality.
> >
> > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> > ---
> > Verified correctness using the following simple unit test:
> >
> > double arr1[] = {1,1,2,2,3}; int size1=5;
> > remove_duplicates(arr1,&size1);
> > assert(size1==3 && arr1[0]==1 && arr1[1]==2 && arr1[2]==3);
> >
> > double arr2[] = {1,2,3}; int size2=3;
> > remove_duplicates(arr2,&size2);
> > assert(size2==3 && arr2[0]==1 && arr2[1]==2 && arr2[2]==3);
> >
> > double arr3[] = {5,5,5,5}; int size3=4;
> > remove_duplicates(arr3,&size3);
> > assert(size3==1 && arr3[0]==5);
> >
> > double arr4[] = {}; int size4=0;
> > remove_duplicates(arr4,&size4);
> > assert(size4==0);
> >
> > .../dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c | 18 ++++++++----------
> > 1 file changed, 8 insertions(+), 10 deletions(-)
> >
> > diff --git a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> > index 2b13a5e88917..5100e0e7af42 100644
> > --- a/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> > +++ b/drivers/gpu/drm/amd/display/dc/dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c
> > @@ -50,18 +50,16 @@ static void set_reserved_time_on_all_planes_with_stream_index(struct display_con
> > static void remove_duplicates(double *list_a, int *list_a_size)
> > {
> > - int cur_element = 0;
> > - // For all elements b[i] in list_b[]
> > - while (cur_element < *list_a_size - 1) {
> > - if (list_a[cur_element] == list_a[cur_element + 1]) {
> > - for (int j = cur_element + 1; j < *list_a_size - 1; j++) {
> > - list_a[j] = list_a[j + 1];
> > - }
> > - *list_a_size = *list_a_size - 1;
> > - } else {
> > - cur_element++;
> > + int j = 0;
> > +
> > + for (int i = 1; i < *list_a_size; i++) {
> > + if (list_a[j] != list_a[i]) {
> > + j++;
> > + list_a[j] = list_a[i];
> > }
> > }
> > +
> > + *list_a_size = j + 1;
>
> A corner case needs fixing:
>
> When input *list_a_size is zero, it will be updated to 1, unlike the
> original code. Maybe a early return when *list_a_size is zero?
>
I noticed this issue while running my simple unit test.
I forgot to squash the fixup patch before submitting.
Sorry about that.
I'll send a v2 shortly.
Regards,
Kuan-Wei
> Hi Aurabindo,
>
> Do you have other comments or other concerns?
>
>
> > }
> > static bool increase_mpc_combine_factor(unsigned int *mpc_combine_factor, unsigned int limit)
>
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2025-09-10 8:01 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-08-24 18:23 [PATCH 0/2] drm/amd/display: optimize reserved time candidates handling Kuan-Wei Chiu
2025-08-24 18:23 ` [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort() Kuan-Wei Chiu
2025-09-08 17:05 ` Alex Hung
2025-09-08 17:35 ` Christian König
2025-09-09 9:09 ` Kuan-Wei Chiu
2025-08-24 18:23 ` [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N) Kuan-Wei Chiu
2025-09-08 17:10 ` Alex Hung
2025-09-08 17:58 ` Aurabindo Pillai
2025-09-09 9:10 ` Kuan-Wei Chiu
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.