Runtime System¶
Runtime Configuration¶
The Stopify runtime system takes a dictionary of options with the following type:
interface RuntimeOpts {
estimator?: "velocity" | "reservoir" | "exact" | "countdown" | "interrupt",
yieldInterval?: number /* must be greater than zero */,
stackSize?: number /* must be greater than zero */
restoreFrames?: number /* must be greater than zero */
}
The first two options control how frequently Stopify yields control to the
browser (yieldInterval
) and the mechanism that it uses to determine elapsed
time (estimator
). The last two options can be used to simulate a larger
stack than what JavaScript natively provides.
Time estimator (.estimator
)¶
By default, Stopify uses the velocity
estimator that samples the current
time (using Date.now()
) and tries to yield every 100 milliseconds. The
velocity
estimator dynamically measures the achieved yield interval and
adapts how frequently it yields accordingly. This mechanism is inexact, but
performs well. You can adjust the yield interval, but we do not recommend using
a value lower than 100.
The reservoir
estimator samples the current time using reservoir sampling
(i.e., the probability of resampling the current time decreases as the program
runs longer). This technique is less robust than velocity
to fluctuations
in program behavior, but still outperforms other methods. This usually has a
lower runtime overhead than velocity
, but sacrifices accuracy. We recommend
velocity
for a more general, nondeterministic estimator.
The countdown
estimator yields after exactly n yield points have passed.
With this estimator, the yieldInterval
is interpreted as the value of $n$
and not a duration. We do not recommend using this estimator in practice, since
a good value of $n$ will depend on platform performance and program
characteristics that are very hard to predict. However, it is useful for
reproducing bugs in Stopify, since the velocity
estimator is
nondeterministic.
The interrupt
estimator is a Node.js-only implementation which
initializes a timer as a C++ extension to Node.js. With this estimator, a
JavaScript Buffer
object is signaled from C++ whenever a
yieldInterval
milliseconds has elapsed from the timer. This estimator is
only supported in Node.js (it depends on native code), but experiments have
shown that it implements the most precise estimation technique, with the
smallest overhead in this environment.
Finally, the exact
estimator checks the current time at every yield point,
instead of sampling the time. This has a higher runtime overhead than
velocity
and we do not recommend it.
Unbounded stacks (.stackSize
and .restoreFrames
)¶
On certain browsers, the JavaScript stack is very shallow. This is a problem for programming languages that rely heavily on recursion (e.g., idiomatic functional code). If this is not a concern, you can ignore these options.
To support heavily recursion code, Stopify can spill stack frames on to the
heap. Therefore, a program will never throw a stack overflow error (however,
it may run out of memory). To do so, it tracks the depth of the JavaScript
stack and spills stack frames when the stack depth exceeds stackSize
.
Similarly, when resuming computation, the restoreFrames
parameter
determines how many saved stack frames are turned into JavaScript stack frames.
To maximize performance, stackSize
should be as high as possible and
restoreFrames
should be equal to stackSize
. The largest possible value
of stackSize
depends on the source language and browser. In our experience,
a value of 500 works well.
The AsyncRun
Interface¶
interface NormalResult {
type: 'normal';
value: any;
}
interface ExceptionResult {
type: 'exception';
value: any;
stack: string[]
};
type Result = NormalResult | ExceptionResult;
interface AsyncRun {
run(onDone: (result: Result) => void,
onYield?: () => void,
onBreakpoint?: (line: number) => void): void;
pause(onPaused: (line?: number) => void): void;
resume(): void;
setBreakpoints(line: number[]): void;
step(onStep: (line: number) => void): void;
pauseImmediate(callback: () => void): void;
continueImmediate(result: Result): void;
processEvent(body: () => any, receiver: (x: Result) => void): void;
}
The AsyncRun
interface provides methods to run, stop, and control the
execution of a stopified program. The interface provides several methods, none
of which should be used directly by the stopified program. The following
methods are meant to be used by the driver program that controls execution
(e.g., a web-based IDE):
- The
run
method starts execution and requires a callback that gets invokes when execution completes. You may provide optional callbacks that are invoked when the program yields control and when a breakpoint is reached. - The
setBreakpoint
method sets the active breakpoints. - The
pause
method pauses the program at the next yield point and requires an optional callback that is invoked when the program has paused. - The
resume
method resumes execution after a pause. - The
step
method resumes execution and pauses again at the next yield point.
The following methods are are meant to be used by non-blocking JavaScript functions to provide simulated blocking interface to the stopified program:
- The
pauseImmediate
method suspends the stopified program and invokes the provided callback. A function should not execute anything after invokingpauseImmediate
. Typically, a function that usespauseImmediate
will use it in areturn
statement. - The
continueImmediate
function resumes execution with the provided value.
Illustrative Examples has several examples that use these methods to implement simulated blocking operations.
Finally, the processEvent(f, onDone)
method allows external event-handlers
to call a stopified function f
. Since f
may pause execution and thus
not return immediately, Stopify passes its result to the onDone
callback,
which must not be a stopified function.