Re: [PATCH v5 1/3] genirq: Use hlist for managing resend handlers

[Liao, Chang]

在 2023/5/30 20:19, Thomas Gleixner 写道:
> On Tue, May 30 2023 at 09:59, Chang Liao wrote:
>> 在 2023/5/30 5:51, Thomas Gleixner 写道:
>>>> What is the benefit of using hlist here? If you want to enjoy the
>>>> low latency of querying elements by key, you must define a hlist table
>>>> with a reasonable number of buckets. Otherwise, I don't think the time
>>>> complexity of hlist is better than a regular double-linked list,
>>>> right?
>>>
>>> What's complex about hlist in this case? Please explain.
>>
>> Honestly, it is not about the complexity. Perhaps I do not understand the
>> usage of hlist very deeply. I have searched some codes in the kernel and
>> found that hlist is always used to speed up arbitrary querying, such as
>> searching a registered kprobe by address. Back to this patch, these resend
>> IRQs are organized in a sequence list actually, and traveled one by one to
>> handle. Further, by comparing the difference between hlist_empty, hlist_add_head,
>> hlist_del_init, and their counterparts in list, it looks like a regular linked
>> list is also good enough.
> 
> Sure that works too.
> 
> The main difference between regular linked lists and hlist is that the
> list head of hlist is half the size of a regular double linked list.
> 
> The only downside of hlist is that there is no back link in the list
> head to the tail. Searching for the tail is O(N) while on a double
> linked list it's O(1).
> 
> Nothing in this use case needs to access the tail. So what's your
> problem?

Oh, that is the point, your explanation made it all clear, my problem is solved,
Thanks!

> 
> Thanks,
> 
>         tglx

-- 
BR
Liao, Chang