linux-kernel - Re: [PATCH v2 2/2] drm/amd/display: Optimize remove

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <d3b94b72-3e38-4951-8c75-8b028db7915c@amd.com>
Date: Mon, 22 Sep 2025 12:06:51 -0600
From: Alex Hung <alex.hung@....com>
To: Kuan-Wei Chiu <visitorckw@...il.com>, austin.zheng@....com,
 jun.lei@....com, harry.wentland@....com, sunpeng.li@....com,
 alexander.deucher@....com, christian.koenig@....com, airlied@...il.com,
 simona@...ll.ch, siqueira@...lia.com, aurabindo.pillai@....com
Cc: chiahsuan.chung@....com, nicholas.kazlauskas@....com,
 wenjing.liu@....com, jserv@...s.ncku.edu.tw, amd-gfx@...ts.freedesktop.org,
 linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2 2/2] drm/amd/display: Optimize remove_duplicates() from
 O(N^2) to O(N)

Reviewed-by: Alex Hung <alex.hung@....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@...il.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)