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

From: Andreas Mohr
Date: Tue Mar 21 2006 - 13:25:33 EST

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
(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?


Andreas Mohr
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/