• Abel Wu's avatar
    sched/eevdf: O(1) fastpath for task selection · ee4373dc
    Abel Wu authored
    Since the RB-tree is now sorted by deadline, let's first try the
    leftmost entity which has the earliest virtual deadline. I've done
    some benchmarks to see its effectiveness.
    
    All the benchmarks are done inside a normal cpu cgroup in a clean
    environment with cpu turbo disabled, on a dual-CPU Intel Xeon(R)
    Platinum 8260 with 2 NUMA nodes each of which has 24C/48T.
    
      hackbench: process/thread + pipe/socket + 1/2/4/8 groups
      netperf:   TCP/UDP + STREAM/RR + 24/48/72/96/192 threads
      tbench:    loopback 24/48/72/96/192 threads
      schbench:  1/2/4/8 mthreads
    
      direct:    cfs_rq has only one entity
      parity:    RUN_TO_PARITY
      fast:      O(1) fastpath
      slow:	     heap search
    
        (%)		direct	parity	fast	slow
      hackbench	92.95	2.02	4.91	0.12
      netperf	68.08	6.60	24.18	1.14
      tbench	67.55	11.22	20.61	0.62
      schbench	69.91	2.65	25.73	1.71
    
    The above results indicate that this fastpath really makes task
    selection more efficient.
    Signed-off-by: default avatarAbel Wu <wuyun.abel@bytedance.com>
    Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Link: https://lkml.kernel.org/r/20231115033647.80785-4-wuyun.abel@bytedance.com
    ee4373dc
fair.c 351 KB