Deep stacks redesign

[arjunguha]

I suspect it is possible to implement deep stacks as a "macro" that uses call/cc, without the need to hack the runtime system internals. However, it is unclear how this "macro" would interact with Stopify, which implements pausing using call/cc.

We should prototype this in Racket before trying to do this in JavaScript.

[arjunguha]

@jpolitz I have an idea for simplifying the implementation of deep stacks that may be just as effective as the current approach in Stopify. Would you read this over and give me your thoughts:

http://plasma-umass.org/pliss2019/playground/#https://gist.githubusercontent.com/arjunguha/070972712fd7ea011c59af07891358c0/raw/a4a3b3063ffaf8ffef30a6cd0787cc6f92f6bd5f/shrink-stack.js

Thanks

[jpolitz]

Two immediate comments:

• shrinkStack as written and instrumented is expecting control to throw an exception, right? Or is the idea that some instrumentation is happening that will check for the return value of shrinkStack in the contexts it's called from along with this? Does this imply a particular kind of capturing strategy?
• In Pyret we got a big speedup from implementing +1/-1 parity on calls and returns instead of just counting up stack depth at the top of functions, which I think is what's happening here. This might be an artifact of Pyret's recursion-heavy style, and if stacks tend to be shallow you pay for it less. But since this is for deep stacks, that experience may be relevant. So I would expect this to have significantly worse performance (though I'd be curious to see the measurement) – in recursion-heavy programs I bet conservative estimates of the available stack size are too small and end up capturing far more than is necessary.

[arjunguha]

1. shrinkStack works with any capturing strategy.
2. Yeah, doing a performance measurement will be tricky. The deep stacks implementation in Stopify has always been worse than the one in Pyret. I also think that it is presently broken. So, we'd have to fix it to get performance parity first.

[jpolitz]

We're running into issues with deep stacks for Pyret now.

• Is the link above totally dead or do you have access to it somehow still?
• Any movement on this?

[arjunguha]

Here is the gist:

https://gist.githubusercontent.com/arjunguha/070972712fd7ea011c59af07891358c0/raw/a4a3b3063ffaf8ffef30a6cd0787cc6f92f6bd5f/shrink-stack.js

Try this:

https://arjunguha.github.io/pliss2019/playground/index.html#https://gist.githubusercontent.com/arjunguha/070972712fd7ea011c59af07891358c0/raw/a4a3b3063ffaf8ffef30a6cd0787cc6f92f6bd5f/shrink-stack.js

[arjunguha]

Er, this approach may be bogus....

[jpolitz]

Yeah, if I do sum(190000) rather than sum(19000) in the example I get a stack overflow.

It seems like there's useful infrastructure in the existing runtime for this. In suspend there's a difference between the stack frames and the estimator, for example. It just doesn't quite work, and I'm not sure where it breaks down.

Here's a dumb question I should know the answer to – when Stopify restarts a stack does it always put all the frames back on the real JS stack in restore mode? Or does it sometimes not put some frames back on the real JS stack and restart from other points deeper into it?

[jpolitz]

CC @blerner

[jpolitz]

OK, so we've got this example:

// stopify-compile.js
const stopify = require('@stopify/stopify');
const fs = require("fs");

let input = process.argv[2]; 
let output = process.argv[3];

let content = fs.readFileSync(input);

let wrapped = "(function(require, exports, module) {" + content + "})(require, exports, module);";

// console.log("WRAPPED:", wrapped);
let opts = {
  // compileFunction: false,
  // getters: false,
  // debug: false,
  captureMethod: "lazy",
  newMethod: "direct",
  // es: "sane",
  jsArgs: "faithful",
  // requireRuntime: false,
  // compileMode: "normal",
};

// We think stackSize and restoreFrames on this stopifyLocally have *no* effect
let runner = stopify.stopifyLocally("(function() {})();", opts, { stackSize: 30, restoreFrames: 10 });

if(output === undefined) {
  // NOTE THE NEXT 3 LINES! Nothing seems to actually initialize these fields (newRTS sets them to infinity)
  const rts = stopify.newRTS('lazy');
  rts.stackSize = 30;
  rts.restoreFrames = 10;
  rts.remainingStack = 30;

  runner.g = { console };

  const start = eval(runner.compile(wrapped));

  runner.eventMode = 0;

  runner.continuationsRTS.runtime(start, result => {
    console.log(result);
  });
}
else {
  fs.writeFileSync(output, runner.compile(wrapped));

}

// deeprec.js
function f(n) {
  if(n <= 1) { return n; }
  else { return n + f(n - 1); }
}

console.log(f(100000));

→ node stopify-compile.js deeprec.js
5000050000
{ type: 'normal', value: undefined }

If we remove those three lines that configure the RTS manually, we get a stack overflow.

Is this all working and it's just that the options weren't propagated correctly from the runner to the runtime?