Messages in this thread | | | Date | Fri, 2 Jun 2023 09:36:00 +0800 | Subject | Re: [PATCH v5 1/3] genirq: Use hlist for managing resend handlers | From | "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
| |