kvm: optimize GFN to memslot lookup with large slots amount
authorIgor Mammedov <imammedo@redhat.com>
Mon, 1 Dec 2014 17:29:27 +0000 (17:29 +0000)
committerPaolo Bonzini <pbonzini@redhat.com>
Thu, 4 Dec 2014 14:29:11 +0000 (15:29 +0100)
commit9c1a5d38780e652275aa55362dbee0d7e827e069
tree0fc252e3948a30b78974e3ba8979d5aa231de22f
parent0e60b0799fedc495a5c57dbd669de3c10d72edd2
kvm: optimize GFN to memslot lookup with large slots amount

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: Igor Mammedov <imammedo@redhat.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
include/linux/kvm_host.h
virt/kvm/kvm_main.c