net: sched: cake: Optimize number of calls to cake_heapify()
Subsystems (4)
PATCH 1/1 net: sched: cake: Optimize number of calls to cake_heapify()
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.
--- 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
Toke Høiland-Jørgensen
maintainerQuoted 4 lines · Kuan-Wei Chiu
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
Quoted 11 lines · Toke Høiland-Jørgensen
Quoted 4 lines · Kuan-Wei Chiu
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
Toke Høiland-Jørgensen
maintainerQuoted 35 lines · Kuan-Wei Chiu
Quoted 11 lines · Toke Høiland-Jørgensen
Quoted 4 lines · Kuan-Wei Chiu
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 nodeCAKE_MAX_TINS*CAKE_QUEUES/ 2 are at indexesCAKE_MAX_TINS*CAKE_QUEUES+ 1 andCAKE_MAX_TINS*CAKE_QUEUES+ 2, respectively. Both children's indexes are beyond the range of the heap, indicating thatCAKE_MAX_TINS*CAKE_QUEUES/ 2 is a leaf node. The left child of nodeCAKE_MAX_TINS*CAKE_QUEUES/ 2 - 1 is at indexCAKE_MAX_TINS*CAKE_QUEUES- 1, and the right child is at indexCAKE_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 forcake_heapify()and another forcake_heap_get_backlog()) and decrease 5 branch condition evaluations (one for iterating through all non-leaf nodes, one inside the while loop ofcake_heapify(), and three more inside the while loop with if conditions). The only added operation is an extra subtraction.
Quoted 2 lines
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