* [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
* 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 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 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
* [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 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 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 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-09 9:10 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.