On Tue, Jul 18, 2023 at 5:43 AM Like Xu <like.xu.linux@xxxxxxxxx> wrote:
>
> On 17/7/2023 11:25 pm, Paolo Bonzini wrote:
> > On Mon, Jul 17, 2023 at 1:58 PM Like Xu <like.xu.linux@xxxxxxxxx> wrote:
> >>> - Use a different data type to track the producers and consumers so that lookups
> >>> don't require a linear walk. AIUI, the "tokens" used to match producers and
> >>> consumers are just kernel pointers, so I _think_ XArray would perform reasonably
> >>> well.
> >>
> >> My measurements show that there is little performance gain from optimizing lookups.
>
> First of all, I agree that the use of linear lookups here is certainly not
> optimal, and meanwhile the point is that it's not the culprit for the long
> delay of irq_bypass_register_consumer().
>
> Based on the user-supplied kvm_irqfd_fork load, we note that this is a test
> scenario where there are no producers and the number of consumer is growing
> linearly, and we note that the time delay [*] for two list_for_each_entry()
> walks (w/o xArray proposal) is:
This scenario is still subject to quadratic complexity in the first
foreach loop:
list_for_each_entry(tmp, &consumers, node) {
if (tmp->token == consumer->token || tmp == consumer) {
ret = -EBUSY;
goto out_err;
}
}
Paolo
