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

[PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort()

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

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

Re: [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort()

Posted by Alex Hung 5 months ago


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

Re: [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort()

Posted by Christian König 5 months ago

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

Re: [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort()

Posted by Kuan-Wei Chiu 5 months ago

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