From mboxrd@z Thu Jan  1 00:00:00 1970
From: Sasha Levin <levinsasha928@gmail.com>
Subject: Re: [PATCH] IO: Intelligent device lookup on bus
Date: Thu, 21 Jul 2011 00:22:09 +0300
Message-ID: <1311196929.21614.5.camel@lappy>
References: <1311163918-14334-1-git-send-email-levinsasha928@gmail.com>
	 <20110720194149.GA21379@amt.cnet>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Cc: kvm@vger.kernel.org, Avi Kivity <avi@redhat.com>
To: Marcelo Tosatti <mtosatti@redhat.com>
Return-path: <kvm-owner@vger.kernel.org>
Received: from mail-wy0-f174.google.com ([74.125.82.174]:46236 "EHLO
	mail-wy0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
	with ESMTP id S1750810Ab1GTVWg (ORCPT <rfc822;kvm@vger.kernel.org>);
	Wed, 20 Jul 2011 17:22:36 -0400
Received: by wyg8 with SMTP id 8so453562wyg.19
        for <kvm@vger.kernel.org>; Wed, 20 Jul 2011 14:22:35 -0700 (PDT)
In-Reply-To: <20110720194149.GA21379@amt.cnet>
Sender: kvm-owner@vger.kernel.org
List-ID: <kvm.vger.kernel.org>

On Wed, 2011-07-20 at 16:41 -0300, Marcelo Tosatti wrote:
> On Wed, Jul 20, 2011 at 03:11:58PM +0300, Sasha Levin wrote:
> > Currently the method of dealing with an IO operation on a bus (PIO/MMIO)
> > is to call the read or write callback for each device registered
> > on the bus until we find a device which handles it.
> > 
> > Since the number of devices on a bus can be significant due to ioeventfds
> > and coalesced MMIO zones, this leads to a lot of overhead on each IO
> > operation.
> > 
> > Instead of registering devices, we now register ranges which points to
> > a device. Lookup is done using an efficient bsearch instead of a linear
> > search.
> > 
> > This should speed up all IO operations generated by the guest.
> 
> Some numbers, please.
> 

I'm not sure how to measure performance in this case. You'd need to
measure access times to each device before and after the patch, and
average them.

It replaces a linear lookup with a binary one, it's not an absolute
improvement.

> > +int kvm_io_bus_find_closest_dev_idx(struct kvm_io_bus *bus,
> > +					gpa_t addr, int len)
> > +{
> > +	int start = 0, end = bus->dev_count - 1;
> > +
> > +	if (bus->dev_count == 0)
> > +		return -1;
> > +
> > +	while (start <= end) {
> > +		int mid = (start + end) / 2;
> > +		struct kvm_io_range *range = &bus->range[mid];
> > +
> > +		if (addr > range->addr)
> > +			start = mid + 1;
> > +		else if (addr < range->addr)
> > +			end = mid - 1;
> 
> If mid is zero, this assigns end = -1?
> 

Yes. Next step would be to exit the while ().

-- 

Sasha.