From: "Alex Bennée" <alex.bennee@linaro.org>
To: Marc Zyngier <marc.zyngier@arm.com>
Cc: linux-arm-kernel@lists.infradead.org, kvm@vger.kernel.org,
kvmarm@lists.cs.columbia.edu
Subject: Re: [PATCH 1/8] arm64: KVM: Switch the sys_reg search to be a binary search
Date: Wed, 10 Feb 2016 13:49:14 +0000 [thread overview]
Message-ID: <87ziv8vfol.fsf@linaro.org> (raw)
In-Reply-To: <1454931622-14902-2-git-send-email-marc.zyngier@arm.com>
Marc Zyngier <marc.zyngier@arm.com> writes:
> 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!
Is there an argument for making this a hash table instead or is this not
possible as you would have to use dynamically allocated instead?
--
Alex Bennée
_______________________________________________
kvmarm mailing list
kvmarm@lists.cs.columbia.edu
https://lists.cs.columbia.edu/mailman/listinfo/kvmarm
WARNING: multiple messages have this Message-ID (diff)
From: alex.bennee@linaro.org (Alex Bennée)
To: linux-arm-kernel@lists.infradead.org
Subject: [PATCH 1/8] arm64: KVM: Switch the sys_reg search to be a binary search
Date: Wed, 10 Feb 2016 13:49:14 +0000 [thread overview]
Message-ID: <87ziv8vfol.fsf@linaro.org> (raw)
In-Reply-To: <1454931622-14902-2-git-send-email-marc.zyngier@arm.com>
Marc Zyngier <marc.zyngier@arm.com> writes:
> 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!
Is there an argument for making this a hash table instead or is this not
possible as you would have to use dynamically allocated instead?
--
Alex Benn?e
next prev parent reply other threads:[~2016-02-10 13:43 UTC|newest]
Thread overview: 60+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-02-08 11:40 [PATCH 0/8] KVM/ARM: Guest Entry/Exit optimizations Marc Zyngier
2016-02-08 11:40 ` Marc Zyngier
2016-02-08 11:40 ` [PATCH 1/8] arm64: KVM: Switch the sys_reg search to be a binary search Marc Zyngier
2016-02-08 11:40 ` Marc Zyngier
2016-02-10 12:44 ` Christoffer Dall
2016-02-10 12:44 ` Christoffer Dall
2016-02-10 13:49 ` Alex Bennée [this message]
2016-02-10 13:49 ` Alex Bennée
2016-02-10 14:00 ` Marc Zyngier
2016-02-10 14:00 ` Marc Zyngier
2016-02-08 11:40 ` [PATCH 2/8] ARM: KVM: Properly sort the invariant table Marc Zyngier
2016-02-08 11:40 ` Marc Zyngier
2016-02-10 12:44 ` Christoffer Dall
2016-02-10 12:44 ` Christoffer Dall
2016-02-08 11:40 ` [PATCH 3/8] ARM: KVM: Enforce sorting of all CP tables Marc Zyngier
2016-02-08 11:40 ` Marc Zyngier
2016-02-10 12:44 ` Christoffer Dall
2016-02-10 12:44 ` Christoffer Dall
2016-02-08 11:40 ` [PATCH 4/8] ARM: KVM: Rename struct coproc_reg::is_64 to is_64bit Marc Zyngier
2016-02-08 11:40 ` Marc Zyngier
2016-02-10 12:44 ` Christoffer Dall
2016-02-10 12:44 ` Christoffer Dall
2016-02-08 11:40 ` [PATCH 5/8] ARM: KVM: Switch the CP reg search to be a binary search Marc Zyngier
2016-02-08 11:40 ` Marc Zyngier
2016-02-10 12:44 ` Christoffer Dall
2016-02-10 12:44 ` Christoffer Dall
2016-02-08 11:40 ` [PATCH 6/8] KVM: arm/arm64: timer: Add active state caching Marc Zyngier
2016-02-08 11:40 ` Marc Zyngier
2016-02-10 12:44 ` Christoffer Dall
2016-02-10 12:44 ` Christoffer Dall
2016-02-08 11:40 ` [PATCH 7/8] KVM: arm/arm64: Avoid accessing GICH registers Marc Zyngier
2016-02-08 11:40 ` Marc Zyngier
2016-02-10 12:45 ` Christoffer Dall
2016-02-10 12:45 ` Christoffer Dall
2016-02-10 13:34 ` Marc Zyngier
2016-02-10 13:34 ` Marc Zyngier
2016-02-10 17:30 ` Christoffer Dall
2016-02-10 17:30 ` Christoffer Dall
2016-02-10 17:43 ` Marc Zyngier
2016-02-10 17:43 ` Marc Zyngier
2016-02-08 11:40 ` [PATCH 8/8] KVM: arm64: Avoid accessing ICH registers Marc Zyngier
2016-02-08 11:40 ` Marc Zyngier
2016-02-10 12:45 ` Christoffer Dall
2016-02-10 12:45 ` Christoffer Dall
2016-02-10 16:47 ` Marc Zyngier
2016-02-10 16:47 ` Marc Zyngier
2016-02-09 20:59 ` [PATCH 0/8] KVM/ARM: Guest Entry/Exit optimizations Christoffer Dall
2016-02-09 20:59 ` Christoffer Dall
2016-02-10 8:34 ` Marc Zyngier
2016-02-10 8:34 ` Marc Zyngier
2016-02-10 12:02 ` Andrew Jones
2016-02-10 12:02 ` Andrew Jones
2016-02-10 12:24 ` Marc Zyngier
2016-02-10 12:24 ` Marc Zyngier
2016-02-10 20:40 ` Christoffer Dall
2016-02-10 20:40 ` Christoffer Dall
2016-02-16 20:05 ` Marc Zyngier
2016-02-16 20:05 ` Marc Zyngier
2016-02-17 9:15 ` Christoffer Dall
2016-02-17 9:15 ` Christoffer Dall
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=87ziv8vfol.fsf@linaro.org \
--to=alex.bennee@linaro.org \
--cc=kvm@vger.kernel.org \
--cc=kvmarm@lists.cs.columbia.edu \
--cc=linux-arm-kernel@lists.infradead.org \
--cc=marc.zyngier@arm.com \
/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.