fext.js
Fast explicit tail calls in JavaScript [live page] [Node.js package]
Classically, tail calls are automatically optimized (LISP...) . In JavaScript, programmers may well not know which "return" statements are optimized by the engine, and which not. This would lead to practical issues when debugging/optimizing (2009).
As of 2018, progress is "slow" and the Chrome team has already removed the automatic self-recursion optimization from its JavaScript engine.
Another possibility is to explicitly mark the tail calls that will be optimized. Several JavaScript extensions were proposed that add new keywords to the language (2013, 2016).
It turns out that we can do this with today's JavaScript, without extending the language.
fext.js demonstrates this.
API
Two entry points:
mfun(...)
returns an optimized function,meth(...)
returns an optimized method.
Debugging
Just append a "D" character:
- turn
mfun()
intomfunD()
. - turn
mret()
intomretD()
.
...to turn off the optimizations. You can then use logging and breakpoints.
Getting started
Wrap the whole function with mfun(...)
and use return mret(<expr>)
to mark the tail calls to be optimized.
Self-recursion example:
Mutual recursion
var groupkey = {} // whatever object (won't be modified) isOdd = isEven = ;console; // true (no call stack issue)console; // false (no call stack issue)
groupkey
is only used as a key to determine "groups" of function that know each other.
You can conveniently omit groupkey
:
// The default `groupkey` is the returned function// `var isOdd` in this casevar isOdd = isEven = ;console; // true (no call stack issue)console; // false (no call stack issue)
Namespace alternative
In some situations the globals mfun
, meth
, mfunD
, etc. may feel
annoying. Solution: use the fext.*
namespace. Below, an example in
the Node.js context:
var fx = fext; var isOdd = fx isEven = fxconsole; // true ; no call stack issue
Shortcut
Note that fext === fext.mfun
as a shortcut for the simplest cases, especially in the Node.js context:
var fx = fext; var self_recursive_fun = ;
...and in the IE11 context, when relying one the fext
namespace, this gives easy access to arrow functions:
var sum_two = ;
Methods
Self-recursion example:
var o = gcd : ;console; // 15 (3*5)
No need for groupkey
here. Moreover, instead of:
use:
"methodname"
MUST be the name of the method,- The first parameter MUST be
that
, - Inside the method, you MUST use
that
(and notthis
). Reason:.bind()
slower in Firefox 60. - Use
that.
in themret
calls, as in:
return
or
return
The mret( that.<methodName> )
call syntax
- makes clear we are calling a method, not just a simple function,
- AND permits easy debugging through
methD
.
Methods: Mutual recursion example
var o = isOdd : isEven : ;console; // true (no call stack issue)console; // false (no call stack issue)
Prototype methods
Pretty much the same as above.
{}AprototypeisOdd = ;AprototypeisEven = ;var o = ;console; // true (no call stack issue)console; // false (no call stack issue)
Speed test
The higher, the better. 100.0 is the highest in each row, (2.6) is a standard deviation, and [9.34e8] is the absolute speed in iterations per second.
Browser | isOdd_mfun | isOdd_meth | isOdd_metaret | isOdd_tailtramp |
---|---|---|---|---|
Firefox 60 | 95.5 (2.6) | 100.0 (1.4) | 81.2 (0.2) | 0.1 (<0.1) |
[9.34e+8] | [9.78e+8] | [7.93e+8] | [1.25e+6] | |
---- | ---- | ---- | ---- | ---- |
Chromium 66 | 98.5 (0.3) | 100.0 (4.9) | 52.0 (0.1) | 0.7 (<0.1) |
[8.87e+8] | [9.00e+8] | [4.68e+8] | [6.12e+6] | |
---- | ---- | ---- | ---- | ---- |
Chrome 67 | 99.8 (0.8) | 100.0 (0.3) | 62.2 (0.2) | 0.8 (<0.1) |
[7.49e+8] | [7.51e+8] | [4.67e+8] | [6.18e+6] |
isOdd_mfun
andisOdd_meth
: Proposed "explicit" approach. Uses standard JavaScript.isOdd_metaret
Another "explicit" approach (2013). Extends JavaScript with new keywords.isOdd_tailtramp
: The fastest trampoline implementation that I could find.
For more details, explanations, and run this test in your browser, either open the live instance or open the ./index.html file here.
Browser support
Modern browsers, and IE11, as of June 2018.
Unit tests
Either in the browser (live instance) or in the command-line (e.g. Nashorn).
sortedSearch
An example: Code: lib/sorted_search.js
Tests: lib/sorted_search_unittest.js
The code in that example shows an issue when having to pass too many parameters around: the code contains 5 times the same list of parameters, as in the code excerpt:
var improveFirst = improveLast = ; { // ... return ; } { // ... return ;} { // ... return ;}
The straightforward answer to this issue would be to put all parameters in an object, but this leads to a performance degradation (see "Performance cost of passing parameters through an object" further below).
An alternative is to declare the parameters only once, use closure
and eval
so that the generated code has access to the parameters
through the closure.
For a complete example see:
Code: lib/sorted_search_closure.js
Tests: lib/sorted_search_closure_unittest.js
Excerpt:
// First "declare" all functions so that co-dependencies can be // solved. // // Use `mfunD` to debug var improveFirst = improveLast = ; // Now we can implement them, using evil access to the local // lexical scope so that we do not need to write parameters // repeatedly 5 times (see above `function sortedSearch(...)`). improveFirst = ; improveLast = ; var first_found last_found i j imax jmin ; var sortedArray x less equal; /* In a sorted array, search for first & last occurences of `x`. If `x` found, return `[ first_index, last_index ]` (integers). If `x` not found, return `null`. */ { // ... return ; } { // ... return ; } { // ... return ; }
Performance cost of passing parameters through an object
To measure the extra overhead of wrapping parameters inside an object, we use the isOdd/isEven case, since each function does very little in itself. First the results, then the detailed implementations.
Browser | isOdd_mfun | isOdd_mfun_obj | isOdd_mfun_obj_inplace |
---|---|---|---|
Firefox 60 | 89.0 (5.4) | 24.8 (1.6) | 19.3 (0.3) |
[8.02e+8] | [2.24e+8] | [1.74e+8] | |
---- | ---- | ---- | ---- |
Chromium 66 | 100.0 (2.3) | 47.9 (0.7) | 87.6 (0.8) |
[8.35e+8] | [4.00e+8] | [7.31e+8] |
Browser | isOdd_meth | isOdd_meth_obj | isOdd_meth_obj_inplace |
---|---|---|---|
Firefox 60 | 94.0 (2.1) | 26.3 (0.5) | 18.7 (0.5) |
[8.47e+8] | [2.37e+8] | [1.69e+8] | |
---- | ---- | ---- | ---- |
Chromium 66 | 99.2 (1.7) | 45.6 (0.2) | 87.9 (0.9) |
[8.28e+8] | [3.80e+8] | [7.34e+8] |
To obtain the best performance, it is preferable to pass parameters
separately: isOdd_mfun
and isOdd_meth
. If there are too many
parameters, one can use closure, see sortedSearchClosure
just
above.
*_obj
implementations:
For the full details, see the *_obj
functions in
test/fext_speedtest.js
Excerpt:
{ // The default `namespacekey` is the returned // function `var isOdd` in this case. var isOdd = isEven = ; // Sanity check ; var result = ; // <<< speedtest // Sanity check result === niter % 2 !== 0 || nullbug;} { // The default `namespacekey` is the returned // function `var isOdd` in this case. var isOdd = isEven = ; // Sanity check ; var result = ; // <<< speedtest // Sanity check result === niter % 2 !== 0 || nullbug;}