• Eric Dumazet's avatar
    [PATCH] SLAB: use a multiply instead of a divide in obj_to_index() · 6a2d7a95
    Eric Dumazet authored
    When some objects are allocated by one CPU but freed by another CPU we can
    consume lot of cycles doing divides in obj_to_index().
    (Typical load on a dual processor machine where network interrupts are
    handled by one particular CPU (allocating skbufs), and the other CPU is
    running the application (consuming and freeing skbufs))
    Here on one production server (dual-core AMD Opteron 285), I noticed this
    divide took 1.20 % of CPU_CLK_UNHALTED events in kernel.  But Opteron are
    quite modern cpus and the divide is much more expensive on oldest
    architectures :
    On a 200 MHz sparcv9 machine, the division takes 64 cycles instead of 1
    cycle for a multiply.
    Doing some math, we can use a reciprocal multiplication instead of a divide.
    If we want to compute V = (A / B)  (A and B being u32 quantities)
    we can instead use :
    V = ((u64)A * RECIPROCAL(B)) >> 32 ;
    where RECIPROCAL(B) is precalculated to ((1LL << 32) + (B - 1)) / B
    Note :
    I wrote pure C code for clarity. gcc output for i386 is not optimal but
    acceptable :
    mull   0x14(%ebx)
    mov    %edx,%eax // part of the >> 32
    xor     %edx,%edx // useless
    mov    %eax,(%esp) // could be avoided
    mov    %edx,0x4(%esp) // useless
    mov    (%esp),%ebx
    [akpm@osdl.org: small cleanups]
    Signed-off-by: default avatarEric Dumazet <dada1@cosmosbay.com>
    Cc: Christoph Lameter <clameter@sgi.com>
    Cc: David Miller <davem@davemloft.net>
    Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
reciprocal_div.h 846 Bytes