From patchwork Fri Aug 18 09:50:00 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liao, Chang" X-Patchwork-Id: 13357616 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 12C65C001DE for ; Fri, 18 Aug 2023 09:52:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238682AbjHRJwG (ORCPT ); Fri, 18 Aug 2023 05:52:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47076 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1357543AbjHRJvw (ORCPT ); Fri, 18 Aug 2023 05:51:52 -0400 Received: from szxga02-in.huawei.com (szxga02-in.huawei.com [45.249.212.188]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A60F92684; Fri, 18 Aug 2023 02:51:50 -0700 (PDT) Received: from kwepemi500012.china.huawei.com (unknown [172.30.72.53]) by szxga02-in.huawei.com (SkyGuard) with ESMTP id 4RRxtB4JmpzVk4Y; Fri, 18 Aug 2023 17:49:38 +0800 (CST) Received: from huawei.com (10.67.174.28) by kwepemi500012.china.huawei.com (7.221.188.12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.31; Fri, 18 Aug 2023 17:51:46 +0800 From: Liao Chang To: , CC: , Subject: [PATCH] cpufreq: stats: Improve the performance of cpufreq_stats_create_table() Date: Fri, 18 Aug 2023 09:50:00 +0000 Message-ID: <20230818095000.937633-1-liaochang1@huawei.com> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 X-Originating-IP: [10.67.174.28] X-ClientProxiedBy: dggems701-chm.china.huawei.com (10.3.19.178) To kwepemi500012.china.huawei.com (7.221.188.12) X-CFilter-Loop: Reflected Precedence: bulk List-ID: X-Mailing-List: linux-pm@vger.kernel.org In the worst case, the freq_table of policy data is not sorted and contains duplicate frequencies, this means that it needs to iterate through the entire freq_table of policy to ensure each frequency is unique in the freq_table of stats data, this has a time complexity of O(N^2), where N is the number of frequencies in the freq_table of policy. However, if the policy.freq_table is already sorted and contains no duplicate frequencices, it can reduce the time complexity of creating stats.freq_table to O(N), the 'freq_table_sorted' field of policy data can be used to indicate whether the policy.freq_table is sorted. Signed-off-by: Liao Chang Acked-by: Viresh Kumar Reviewed-by: Dhruva Gole --- drivers/cpufreq/cpufreq_stats.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/drivers/cpufreq/cpufreq_stats.c b/drivers/cpufreq/cpufreq_stats.c index 55c7ffd37d1c..fcb74050711a 100644 --- a/drivers/cpufreq/cpufreq_stats.c +++ b/drivers/cpufreq/cpufreq_stats.c @@ -243,7 +243,8 @@ void cpufreq_stats_create_table(struct cpufreq_policy *policy) /* Find valid-unique entries */ cpufreq_for_each_valid_entry(pos, policy->freq_table) - if (freq_table_get_index(stats, pos->frequency) == -1) + if ((policy->freq_table_sorted != CPUFREQ_TABLE_UNSORTED) || + (freq_table_get_index(stats, pos->frequency) == -1)) stats->freq_table[i++] = pos->frequency; stats->state_num = i;