linux-kernel - Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the 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 for Android: free password hash cracker in your pocket

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

Date:	Fri, 14 Nov 2014 15:44:00 +0100
From:	Paolo Bonzini <pbonzini@...hat.com>
To:	Radim Krčmář <rkrcmar@...hat.com>,
	Igor Mammedov <imammedo@...hat.com>
CC:	linux-kernel@...r.kernel.org, kvm@...r.kernel.org,
	yoshikawa_takuya_b1@....ntt.co.jp
Subject: Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the
 insertion sort

On 14/11/2014 15:41, Radim Krčmář wrote:
> Yes, your improvement is great and would work even for higher amounts.
> 
> I meant that our lookup is currently pretty sad -- O(N) that is
> presumably optimized by looking at the largest regions first.

Yes, that's the optimization.

> Maybe we would benefit from O(log N) lookup even with 128 memslots.

Maybe, but the common case so far is about 10, and all but two of them
are only used at boot time. :)

Perhaps we could add a one-item MRU cache, that could help lookups a
bit.  That's what QEMU does too, by the way.  It used to sort the list
in MRU-to-LRU order, but that wasn't too thread-friendly so it was
switched to biggest-to-smallest (with inspiration taken from KVM).

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/