www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Optimizing recursive templates

reply Stefan Koch <uplink.coder googlemail.com> writes:
Hi Guys,

I am starting this thread to talk about the feasibility of 
rewriting recursive templates as iterative internal forms.

This addresses the general issue and does not concern itself with 
particular local instances of the problem which may be solvable 
with lesser means.

The Problem is essentially equivalent to this:

Solve for the outcome of a particular state of "Conway game of 
live.", given an initial state and a number of steps. In constant 
time and at most linear space.

Also particular configurations of cells may change local 
evaluation rules of the automaton.

So it's my challenge to you.

Can you proof or refute the existence of a closed form function 
which can simulate the game of life in constant time ?
Sep 24 2020
next sibling parent reply M.M. <matus email.cz> writes:
On Thursday, 24 September 2020 at 19:49:44 UTC, Stefan Koch wrote:
 The Problem is essentially equivalent to this:

 Solve for the outcome of a particular state of "Conway game of 
 live.", given an initial state and a number of steps. In 
 constant time and at most linear space.
What do you mean by constant time and linear space? In classical algorithm analysis, in constant time you can only access constant-size memory, so linear-space cannot really help here, and your question boils down to: can you simulate the game of life in constant time?
Sep 24 2020
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 24 September 2020 at 20:11:53 UTC, M.M. wrote:
 On Thursday, 24 September 2020 at 19:49:44 UTC, Stefan Koch 
 wrote:
 The Problem is essentially equivalent to this:

 Solve for the outcome of a particular state of "Conway game of 
 live.", given an initial state and a number of steps. In 
 constant time and at most linear space.
What do you mean by constant time and linear space? In classical algorithm analysis, in constant time you can only access constant-size memory, so linear-space cannot really help here, and your question boils down to: can you simulate the game of life in constant time?
Hmm yes. Indeed.
Sep 24 2020
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Sep 24, 2020 at 07:49:44PM +0000, Stefan Koch via Digitalmars-d wrote:
 Hi Guys,
 
 I am starting this thread to talk about the feasibility of rewriting
 recursive templates as iterative internal forms.
 
 This addresses the general issue and does not concern itself with
 particular local instances of the problem which may be solvable with
 lesser means.
 
 The Problem is essentially equivalent to this:
 
 Solve for the outcome of a particular state of "Conway game of live.",
 given an initial state and a number of steps. In constant time and at
 most linear space.
 
 Also particular configurations of cells may change local evaluation
 rules of the automaton.
While this is an interesting subject in its own right, I think we're kinda missing the point of template optimization here. Templates being Turing-complete, I doubt whether any closed-form function exists that can solve the above stated problem. The same can be said for programs in general -- the global optimization function is uncomputable (I didn't work it out rigorously, but I think it essentially boils down to the perfect compression problem, which is known to be uncomputable). However, that does not stop us from creating effective optimizers, as proven by current compiler technology like GDC and LDC. The point being, optimization of programs in a Turing-complete language generally proceeds by identifying common patterns, and writing recognizers for said patterns and emitting known optimal or near-optimal (or at least more efficient!) substitutions. The patterns can't cover *all* cases, but if they hit the most common cases, we still reap the benefits. So I think a more practical approach to this problem is study common recursive templates (e.g., comb through Phobos and pick up the most commonly-used recursive templates) and identify the most common patterns among them that can be replaced with more efficient versions. It won't be possible to cover *all* cases of recursive templates, but if we can hit the most common cases, we can still get a lot of mileage out of it. T -- Why waste time reinventing the wheel, when you could be reinventing the engine? -- Damian Conway
Sep 24 2020
parent Bruce Carneal <bcarneal gmail.com> writes:
On Thursday, 24 September 2020 at 20:53:25 UTC, H. S. Teoh wrote:
 On Thu, Sep 24, 2020 at 07:49:44PM +0000, Stefan Koch via 
 Digitalmars-d wrote
 Hi Guys,
 
 I am starting this thread to talk about the feasibility of 
 rewriting recursive templates as iterative internal forms.
 
 ...
