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@xxxxxxxxxx> > --- > 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@xxxxxxxxxx> Paolo -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
