[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <0480a12c-7b4f-4d53-adf4-25f39d59e14b@amd.com>
Date: Mon, 8 Sep 2025 13:58:22 -0400
From: Aurabindo Pillai <aurabindo.pillai@....com>
To: Alex Hung <alex.hung@....com>, Kuan-Wei Chiu <visitorckw@...il.com>,
<austin.zheng@....com>, <jun.lei@....com>, <harry.wentland@....com>,
<sunpeng.li@....com>, <siqueira@...lia.com>, <alexander.deucher@....com>,
<christian.koenig@....com>, <airlied@...il.com>, <simona@...ll.ch>
CC: <zaeem.mohamed@....com>, <wenjing.liu@....com>, <chiahsuan.chung@....com>,
<Natanel.Roizenman@....com>, <Daniel.Sa@....com>, <jserv@...s.ncku.edu.tw>,
<amd-gfx@...ts.freedesktop.org>, <dri-devel@...ts.freedesktop.org>,
<linux-kernel@...r.kernel.org>
Subject: Re: [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from
O(N^2) to O(N)
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@...il.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
Powered by blists - more mailing lists