lkml.org 
[lkml]   [2013]   [Jan]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH 0/5] x86,smp: make ticket spinlock proportional backoff w/ auto tuning
    On 01/09/2013 03:56 AM, Rik van Riel wrote:
    > Many spinlocks are embedded in data structures; having many CPUs
    > pounce on the cache line the lock is in will slow down the lock
    > holder, and can cause system performance to fall off a cliff.
    >
    > The paper "Non-scalable locks are dangerous" is a good reference:
    >
    > http://pdos.csail.mit.edu/papers/linux:lock.pdf
    >
    > In the Linux kernel, spinlocks are optimized for the case of
    > there not being contention. After all, if there is contention,
    > the data structure can be improved to reduce or eliminate
    > lock contention.
    >
    > Likewise, the spinlock API should remain simple, and the
    > common case of the lock not being contended should remain
    > as fast as ever.
    >
    > However, since spinlock contention should be fairly uncommon,
    > we can add functionality into the spinlock slow path that keeps
    > system performance from falling off a cliff when there is lock
    > contention.
    >
    > Proportional delay in ticket locks is delaying the time between
    > checking the ticket based on a delay factor, and the number of
    > CPUs ahead of us in the queue for this lock. Checking the lock
    > less often allows the lock holder to continue running, resulting
    > in better throughput and preventing performance from dropping
    > off a cliff.
    >
    > The test case has a number of threads locking and unlocking a
    > semaphore. With just one thread, everything sits in the CPU
    > cache and throughput is around 2.6 million operations per
    > second, with a 5-10% variation.
    >
    > Once a second thread gets involved, data structures bounce
    > from CPU to CPU, and performance deteriorates to about 1.25
    > million operations per second, with a 5-10% variation.
    >
    > However, as more and more threads get added to the mix,
    > performance with the vanilla kernel continues to deteriorate.
    > Once I hit 24 threads, on a 24 CPU, 4 node test system,
    > performance is down to about 290k operations/second.
    >
    > With a proportional backoff delay added to the spinlock
    > code, performance with 24 threads goes up to about 400k
    > operations/second with a 50x delay, and about 900k operations/second
    > with a 250x delay. However, with a 250x delay, performance with
    > 2-5 threads is worse than with a 50x delay.
    >
    > Making the code auto-tune the delay factor results in a system
    > that performs well with both light and heavy lock contention,
    > and should also protect against the (likely) case of the fixed
    > delay factor being wrong for other hardware.
    >
    > The attached graph shows the performance of the multi threaded
    > semaphore lock/unlock test case, with 1-24 threads, on the
    > vanilla kernel, with 10x, 50x, and 250x proportional delay,
    > as well as the v1 patch series with autotuning for 2x and 2.7x
    > spinning before the lock is obtained, and with the v2 series.
    >
    > The v2 series integrates several ideas from Michel Lespinasse
    > and Eric Dumazet, which should result in better throughput and
    > nicer behaviour in situations with contention on multiple locks.
    >
    > For the v3 series, I tried out all the ideas suggested by
    > Michel. They made perfect sense, but in the end it turned
    > out they did not work as well as the simple, aggressive
    > "try to make the delay longer" policy I have now. Several
    > small bug fixes and cleanups have been integrated.
    >
    > Performance is within the margin of error of v2, so the graph
    > has not been update.
    >
    > Please let me know if you manage to break this code in any way,
    > so I can fix it...
    >

    Patch series does not show anymore weird behaviour because of the
    underflow (pointed by Michael) and looks fine.

    I ran kernbench on 32 core (mx3850) machine with 3.8-rc2 base.
    x base_3.8rc2
    + rik_backoff
    N Min Max Median Avg Stddev
    x 8 222.977 231.16 227.735 227.388 3.1512986
    + 8 218.75 232.347 229.1035 228.25425 4.2730225
    No difference proven at 95.0% confidence

    The run did not show much difference. But I believe a spinlock stress
    test would have shown the benefit.
    I 'll start running benchmarks now on kvm guests and comeback with report.



    \
     
     \ /
      Last update: 2013-01-09 14:41    [W:8.074 / U:1.072 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site