From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-qt1-f174.google.com (mail-qt1-f174.google.com [209.85.160.174]) (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 0CB877C for ; Sun, 28 May 2023 15:32:15 +0000 (UTC) Received: by mail-qt1-f174.google.com with SMTP id d75a77b69052e-3f8008cb772so12369421cf.3 for ; Sun, 28 May 2023 08:32:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1685287935; x=1687879935; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=PHJV1HfYIplIh99Ejgm8xeYpF8nKcBe4zUEBNIOYV4E=; b=MagmmRExvh9FigOOEx342zgTKf0Fz2pW/Iw0gUmyfojCBK0u3qWU6bliHJIHTW6IeZ HmMnTXiYqwg2gHavU9ReT3TCuKxeJ+ThP4HV7j60f4S1MyHhSpgj8g+YfacmmmYY7MDk uQm2nNcG06hFn1mjEwZ+7EfYqz3DZS6aPZgdy6nqOtLZF4bWSzYBeyZZzITp09lHrUhn 11JZHzu5VQiELOT7vlneVMFTs8TTiZ5EK3MzOTtPio99rxteY+Kl3Kd8VDokxh3/tviN zmQTNQjitQ4fJnnxzNT13tQ7pCMeynzOSVw5eCClXJHRm/B/jjik/t23sWQYsYuaZj1b 7ckw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685287935; x=1687879935; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=PHJV1HfYIplIh99Ejgm8xeYpF8nKcBe4zUEBNIOYV4E=; b=FixxCmoG/ggIRE03XsMvdFmJadA91CKB1KkVcddU6xSNdVup79Vmdp34X1A5f1aP48 xpsUIdn4PSq4vn4n8d4N7xNdfu6cYIl/Ulk+q6XU36MLcm9FUsW7qE2Hf5P4UWS5L3AF /VgJ/rDt/WVSGWnFHrXGbD/6YPJKXYcRF/nlYGmf8AC+Rilw5XOFrroi3COBz6QD0zON UaRj7/H+8o5gQPDEonTEGQXMpczf7W0+0gviiUIJraC4Jp8tsZFfP6RAxigYzUpB4JAO xEf3CAz9nT0QNmsEd6ixR67jv/jhPd8i0jt/J3xtq0+LhclPIlEDf+sMDJojpOLiU/DQ 8uPA== X-Gm-Message-State: AC+VfDxUTkxLhiGFW167bF7UL+Gte2BcXWz0/op8zc71wcOJ90Zf/QQw fFfKLqOszqOf78K6OP89mNj3tES9MfELQBjgVI48bh1XiHLxAQ== X-Google-Smtp-Source: ACHHUZ7gI6U6SNIJTmG4/dIsma30xjeqVNBoC6verlSPCnoRTbnZxjsEVh55ZqdhXPRko/v8U2bpn0RHmcdW2BQSGC8= X-Received: by 2002:a05:6214:5094:b0:5f1:606b:a9ca with SMTP id kk20-20020a056214509400b005f1606ba9camr7344504qvb.37.1685287934731; Sun, 28 May 2023 08:32:14 -0700 (PDT) Precedence: bulk X-Mailing-List: linux-sunxi@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 References: <20230527132747.83196-1-frank@oltmanns.dev> <20230527132747.83196-3-frank@oltmanns.dev> <87sfbgwyvp.fsf@oltmanns.dev> In-Reply-To: <87sfbgwyvp.fsf@oltmanns.dev> From: Julian Calaby Date: Mon, 29 May 2023 01:32:02 +1000 Message-ID: Subject: Re: [RFC PATCH 2/3] clk: sunxi-ng: Implement precalculated NKM rate selection To: Frank Oltmanns Cc: linux-arm-kernel@lists.infradead.org, linux-clk@vger.kernel.org, linux-kernel@vger.kernel.org, linux-sunxi@lists.linux.dev, Andre Przywara , Chen-Yu Tsai , Icenowy Zheng , Jernej Skrabec , Maxime Ripard , Michael Turquette , Rob Herring , Samuel Holland , Stephen Boyd Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Frank, On Sun, May 28, 2023 at 8:10=E2=80=AFPM Frank Oltmanns = wrote: > > Hi Julian, > > On 2023-05-28 at 09:19:36 +1000, Julian Calaby = wrote: > > Hi Frank, > > > > On Sat, May 27, 2023 at 11:37=E2=80=AFPM Frank Oltmanns wrote: > >> > >> Add a new precalculation method for NKM clock rate selection in the > >> sunxi-ng clock driver. Introduce ccu_nkm_find_best_precalc which uses = a > >> precalculated table of valid NKM combinations (struct clk_nkm_table an= d > >> struct clk_nkm_combo) to find the best rate. This approach provides > >> faster rate selection by searching a table of valid combinations rathe= r > >> than calculating for all possible combinations. > >> > >> The table of NKM combinations needs to be initialized with meaningful > >> combinations only, i.e. removing redundant combinations that result in > >> the same rate. > >> > >> Keep the existing ccu_nkm_find_best function in place and use it as a > >> fallback if no precalculated table is provided. > >> > >> Signed-off-by: Frank Oltmanns > >> --- > >> drivers/clk/sunxi-ng/ccu_nkm.c | 84 +++++++++++++++++++++++++++------= - > >> drivers/clk/sunxi-ng/ccu_nkm.h | 26 +++++++++++ > >> 2 files changed, 94 insertions(+), 16 deletions(-) > >> > >> diff --git a/drivers/clk/sunxi-ng/ccu_nkm.c b/drivers/clk/sunxi-ng/ccu= _nkm.c > >> index 94d2a83992b2..9652f6df17bd 100644 > >> --- a/drivers/clk/sunxi-ng/ccu_nkm.c > >> +++ b/drivers/clk/sunxi-ng/ccu_nkm.c > >> @@ -54,6 +54,49 @@ static unsigned long ccu_nkm_find_best(unsigned lon= g parent, unsigned long rate, > >> return best_rate; > >> } > >> > >> +static unsigned long ccu_nkm_find_best_precalc(unsigned long parent, > >> + unsigned long rate, > >> + struct _ccu_nkm *nkm, > >> + struct clk_nkm_table *t= able) > >> +{ > >> + unsigned long best_rate =3D 0, best_diff =3D ULONG_MAX; > >> + unsigned long best_n =3D 0, best_k =3D 0, best_m =3D 0; > >> + int start =3D 0, end =3D table->num - 1, mid; > >> + > >> + while (start <=3D end) { > >> + unsigned long tmp_rate; > >> + unsigned long tmp_diff; > >> + > >> + mid =3D (start + end) / 2; > >> + > >> + tmp_rate =3D parent * table->combos[mid].n * table->co= mbos[mid].k / > >> + table->combos[mid].m; > >> + > >> + tmp_diff =3D abs(rate - tmp_rate); > >> + > >> + if (tmp_diff < best_diff) { > >> + best_rate =3D tmp_rate; > >> + best_diff =3D tmp_diff; > >> + best_n =3D table->combos[mid].n; > >> + best_k =3D table->combos[mid].k; > >> + best_m =3D table->combos[mid].m; > >> + if (best_diff =3D=3D 0) > >> + goto out; > >> + } > > > > Thank you for your feedback! > > In my proposal, the code performs a binary search by > 1. taking the element in the middle (mid) > 2. calculating the rate of the element (tmp_rate) > 3. calculating the difference to the requested rate (tmp_diff) > 4. if the diff is better than the best_diff making it the new best > n-k-m-combo (the if block) I'm so sorry, I thought that this was still doing a linear search as it's so close to the original code. > > > If the table was sorted by n * k / m, this could just be a process of > > Please note, the table already has to be sorted for the function to > work, as is the nature of a binary search. I should definitely add > comments. I'm sorry, the code was intended more as a basis to discuss > the general idea that I described in the cover letter. I should have > made that clearer. > > > searching through until we either: > > - find that the first rate in the table is too high > > I could see that I could add two steps in the beginning, before the loop: > - Take the first element and see if its rate is greater than the > requested rate, if so immediatly return it > - Take the last element and see if its rate is less than the requested > rate, if so immediatly return it > > Is that what you mean? I'd have to run some simulations to see, if this > is a real improvement, because we would need two additional rate > calculations. Worst case would therefore be 2+log(n) calculations > instead of log(n) and the code would be slightly more complicated in my > opinion. But if we run this function with all possible parents rate (as > suggested in the end of my cover letter) these two special cases could > very well be often applicable. Thanks! > > > - find an exact rate > > What do you mean by "exact rate"? Do you mean a rate that matches the > requested rate exactly. This is what the code is already trying to do. > But, as this is not always possible, in cases where it does not find an > exact match, it takes the closest match instead. > > > - go above the requested rate, then there's only two to compare: our > > current rate and the previous one > > Sorry, you've lost me here. How would I go above the requested rate? You > would have to do the binary search to find that rate, but then why not > search the closest rate directly (as the code does) instead of searching > the closest rate above the requested (as you proposed). I feel like > either one of us is missing something. :) What we're missing is that I'm not explaining this well. Let's take a very simple table: (value =3D parent * n * k / m) 0. 100 1. 200 2. 300 3. 400 If we search for 50, our closest is the first rate, so index 0: this is the "find that the first rate in the table is too high" case. If we search for 300, we'll converge on index 2: this is the "exact rate" situation. If we search for 275, then we'll converge on either 200 or 300: this is the "two to compare" situation: if we converge until we get to the lowest rate above our target, we only need to check the rate immediately before it in the table and the one we converged on to find the closest. So in pseudo-code, we'd end up with something like this: -------- start =3D 0; cur_rate =3D parent * table[start].n * table[start].k / table[start].m; if (cur_rate >=3D target) return table[start]; while (start <=3D end) { mid =3D (start + end) / 2; cur_rate =3D parent * table[mid].n * table[mid].k / table[mid].m; if (cur_rate =3D=3D target) return table[mid]; if (target < cur_rate) end =3D mid - 1; else start =3D mid + 1; } prev_rate =3D parent * table[mid - 1].n * table[mid - 1].k / table[mid - 1]= .m; if (abs(target - prev_rate) < abs(target - cur_rate)) return table[mid - 1]; return table[mid]; -------- Which seems simpler to my eye and moves all the difference calculations out of the loop so they only have to be done once, effectively trading a difference calculation on each checked rate for a rate calculation, and dropping some variables in the process. Thanks, --=20 Julian Calaby Email: julian.calaby@gmail.com Profile: http://www.google.com/profiles/julian.calaby/