From mboxrd@z Thu Jan 1 00:00:00 1970 From: Paolo Bonzini Subject: Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the insertion sort Date: Fri, 14 Nov 2014 15:44:00 +0100 Message-ID: <54661530.6090301@redhat.com> References: <1415963522-5255-1-git-send-email-pbonzini@redhat.com> <1415963522-5255-2-git-send-email-pbonzini@redhat.com> <20141114133500.GA10593@potion.brq.redhat.com> <20141114151725.55774165@igors-macbook-pro.local> <20141114144135.GC27697@potion.brq.redhat.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: QUOTED-PRINTABLE Cc: linux-kernel@vger.kernel.org, kvm@vger.kernel.org, yoshikawa_takuya_b1@lab.ntt.co.jp To: =?UTF-8?B?UmFkaW0gS3LEjW3DocWZ?= , Igor Mammedov Return-path: In-Reply-To: <20141114144135.GC27697@potion.brq.redhat.com> Sender: linux-kernel-owner@vger.kernel.org List-Id: kvm.vger.kernel.org On 14/11/2014 15:41, Radim Kr=C4=8Dm=C3=A1=C5=99 wrote: > Yes, your improvement is great and would work even for higher amounts= =2E >=20 > 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