kvm: memslots: replace heap sort with an insertion sort pass
authorIgor Mammedov <imammedo@redhat.com>
Thu, 13 Nov 2014 23:00:13 +0000 (23:00 +0000)
committerPaolo Bonzini <pbonzini@redhat.com>
Fri, 14 Nov 2014 09:49:04 +0000 (10:49 +0100)
commit063584d44377ebde5ebc6e99cedc1bc6561939d7
treec7ce69f00f8b1edfd89ca621d51a590709b5f14f
parent1d4e7e3c0bca747d0fc54069a6ab8393349431c0
kvm: memslots: replace heap sort with an insertion sort pass

memslots is a sorted array.  When a slot is changed, heapsort (lib/sort.c)
would take O(n log n) time to update it; an optimized insertion sort will
only cost O(n) on an array with just one item out of order.

Replace sort() with a custom sort that takes advantage of memslots usage
pattern and the known position of the changed slot.

performance change of 128 memslots insertions with gradually increasing
size (the worst case):

      heap sort   custom sort
max:  249747      2500 cycles

with custom sort alg taking ~98% less then original
update time.

Signed-off-by: Igor Mammedov <imammedo@redhat.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
virt/kvm/kvm_main.c