Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Vitaly Kuznetsov <vkuznets@redhat.com>
To:     Paolo Bonzini <pbonzini@redhat.com>
Cc:     kvm@vger.kernel.org,
        Radim =?utf-8?B?S3LEjW3DocWZ?= <rkrcmar@redhat.com>,
        Roman Kagan <rkagan@virtuozzo.com>,
        "K. Y. Srinivasan" <kys@microsoft.com>,
        Haiyang Zhang <haiyangz@microsoft.com>,
        Stephen Hemminger <sthemmin@microsoft.com>,
        "Michael Kelley \(EOSG\)" <Michael.H.Kelley@microsoft.com>,
        Wanpeng Li <wanpeng.li@hotmail.com>,
        linux-kernel@vger.kernel.org
Subject: Re: [PATCH v4 RESEND 3/5] KVM: x86: hyperv: use get_vcpu_by_vpidx() in kvm_hv_flush_tlb()
References: <20180822101832.31763-1-vkuznets@redhat.com>
        <20180822101832.31763-4-vkuznets@redhat.com>
        <8da03d2a-5405-f363-f081-e4bc46b106e3@redhat.com>
Date:   Mon, 17 Sep 2018 10:32:55 +0200
In-Reply-To: <8da03d2a-5405-f363-f081-e4bc46b106e3@redhat.com> (Paolo
        Bonzini's message of "Fri, 14 Sep 2018 19:33:34 +0200")
Message-ID: <87r2hs7cco.fsf@vitty.brq.redhat.com>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

Paolo Bonzini <pbonzini@redhat.com> writes:

> On 22/08/2018 12:18, Vitaly Kuznetsov wrote:
>> VP_INDEX almost always matches VCPU id and get_vcpu_by_vpidx() is fast,
>> use it instead of traversing full vCPU list every time.
>
> ... but if it doesn't, the algorithm is now quadratic, isn't i?

Yes,

I even had an implementation with a logarythmic search back in v2 but
we had a discussion with Roman and he convinced me this is an overkill
and not currently required. It seems that with Qemu this is true indeed,
vp_index always matches vcpu is but in case some other userspace decides
to break this unwritten rule users may experience significant slowdown.

-- 
  Vitaly