From mboxrd@z Thu Jan 1 00:00:00 1970 From: Christoffer Dall Subject: Re: [PATCH 1/8] arm64: KVM: Switch the sys_reg search to be a binary search Date: Wed, 10 Feb 2016 13:44:28 +0100 Message-ID: <20160210124428.GH5171@cbox> References: <1454931622-14902-1-git-send-email-marc.zyngier@arm.com> <1454931622-14902-2-git-send-email-marc.zyngier@arm.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Cc: kvm@vger.kernel.org, linux-arm-kernel@lists.infradead.org, kvmarm@lists.cs.columbia.edu To: Marc Zyngier Return-path: Content-Disposition: inline In-Reply-To: <1454931622-14902-2-git-send-email-marc.zyngier@arm.com> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: kvmarm-bounces@lists.cs.columbia.edu Sender: kvmarm-bounces@lists.cs.columbia.edu List-Id: kvm.vger.kernel.org On Mon, Feb 08, 2016 at 11:40:15AM +0000, Marc Zyngier wrote: > Our 64bit sys_reg table is about 90 entries long (so far, and the > PMU support is likely to increase this). This means that on average, > it takes 45 comparaisons to find the right entry (and actually the > full 90 if we have to search the invariant table). > > Not the most efficient thing. Specially when you think that this > table is already sorted. Switching to a binary search effectively > reduces the search to about 7 comparaisons. Slightly better! > > As an added bonus, the comparaison is done by comparing all the s/comparaison/comparison/ > fields at once, instead of one at a time. > > Signed-off-by: Marc Zyngier Reviewed-by: Christoffer Dall