From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail.toke.dk (mail.toke.dk [45.145.95.4]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id E17163B2A4 for ; Mon, 8 Apr 2024 09:00:30 -0400 (EDT) From: Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=toke.dk; s=20161023; t=1712581229; bh=FkXLzyxqjZzUX3ydZJqpehjHFFdMSDLx+4h5DWHTIiY=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=wNVB4yArKpa2PUdlKiLdUKq+m0PD/rqSv51mIeW6FY3daUZxgK8MjoX3api0EigvJ d5z8okWEZnkeGojomYZA7aj65SsZa2dOSApaNxn8tFnlvRvlc/7hgZwq5qAZFZp7pL 1iaq0RtpGeDFMHpwyKAhdlW4p+XbPu3Kc3DuG0drdQvu4h3ol/L5ja8gwcd0Hitm1K T2NtVewABkVOGdCDoZbjpCZVKXITP4DD8t2PTpdUAby5d4tjjTeE6dNCaRZQfI7Ick FgMlzoZJSH9a24rzBvXxDStS9jsl0JRPl77FgvewUknuJ5doB+aFCH1YU8LucGi4yv LXUTQZ5bAez+A== To: Kuan-Wei Chiu 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 In-Reply-To: References: <20240406235532.613696-1-visitorckw@gmail.com> <87frvxgnmr.fsf@toke.dk> Date: Mon, 08 Apr 2024 15:00:29 +0200 X-Clacks-Overhead: GNU Terry Pratchett Message-ID: <87cyr0ggb6.fsf@toke.dk> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Cake] [PATCH net-next] net: sched: cake: Optimize number of calls to cake_heapify() X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 08 Apr 2024 13:00:31 -0000 Kuan-Wei Chiu writes: > On Sun, Apr 07, 2024 at 06:10:04PM +0200, Toke H=C3=B8iland-J=C3=B8rgense= n wrote: >> Kuan-Wei Chiu 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