An approach to implement async/await in Javascript with nearly zero overhead

[hackwaly]

Consider this Javascript, executed in chrome in 2775.01ms on my MBP (please close devtools first before you test it). Why? Because under the hood ES7 use promise to implement await/async, which introduce massive overhead. Call an async function is doggy slow even if it actually doesn't do any async thing.

function sleep(t) {
    return new Promise((resolve) => {
        setTimeout(resolve, t);
    });
}
async function small(i, n) {
    if (i === Math.floor(n / 2)) {
        await sleep(1000);
    }
}
async function test(n) {
    let t = performance.now();
    for (let i = 0; i < n; i++) {
        await small(i, n);
    }
    console.log(performance.now() - t);
}
test(5000000);

Now, I'll present you a novel approach to implement async/await. It combines CPS, state machine and exception to reconstruct call stack and avoid closure creation.

The javascript above then can transform to the javascript below. You can test it in your chrome. I'll explain it next time. These code is just prototype for proof. You don't need handwrite your async logic like these. There will be some compilers do it. Thank you!

function GetContinuation(callback, outerState) {
    this.callback = callback;
    this.stack = [];
    this.outerState = outerState;
}

function makeContinuation(stack, index) {
    if (index === stack.length) {
        return function () {};
    }
    let func = stack[index];
    let args = stack[index + 1];
    let parent = makeContinuation(stack, index + 2);
    return function () {
        return func.apply(parent, args);;
    };
}

function bind(func, this_, args) {
    return function () {
        return func.apply(this_, args);
    };
}

function callcc(callback, outerState) {
    throw new GetContinuation(callback, outerState);
}

function sleep(timeout, outerState) {
    return callcc(function (continuation) {
        setTimeout(continuation, timeout);
    }, outerState);
}

function small(i, n, outerState) {
    try {
        if (i === Math.floor(n / 2)) {
            sleep(1000, 0);
        }
    } catch (exn) {
        if (exn instanceof GetContinuation) {
            exn.stack.push(small_async, [exn.outerState, i, n]);
            exn.outerState = outerState;
        }
        throw exn;
    }
}

function small_async(state, i, n) {
    try {
        while (true) {
            switch (state) {
            case 0:
                return this();
            }
        }
    } catch (exn) {
        if (exn instanceof GetContinuation) {
            return exn.callback(bind(small_async, this, [exn.outerState, i, n]));
        }
        throw exn;
    }
}

function test(n, outerState) {
    var i;
    var t;
    try {
        t = performance.now();
        i = 0;
        while (i < n) {
            small(i, n, 0);
            i ++;
        }
        console.log(performance.now() - t);
    } catch (exn) {
        if (exn instanceof GetContinuation) {
            exn.stack.push(test_async, [exn.outerState, t, i, n]);
            exn.outerState = outerState;
        }
        throw exn;
    }
}

function test_async(state, t, i, n) {
    try {
        while (true) {
            switch (state) {
            case 0:
                i++;
            case 1:
                if (i >= n) {
                    state = 2;
                    continue;
                }
                small(i, n, 0);
                continue;
            case 2:
                console.log(performance.now() - t);
                return this();
            }
            
        }
    } catch (exn) {
        if (exn instanceof GetContinuation) {
            return exn.callback(bind(test_async, this, [exn.outerState, t, i, n]));
        }
        throw exn;
    }
}

function main() {
    test(5000000, 0);
}

function exec(main) {
    var task;
    task = main;
    while (true) {
        try {
            return task();
        } catch (exn) {
            if (exn instanceof GetContinuation) {
                task = function () {
                    return exn.callback(makeContinuation(exn.stack, 0));
                };
            } else {
                throw exn;
            }
        }
    }
}
exec(main);

[arendjr]

I know Babel also transpiles to code using state machines to be able to support async/await in lower ECMAScript versions, but I haven't studied in detail what those state machines look like. Can you explain if this is actually different and how?

[hackwaly]

The difference is that this approach compile one async function to two functions: one is fast like the original function but wrapped in a try catch block. the other one is compiled state machine. The async function call is rewrote with addition parameter outerState which indicate where to continue in state machine one. When async operation occurred, the execution is switched from fast one to state machine one and call stack is reconstructed via exception throw-catch. If there's no async operation occurred, the execution is always run on the fast one. Like SEH, there's no overhead if exception not occurred.

[arendjr]

Cool, that sounds like an interesting optimization indeed!

[hackwaly]

Typescript compiled es3 javascript code:

 var __awaiter = (this && this.__awaiter) || function (thisArg, _arguments, P, generator) {
    return new (P || (P = Promise))(function (resolve, reject) {
        function fulfilled(value) { try { step(generator.next(value)); } catch (e) { reject(e); } }
        function rejected(value) { try { step(generator["throw"](value)); } catch (e) { reject(e); } }
        function step(result) { result.done ? resolve(result.value) : new P(function (resolve) { resolve(result.value); }).then(fulfilled, rejected); }
        step((generator = generator.apply(thisArg, _arguments || [])).next());
    });
};
var __generator = (this && this.__generator) || function (thisArg, body) {
    var _ = { label: 0, sent: function() { if (t[0] & 1) throw t[1]; return t[1]; }, trys: [], ops: [] }, f, y, t, g;
    return g = { next: verb(0), "throw": verb(1), "return": verb(2) }, typeof Symbol === "function" && (g[Symbol.iterator] = function() { return this; }), g;
    function verb(n) { return function (v) { return step([n, v]); }; }
    function step(op) {
        if (f) throw new TypeError("Generator is already executing.");
        while (_) try {
            if (f = 1, y && (t = y[op[0] & 2 ? "return" : op[0] ? "throw" : "next"]) && !(t = t.call(y, op[1])).done) return t;
            if (y = 0, t) op = [0, t.value];
            switch (op[0]) {
                case 0: case 1: t = op; break;
                case 4: _.label++; return { value: op[1], done: false };
                case 5: _.label++; y = op[1]; op = [0]; continue;
                case 7: op = _.ops.pop(); _.trys.pop(); continue;
                default:
                    if (!(t = _.trys, t = t.length > 0 && t[t.length - 1]) && (op[0] === 6 || op[0] === 2)) { _ = 0; continue; }
                    if (op[0] === 3 && (!t || (op[1] > t[0] && op[1] < t[3]))) { _.label = op[1]; break; }
                    if (op[0] === 6 && _.label < t[1]) { _.label = t[1]; t = op; break; }
                    if (t && _.label < t[2]) { _.label = t[2]; _.ops.push(op); break; }
                    if (t[2]) _.ops.pop();
                    _.trys.pop(); continue;
            }
            op = body.call(thisArg, _);
        } catch (e) { op = [6, e]; y = 0; } finally { f = t = 0; }
        if (op[0] & 5) throw op[1]; return { value: op[0] ? op[1] : void 0, done: true };
    }
};
function sleep(t) {
    return new Promise(function (resolve) {
        setTimeout(resolve, t);
    });
}
function small(i, n) {
    return __awaiter(this, void 0, void 0, function () {
        return __generator(this, function (_a) {
            switch (_a.label) {
                case 0:
                    if (!(i === Math.floor(n / 2))) return [3 /*break*/, 2];
                    return [4 /*yield*/, sleep(1000)];
                case 1:
                    _a.sent();
                    _a.label = 2;
                case 2: return [2 /*return*/];
            }
        });
    });
}
function test(n) {
    return __awaiter(this, void 0, void 0, function () {
        var t, i;
        return __generator(this, function (_a) {
            switch (_a.label) {
                case 0:
                    t = performance.now();
                    i = 0;
                    _a.label = 1;
                case 1:
                    if (!(i < n)) return [3 /*break*/, 4];
                    return [4 /*yield*/, small(i, n)];
                case 2:
                    _a.sent();
                    _a.label = 3;
                case 3:
                    i++;
                    return [3 /*break*/, 1];
                case 4:
                    console.log(performance.now() - t);
                    return [2 /*return*/];
            }
        });
    });
}
test(5000000);

[awto]

my effects compiler can help to implement and experiment with different options pretty quickly https://github.com/awto/effectfuljs
it supports both async/await separate syntax layer and single layer syntax.

Avoiding promises then step will indeed improve performance, I used this in the older version of delimited continuation, however, this may break some programs already written and depending on something after await is executed in the next event loop step. I personally wrote a lot of code like this.

[hackwaly]

Generator base approach:

class CallCC {
   constructor(callback) {
       this.callback = callback;
   }
}

function* sleep(timeout) {
   yield new CallCC((cont) => {
       setTimeout(cont, timeout);
   });
}
function* small(i, n) {
   if (i === Math.floor(n / 2)) {
       yield* sleep(1000);
   }
}
function* test(n) {
   let t = performance.now();
   for (let i = 0; i < n; i++) {
       yield* small(i, n);
   }
   console.log(performance.now() - t);
}
function* main() {
   yield* test(5000000);
}
function go(g) {
   let r = g.next();
   if (r.done) {
       return;
   }
   r.value.callback(() => {
       go(g);
   });
}
go(main());