From nobody Fri Oct 3 21:53:30 2025 Received: from mail-pl1-f175.google.com (mail-pl1-f175.google.com [209.85.214.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C16A01DF248 for ; Sun, 24 Aug 2025 18:24:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756059853; cv=none; b=TqHaa4R+pHKqrL8GfQ58b4aSfXShlEwmoETjClBmZmwld9pHricu/iny/OcsonXwlTz/dOpm8OB6YT1KELoDfpD5fZ/H7x7zWSrKe08DyBUoaYBGV7qxEP5S9HJkNsw2MLmJhXx81hVtrA71gX9ot/G4oyPyurslB+KMZI/4ZDk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756059853; c=relaxed/simple; bh=5umpghsVLHvB2BsI0p8i+BZO8l0QUN/lne/qBEkpRmQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=RSVOVc+Oo16EYsNchVuV5RQUGcNiRn8p0LtOm5g5WRzEO2ciJ0vGW5Nqh3lEOfHbalcKVrrVUamhtnmIpIlmKs2ZvHOj0ZGHwmxYM6dzTc331foUY3nlDBiWastjkkwWViLgjA5kUa82bMhQtaGZKakU3/+KsV04Z3x/ego6loE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Nh5A02HX; arc=none smtp.client-ip=209.85.214.175 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Nh5A02HX" Received: by mail-pl1-f175.google.com with SMTP id d9443c01a7336-246181827e9so26582035ad.3 for ; Sun, 24 Aug 2025 11:24:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1756059851; x=1756664651; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=p2v1IYFTL9EjW4OmXMSiVEBKcc5tiC6DS+GF23hLI0E=; b=Nh5A02HX++wviGd6/RCKy1V3yl/Xamwh0dTKLDmaGTGnUYiV/TDEe2Lbzz//mzJY3X sFQa+x1GVNjJ6CBGlxhHtM7JD1RuFM7HOinbOMd6kBnloJW/I1HAVoxKuBzs45y26T/C pAbvwsWfhZEBh7VMu0b+5ju7zWCXGAkJp5GrogzXdL6+sMgxWokCL2Mi3S4hVu+YsGFN pbFBRTrr937FfnIRKz7AUcHIJE9xgMSUI6m4wGq3o5lZrbm7d6Rc9Y4Np1G+//fQ8oCR fkwdTD6RpFjJWvVtqLBhU7A0sV28ADApA92DWbfjo+wBV1Kkck5CoSzPu/JcN6i+2V0v l9ew== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1756059851; x=1756664651; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=p2v1IYFTL9EjW4OmXMSiVEBKcc5tiC6DS+GF23hLI0E=; b=cSH1UHHoTPixbZTgPxYK+coa5E5kJGgAQvRDExIhS06g/mHi+L9LAGyrr1PLpFHQSj 6SksyaobC89tDKcV4rf8t06aLgq/De7wFCMs4CBLlAShn4ANcQMui3tUIWwfcykq4HLk e/uYyxxssxg+1CuFbhLXGaZfDH35WmpygdUsBvoncvvLjOHE/H1n+2a8cEzT2SBSD5k1 llwHNGOUwANrUjvP9/wYqXVET4NaIBtpMDoX11u0lmt3fKdCwpbUdRbCzBXhDj1XTkU+ fX2tkPdvad9vyokU4Hf6gvhQ+HMEbe/l2WHTl4PrYdSFLBragpHwXzzIcPYE8mTxsGQK D5YA== X-Forwarded-Encrypted: i=1; AJvYcCXZUwCGmMiGn+zxUZZjsPum6fr507CCjrbz9CJ9lfHDFSd7RcfNaIZqn4H5XE9oHI7LfJKrmgIxsxPU1iA=@vger.kernel.org X-Gm-Message-State: AOJu0Yx/mDksR7qrXSRz5YDy5UwzK8xEEfghkrGQjGHV7FLNAlrJQUT6 lcp4vfmElQI6L5oX89xvkOGk15kBg2yy35/qPN+zWFoGkzKi3I3qMnOYEiM/HbiM X-Gm-Gg: ASbGnctxJAg43K+JF5lw9kf6oOX+hSBcEcufR2SWJhS+Ozj7hsF+ohQdtz6TOWy8mky 6ejnNeLqqckX8tS6y2N8n9nKDS5q5u3U4mlbue3SfyXr6af+3utxOL8zCnruVd7CPdh7lqmrXDR O9ecohvE8+Ffv3VqmVHHSoC8VBCF7K9LHMj2DFJaR7HR2goXbJ2jIlNZNRAOSnVr2WZUY0QEqgd dRGnjsCRYb1FlnuR22Gwm4PFmnSUj5UnfTVGiSieIvaWDBu5TDOubPKAkRcqKaxkTuBRGM/zVbZ sz5ZRHSmUKjyjj7Dv9lMffJElvr7qwdPVAdQN3YOQ44st+Esx3ts+Ixh0Pt++Y/IF/XdKNRebVN 9kpzcOxMh/uyc41pYnu9139vCgSikiRlLAVqpljceQW2KzfP5NvcwsUYfx7c6DzI= X-Google-Smtp-Source: AGHT+IEcmIAoNLGgWs51AJwLfXP1RCoyG3ATRWOL86MbvJbfx+dgqpWtFQD61mP3GyAan2qMIob2vQ== X-Received: by 2002:a17:903:46c5:b0:246:7b42:a223 with SMTP id d9443c01a7336-2467b42a323mr57162615ad.25.1756059850757; Sun, 24 Aug 2025 11:24:10 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2466889f11esm47903635ad.150.2025.08.24.11.24.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 24 Aug 2025 11:24:10 -0700 (PDT) From: Kuan-Wei Chiu To: austin.zheng@amd.com, jun.lei@amd.com, harry.wentland@amd.com, sunpeng.li@amd.com, siqueira@igalia.com, alexander.deucher@amd.com, christian.koenig@amd.com, airlied@gmail.com, simona@ffwll.ch Cc: zaeem.mohamed@amd.com, wenjing.liu@amd.com, chiahsuan.chung@amd.com, Natanel.Roizenman@amd.com, Daniel.Sa@amd.com, jserv@ccns.ncku.edu.tw, amd-gfx@lists.freedesktop.org, dri-devel@lists.freedesktop.org, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 1/2] drm/amd/display: Optimize reserved time candidates sorting using standard sort() Date: Mon, 25 Aug 2025 02:23:58 +0800 Message-Id: <20250824182359.142050-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250824182359.142050-1-visitorckw@gmail.com> References: <20250824182359.142050-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 --- Compile test only.=20 .../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_pm= o_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. =20 +#include + #include "dml2_pmo_factory.h" #include "dml2_pmo_dcn3.h" =20 -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 =3D 0; i < list_a_size - 1; i++) { - // Find the first element of list_a that's larger than b[i] - for (int j =3D 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 =3D *(const double *)a; + double db =3D *(const double *)b; + + if (da < db) + return -1; + if (da > db) + return 1; + return 0; } =20 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_i= nit_for_pstate_support_in =20 // 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); =20 remove_duplicates(pmo->scratch.pmo_dcn3.reserved_time_candidates[stream_= index], &pmo->scratch.pmo_dcn3.reserved_time_candidates_count[stream_index]); --=20 2.34.1 From nobody Fri Oct 3 21:53:30 2025 Received: from mail-pg1-f170.google.com (mail-pg1-f170.google.com [209.85.215.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A250922541C for ; Sun, 24 Aug 2025 18:24:15 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756059857; cv=none; b=CiWrcMLm/XJN2OW4lym/LZk63CTjPa0ubHeIQMQEVGjKHSpk/5drtEhsdXWaDryA8AKtX5L/7+iRptq45dVYerVc+IMsP/L08U4DBajdxAVjEBPMSrdlqXokQrZi1ihgypF8QMKIonAus9+zFEjSO9yuaP8g3KdUT5UlEu0lUng= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756059857; c=relaxed/simple; bh=edteeakluFvE1/Gn0LPnNiLLwnm0Gp+YtbVV4il9WUI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=PN7nL8ZjzFO1CHrmF1USXtwsGx6ogW13AuP1lEw7ITS0mKxAN9lqKsK97itS3Gc8rOm5558IbFQlPq1rptQW7PX4XPSxquMZKC5sO0BmB31TtMa16TTDFSqgsPgXP9UbHAa8MU/umXYaI2GYbH2bERmls9U246JkM0XoaOBidrY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=kHLIcNC/; arc=none smtp.client-ip=209.85.215.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="kHLIcNC/" Received: by mail-pg1-f170.google.com with SMTP id 41be03b00d2f7-b4755f37c3eso3217762a12.3 for ; Sun, 24 Aug 2025 11:24:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1756059855; x=1756664655; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=sdgoKxIG8/LQsHbKVpjz+drIjpSbT2c+ZQGF2CUmKYI=; b=kHLIcNC/pCAH64axvC6w1u4h7y4SxRvoj0iW8mLRQ+YNrP3hVfIvij0SSbwdVfhddC /le6Mgee4w2bph4X4V6s3/YMxPl9Y460RE9fS+DPSetKPgfjyWeUA+KLCw9ag9PZNcaL WowXDtp6K5ZMsODYahs2flup6lHu5mhFnjO3SsbN3UOiNPfsRUrPBCfM0piTJ0FuYILY hH4/CLkO/ZbPYZdzbCcJ17a+KYusNKETFaD7UI9kpzX5cNTR/FK8HKZ3f5N5F0QElaAB RJwz4V6tgXuJScSfbYDltEV/GM8I8HqO5+3W/ay1Y78/asJDF5+vJK1zqoepsME3hMCt Ntdg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1756059855; x=1756664655; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=sdgoKxIG8/LQsHbKVpjz+drIjpSbT2c+ZQGF2CUmKYI=; b=gu+ExIE6LrLhNTfauyt2YWYns66I5pE/f8JPF9Bs4W6AtX3ghH1mVumnGOSlsG3XAE Brs30vdJOoM1t32b24Bj9bay1P08venPrjnuh6pJxbgH1b/KkP2SmrX92CMqa31jz0DU AVDTHGB9rvX2pWcRaPX8Ps15sRsrc4luXEwrvZHbYXOuBec/ox2WYqZYzzNk4/pswOiM 1AzxNF9V3BTLOD+1TtEC7gdzNLDZ/T7fyWVbOPOeSc97DGfWO4iRCH6tVhEbsLLbgi8x r5TG66ggrtsdzMKEcaQjPadbmxWxtWWoMHo7ljJlGfnPk5SJ0r6b3H7GGh8jHQE+drHG HYwA== X-Forwarded-Encrypted: i=1; AJvYcCUe7VEwNpO6i/QG79DGz0CMPU5KvsrWZ5DjJpA7IwCLHO7d1LOYLFkB6nQf9Taj7R4jkTUcQ93hAiFtzY0=@vger.kernel.org X-Gm-Message-State: AOJu0YwFtrALNEhaWhEp7fqDwU+rH9kmELVfHG1KZDdf5ca8l+mxU4In 38uosczAenHXkQQdhuebDewwMlaTOo23mprAQTVDAUW6lMz1FMqYWZVg X-Gm-Gg: ASbGncshFBXtmaK1DkuWbwXGcwALlGY013N0nvRfEQiafQl0hulI9WKj/6IYsbuWwoA xIL5t50DspXLkgf1fpipxZAI57fnlFLsfroTmPymzuYleVAVy++/WTqzfhIg6rj1iWywDhXYf0i gH3BJUsrk/vI4DnRpxm8laCEhZFjDuGDC037uZ07ufgzrE/6A9Sg5V5g5vEk7qVfglawNWYCM8N 2n32dvGbqwHDIlXYKd3CCdJUQxgD5nM3tjlrcRBPM3DywZyMWQMIzRkBmX2Mis02Z/x506vELf8 20VewWWPB4uFJndeRc8PraWEauxKYUDVLF9s+cFdBgOxQyUIQrlKY4aWnqX8PltRamGUGZ1rga8 yczThsUbrdXt4//U+acGjCgRH9DabkQq9dXhcOfIqGcIuuqfmpn2hd/INMvsTmxA= X-Google-Smtp-Source: AGHT+IFTU5oW4ymRV8/xPeqRq4/qqEYx3zIjjLkoyBxb1dFnjnFQtkKwEnEovKNUweZV2b84+zY2/Q== X-Received: by 2002:a17:902:dad1:b0:240:8262:1a46 with SMTP id d9443c01a7336-2462ee54512mr127900995ad.25.1756059854831; Sun, 24 Aug 2025 11:24:14 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2466889f11esm47903635ad.150.2025.08.24.11.24.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 24 Aug 2025 11:24:14 -0700 (PDT) From: Kuan-Wei Chiu To: austin.zheng@amd.com, jun.lei@amd.com, harry.wentland@amd.com, sunpeng.li@amd.com, siqueira@igalia.com, alexander.deucher@amd.com, christian.koenig@amd.com, airlied@gmail.com, simona@ffwll.ch Cc: zaeem.mohamed@amd.com, wenjing.liu@amd.com, chiahsuan.chung@amd.com, Natanel.Roizenman@amd.com, Daniel.Sa@amd.com, jserv@ccns.ncku.edu.tw, amd-gfx@lists.freedesktop.org, dri-devel@lists.freedesktop.org, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 2/2] drm/amd/display: Optimize remove_duplicates() from O(N^2) to O(N) Date: Mon, 25 Aug 2025 02:23:59 +0800 Message-Id: <20250824182359.142050-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250824182359.142050-1-visitorckw@gmail.com> References: <20250824182359.142050-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 --- Verified correctness using the following simple unit test: double arr1[] =3D {1,1,2,2,3}; int size1=3D5; remove_duplicates(arr1,&size1); assert(size1=3D=3D3 && arr1[0]=3D=3D1 && arr1[1]=3D=3D2 && arr1[2]=3D=3D3); double arr2[] =3D {1,2,3}; int size2=3D3; remove_duplicates(arr2,&size2); assert(size2=3D=3D3 && arr2[0]=3D=3D1 && arr2[1]=3D=3D2 && arr2[2]=3D=3D3); double arr3[] =3D {5,5,5,5}; int size3=3D4; remove_duplicates(arr3,&size3); assert(size3=3D=3D1 && arr3[0]=3D=3D5); double arr4[] =3D {}; int size4=3D0; remove_duplicates(arr4,&size4); assert(size4=3D=3D0); .../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_pm= o_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 =20 static void remove_duplicates(double *list_a, int *list_a_size) { - int cur_element =3D 0; - // For all elements b[i] in list_b[] - while (cur_element < *list_a_size - 1) { - if (list_a[cur_element] =3D=3D list_a[cur_element + 1]) { - for (int j =3D cur_element + 1; j < *list_a_size - 1; j++) { - list_a[j] =3D list_a[j + 1]; - } - *list_a_size =3D *list_a_size - 1; - } else { - cur_element++; + int j =3D 0; + + for (int i =3D 1; i < *list_a_size; i++) { + if (list_a[j] !=3D list_a[i]) { + j++; + list_a[j] =3D list_a[i]; } } + + *list_a_size =3D j + 1; } =20 static bool increase_mpc_combine_factor(unsigned int *mpc_combine_factor, = unsigned int limit) --=20 2.34.1