Re: [PATCH] loop unrolling in net/sched/sch_generic.c

[Eric Dumazet <dada1@cosmosbay.com>]

Eric Dumazet a écrit :
>
> 
> Maybe we can rewrite the whole thing without branches, examining prio 
> from PFIFO_FAST_BANDS-1 down to 0, at least for modern cpu with 
> conditional mov (cmov)
> 
> struct sk_buff_head *best = NULL;
> struct sk_buff_head *list = qdisc_priv(qdisc)+PFIFO_FAST_BANDS-1;
> if (skb_queue_empty(list)) best = list ;
> list--;
> if (skb_queue_empty(list)) best = list ;
> list--;
> if (skb_queue_empty(list)) best = list ;
> if (best != NULL) {
>     qdisc->q.qlen--;
>     return __qdisc_dequeue_head(qdisc, best);
>     }
> 
> This version should have one branch.
> I will test this after some sleep :)
> See you
> Eric
> 
> 

(Sorry, still using 2.6.12, but the idea remains)

static struct sk_buff *
pfifo_fast_dequeue(struct Qdisc* qdisc)
{
         struct sk_buff_head *list = qdisc_priv(qdisc);
         struct sk_buff_head *best = NULL;

	list += 2;
         if (!skb_queue_empty(list))
                 best = list;
         list--;
         if (!skb_queue_empty(list))
                 best = list;
         list--;
         if (!skb_queue_empty(list))
                 best = list;
         if (best) {
                 qdisc->q.qlen--;
                 return __skb_dequeue(best);
                 }
         return NULL;
}



At least the compiler output seems promising :

0000000000000550 <pfifo_fast_dequeue>:
  550:   48 8d 97 f0 00 00 00    lea    0xf0(%rdi),%rdx
  557:   31 c9                   xor    %ecx,%ecx
  559:   48 8d 87 c0 00 00 00    lea    0xc0(%rdi),%rax
  560:   48 39 97 f0 00 00 00    cmp    %rdx,0xf0(%rdi)
  567:   48 0f 45 ca             cmovne %rdx,%rcx
  56b:   48 8d 97 d8 00 00 00    lea    0xd8(%rdi),%rdx
  572:   48 39 97 d8 00 00 00    cmp    %rdx,0xd8(%rdi)
  579:   48 0f 45 ca             cmovne %rdx,%rcx
  57d:   48 39 87 c0 00 00 00    cmp    %rax,0xc0(%rdi)
  584:   48 0f 45 c8             cmovne %rax,%rcx
  588:   31 c0                   xor    %eax,%eax
  58a:   48 85 c9                test   %rcx,%rcx
  58d:   74 32                   je     5c1 <pfifo_fast_dequeue+0x71> // one conditional branch
  58f:   ff 4f 40                decl   0x40(%rdi)
  592:   48 8b 11                mov    (%rcx),%rdx
  595:   48 39 ca                cmp    %rcx,%rdx
  598:   74 27                   je     5c1 <pfifo_fast_dequeue+0x71> // never taken branch : always predicted OK
  59a:   48 89 d0                mov    %rdx,%rax
  59d:   48 8b 12                mov    (%rdx),%rdx
  5a0:   ff 49 10                decl   0x10(%rcx)
  5a3:   48 c7 40 10 00 00 00    movq   $0x0,0x10(%rax)
  5aa:   00
  5ab:   48 89 4a 08             mov    %rcx,0x8(%rdx)
  5af:   48 89 11                mov    %rdx,(%rcx)
  5b2:   48 c7 40 08 00 00 00    movq   $0x0,0x8(%rax)
  5b9:   00
  5ba:   48 c7 00 00 00 00 00    movq   $0x0,(%rax)
  5c1:   90                      nop
  5c2:   c3                      retq

I Will post tomorrow some profiling results.
Eric