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