On Fri, Aug 4, 2017 at 6:38 AM, Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx> wrote: > 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. That is exactly the feeling I am getting from you. You said some thing might not work. I want to find out exactly what do you have in mind might not work. Otherwise the conversion is base on doubt is not very useful. I want details. This goes both ways. You can also ask me to clarify more details on certain things in my mental model. > > 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). In my observe and modify model, the traverse of a tree can use recursive, even on the same ptrlist. It is the modify get deferred. I think I mention that observe and modify in previous email already. So what you are describing above is not a good example to against it. > 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. You walk the graph to do some thing. That is given. Nobody walk the graph for the sake of just walking the graph. The optimize can be model as an algorithm walk the graph and make modification of the graph. Is that a fair statement? > > 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. Now we are talking. > 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 Here you make some assumption that you can't save the context of the instruction in the work queue. That is not necessary true. In my mental model, the work queue will contain the context of what needs to be done, e.g. the pointer to the instruct. Other context if needed. I want to know more about what context you can't save. BTW, most of the context can be found on the graph does not need to save in to work queue. Take simplify_branch_branch for example, when you know this instruction should be simplified, there is very little information need to be save in the work queue. Basically we can start with call arguments to rewrite_branch(), go from there. > - 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. Again, I don't have a clear picture of what context you are talking about. Please clarify. If it is the instruction before this instruction, I can't image why I need it. If really need it I can still cache it or search it in the bb->insns list. BTW, my impression is that, the algorithm "constant propagation using ssa" is such an example what you are describing here. In the constant propagation, you first find the instruction that use constant. Then you find out if that instruction can be simplify as constant. Next thing is put the instruction using of this simplify instruction result into the queue to see if they can be simplify as well. It is actually a lot better than our current approach to rescan the whole instruction list just to find out, oh, we got some new instruction have constant input now (due to last round constant propagation). > 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). Caching, maybe. But I don't think caching is a strong point to against it. I am just a system guy playing catch up game on compiler designs. The more I read, the more I find out using work queue is a very common thing amount those classic optimization algorithms. > 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. My reading is that, "I have doubt but I can't articulate precisely why it is the case." Fill in more detail we can have more discussion. Granted, no algorithm is *always" a good solution to all problem. As I express in my previous email, I have no doubt this can be done. The question is weather it can be done *clean* enough for sparse. When we introduce "dead code elimination using ssa", work queue like frame work will be needed any way. Chris -- 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
