[PATCH v2 0/2] drm/amd/display: optimize reserved time candidates handling

[PATCH v2 0/2] drm/amd/display: optimize reserved time candidates handling

[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.
---
Changes from v1:
- Add early return when *list_a_size = 0 to fix a corner case.

v1: https://lore.kernel.org/lkml/20250824182359.142050-1-visitorckw@gmail.com

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   | 44 ++++++++++---------
 1 file changed, 24 insertions(+), 20 deletions(-)

-- 
2.34.1

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

[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>
---
Changes from v1:
- No changes.

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

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

[Kuan-Wei Chiu]

Replace the previous O(N^2) implementation of remove_duplicates() 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>
---
Changes from v1:
- Add early return when *list_a_size = 0 to fix a corner case.

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

 .../dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c   | 21 ++++++++++---------
 1 file changed, 11 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..1068ddc97859 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,19 @@ 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;
+
+	if (*list_a_size == 0)
+		return;
+
+	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 v2 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N)

[Alex Hung]

Reviewed-by: Alex Hung <alex.hung@amd.com>

On 9/9/25 03:20, Kuan-Wei Chiu wrote:
> Replace the previous O(N^2) implementation of remove_duplicates() 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>
> ---
> Changes from v1:
> - Add early return when *list_a_size = 0 to fix a corner case.
> 
> 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);
> 
>   .../dml2/dml21/src/dml2_pmo/dml2_pmo_dcn3.c   | 21 ++++++++++---------
>   1 file changed, 11 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..1068ddc97859 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,19 @@ 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;
> +
> +	if (*list_a_size == 0)
> +		return;
> +
> +	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)