diff options
author | Igor Mammedov <imammedo@redhat.com> | 2014-11-13 23:00:13 +0000 |
---|---|---|
committer | Paolo Bonzini <pbonzini@redhat.com> | 2014-11-14 10:49:04 +0100 |
commit | 063584d44377ebde5ebc6e99cedc1bc6561939d7 (patch) | |
tree | c7ce69f00f8b1edfd89ca621d51a590709b5f14f /virt/kvm/coalesced_mmio.h | |
parent | 1d4e7e3c0bca747d0fc54069a6ab8393349431c0 (diff) |
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>
Diffstat (limited to 'virt/kvm/coalesced_mmio.h')
0 files changed, 0 insertions, 0 deletions