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

[Thomas Gleixner <tglx@linutronix.de>]

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?

Thanks,

        tglx