From: "Radim Krčmář" <rkrcmar@redhat.com>
To: Igor Mammedov <imammedo@redhat.com>
Cc: Paolo Bonzini <pbonzini@redhat.com>,
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:41:36 +0100 [thread overview]
Message-ID: <20141114144135.GC27697@potion.brq.redhat.com> (raw)
In-Reply-To: <20141114151725.55774165@igors-macbook-pro.local>
2014-11-14 15:17+0100, Igor Mammedov:
> > (We'll have to change it into an interval tree, or something, if the
> > number of slots rises anyway.)
> Only if it rises to huge amount, I've played with proposed 512 memslots
> and it takes ~10000 cycles which is 5% of current heapsort overhead.
> Taking in account that it's slow path anyway, it's unlikely that there
> would be need to speedup this case even more.
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.
Maybe we would benefit from O(log N) lookup even with 128 memslots.
next prev parent reply other threads:[~2014-11-14 14:41 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ář [this message]
2014-11-14 14:44 ` Paolo Bonzini
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=20141114144135.GC27697@potion.brq.redhat.com \
--to=rkrcmar@redhat.com \
--cc=imammedo@redhat.com \
--cc=kvm@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=pbonzini@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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.