Skip to contentSkip to conversation

ring buffer indices: way too much modulo (division!) fiddling

DISCUSSION Andreas Mohr 2 participants 2 messages Mar 21, 2006

lore
Share & tools
lore
#0 lore raw

Hello all,

"Just One" shocking example (2.6.16 arch/i386/kernel/apm.c):

static apm_event_t get_queued_event(struct apm_user *as)

{
        as->event_tail = (as->event_tail + 1) % APM_MAX_EVENTS;
        return as->events[as->event_tail];
}

objdump x86 output:

000007cf <get_queued_event>:

     7cf:       83 ec 08                sub    $0x8,%esp
     7d2:       ba 67 66 66 66          mov    $0x66666667,%edx
     7d7:       89 74 24 04             mov    %esi,0x4(%esp)
     7db:       89 1c 24                mov    %ebx,(%esp)
     7de:       89 c6                   mov    %eax,%esi
     7e0:       8b 58 24                mov    0x24(%eax),%ebx
     7e3:       83 c3 01                add    $0x1,%ebx
     7e6:       89 d8                   mov    %ebx,%eax
     7e8:       89 d9                   mov    %ebx,%ecx
     7ea:       f7 ea                   imul   %edx
     7ec:       c1 f9 1f                sar    $0x1f,%ecx
     7ef:       c1 fa 03                sar    $0x3,%edx
     7f2:       29 ca                   sub    %ecx,%edx
     7f4:       6b d2 14                imul   $0x14,%edx,%edx
     7f7:       29 d3                   sub    %edx,%ebx
     7f9:       0f b7 44 5e 28          movzwl 0x28(%esi,%ebx,2),%eax
     7fe:       89 5e 24                mov    %ebx,0x24(%esi)
     801:       8b 1c 24                mov    (%esp),%ebx
     804:       8b 74 24 04             mov    0x4(%esp),%esi
     808:       83 c4 08                add    $0x8,%esp
     80b:       c3                      ret

Doing it The Probably Proper Way (tm):

static apm_event_t get_queued_event(struct apm_user *as)

{
        if (++as->event_tail >= APM_MAX_EVENTS)
              as->event_tail = 0;
        return as->events[as->event_tail];
}

objdump x86 output:

000007cf <get_queued_event>:

     7cf:       8b 48 24                mov    0x24(%eax),%ecx
     7d2:       31 d2                   xor    %edx,%edx
     7d4:       83 c1 01                add    $0x1,%ecx
     7d7:       83 f9 14                cmp    $0x14,%ecx
     7da:       0f 4c d1                cmovl  %ecx,%edx
     7dd:       89 50 24                mov    %edx,0x24(%eax)
     7e0:       0f b7 44 50 28          movzwl 0x28(%eax,%edx,2),%eax
     7e5:       c3                      ret

Result: no painful division avoidance (0x66666667 factors, imul), *vastly* shorter function (22 vs. 60 bytes), most likely **WAY** faster (no multiplication cycle burning, better pipelining, less opcodes).

Any problems with such a change that I'm missing here?

If such a change holds water, then I'd strongly suggest creating a new (arch-specific?) macro named something like

ringbuf_advance_idx(my_idx_var, MY_BUF_SIZE)

(any more generic name? It's not always about ring buffers...)

to be used all over the place instead of custom-writing stuff (and getting it imperfect/wrong) in many cases.
This would be a perfect job for kernel-janitors, if you ask me.

Or does there happen to be a macro already for such a rather common operation?

This kind of unnecessary modulo operation happens in lots of places (mostly network drivers).
Probably the most prominent (read: painful) place is ./mm/hugetlb.c/alloc_fresh_huge_page()
(if I judge that place right; I cannot easily verify it since I don't have and don't know how to configure a NUMA machine setup/image)
So, additional question:
can anyone confirm that alloc_fresh_huge_page() binary code uses an expensive division or multiplication on a NUMA machine?

Comments?

Andreas Mohr

#1 lore raw
Quoted 7 lines · Andreas Mohr

"Just One" shocking example (2.6.16 arch/i386/kernel/apm.c):

static apm_event_t get_queued_event(struct apm_user *as)

{
        as->event_tail = (as->event_tail + 1) % APM_MAX_EVENTS;
        return as->events[as->event_tail];
}

[...]

Quoted 1 line
     7d7:       83 f9 14                cmp    $0x14,%ecx

APM_MAX_EVENTS appears to be 20, not a power of 2. GCC does the obvious transform of modulo to an ANDL when the modulus is a sane value. Rewrite the above as a four line function and run it through gcc -S to see to difference bewteen APM_MAX_EVENTS=20 and =32.

Quoted 1 line

Any problems with such a change that I'm missing here?

<shrug> It's probably not a wide-spread problem. How many places in the kernel use ringbuffers that aren't sized to a power of 2?

Quoted 2 lines

ringbuf_advance_idx(my_idx_var, MY_BUF_SIZE)
(any more generic name? It's not always about ring buffers...)

modulo_add? But it's probably unneccessary, unless this really is widespread. Even then, just correcting those already in place would be better than adding yet another abstraction of a simple operation to the kernel.

Quoted 2 lines

This kind of unnecessary modulo operation happens in lots of places (mostly network drivers).

Check to see if those are power of 2 sized buffers. gcc really will do those correctly.

Ray