Compile-time optimization

[H. S. Teoh]

On Wed, Jul 24, 2013 at 08:12:36PM +0200, JS wrote:
> T,
> 
> I've looked over your code and understand what you are doing but I
> don't understand the expression
> 
>      is(typeof(func(args[0], args[1]))))
> 
> you are checking if func(a,b)'s return type is a type?

That's the usual idiom for checking if it's legal to pass args[0] and
args[1] to func().

If it's legal, then typeof(func(args[0],args[1])) will return some type,
which then passes the check. If it's illegal, then the call to func has
no type because the compiler rejects the call; say you have
func(int,int) and you attempted to call func("a","a"). So then
typeof(func(...)) will not be a valid type, and the check fails.


On Wed, Jul 24, 2013 at 08:42:48PM +0200, JS wrote:
> On Wednesday, 24 July 2013 at 18:12:37 UTC, JS wrote:
> T,
> 
> Also, I've tried to wrap the template in a function and I can't get
> it to work:
> 
> 	
> 	string join(T...)(string delim, T args)
> 	{
> 		return tupleStringReduce!(args);
> 	}
> 
> it seems tupleStringReduce just returns the tuple of of the
> optimized strings. I'll still need to write code that will deal
> mixing in the actual compile time and runtime code.

You can't return a tuple as a string. :)  Mainly because the joining has
only happened to the string literals, but you haven't told the compiler
how the tuple itself is to be joined into a string.

I thought I already gave example code to do this:

	string join(string[] args...) {
		string result;
		string delim;

		// You need this in order for the compiler to know what
		// you wanna do with the optimized tuple.
		foreach (arg; args) {
			result ~= delim ~ arg;
			delim = ",";	// just for example
		}
		return result;
	}

	template optimizedJoin(args...)
	{
		// This wrapper optimizes the tuple and passes the
		// result to join().
		string optimizedJoin() {
			return join(tupleReduce!((string x, string y) => x~y, args));
		}
	}

Note that you have to use template calling syntax for optimizedJoin,
like this:

	string result = optimizedJoin!("a", "b", x, "c", "d");

I did try wrapping it so that you can use normal runtime call syntax,
but it doesn't work because the tuple reduction must happen at template
expansion stage. It's too late to do it in CTFE proper.


> This doesn't seem that hard as tupleReduce essentially outlines the
> approach. The difference is instead of calling func directly I sort
> of need to mix it in as a code string.
> 
> e.g., for tupleStringReduce, func is x~y. I need to build a string
> using that "((arg[0]~arg[1])~arg[2])..." which is then mixed in at
> compile time but at runtime evaluates to a string(not an array).
> 
> Since there is no .codeof, AFAIK, I guess the only way to do this is
> pass func, and the func code string("x~y") in this case.
> 
> The idea though is to use the lamba as a ctfe to reduce the tuple
> when possible but *also* use it at runtime to evaluate the tuple.
[...]

Alright, here's an improved version of the code:

	import std.stdio;
	
	template tuple(args...) {
		alias tuple = args;
	}
	
	/**
	 * Given a binary function and a tuple, returns a tuple in which all adjacent
	 * compile-time readable items are recursively substituted with the return
	 * value of the binary function applied to them.
	 */
	template tupleReduce(alias func, args...)
	{
		static if (args.length > 1)
		{
			static if (__traits(compiles, { enum x = args[0]; }))
			{
				static if (__traits(compiles, { enum x = args[1]; }) &&
					is(typeof(func(args[0], args[1]))))
				{
					enum result = func(args[0], args[1]);
					alias tupleReduce = tupleReduce!(func, result,
						args[2..$]);
				}
				else
				{
					alias tupleReduce = tuple!(args[0], args[1],
						tupleReduce!(func, args[2..$]));
				}
			}
			else
			{
				alias tupleReduce = tuple!(args[0],
					tupleReduce!(func, args[1..$]));
			}
		}
		else
		{
			alias tupleReduce = args;
		}
	}
	
	// I decided to use a real variadic instead of an array, to
	// force loop-unrolling.
	// Strictly speaking, we should add a signature constraint to
	// enforce uniform types in T..., but I was too lazy to figure
	// out how to phrase allSatisfy to check for that. For
	// production code, though you'll definitely want to do this.
	auto reduceImpl(alias fun, T...)(T args)
	{
		import std.functional;
		typeof(unaryFun!fun(args[0],args[0])) result;
	
		foreach (arg; args) {
			result = unaryFun!fun(result, arg);
		}
		return result;
	}
	
	// Nice wrapper for reduceImpl, so that we don't have to type
	// the lambda twice.
	template reduce(alias fun, args...)
	{
		string reduce() {
			return reduceImpl!fun(tupleReduce!(fun, args));
		}
	}
	
	/**
	 * Joins a list of strings. Adjacent CTFEable strings are joined
	 * at compile-time into single strings, while runtime arguments
	 * are joined at runtime.
	 */
	template join(args...)
	{
		string join() {
			// Behold, only one instance of the lambda! It
			// gets used both at compile-time and runtime.
			return reduce!((string x, string y) => x~y, args);
		}
	}
	
	void main() {
		// Example of how to use tupleReduce for compile-time
		// optimization of join:
		string x = "(runtime1)";
		string y = "(runtime2)";

		// Note that you still have to use compile-time argument
		// syntax for join.
		writeln(join!(x, "a", "bc", y, "de", "f", "g"));
	}

Compiling with dmd -O -inline produced two nested function calls for the
join!(...), though inside, the string literals have already been
concatenated.

Compiling with gdc -O3, OTOH, produced an unrolled loop in Dmain which
basically sequentially appends to the result of join!(), i.e., it's as
though I wrote:

	void main() {
		string x = "(runtime1)";
		string y = "(runtime2)";
		writeln(x ~ "abc" ~ y ~ "defg");
	}

You can't get much better than that. :)

I think trying to repackage join!(...) as join(...) is a fool's errand,
though. You'll likely only end up with pain. :) IMO writing join!(...)
is a Good Enough(tm) compromise given that we have already achieved
maximal compile-time optimization.


T

-- 
ASCII stupid question, getty stupid ANSI.