Proof-of-concept: UGen caching

Development
1

Here’s a proof of concept of something I’ve been thinking about for a while.

One of the arguments against making e.g. a C++ LinLin is that it would bypass math-op UGen optimizations (e.g. in .linlin(0, inHi, 0, outHi), the - 0 operations disappear).

But the argument against this is that calling aUGen.linlin repeatedly with the same ranges will repeat math UGens that are completely identical.

(
d = SynthDef(\test, { |lo = 0, hi = 1, outLo = 0, outHi = 10|
	Out.kr(0,
		Array.fill(2, {
			Rand(lo, hi).linlin(lo, hi, outLo, outHi)
		})
	)
});
)

d.dumpUGens;

[ 0_Control, control, nil ]
[ 1_Rand, scalar, [ 0_Control[0], 0_Control[1] ] ]
[ 2_Clip, scalar, [ 1_Rand, 0_Control[0], 0_Control[1] ] ]
[ 3_-, control, [ 0_Control[3], 0_Control[2] ] ]
[ 4_-, control, [ 0_Control[1], 0_Control[0] ] ]
[ 5_/, control, [ 3_-, 4_- ] ]
[ 6_*, control, [ 5_/, 0_Control[0] ] ]
[ 7_-, control, [ 0_Control[2], 6_* ] ]
[ 8_MulAdd, control, [ 5_/, 2_Clip, 7_- ] ]
[ 9_Rand, scalar, [ 0_Control[0], 0_Control[1] ] ]
[ 10_Clip, scalar, [ 9_Rand, 0_Control[0], 0_Control[1] ] ]
[ 11_-, control, [ 0_Control[3], 0_Control[2] ] ]    // == ugen 3
[ 12_-, control, [ 0_Control[1], 0_Control[0] ] ]    // == ugen 4
[ 13_/, control, [ 11_-, 12_- ] ]                    // == ugen 5
[ 14_*, control, [ 13_/, 0_Control[0] ] ]            // == ugen 6
[ 15_-, control, [ 0_Control[2], 14_* ] ]            // == ugen 7
[ 16_MulAdd, control, [ 13_/, 10_Clip, 15_- ] ]
[ 17_Out, control, [ 0, 8_MulAdd, 16_MulAdd ] ]

UGens 3-7 and 11-15 are deterministic, side-effect-free operations applied to identical inputs – therefore guaranteed to produce the same output.

What if we could cache them?

UGenCache {
	classvar <>cache;
	classvar <>optimize = false;  // testing! want to be able to turn it on and off

	*clear {
		cache = MultiLevelIdentityDictionary.new;
	}

	*at { |... args|
		var test;
		^if(optimize) {
			test = cache.at(*args);
			// cache hit only if 'args' points to a legit UGen
			// if it's a subtree, cache miss
			if(test.isUGen) { test }  // else nil
		}  // else nil
	}

	*put { |... args|
		if(optimize) { cache.put(*args) }
	}
}

+ SynthDef {
	initBuild {
		UGen.buildSynthDef = this;
		constants = Dictionary.new;
		constantSet = Set.new;
		controls = nil;
		controlIndex = 0;
		maxLocalBufs = nil;

		// experimental
		UGenCache.clear;
	}

	finishBuild {
		this.addCopiesIfNeeded;
		this.optimizeGraph;
		this.collectConstants;
		this.checkInputs;// will die on error

		// re-sort graph. reindex.
		this.topologicalSort;
		this.indexUGens;
		UGen.buildSynthDef = nil;
		// experimental
		UGenCache.clear;
	}

}

+ UGen {
	isPure { ^false }  // deal with other ugens later

	// notes:
	// a. Rate is already args[0]
	// b. Operator is already args[1] for op ugens
	// therefore the UGen class ++ args should uniquely identify pure ops
	*multiNewList { arg args;
		var size = 0, newArgs, results, new, cacheKeys;
		args = args.asUGenInput(this);
		args.do({ arg item;
			(item.class == Array).if({ size = max(size, item.size) });
		});
		if (size == 0) {
			^this.new1FromCache(args);
		};
		newArgs = Array.newClear(args.size);
		results = Array.newClear(size);
		size.do({ arg i;
			args.do({ arg item, j;
				newArgs.put(j, if (item.class == Array, { item.wrapAt(i) },{ item }));
			});
			// needs more testing
			// in theory this recursive call will eventually check cache
			// against concrete values or UGens (but not subarrays)
			// this did work in one quick test
			results.put(i, this.multiNewList(newArgs));
		});
		^results
	}

	*new1FromCache { |args|
		var cacheKeys, new;
		cacheKeys = [this] ++ args;
		new = this.new1( *args );
		// yeah, bummer that I have to make the instance
		// in order to know if I need or don't need it
		if(new.isPure) {
			new = UGenCache.at(*cacheKeys) ?? { new };
		};
		// to optimize: don't re-put if you got it from cache
		UGenCache.put(*(cacheKeys ++ new));
		^new
	}
}

+ UnaryOpUGen {
	isPure {
		^#['rand', 'rand2', 'linrand', 'bilinrand', 'sum3rand']
		.includes(operator).not
	}
}

+ BinaryOpUGen {
	isPure {
		^#['rrand', 'exprand']
		.includes(operator).not
	}
}

+ Collection {
	isPure {
		^this.every(_.isPure)
	}
}

+ Number {
	isPure { ^true }
}

Needs style improvements, and here I’m applying it only to UnaryOpUGen and BinaryOpUGen, but:

(
UGenCache.optimize = true;
d = SynthDef(\test, { |lo = 0, hi = 1, outLo = 0, outHi = 10|
	Out.kr(0,
		Array.fill(2, {
			Rand(lo, hi).linlin(lo, hi, outLo, outHi)
		})
	)
});
d.dumpUGens;
)

[ 0_Control, control, nil ]
[ 1_Rand, scalar, [ 0_Control[0], 0_Control[1] ] ]
[ 2_Clip, scalar, [ 1_Rand, 0_Control[0], 0_Control[1] ] ]
[ 3_-, control, [ 0_Control[3], 0_Control[2] ] ]
[ 4_-, control, [ 0_Control[1], 0_Control[0] ] ]
[ 5_/, control, [ 3_-, 4_- ] ]
[ 6_*, control, [ 5_/, 0_Control[0] ] ]
[ 7_-, control, [ 0_Control[2], 6_* ] ]
[ 8_MulAdd, control, [ 5_/, 2_Clip, 7_- ] ]
[ 9_Rand, scalar, [ 0_Control[0], 0_Control[1] ] ]
[ 10_Clip, scalar, [ 9_Rand, 0_Control[0], 0_Control[1] ] ]
[ 11_MulAdd, control, [ 5_/, 10_Clip, 7_- ] ]
[ 12_Out, control, [ 0, 8_MulAdd, 11_MulAdd ] ]

… and the shared math ops on the Control channels are done only once, and reused in 8 and 11. It’s a correct graph, minus 5 redundant UGens.

In theory this could be extended to oscillators and filters, but this would require attention to the PureUGen interface (which is a big job – hence not dealing with it for a proof of concept).

This is not ready for a pull request quite yet (one issue is unit testing… how do you even…?), so I thought I’d ask for some feedback here.

hjh

2 Likes