Re: [PATCH 1/8] arm64: KVM: Switch the sys_reg search to be a binary search

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 10/02/16 13:49, Alex Bennée wrote:
> 
> Marc Zyngier <marc.zyngier@xxxxxxx> 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?

I believe it would be possible, assuming we have the right hash. Another
alternative would be a radix tree, which would always give us the right
sysreg in four memory accesses. It has some impacts on the memory side,
but that's shouldn't a blocker.

As I said, the binary search was a very low hanging fruit, so it made
some sense to implement it and see how we fared. Finding the perfect
data structure is left as an exercise for the reader! ;-)

Thanks,

	M.
-- 
Jazz is not dead. It just smells funny...
--
To unsubscribe from this list: send the line "unsubscribe kvm" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html



[Index of Archives]     [KVM ARM]     [KVM ia64]     [KVM ppc]     [Virtualization Tools]     [Spice Development]     [Libvirt]     [Libvirt Users]     [Linux USB Devel]     [Linux Audio Users]     [Yosemite Questions]     [Linux Kernel]     [Linux SCSI]     [XFree86]
  Powered by Linux