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 3686E3B2A4 for ; Tue, 9 Apr 2024 05:45:05 -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=1712655903; bh=7OKr4HycDUeB/zx8rBNu9gxtoijefw8jgpd7xIePUfQ=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=J1tiPFsk9FCwNjYBmljWSGdsrXeJyiwirEHHvVen2Uh35VRFDdhBPVG/RTTXdPoAX TMvFcJZQp1aTUYf7YWbBs0EUMw2yoFF6BqJrv0G/VR2OClsb9aGPFG861t6Y6FGrbG DrFBoHao4ZKGjsRrj6QWwLz5FwetZ+g640M8Kg3QKJePV/PTEVpHUjYzoFMKLDmVug c4scIHdjgRqCs4saDZgRX/EydaWn/d0G3iqKvciQ00iyzwyQip0TAig02Tih5S0jxQ loYscQccqiVg93MfmS+G6HSO2UvFFznIZvVlToA+jujb58tzsTFVcIbPaRLI03zK5j gNbooxZuWXj2Q== 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, Kuan-Wei Chiu In-Reply-To: <20240408174716.751069-1-visitorckw@gmail.com> References: <20240408174716.751069-1-visitorckw@gmail.com> Date: Tue, 09 Apr 2024 11:45:03 +0200 X-Clacks-Overhead: GNU Terry Pratchett Message-ID: <871q7ehnts.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 v2] net: sched: cake: Optimize the number of function calls and branches in heap construction 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: Tue, 09 Apr 2024 09:45:05 -0000 Kuan-Wei Chiu writes: > When constructing a heap, heapify operations are required on all > non-leaf nodes. Thus, determining the index of the first non-leaf node > is crucial. In a heap, the left child's index of node i is 2 * i + 1 > and the right child's index is 2 * i + 2. Node CAKE_MAX_TINS * > CAKE_QUEUES / 2 has its left and right children at indexes > CAKE_MAX_TINS * CAKE_QUEUES + 1 and CAKE_MAX_TINS * CAKE_QUEUES + 2, > respectively, which are beyond the heap's range, indicating it as a > leaf node. Conversely, node CAKE_MAX_TINS * CAKE_QUEUES / 2 - 1 has a > left child at index CAKE_MAX_TINS * CAKE_QUEUES - 1, confirming its > non-leaf status. The loop should start from it since it's not a leaf > node. > > By starting the loop from CAKE_MAX_TINS * CAKE_QUEUES / 2 - 1, we > minimize function calls and branch condition evaluations. This > adjustment theoretically reduces two function calls (one for > cake_heapify() and another for cake_heap_get_backlog()) and five branch > evaluations (one for iterating all non-leaf nodes, one within > cake_heapify()'s while loop, and three more within the while loop > with if conditions). > > Signed-off-by: Kuan-Wei Chiu Acked-by: Toke H=C3=B8iland-J=C3=B8rgensen