lkml.org 
[lkml]   [2014]   [Jan]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [PATCH RFC] reciprocal_divide: correction/update of the algorithm
    From
    Date
    On Tue, 2014-01-14 at 15:53 -0500, Austin S Hemmelgarn wrote:
    > On 2014-01-14 14:50, Eric Dumazet wrote:
    > > On Tue, 2014-01-14 at 14:22 -0500, Austin S Hemmelgarn wrote:
    > >
    > >> I disagree with the statement that current CPU's have reasonably fast
    > >> dividers. A lot of embedded processors and many low-end x86 CPU's do
    > >> not in-fact have any hardware divider, and usually provide it using
    > >> microcode based emulation if they provide it at all. The AMD Jaguar
    > >> micro-architecture in particular comes to mind, it uses an iterative
    > >> division algorithm provided by the microcode that only produces 2 bits
    > >> of quotient per cycle, even in the best case (2 8-bit integers and an
    > >> integral 8-bit quotient) this still takes 4 cycles, which is twice as
    > >> slow as any other math operation on the same processor.
    > >
    > > I doubt you run any BPF filter with a divide instruction in it on these
    > > platform.
    > >
    > > Get real, do not over optimize things where it does not matter.
    > >
    > Actually, I have three Jaguar based routers, and use BPF regularly as
    > part of their iptables rules to log certain packet types.



    1) Have you enabled BPF JIT

    2) Do you have divide instructions in a BPF filter,
    if yes, I would like to have an example.
    (current code works well for small divisors anyway)

    3) How much time is spent in BPF compared to the rest of the stack,
    especially if you run iptables...

    Spending 2 or 3 days of work to save ~7 cycles for a divide that
    probably can be replaced by a shift anyway, while spending 5000 cycles
    per packet is what I call not a wise optimization, especially
    if dealing with old hardware.

    Even on a Jaguar, the proposed alternative

    + u32 t = (u32)(((u64)a * R.m) >> 32);
    + return (t + ((a - t) >> R.sh1)) >> R.sh2;

    will have a similar cost.




    \
     
     \ /
      Last update: 2014-01-15 00:21    [W:2.206 / U:0.016 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site