• Davidlohr Bueso's avatar
    sysvipc: make get_maxid O(1) again · 15df03c8
    Davidlohr Bueso authored
    For a custom microbenchmark on a 3.30GHz Xeon SandyBridge, which calls
    IPC_STAT over and over, it was calculated that, on avg the cost of
    ipc_get_maxid() for increasing amounts of keys was:
    
     10 keys: ~900 cycles
     100 keys: ~15000 cycles
     1000 keys: ~150000 cycles
     10000 keys: ~2100000 cycles
    
    This is unsurprising as maxid is currently O(n).
    
    By having the max_id available in O(1) we save all those cycles for each
    semctl(_STAT) command, the idr_find can be expensive -- which some real
    (customer) workloads actually poll on.
    
    Note that this used to be the case, until commit 7ca7e564 ("ipc:
    store ipcs into IDRs").  The cost is the extra idr_find when doing
    RMIDs, but we simply go backwards, and should not take too many
    iterations to find the new value.
    
    [akpm@linux-foundation.org: coding-style fixes]
    Link: http://lkml.kernel.org/r/20170831172049.14576-5-dave@stgolabs.netSigned-off-by: default avatarDavidlohr Bueso <dbueso@suse.de>
    Cc: Manfred Spraul <manfred@colorfullife.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    15df03c8
util.c 22.2 KB