• Igor Mammedov's avatar
    kvm: optimize GFN to memslot lookup with large slots amount · 9c1a5d38
    Igor Mammedov authored
    Current linear search doesn't scale well when
    large amount of memslots is used and looked up slot
    is not in the beginning memslots array.
    Taking in account that memslots don't overlap, it's
    possible to switch sorting order of memslots array from
    'npages' to 'base_gfn' and use binary search for
    memslot lookup by GFN.
    
    As result of switching to binary search lookup times
    are reduced with large amount of memslots.
    
    Following is a table of search_memslot() cycles
    during WS2008R2 guest boot.
    
                             boot,          boot + ~10 min
                             mostly same    of using it,
                             slot lookup    randomized lookup
                    max      average        average
                    cycles   cycles         cycles
    
    13 slots      : 1450       28           30
    
    13 slots      : 1400       30           40
    binary search
    
    117 slots     : 13000      30           460
    
    117 slots     : 2000       35           180
    binary search
    Signed-off-by: default avatarIgor Mammedov <imammedo@redhat.com>
    Signed-off-by: default avatarPaolo Bonzini <pbonzini@redhat.com>
    9c1a5d38
kvm_main.c 75.4 KB