Optimizing recursive templates

[H. S. Teoh]

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