Speed-up pfifo_fast lookup using a bitmap
Subsystems (3)
PATCH 1/1 Speed-up pfifo_fast lookup using a bitmap
Maintain a per-qdisc bitmap indicating availability of skbs for each band. This helps in faster lookup for a skb when there are no high priority skbs. Also, it helps in (rare) cases where there are no skbs on the list where an immediate lookup helps rather than iterating through the three bands.
Another option I considered was to create a private qdisc pointer and avoid touching Qdisc structure:
struct pfifo_fast_priv {
unsigned long bitmap;
struct sk_buff_head q[PFIFO_FAST_BANDS];
};but the test numbers came a little less, since it takes a few more memory references on enqueue/dequeue.
By keeping the bitmap in Qdisc, it is possible to implement the lookup for other schedulers, maybe sch_prio which goes through 16 bands?
The BW numbers are average across 5 iterations for multiple netperf sessions (1-12 on x86_64, and 1-32 on P6) tested with Chelsio 10 gbps cards over a 2 hour run:
-------------------------------------------------------------------------
| x86_64 (Mb/s) | P6 (Mb/s) --------------------------------------|---------------------------------- Size | ORG BW NEW BW | ORG BW NEW BW -----|--------------------------------|---------------------------------- 16K | 157700 158237 | 153876 156696 64K | 155916 157882 | 154176 155987 128K | 155122 155628 | 154983 155904 256K | 154808 158913 | 153898 155164
-------------------------------------------------------------------------
Thanks,
- KK
---
include/net/sch_generic.h | 1 net/sched/sch_generic.c | 46 +++++++++++++++++++++++------------- 2 files changed, 31 insertions(+), 16 deletions(-)
include/net/sch_generic.h +1 -0
@@ -72,6 +72,7 @@ struct Qdisc* For performance sake on SMP, we put highly modified fields at the end */ unsigned long state; +unsigned long bitmap;struct sk_buff_head q;struct gnet_stats_basic bstats;struct gnet_stats_queue qstats;
net/sched/sch_generic.c +30 -16
74 lines not on this page · raw message
Quoted 6 lines · Krishna Kumar
Maintain a per-qdisc bitmap indicating availability of skbs for each band. This helps in faster lookup for a skb when there are no high priority skbs. Also, it helps in (rare) cases where there are no skbs on the list where an immediate lookup helps rather than iterating through the three bands.
Quoted 8 lines
Another option I considered was to create a private qdisc pointer and avoid touching Qdisc structure:
struct pfifo_fast_priv { unsigned long bitmap; struct sk_buff_head q[PFIFO_FAST_BANDS]; };but the test numbers came a little less, since it takes a few more memory references on enqueue/dequeue.
If it's exactly "a little less" I'd consider keeping it private yet...
Quoted 18 lines
By keeping the bitmap in Qdisc, it is possible to implement the lookup for other schedulers, maybe
sch_priowhich goes through 16 bands?The BW numbers are average across 5 iterations for multiple netperf sessions (1-12 on
x86_64, and 1-32 on P6) tested with Chelsio 10 gbps cards over a 2 hour run:-------------------------------------------------------------------------
| x86_64 (Mb/s) | P6 (Mb/s) --------------------------------------|---------------------------------- Size | ORG BW NEW BW | ORG BW NEW BW -----|--------------------------------|---------------------------------- 16K | 157700 158237 | 153876 156696 64K | 155916 157882 | 154176 155987 128K | 155122 155628 | 154983 155904 256K | 154808 158913 | 153898 155164
Quoted 1 line
-------------------------------------------------------------------------
Btw, I wonder how much gain of your previous (_CAN_BYPASS) patch is saved after this change...
Quoted 27 lines
Thanks,
- KK
Signed-off-by Krishna Kumar <[email protected]>---
include/net/sch_generic.h | 1 net/sched/sch_generic.c | 46 +++++++++++++++++++++++------------- 2 files changed, 31 insertions(+), 16 deletions(-)diff -ruNp
org/include/net/sch_generic.hnew/include/net/sch_generic.hinclude/net/sch_generic.h +1
-0@@ -72,6 +72,7 @@ struct Qdisc* For performance sake on SMP, we put highly modified fields at the end */ unsigned long state; +unsigned long bitmap;struct sk_buff_head q;struct gnet_stats_basic bstats;struct gnet_stats_queue qstats;diff -ruNp
org/net/sched/sch_generic.cnew/net/sched/sch_generic.c
net/sched/sch_generic.c static const u8 prio2band[TC_PRIO_MAX+1] · line 410
Quoted 7 lines
net/sched/sch_generic.c +2
-2@@ -406,18 +406,29 @@ static const u8 prio2band[TC_PRIO_MAX+1]#define PFIFO_FAST_BANDS 3 -static inline struct sk_buff_head *prio2list (struct sk_buff *skb, -struct Qdisc *qdisc) +/* +* Convert a bitmap to the first band number where an skb is queue'd, where:
- * Convert a bitmap to the first band number where an skb is queue'd, where:
+ * Convert a bitmap to the first band number where an skb is queued, where:
net/sched/sch_generic.c static const u8 prio2band[TC_PRIO_MAX+1] · line 412
Quoted 2 lines
net/sched/sch_generic.c +2
-0+* bitmap=0 means there are no skbs for any bands +* bitmap=1 means there is a skb on band 0
- * bitmap=1 means there is a skb on band 0
+ * bitmap=1 means there is an skb on band 0
net/sched/sch_generic.c static const u8 prio2band[TC_PRIO_MAX+1] · line 416
Quoted 4 lines
net/sched/sch_generic.c +4
-0+* bitmap=7 means there are skbs on all 3 bands, etc. +*/ +static const int bitmap2band[] = + {-1 ,0 ,1 ,0 ,2 ,0 ,1 ,0 };
Why wrapped?
...
... pfifo_fast_reset(...)
{
...+ qdisc->bitmap = 0; ?
}
Thanks,
Jarek P.
Quoted 6 lines
Jarek Poplawski <[email protected]>
Quoted 2 lines
but the test numbers came a little less, since it takes a few more memory references on enqueue/dequeue.
If it's exactly "a little less" I'd consider keeping it private yet...
Sounds reasonable. To quantify that, I will test again for a longer run and report the difference.
Quoted 2 lines
Btw, I wonder how much gain of your previous (
_CAN_BYPASS) patch is saved after this change...
The tests are on the latest tree which contains CAN_BYPASS. So a single netperf process running this change will get no advantage since this enqueue/dequeue never happens unless the NIC is slow. But for multiple processes, it should help.
Quoted 1 line
- * Convert a bitmap to the first band number where an skb is queue'd,
where:
Quoted 1 line
+ * Convert a bitmap to the first band number where an skb is queued,
where:
Quoted 7 lines
Quoted 3 lines
+ * bitmap=0 means there are no skbs for any bands
+ * bitmap=1 means there is a skb on band 0- * bitmap=1 means there is a skb on band 0
+ * bitmap=1 means there is an skb on band 0
Quoted 6 lines
net/sched/sch_generic.c static const u8 prio2band[TC_PRIO_MAX+1] · line 416
Quoted 4 lines
+ * bitmap=7 means there are skbs on all 3 bands, etc.
+ */net/sched/sch_generic.c +2
-0+static const int bitmap2band[] = + {-1 ,0 ,1 ,0 ,2 ,0 ,1 ,0 };Why wrapped?
cut-n-paste of prio2band, I will fix this and the above comments.
Quoted 7 lines
...
...pfifo_fast_reset(...){ ...+
qdisc->bitmap= 0; ?
}
Correct. Thanks for pointing this out.
Regards,
- KK
Quoted 9 lines · On Thu, Aug 13, 2009 at 04:11:57PM +0530, Krishna Kumar2 wrote:
Quoted 6 lines
Jarek Poplawski <[email protected]>
Quoted 2 lines
but the test numbers came a little less, since it takes a few more memory references on enqueue/dequeue.
If it's exactly "a little less" I'd consider keeping it private yet...
Sounds reasonable. To quantify that, I will test again for a longer run and report the difference.
Yes, more numbers would be appreciated.
Quoted 8 lines
Quoted 3 lines
Btw, I wonder how much gain of your previous (
_CAN_BYPASS) patch is saved after this change...The tests are on the latest tree which contains
CAN_BYPASS. So a single netperf process running this change will get no advantage since this enqueue/dequeue never happens unless the NIC is slow. But for multiple processes, it should help.
I mean: since the previous patch saved ~2% on omitting enqueue/dequeue, and now enqueue/dequeue is ~2% faster, is it still worth to omit this?
Regards,
Jarek P.