Thread overview
Optimizing recursive templates
Sep 24
M.M.
September 24
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 ?
September 24
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?
September 24
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.

September 24
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
September 24
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.










October 09
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

October 09
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.