Generators (v3)

Revision 3 of this benchmark created on February 10, 2024

Setup

function fib1(n) {
	if (n < 2)
		return 1;
	return fib1(n - 1) + fib1(n - 2);
}

function *fib2(n) {
	if (n < 2) return 1;
	return (yield fib2(n - 1)) + (yield fib2(n - 2));
}

function trampoline(it) {
	let stack = [];
	let val;
	while (true) {
		let {done, value} = it.next(val);
		if (done) {
			if (stack.length === 0)
				return value;
			it = stack.pop();
			val = value;
			continue;
		}
		stack.push(it);
		it = value;
		val = undefined;
	}
}

function fib3(n) {
	return f1(n, (a) => a);
}

function f1(n, cont) {	
	if (n < 2) return () => cont(1);
	return () => f1(n - 1, (a) => f1(n - 2, (b) => cont(a + b)));
}

function trampoline3(thunk) {
	while (typeof (thunk = thunk()) === 'function');
	return thunk;
}

function fib4(n) {
	let a = 0;
	let stack = [];
	function g1(n) {
		if (n < 2) {
			a = a + 1;
			if (stack.length === 0)
			    return;
			const t = stack.pop();
			return () => g1(t);
		}
		stack.push(n - 1);
		return () => g1(n - 2);
	}	
	pc = () => g1(n);
	while (pc)
	  pc = pc();
	return a;
}

let run = (function () {
const I = {
  CONST: 1,
  ADD: 2,
  PRINT: 3,
  HALT: 4,
  CALL: 5,
  RETURN: 6,
  LOAD: 7,
  JUMP_IF_ZERO: 8,
  JUMP_IF_NOT_ZERO: 9,
  SUB: 10,
  MUL: 11,
};

function createVM(code, builtins) {
  /** Instruction pointer. */
  let ip = 0;
  /** Stack pointer. */
  let sp = -1;
  /** Stack frame. */
  let fp = 0;

  let stack = new Int32Array(256);

  function run() {
  /** Instruction pointer. */
  let ip = 0;
  /** Stack pointer. */
  let sp = -1;
  /** Stack frame. */
  let fp = 0;
  	let res;
    while (ip < code.length) {
      const instruction = code[ip++];
      switch (instruction) {
        case I.CONST: {
          const op_value = code[ip++];
          stack[++sp] = op_value;
          break;
        }
        case I.ADD: {
          const op1 = stack[sp--];
          const op2 = stack[sp--];
          stack[++sp] = op1 + op2;
          break;
        }
        case I.MUL: {
          const op1 = stack[sp--];
          const op2 = stack[sp--];
          stack[++sp] = op1 * op2;
          break;
        }
        case I.SUB: {
          const op1 = stack[sp--];
          const op2 = stack[sp--];
          stack[++sp] = op2 - op1;
          break;
        }
        case I.PRINT: {
          const value = stack[sp--];
          //console.log(value);
          res = value;
          break;
        }
        case I.HALT: {
          return res;
        }
        case I.CALL: {
          const op1_address = code[ip++];
          const op2_numberOfArguments = code[ip++];

          stack[++sp] = op2_numberOfArguments;
          stack[++sp] = fp;
          stack[++sp] = ip;

          fp = sp;
          ip = op1_address;
          break;
        }
        case I.RETURN: {
          const returnValue = stack[sp--];
          sp = fp;

          ip = stack[sp--];
          fp = stack[sp--];
          const number_of_arguments = stack[sp--];

          sp -= number_of_arguments;
          stack[++sp] = returnValue;
          break;
        }
        case I.LOAD: {
          const op_offset = code[ip++];
          const value = stack[fp + op_offset];
          stack[++sp] = value;
          break;
        }
        case I.JUMP_IF_ZERO: {
          const op_address = code[ip++];
          const value = stack[sp--];
          if (value === 0) {
            ip = op_address;
          }
          break;
        }
        case I.JUMP_IF_NOT_ZERO: {
          const op_address = code[ip++];
          const value = stack[sp--];
          if (value !== 0) {
            ip = op_address;
          }
          break;
        }
        default:
          throw new Error(`Unknown instruction: ${instruction}.`);
      }
    }
  }

  return {
    run,
  };
}


const builtins = {
  print: (x) => console.log(x),
};

const bytecode =
new Int8Array([
  I.CONST,
  13,
  I.CALL,
  /* fibonacci */ 7,
  1,
  I.PRINT,
  I.HALT,
  I.LOAD, // if (n === 1) { return 1; }
  -3,
  I.CONST,
  1,
  I.SUB,
  I.JUMP_IF_NOT_ZERO,
  17,
  I.CONST,
  1,
  I.RETURN,
  I.LOAD, // if (n === 2) { return 1; }
  -3,
  I.CONST,
  2,
  I.SUB,
  I.JUMP_IF_NOT_ZERO,
  27,
  I.CONST,
  1,
  I.RETURN,
  I.LOAD, // return fibonacci(n - 1) + fibonacci(n - 2)
  -3,
  I.CONST,
  1,
  I.SUB,
  I.CALL,
  7,
  1,
  I.LOAD,
  -3,
  I.CONST,
  2,
  I.SUB,
  I.CALL,
  7,
  1,
  I.ADD,
  I.RETURN,
]);

const vm = createVM(bytecode, builtins);

return vm.run;
})();

async function *fib6(n) {
	if (n < 2) return 1;
	return (yield fib6(n - 1)) + (yield fib6(n - 2));
}

async function trampoline6(it) {
	let stack = [];
	let val;
	while (true) {
		let {done, value} = await it.next(val);
		if (done) {
			if (stack.length === 0)
				return value;
			it = stack.pop();
			val = value;
			continue;
		}
		stack.push(it);
		it = value;
		val = undefined;
	}
}

Test runner

fib1(12);

trampoline(fib2(12));

trampoline3(() => fib3(12))

fib4(12)

run()

trampoline6(fib6(12)).then((n) => deferred.resolve(n))

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on February 10, 2024
• Revision 2: published on February 10, 2024
• Revision 3: published on February 10, 2024