On Thu, Aug 03, 2017 at 10:22:34PM -0400, Christopher Li wrote: > On Thu, Aug 3, 2017 at 8:41 PM, Luc Van Oostenryck > <luc.vanoostenryck@xxxxxxxxx> wrote: > >> > >> Can you give an example what nest looping will have to remain. > > > > Can you give the assurance that none will remains? > > I can have the ptr ref count patch to check if such thing > happen. But I am sure that is not what you are asking :-) It was a rethorical question as a reponse to your own question because your own asking to show something while we're talking design and potentiality doesn't help at all. > >> Converting recursive call into work queue without recursive > >> is pretty stander algorithm. In theory, as long as you defer > >> the inner loop calling into the work queue. It can always > >> avoid the nest looping. In the extreme case you can think > >> the work queue holding a copy of the list and move the inner > >> loop body to the outer work queue. > > > > *standard algorithm*, *in theory*, ... > > I am actually don't worry about weather it can be done or not. > I am sure you don't need me to google converting recursion > to iteration for you. 1) Converting a recursive algo to an iterative one is not always a good solution, for example the iterative one can be much more complex/less elegant. You may also need more memory (because you often need to store additional info). A typical example is searching in a tree: it can be done with iteration but it's generaly not done because the recursive version is so much simpler & elegant (and probably efficient too). 2) Converting something to a work queue is not the same as converting recursion to iteration anyway. Recursion vs. iteration is something about how walking through a data structure. Using a work queue is about how/when doing an operation on an object. An example among other of complications you can have when converting to work queue is something like: Imagine you're iterating through a list of instruction checking/ searching after something. If found, you want to do an operation on the instruction just found. Sound like something for a work queue, right? Just put the object you found in the work queue and let do the operation later. Now what if the operation is about inserting another instruction just before the one just found (like done when adding death notes)? - if you do it immediatly, you have the context of the instruction and inserting the death notes is easy/cheap - if you do the insertion later when processing the work queue you won't have anymore the context of the instruction and to insert the death note you will first have to search after it (to have the context back) before you will be able to do the insertion and this search will cost you. It's just an example but there is a whole class of similar situations. Delaying thing by moving it to a work queue will also have negative impact on cache (but in a way, it's also a problem of having lost the context). And again, I'm not telling that using workqueue is never a good solution, I'm saying that most probably it won't always be a good solution. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
