net: sched: cake: Optimize the number of function calls and branches in heap construction
Subsystems (4)
PATCH v2 1/1 net: sched: cake: Optimize the number of function calls and branches in heap construction
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).
--- net/sched/sch_cake.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_cake.c +1 -1
@@ -1512,7 +1512,7 @@ static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)if (!q->overflow_timeout) {int i;/* Build fresh max-heap */ -for (i =CAKE_MAX_TINS *CAKE_QUEUES /2 ; i >=0 ; i--) +for (i =CAKE_MAX_TINS *CAKE_QUEUES /2 -1 ; i >=0 ; i--)cake_heapify (q, i); } q->overflow_timeout =65535 ;
Signature · 1 line
2.34.1
Quoted 20 lines · Kuan-Wei Chiu
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 indexesCAKE_MAX_TINS*CAKE_QUEUES+ 1 andCAKE_MAX_TINS*CAKE_QUEUES+ 2, respectively, which are beyond the heap's range, indicating it as a leaf node. Conversely, nodeCAKE_MAX_TINS*CAKE_QUEUES/ 2 - 1 has a left child at indexCAKE_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 forcake_heapify()and another forcake_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).
Quoted 1 line
Signed-off-by Kuan-Wei Chiu <[email protected]>
This patch was applied to netdev/net-next.git (main) by Jakub Kicinski <[email protected]>:
Hello:
This patch was applied to netdev/net-next.git (main) by Jakub Kicinski <[email protected]>:
Quoted 12 lines · On Tue, 9 Apr 2024 01:47:16 +0800 you wrote:
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 indexesCAKE_MAX_TINS*CAKE_QUEUES+ 1 andCAKE_MAX_TINS*CAKE_QUEUES+ 2, respectively, which are beyond the heap's range, indicating it as a leaf node. Conversely, nodeCAKE_MAX_TINS*CAKE_QUEUES/ 2 - 1 has a left child at indexCAKE_MAX_TINS*CAKE_QUEUES- 1, confirming its non-leaf status. The loop should start from it since it's not a leaf node.
Quoted 1 line
[...]
Here is the summary with links:
- [net-next,v2] net: sched: cake: Optimize the number of function calls and branches in heap construction
https://git.kernel.org/netdev/net-next/c/d034d02de882
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html