Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Luc Van Oostenryck <luc.vanoostenryck@gmail.com>]

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@gmail.com> 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