From: Paolo Bonzini <pbonzini@redhat.com>
To: "Radim Krčmář" <rkrcmar@redhat.com>,
"Igor Mammedov" <imammedo@redhat.com>
Cc: linux-kernel@vger.kernel.org, kvm@vger.kernel.org,
yoshikawa_takuya_b1@lab.ntt.co.jp
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 [thread overview]
Message-ID: <54661530.6090301@redhat.com> (raw)
In-Reply-To: <20141114144135.GC27697@potion.brq.redhat.com>
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
next prev parent reply other threads:[~2014-11-14 14:44 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-11-14 11:11 [PATCH 0/3] KVM: simplification to the memslots code Paolo Bonzini
2014-11-14 11:12 ` [PATCH 1/3] kvm: memslots: track id_to_index changes during the insertion sort Paolo Bonzini
2014-11-14 13:34 ` Igor Mammedov
2014-11-14 13:35 ` Radim Krčmář
2014-11-14 14:17 ` Igor Mammedov
2014-11-14 14:41 ` Radim Krčmář
2014-11-14 14:44 ` Paolo Bonzini [this message]
2014-11-14 14:29 ` Paolo Bonzini
2014-11-14 14:44 ` Radim Krčmář
2014-11-14 11:12 ` [PATCH 2/3] kvm: commonize allocation of the new memory slots Paolo Bonzini
2014-11-14 14:21 ` Igor Mammedov
2014-11-17 1:49 ` Takuya Yoshikawa
2014-11-14 11:12 ` [PATCH 3/3] kvm: simplify update_memslots invocation Paolo Bonzini
2014-11-14 14:24 ` Igor Mammedov
2014-11-17 1:56 ` [PATCH 0/3] KVM: simplification to the memslots code Takuya Yoshikawa
2014-11-17 9:23 ` Paolo Bonzini
2014-11-17 9:30 ` Takuya Yoshikawa
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=54661530.6090301@redhat.com \
--to=pbonzini@redhat.com \
--cc=imammedo@redhat.com \
--cc=kvm@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=rkrcmar@redhat.com \
--cc=yoshikawa_takuya_b1@lab.ntt.co.jp \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox