Compile-time optimization

[H. S. Teoh]

On Thu, Jul 25, 2013 at 03:47:23PM +0200, JS wrote:
[...]
> Cool, this is definitely on the right track! I like how you are able
> to generate the expansion reduction without string mixins(the naive
> way I would try and do it).
 
String mixins are sorta like nuclear warheads, a last resort when
absolutely nothing else will work. They're usually overkill for most
tasks. Generally, other less drastic alternatives should be tried first.
:)


> The main things I was after are achieved: Loop unrolling, mixed-time
> constant folding, and variable arguments.

While it has been a fun exercise, I still think loop unrolling is in the
province of the compiler's optimizer (e.g. gdc -O3). Unless you're
writing performance-critical inner loops in a 3D game engine or a hard
real-time application, it seems like premature optimization to me.

As for constant folding, I wonder if expression templates may be a
better approach for the general case. Tuple reduction works well when
the reduction can be done pairwise, but in more complicated cases, like
optimizing matrix expressions, say, you probably need something more
sophisticated.

Still, I think it would be cleaner if the language provided a way for
the compiler to support such optimizations, so that we can take
advantage of its built-in optimizer instead of reinventing the wheel in
user code. I've often thought about how one might go about specifying
expression reduction rules for user-defined types, like associativity
for matrix expressions, etc., that tell the compiler what kind of rules
the custom operators obey, that the optimizer can make use of.


> While I think I understand the overall idea you are using it will
> take me a bit to grasp exactly how you were able to get it all done
> correctly.

Maybe you should take the time to study the code, then next time you can
do it yourself. ;-)


> I have two requests if you don't mind and have the time...
> 
> Allow for array reduction and delim/indexing. When using join we
> typically want to join an array of strings while also inserting a
> delimiter between them... usually with the last one removed.

We already have std.algorithm.join... yes, yes I know you want
compile-time optimization, so that can be an interesting exercise for
your learning. ;-)

But for starters, one way to achieve this is to preprocess your tuple to
insert delimiters between elements, then hand it over to tupleReduce to
optimize it. Something like this might do it:

	// Warning: untested code
	template insertDelim(string delim, args...) {
		static if (args.length > 1) {
			alias insertDelim = tuple!(args[0], delim,
				insertDelim!(args[1..$]));
		} else {
			alias insertDelim = args;
		}
	}

	// This should do the trick. Use insertDelim to insert the
	// delimiters, then tupleReduce it to concatenate all
	// compile-time-known arguments, then hand over the rest to the
	// runtime function as before.
	template join(string delim, args...) {
		string join() {
			return joinImpl(tupleReduce!(
				(string x, string y) => x~y,
				insertDelim!(delim, args)));
		}
	}

If I didn't make a mistake in the above code, it should be able to
optimize:

	join!(",", "a", "b", x, "c", "d");

into:

	"a,b," ~ x ~ ",c,d"


> Sometimes we want to know the index and maximum array size to do
> specialized joins.
[...]

That's trivial, tuples can be indexed just like arrays at compile-time,
and have a .length property just like arrays.


T

-- 
"Real programmers can write assembly code in any language. :-)" -- Larry Wall