Re: [PATCH] kvm: memslots: replace heap sort with insertion sort

[Paolo Bonzini <pbonzini@redhat.com>]

On 13/11/2014 17:31, Igor Mammedov wrote:
> memslots is a sorted array, when slot changes in it
> with current heapsort it would take O(n log n) time
> to update array, while using insertion sort like
> algorithm on array with 1 item out of order will
> take only O(n) time.
> 
> Replace current heapsort with custom sort that
> takes advantage of memslots usage pattern and known
> position of changed slot.
> 
> performance change of 128 memslots insersions with
> gradually increasing size (the worst case):
>       heap sort   custom sort
> max:  249747      15654 cycles
> min:  52536       5562 cycles
> with custom sort alg taking 90% less then original
> update time.
> 
> Signed-off-by: Igor Mammedov <imammedo@redhat.com>
> ---
>  virt/kvm/kvm_main.c | 54 +++++++++++++++++++++++++++++------------------------
>  1 file changed, 30 insertions(+), 24 deletions(-)

Nice!  I think strictly speaking it's not an insertion sort because
insertion sort doesn't use swaps; it's more similar to a bubble sort.
But the code is very readable and we do not need ultimate
performance---we are just trying to avoid doing something stupid.

Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>

Paolo