[v1] drm/amd/display: optimize reserved time candidates handling

[PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)

Posted by Kuan-Wei Chiu 5 months, 2 weeks ago

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

Re: [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)

Posted by Alex Hung 5 months ago


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)

Re: [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)

Posted by Kuan-Wei Chiu 5 months ago

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)
>

Re: [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)

Posted by Aurabindo Pillai 5 months ago


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