lkml.org 
[lkml]   [2016]   [Sep]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [RFC PATCH v2 3/5] futex: Throughput-optimized (TO) futexes
    On 09/22/2016 04:38 PM, Thomas Gleixner wrote:
    > On Thu, 22 Sep 2016, Waiman Long wrote:
    >> BTW, my initial attempt for the new futex was to use the same workflow as the
    >> PI futexes, but use mutex which has optimistic spinning instead of rt_mutex.
    >> That version can double the throughput compared with PI futexes but still far
    >> short of what can be achieved with wait-wake futex. Looking at the performance
    >> figures from the patch:
    >>
    >> wait-wake futex PI futex TO futex
    >> --------------- -------- --------
    >> max time 3.49s 50.91s 2.65s
    >> min time 3.24s 50.84s 0.07s
    >> average time 3.41s 50.90s 1.84s
    >> sys time 7m22.4s 55.73s 2m32.9s
    > That's really interesting. Do you have any explanation for this massive
    > system time differences?

    For the wait-wake futexes, the waiters will be kicked out with EAGAIN
    without sleeping as long as the futex value changes before they acquire
    the hash bucket spinlock. These waiters will attempt to acquire the lock
    again in the user space. If that fails, they will call FUTEX_WAIT again.

    In the above test case, the critical section is pretty short and about
    4/5 of the FUTEX_WAIT calls resulted in an EAGAIN error. So there are a
    lot more user-space/kernel transitions than the TO futexes. I think the
    difference in the number of FUTEX_WAIT calls vs. the FUTEX_LOCK_TO calls
    causes the difference between their sys times. As for the PI futex, it
    is a strictly sleeping lock and so won't use that much sys time.

    >> lock count 3,090,294 9,999,813 698,318
    >> unlock count 3,268,896 9,999,814 134
    >>
    >> The problem with a PI futexes like version is that almost all the lock/unlock
    >> operations were done in the kernel which added overhead and latency. Now
    >> looking at the numbers for the TO futexes, less than 1/10 of the lock
    >> operations were done in the kernel, the number of unlock was insignificant.
    >> Locking was done mostly by lock stealing. This is where most of the
    >> performance benefit comes from, not optimistic spinning.
    > How does the lock latency distribution of all this look like and how fair
    > is the whole thing?

    The TO futexes are unfair as can be seen from the min/max thread times
    listed above. It took the fastest thread 0.07s to complete all the
    locking operations, whereas the slowest one needed 2.65s. However, the
    situation reverses when I changed the critical section to a 1us sleep.
    In this case, there will be no optimistic spinning. The performance
    results for 100k locking operations were listed below.

    wait-wake futex PI futex TO futex
    --------------- -------- --------
    max time 0.06s 9.32s 4.76s
    min time 5.59s 9.36s 5.62s
    average time 3.25s 9.35s 5.41s

    In this case, the TO futexes are fairer but perform worse than the
    wait-wake futexes. That is because the lock handoff mechanism limit the
    amount of lock stealing in the TO futexes while the wait-wake futexes
    have no such restriction. When I disabled lock handoff, the TO futexes
    would then perform similar to the wait-wake futexes.

    >
    >> This is also the reason that a lock handoff mechanism is implemented to
    >> prevent lock starvation which is likely to happen without one.
    > Where is that lock handoff mechanism?
    >
    >

    In the futex_state object, there is a new field handoff_pid. It is set
    when the threshold count in futex_spin_on_owner() becomes negative When
    this field is set, the unlocker will change the futex word to that value
    instead of clearing it to 0 and others can steal it. I will separate out
    the lock handoff in a separate patch in the next revision to highlight it.

    Cheers,
    Longman

    \
     
     \ /
      Last update: 2016-09-23 00:04    [W:4.344 / U:0.696 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site