From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754907AbbFPVHh (ORCPT ); Tue, 16 Jun 2015 17:07:37 -0400 Received: from mx1.redhat.com ([209.132.183.28]:52922 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753246AbbFPVH1 (ORCPT ); Tue, 16 Jun 2015 17:07:27 -0400 Date: Tue, 16 Jun 2015 23:07:24 +0200 From: "Michael S. Tsirkin" To: Igor Mammedov Cc: linux-kernel@vger.kernel.org, kvm@vger.kernel.org, pbonzini@redhat.com Subject: Re: [PATCH 1/5] vhost: use binary search instead of linear in find_region() Message-ID: <20150616230700-mutt-send-email-mst@redhat.com> References: <1434472419-148742-1-git-send-email-imammedo@redhat.com> <1434472419-148742-2-git-send-email-imammedo@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1434472419-148742-2-git-send-email-imammedo@redhat.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Jun 16, 2015 at 06:33:35PM +0200, Igor Mammedov wrote: > For default region layouts performance stays the same > as linear search i.e. it takes around 210ns average for > translate_desc() that inlines find_region(). > > But it scales better with larger amount of regions, > 235ns BS vs 300ns LS with 55 memory regions > and it will be about the same values when allowed number > of slots is increased to 509 like it has been done in kvm. > > Signed-off-by: Igor Mammedov > --- > drivers/vhost/vhost.c | 38 ++++++++++++++++++++++++++++---------- > 1 file changed, 28 insertions(+), 10 deletions(-) > > diff --git a/drivers/vhost/vhost.c b/drivers/vhost/vhost.c > index 2ee2826..a22f8c3 100644 > --- a/drivers/vhost/vhost.c > +++ b/drivers/vhost/vhost.c > @@ -25,6 +25,7 @@ > #include > #include > #include > +#include > > #include "vhost.h" > > @@ -590,6 +591,16 @@ int vhost_vq_access_ok(struct vhost_virtqueue *vq) > } > EXPORT_SYMBOL_GPL(vhost_vq_access_ok); > > +static int vhost_memory_reg_sort_cmp(const void *p1, const void *p2) > +{ > + const struct vhost_memory_region *r1 = p1, *r2 = p2; > + if (r1->guest_phys_addr < r2->guest_phys_addr) > + return 1; > + if (r1->guest_phys_addr > r2->guest_phys_addr) > + return -1; > + return 0; > +} > + > static long vhost_set_memory(struct vhost_dev *d, struct vhost_memory __user *m) > { > struct vhost_memory mem, *newmem, *oldmem; > @@ -609,9 +620,11 @@ static long vhost_set_memory(struct vhost_dev *d, struct vhost_memory __user *m) > memcpy(newmem, &mem, size); > if (copy_from_user(newmem->regions, m->regions, > mem.nregions * sizeof *m->regions)) { > - kfree(newmem); > + kvfree(newmem); > return -EFAULT; > } What's this doing here? > + sort(newmem->regions, newmem->nregions, sizeof(*newmem->regions), > + vhost_memory_reg_sort_cmp, NULL); > > if (!memory_access_ok(d, newmem, 0)) { > kfree(newmem); > @@ -913,17 +926,22 @@ EXPORT_SYMBOL_GPL(vhost_dev_ioctl); > static const struct vhost_memory_region *find_region(struct vhost_memory *mem, > __u64 addr, __u32 len) > { > - struct vhost_memory_region *reg; > - int i; > + const struct vhost_memory_region *reg; > + int start = 0, end = mem->nregions; > > - /* linear search is not brilliant, but we really have on the order of 6 > - * regions in practice */ > - for (i = 0; i < mem->nregions; ++i) { > - reg = mem->regions + i; > - if (reg->guest_phys_addr <= addr && > - reg->guest_phys_addr + reg->memory_size - 1 >= addr) > - return reg; > + while (start < end) { > + int slot = start + (end - start) / 2; > + reg = mem->regions + slot; > + if (addr >= reg->guest_phys_addr) > + end = slot; > + else > + start = slot + 1; > } > + > + reg = mem->regions + start; > + if (addr >= reg->guest_phys_addr && > + reg->guest_phys_addr + reg->memory_size > addr) > + return reg; > return NULL; > } > > -- > 1.8.3.1