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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 13 Nov 2014 17:58:30 +0100
From:	Paolo Bonzini <pbonzini@...hat.com>
To:	Igor Mammedov <imammedo@...hat.com>, linux-kernel@...r.kernel.org
CC:	kvm@...r.kernel.org
Subject: Re: [PATCH] kvm: memslots: replace heap sort with insertion sort



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@...hat.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@...hat.com>

Paolo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/