Received-SPF: pass (google.com: domain of linux-kernel+bounces-135383-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99;
From: Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= <toke@toke.dk>
To: Kuan-Wei Chiu <visitorckw@gmail.com>
Cc: jhs@mojatatu.com, xiyou.wangcong@gmail.com, jiri@resnulli.us,
 davem@davemloft.net, edumazet@google.com, kuba@kernel.org,
 pabeni@redhat.com, jserv@ccns.ncku.edu.tw, cake@lists.bufferbloat.net,
 netdev@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH net-next] net: sched: cake: Optimize number of calls to
 cake_heapify()
In-Reply-To: <ZhPRfYt0BLh9UELN@visitorckw-System-Product-Name>
References: <20240406235532.613696-1-visitorckw@gmail.com>
 <87frvxgnmr.fsf@toke.dk> <ZhPRfYt0BLh9UELN@visitorckw-System-Product-Name>
Date: Mon, 08 Apr 2024 15:00:29 +0200
Message-ID: <87cyr0ggb6.fsf@toke.dk>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Kuan-Wei Chiu <visitorckw@gmail.com> writes:

> On Sun, Apr 07, 2024 at 06:10:04PM +0200, Toke H=C3=B8iland-J=C3=B8rgense=
n wrote:
>> Kuan-Wei Chiu <visitorckw@gmail.com> writes:
>>=20
>> > Improve the max-heap construction process by reducing unnecessary
>> > heapify operations. Specifically, adjust the starting condition from
>> > n / 2 to n / 2 - 1 in the loop that iterates over all non-leaf
>> > elements.
>>=20
>> Please add an explanation for why this change is correct, and why it is
>> beneficial. "Improve" and "unnecessary" is way too implicit.
>>=20
>> pw-bot: cr
>
> For correctness:
> To build a heap, we need to perform heapify operations on all non-leaf
> nodes, so we need to find the index of the first non-leaf node. In a
> heap, the index of node i, the left child's index is 2 * i + 1, and the
> right child's index is 2 * i + 2. The left and right children of node
> CAKE_MAX_TINS * CAKE_QUEUES / 2 are at indexes CAKE_MAX_TINS *
> CAKE_QUEUES + 1 and CAKE_MAX_TINS * CAKE_QUEUES + 2, respectively. Both
> children's indexes are beyond the range of the heap, indicating that
> CAKE_MAX_TINS * CAKE_QUEUES / 2 is a leaf node. The left child of node
> CAKE_MAX_TINS * CAKE_QUEUES / 2 - 1 is at index CAKE_MAX_TINS *
> CAKE_QUEUES - 1, and the right child is at index CAKE_MAX_TINS *
> CAKE_QUEUES. Therefore, we know the left child exists, but the right
> child does not. Since it's not a leaf node, the loop should start from
> it.
>
> For benefit:
> We can reduce 2 function calls (one for cake_heapify() and another for
> cake_heap_get_backlog()) and decrease 5 branch condition evaluations
> (one for iterating through all non-leaf nodes, one inside the while
> loop of cake_heapify(), and three more inside the while loop with if
> conditions). The only added operation is an extra subtraction.
>
> If you're satisfied with the explanation above, I can attempt to
> rewrite the commit message and send the v2 patch.

Yes, sounds reasonable. Did you measure any real-world performance
benefit, or is this purely a theoretical optimisation? Either way,
please indicate this in the updated patch description.

-Toke