netdev - Re: [PATCH net-next] net: sched: cake: Optimize number of calls to cake

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <ZhPRfYt0BLh9UELN@visitorckw-System-Product-Name>
Date: Mon, 8 Apr 2024 19:14:05 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: Toke Høiland-Jørgensen <toke@...e.dk>
Cc: jhs@...atatu.com, xiyou.wangcong@...il.com, jiri@...nulli.us,
	davem@...emloft.net, edumazet@...gle.com, kuba@...nel.org,
	pabeni@...hat.com, jserv@...s.ncku.edu.tw,
	cake@...ts.bufferbloat.net, netdev@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH net-next] net: sched: cake: Optimize number of calls to
 cake_heapify()

On Sun, Apr 07, 2024 at 06:10:04PM +0200, Toke Høiland-Jørgensen wrote:
> Kuan-Wei Chiu <visitorckw@...il.com> writes:
> 
> > 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.
> 
> Please add an explanation for why this change is correct, and why it is
> beneficial. "Improve" and "unnecessary" is way too implicit.
> 
> 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.

Thanks,
Kuan-Wei