Context Navigation

rec_perf.html

Last change on this file was 483, checked in by hendrikvanantwerpen, 11 years ago
Added Dojo 1.9.3 release.
File size: 14.0 KB

Line
1	<html>
2	<head>
3	<title>Clocking recursion combinators</title>
4	<style type="text/css">
5	@import "../../../dojo/resources/dojo.css";
6	</style>
7	<script type="text/javascript" src="../../../dojo/dojo.js" data-dojo-config="isDebug:true"></script>
8	<script type="text/javascript" src="../functional.js"></script>
9	<script type="text/javascript" src="../functional/linrec.js"></script>
10	<script type="text/javascript" src="../functional/tailrec.js"></script>
11	<script type="text/javascript" src="../functional/numrec.js"></script>
12	<script type="text/javascript" src="../functional/binrec.js"></script>
13	<script type="text/javascript" src="../functional/multirec.js"></script>
14	<script type="text/javascript" src="../functional/sequence.js"></script>
15	<script type="text/javascript">
16	// reference implementations
17
18	var linrec1 = function(cond, then, before, after){
19	var cond = df.lambda(cond),
20	then = df.lambda(then),
21	before = df.lambda(before),
22	after = df.lambda(after);
23	return function(){
24	if(cond.apply(this, arguments)){
25	return then.apply(this, arguments);
26	}
27	var args = before.apply(this, arguments);
28	var ret = arguments.callee.apply(this, args);
29	return after.call(this, ret, arguments);
30	};
31	};
32
33	var linrec2 = function(cond, then, before, after){
34	var cond = df.lambda(cond),
35	then = df.lambda(then),
36	before = df.lambda(before),
37	after = df.lambda(after);
38	return function(){
39	var args = arguments, top, ret;
40	// 1st part
41	for(; !cond.apply(this, args); args = before.apply(this, args)){
42	top = {prev: top, args: args};
43	}
44	ret = then.apply(this, args);
45	//2nd part
46	for(; top; top = top.prev){
47	ret = after.call(this, ret, top.args);
48	}
49	return ret;
50	};
51	};
52
53	var tailrec1 = function(cond, then, before){
54	var cond = df.lambda(cond),
55	then = df.lambda(then),
56	before = df.lambda(before);
57	return function(){
58	if(cond.apply(this, arguments)){
59	return then.apply(this, arguments);
60	}
61	var args = before.apply(this, arguments);
62	return arguments.callee.apply(this, args);
63	};
64	};
65
66	var tailrec2 = function(cond, then, before){
67	var cond = df.lambda(cond),
68	then = df.lambda(then),
69	before = df.lambda(before);
70	return function(){
71	var args = arguments;
72	for(; !cond.apply(this, args); args = before.apply(this, args));
73	return then.apply(this, args);
74	};
75	};
76
77	var numrec1 = function(then, after){
78	var after = df.lambda(after);
79	return function(x){
80	return x ? after.call(this, arguments.callee.call(this, x - 1), x) : then;
81	};
82	};
83
84	var numrec2 = function(then, after){
85	var after = df.lambda(after);
86	return function(x){
87	var ret = then, i;
88	for(i = 1; i <= x; ++i){
89	ret = after.call(this, ret, i);
90	}
91	return ret;
92	};
93	};
94
95	var binrec1 = function(cond, then, before, after){
96	var cond = df.lambda(cond),
97	then = df.lambda(then),
98	before = df.lambda(before),
99	after = df.lambda(after);
100	return function(){
101	if(cond.apply(this, arguments)){
102	return then.apply(this, arguments);
103	}
104	var args = before.apply(this, arguments);
105	var ret1 = arguments.callee.apply(this, args[0]);
106	var ret2 = arguments.callee.apply(this, args[1]);
107	return after.call(this, ret1, ret2, arguments);
108	};
109	};
110
111	var binrec2 = function(cond, then, before, after){
112	var cond = df.lambda(cond),
113	then = df.lambda(then),
114	before = df.lambda(before),
115	after = df.lambda(after);
116	return function(){
117	var top1, top2, ret, args = arguments;
118	// first part: start the pump
119	while(!cond.apply(this, args)){
120	ret = before.apply(this, args);
121	top1 = {prev: top1, args: ret[1]};
122	top2 = {prev: top2, args: args};
123	args = ret[0];
124	}
125	for(;;){
126	// second part: mop up
127	do{
128	ret = then.apply(this, args);
129	if(!top2){
130	return ret;
131	}
132	while("ret" in top2){
133	ret = after.call(this, top2.ret, ret, top2.args);
134	if(!(top2 = top2.prev)){
135	return ret;
136	}
137	}
138	top2.ret = ret;
139	args = top1.args;
140	top1 = top1.prev;
141	}while(cond.apply(this, args));
142	// first part (encore)
143	do{
144	ret = before.apply(this, args);
145	top1 = {prev: top1, args: ret[1]};
146	top2 = {prev: top2, args: args};
147	args = ret[0];
148	}while(!cond.apply(this, args));
149	}
150	};
151	};
152
153	var multirec1 = function(cond, then, before, after){
154	var cond = df.lambda(cond),
155	then = df.lambda(then),
156	before = df.lambda(before),
157	after = df.lambda(after);
158	return function(){
159	if(cond.apply(this, arguments)){
160	return then.apply(this, arguments);
161	}
162	var args = before.apply(this, arguments),
163	ret = new Array(args.length);
164	for(var i = 0; i < args.length; ++i){
165	ret[i] = arguments.callee.apply(this, args[i]);
166	}
167	return after.call(this, ret, arguments);
168	};
169	};
170
171	var multirec2 = function(cond, then, before, after){
172	var cond = df.lambda(cond),
173	then = df.lambda(then),
174	before = df.lambda(before),
175	after = df.lambda(after);
176	return function(){
177	var top = {args: arguments}, args, ret, parent, i;
178	for(;;){
179	for(;;){
180	if(top.old){
181	ret = after.call(this, top.ret, top.old);
182	break;
183	}
184	args = top.args;
185	if(cond.apply(this, args)){
186	ret = then.apply(this, args);
187	break;
188	}
189	top.old = args;
190	args = before.apply(this, args);
191	top.ret = [];
192	parent = top;
193	for(i = args.length - 1; i >= 0; --i){
194	top = {prev: top, args: args[i], parent: parent};
195	}
196	}
197	if(!(parent = top.parent)){
198	return ret;
199	}
200	parent.ret.push(ret);
201	top = top.prev;
202	}
203	};
204	};
205
206	// tests
207
208	var clock = function(body){
209	var b = new Date();
210	body();
211	var e = new Date();
212	return e.getTime() - b.getTime(); // in ms
213	};
214
215	var log = function(name, body){
216	var ms = clock(body);
217	console.log(name + ":", ms);
218	};
219
220	var LEN1 = 15, LEN2 = 10, ITER = 1000, tests = {},
221	df = dojox.lang.functional,
222	sample1 = df.repeat(LEN1, "+1", 0),
223	sample2 = df.repeat(LEN2, "+1", 0);
224
225	var fact1 = function(n){
226	var ret = 1;
227	for(var i = 2; i <= n; ++i){
228	ret *= i;
229	}
230	return ret;
231	};
232	tests["factorial: raw iterative"] = function(){
233	for(var i = 0; i < ITER; ++i){
234	df.forEach(sample1, fact1);
235	}
236	};
237
238	var fact2 = function(n){ return n ? n * arguments.callee.call(this, n - 1) : 1; };
239	tests["factorial: raw recursion"] = function(){
240	for(var i = 0; i < ITER; ++i){
241	df.forEach(sample1, fact2);
242	}
243	};
244
245	var fact3_1 = linrec1("<= 1", "1", "[n - 1]", "a * b[0]");
246	tests["factorial: linrec1 (recursive reference)"] = function(){
247	for(var i = 0; i < ITER; ++i){
248	df.forEach(sample1, fact3_1);
249	}
250	};
251
252	var fact3_2 = linrec2("<= 1", "1", "[n - 1]", "a * b[0]");
253	tests["factorial: linrec2 (iterative reference)"] = function(){
254	for(var i = 0; i < ITER; ++i){
255	df.forEach(sample1, fact3_2);
256	}
257	};
258
259	var fact3 = df.linrec("<= 1", "1", "[n - 1]", "a * b[0]");
260	tests["factorial: linrec"] = function(){
261	for(var i = 0; i < ITER; ++i){
262	df.forEach(sample1, fact3);
263	}
264	};
265
266	var fact4_1 = numrec1(1, "*");
267	tests["factorial: numrec1 (recursive reference)"] = function(){
268	for(var i = 0; i < ITER; ++i){
269	df.forEach(sample1, fact4_1);
270	}
271	};
272
273	var fact4_2 = numrec2(1, "*");
274	tests["factorial: numrec2 (iterative reference)"] = function(){
275	for(var i = 0; i < ITER; ++i){
276	df.forEach(sample1, fact4_2);
277	}
278	};
279
280	var fact4 = df.numrec(1, "*");
281	tests["factorial: numrec"] = function(){
282	for(var i = 0; i < ITER; ++i){
283	df.forEach(sample1, fact4);
284	}
285	};
286
287	var fact5_1a = tailrec1("<= 1", "a, b -> b", "[n - 1, n * acc]");
288	var fact5_1 = function(n){ return fact5_1a(n, 1); };
289	tests["factorial: tailrec1 (recursive reference)"] = function(){
290	for(var i = 0; i < ITER; ++i){
291	df.forEach(sample1, fact5_1);
292	}
293	};
294
295	var fact5_2a = tailrec2("<= 1", "a, b -> b", "[n - 1, n * acc]");
296	var fact5_2 = function(n){ return fact5_2a(n, 1); };
297	tests["factorial: tailrec2 (iterative reference)"] = function(){
298	for(var i = 0; i < ITER; ++i){
299	df.forEach(sample1, fact5_2);
300	}
301	};
302
303	var fact5a = df.tailrec("<= 1", "a, b -> b", "[n - 1, n * acc]");
304	var fact5 = function(n){ return fact5a(n, 1); };
305	tests["factorial: tailrec"] = function(){
306	for(var i = 0; i < ITER; ++i){
307	df.forEach(sample1, fact5);
308	}
309	};
310
311	var fact6_1 = multirec1("<= 0", "1", "[[n - 1]]", "a[0] * b[0]");
312	tests["factorial: multirec1 (recursive reference)"] = function(){
313	for(var i = 0; i < ITER; ++i){
314	df.forEach(sample1, fact6_1);
315	}
316	};
317
318	var fact6_2 = multirec2("<= 0", "1", "[[n - 1]]", "a[0] * b[0]");
319	tests["factorial: multirec2 (iterative reference)"] = function(){
320	for(var i = 0; i < ITER; ++i){
321	df.forEach(sample1, fact6_2);
322	}
323	};
324
325	var fact6 = df.multirec("<= 0", "1", "[[n - 1]]", "a[0] * b[0]");
326	tests["factorial: multirec"] = function(){
327	for(var i = 0; i < ITER; ++i){
328	df.forEach(sample1, fact6);
329	}
330	};
331
332	var fib1 = function(n){
333	var a = 1, b = 1;
334	for(var i = 2; i <= n; ++i){
335	var c = a + b;
336	b = a;
337	a = c;
338	}
339	return a;
340	};
341	tests["fibonacci: raw iterative"] = function(){
342	for(var i = 0; i < ITER; ++i){
343	df.forEach(sample2, fib1);
344	}
345	};
346
347	var fib2 = function(n){ return n <= 1 ? 1 : arguments.callee.call(this, n - 1) + arguments.callee.call(this, n - 2); };
348	tests["fibonacci: raw recursion"] = function(){
349	for(var i = 0; i < ITER; ++i){
350	df.forEach(sample2, fib2);
351	}
352	};
353
354	var fib3a = function(n, next, result){ return n <= 0 ? result : arguments.callee.call(this, n - 1, next + result, next); };
355	var fib3 = function(n){ return fib3a(n, 1, 1); };
356	tests["fibonacci: raw tail recursion"] = function(){
357	for(var i = 0; i < ITER; ++i){
358	df.forEach(sample2, fib3);
359	}
360	};
361
362	var fib4_1 = binrec1("<= 1", "1", "[[n - 1], [n - 2]]", "+");
363	tests["fibonacci: binrec1 (recursive reference)"] = function(){
364	for(var i = 0; i < ITER; ++i){
365	df.forEach(sample2, fib4_1);
366	}
367	};
368
369	var fib4_2 = binrec2("<= 1", "1", "[[n - 1], [n - 2]]", "+");
370	tests["fibonacci: binrec2 (iterative reference)"] = function(){
371	for(var i = 0; i < ITER; ++i){
372	df.forEach(sample2, fib4_2);
373	}
374	};
375
376	var fib4 = df.binrec("<= 1", "1", "[[n - 1], [n - 2]]", "+");
377	tests["fibonacci: binrec"] = function(){
378	for(var i = 0; i < ITER; ++i){
379	df.forEach(sample2, fib4);
380	}
381	};
382
383	var fib5_1a = tailrec1("<= 0", "a, b, c -> c", "[n - 1, next + result, next]");
384	var fib5_1 = function(n){ return fib5_1a(n, 1, 1); };
385	tests["fibonacci: tailrec1 (recursive reference)"] = function(){
386	for(var i = 0; i < ITER; ++i){
387	df.forEach(sample2, fib5_1);
388	}
389	};
390
391	var fib5_2a = tailrec2("<= 0", "a, b, c -> c", "[n - 1, next + result, next]");
392	var fib5_2 = function(n){ return fib5_2a(n, 1, 1); };
393	tests["fibonacci: tailrec2 (iterative reference)"] = function(){
394	for(var i = 0; i < ITER; ++i){
395	df.forEach(sample2, fib5_2);
396	}
397	};
398
399	var fib5a = df.tailrec("<= 0", "a, b, c -> c", "[n - 1, next + result, next]");
400	var fib5 = function(n){ return fib5a(n, 1, 1); };
401	tests["fibonacci: tailrec"] = function(){
402	for(var i = 0; i < ITER; ++i){
403	df.forEach(sample2, fib5);
404	}
405	};
406
407	var fib6_1 = multirec1("<= 1", "1", "[[n - 1], [n - 2]]", "a[0] + a[1]");
408	tests["fibonacci: multirec1 (recursive reference)"] = function(){
409	for(var i = 0; i < ITER; ++i){
410	df.forEach(sample2, fib6_1);
411	}
412	};
413
414	var fib6_2 = multirec2("<= 1", "1", "[[n - 1], [n - 2]]", "a[0] + a[1]");
415	tests["fibonacci: multirec2 (iterative reference)"] = function(){
416	for(var i = 0; i < ITER; ++i){
417	df.forEach(sample2, fib6_2);
418	}
419	};
420
421	var fib6 = df.multirec("<= 1", "1", "[[n - 1], [n - 2]]", "a[0] + a[1]");
422	tests["fibonacci: multirec"] = function(){
423	for(var i = 0; i < ITER; ++i){
424	df.forEach(sample2, fib6);
425	}
426	};
427
428	var keys = df.keys(tests), i = 0;
429
430	var doTest = function(){
431	log(keys[i], tests[keys[i]]);
432	++i;
433	if(i < keys.length){
434	setTimeout(doTest, 20);
435	}else{
436	console.log("that's all");
437	}
438	};
439
440	var test = function(){
441	i = 0;
442	setTimeout(doTest, 20);
443	};
444
445	dojo.addOnLoad(function(){
446	// sanity check
447
448	console.assert(fact1(5) == 120, "fact1");
449	console.assert(fact2(5) == 120, "fact2");
450	console.assert(fact3_1(5) == 120, "fact3_1");
451	console.assert(fact3_2(5) == 120, "fact3_2");
452	console.assert(fact3(5) == 120, "fact3");
453	console.assert(fact4_1(5) == 120, "fact4_1");
454	console.assert(fact4_2(5) == 120, "fact4_2");
455	console.assert(fact4(5) == 120, "fact4");
456	console.assert(fact5_1(5) == 120, "fact5_1");
457	console.assert(fact5_2(5) == 120, "fact5_2");
458	console.assert(fact5(5) == 120, "fact5");
459	console.assert(fact6_1(5) == 120, "fact6_1");
460	console.assert(fact6_2(5) == 120, "fact6_2");
461	console.assert(fact6(5) == 120, "fact6");
462
463	console.assert(fib1(5) == 8, "fib1");
464	console.assert(fib2(5) == 8, "fib2");
465	console.assert(fib3(5) == 8, "fib3");
466	console.assert(fib4_1(5) == 8, "fib4_1");
467	console.assert(fib4_2(5) == 8, "fib4_2");
468	console.assert(fib4(5) == 8, "fib4");
469	console.assert(fib5_1(5) == 8, "fib5_1");
470	console.assert(fib5_2(5) == 8, "fib5_2");
471	console.assert(fib5(5) == 8, "fib5");
472	console.assert(fib6_1(5) == 8, "fib6_1");
473	console.assert(fib6_2(5) == 8, "fib6_2");
474	console.assert(fib6(5) == 8, "fib6");
475
476	console.log("sanity check finished");
477	});
478	</script>
479	</head>
480	<body>
481	<p>This test is meant to run with Firebug. Open the console to see the output.</p>
482	<p><button onclick="test()">Start</button></p>
483	</body>
484	</html>

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: Dev/trunk/src/client/dojox/lang/tests/rec_perf.html

Download in other formats: