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