While this is an interesting subject in its own right, I think we're kinda missing the point of template optimization here. ... So I think a more practical approach to this problem is study common recursive templates (e.g., comb through Phobos and pick up the most commonly-used recursive templates) and identify the most common patterns among them that can be replaced with more efficient versions. It won't be possible to cover *all* cases of recursive templates, but if we can hit the most common cases, we can still get a lot of mileage out of it. T
I think the practical approach is to bring type functions online. This would let us replace our, often disappointed, hopes that the next set of hacks will finally "fix" templates with actual trials of an extant system (type functions). Want to use recursive type functions? Have at it! Want to iterate? Congratulations! You've single-handidly crushed the performance of the super-duper template recursion hueristic optimizer that'll happen any day now! Kidding aside, while I believe we'll see performance and compiler convergence benefits from type functions, the bigger benefit should be a reduction in complexity for a big chunk of our future meta programming. Templates are very powerful, a huge improvement over their C++ predecessors. They are are also wildly unconstrained. Their successful use depends on programmer discipline, on best practices, on convention. Absent strong, manually applied constraints, non-trivial templates can lead to problems that are very difficult to localize, let alone fix. So, performance? Love it. Simplicity? Love it more, especially when it yields better performance.
Sep 24 2020
prev sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 24 September 2020 at 19:49:44 UTC, Stefan Koch wrote:
 Hi Guys,

 I am starting this thread to talk about the feasibility of 
 rewriting recursive templates as iterative internal forms.
Hi, I very recently had a conversation about template optimization. And during that an interesting example came up. For a sequence of types (candidates) select the first one that is convertible to a given conversion target (convTarget) The naive way of writing this template is not even this bad. --- alias Seq(T...) = T; alias EmptySeq = Seq!() template selectFirstConvertable(convTarget, candidates...) { static if (!candidates.length) selectFirstConvertable = EmptySeq; else static if (is(candidates[0] : convTarget)) selectFirstConvertable = candidates[0]; else selectFirstConvertable = selectFirstConvertable!(candidates[1 .. $]); } --- So if I wanted to get rid of the recursion here, what would I do? .... I don't really know. Let's write the type function: --- type selectFirstConvertable(type convTarget, type[] candidates ...) { type result; // initialzed to ∅ foreach(c;candidates) { if (is(c : convTarget)) { result = c; break; } } return result; } --- now let's search for commonalities. a good one would be the exit condition of the loop `if (is(c : convTarget))` we can find a line in the template which almost looks like that `else static if (is(candidates[0] : convTarget))` we could substitute c for candidates[0] and get `else static if (is(c : convTarget))` which looks a lot like the condition in our loop. so how can we determine that this will "break;" ? Well as long as it does not recurse (directly or indirectly). It must end the recursion. That means if what's inside the static if branch does not instantiate any template, we can assume it to be termination. is this true for the static if body in question? yes. `selectFirstConvertable = candidates[0];` does not recurse into itself. So we've established a "break point" if you've pardon the pun :) From that we can deduce that the 'exit' condition is `is(candidates[0] : convTarget)` We can further establish from `selectFirstConvertable = candidates[0];` that we essentially do `return candidates[0]`; which gives us a rewrite rule templateName = X; can be rewritten as return X; let's apply those rewrite rule. And annotate meaning. template selectFirstConvertable(convTarget, candidates...) { static if (!candidates.length) // reversed loop entrance condition return EmptySeq; else static if (is(candidates[0] : convTarget)) // loop exit condition return candidates[0]; else return selectFirstConvertable!(candidates[1 .. $]); // loop increment } Now that's more like a function wouldn't you say? so let's build a loop template selectFirstConvertable(convTarget, candidates...) { bool exitCondition = is(candidates[0] : convTarget); if (!canidates.length) return EmptySeq; else while (!exitCondition) // hitting this means the entrance condition was met { candidates = candidates[1 .. $] // problem is we can't do this! // re-evaluate exit condition exitCondition = is(candidates[0] : convTarget) } return candidates[0]; } As we see, the loop necessitates for the language to be able to store a tuple in a variable and for that variable to be mutable! Also we need to be able to actually interpret the loop. Which (for this example) requires for CTFE to know about is expressions And for CTFE to turn Type into expressions (An ability which exists internal to dmd but is not exposed to the user) Alternatively we could of course implement another interpretation system which would mirror most of CTFE but also allows type variables. In order to keep the systems unchanged. The question then is, if we already have to do this. Why not expose it to the user? And when you follow that line of inquiry that leads you directly to ... Well you can figure that out for yourself ;) Cheers, Stefan
Oct 09 2020
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 9 October 2020 at 11:03:57 UTC, Stefan Koch wrote:
 Hi,

 I very recently had a conversation about template optimization.
 And during that an interesting example came up.
P.S. If you use any ideas in this post it would be very nice and common courtesy to give attribution and mention it in your derived work.
Oct 09 2020