Introducing Esperanza
Jasvir Nagra
In thinking about how to address some of the performance penalties of
caja, the following ideas arose from an initial conversation between
Mark Miller, Kevin Brown and Louis Ryan. These are useful to wider
javascript community but work especially well for programs written in
caja.
- javascript programs often execute only a very small portion of the
javascript that is downloaded. Increasingly entire libraries are
included by a gadget even if only a small number of functions from
that library are used. Even in cases where more of the library is
used, the fraction of the javascript required to initially render a
gadget is small compared to the download. It would be useful if there
was a way to reduce the size of the download required to start
executing javascript and to prioritize the remaining download.
Solution: Esperanza
* instrument javascript to give information about what "parts" of a
program are executed regularly
* regularly executed code is the initial piece that is downloaded,
with the remaining pieces replaced with stubs
+ for example, all of the code before the first user event is
received by a cajoled program can be part of the original download
* an asynchronous xhr process downloads and patches in the missing
pieces of code
* if a fault occurs, the remaining chunk is downloaded (perhaps in
large pieces) via a synchronous xhr
+ depending on how we architecture the remaining download, this may
be at most one additional round trip
* instrumentation decides the first guess of what is served initially.
The container (or indeed the esperanza server) may either statically
or dynamically override this choice. This is especially useful when
feedback from one batch of users informs the partitioning for
remaining users.
While there are several ways of achieving this that have been tried
(including Microsoft's Deloto
http://research.microsoft.com/projects/doloto/ and Razorspeed
http://razorspeed.com/), by restricting our input to the lexically
analyzable subset of JavaScript (ES3.1-strict), we can eval() the stub
replacement just once per stub source rather than once per stub
instantiation. (To be explained in a later message.) The caja parser
also makes it simpler to perform the analysis, rewriting and
interception needed to do both the instrumentation and the actual
implementation.
Pieces of the puzzle:
* requires a cajoling server that returns cajoled functions of a
program as they are requested
* requires new stages in the cajoling pipeline to stub out a program
* requires a cleverly named godlike function on the client side to
replace stubbed functions with real ones
Regards
Jasvir
Mark S. Miller
// Copyright (C) 2008 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
/**
* @fileoverview
* The Glaroon is the component of Esperanza that creates stub
* functions that fault on invocation (or <tt>toString</tt>) to
* download and patch in the real function. The sketch shown here is
* of a translation from nested functions to a list of strings
* containing sources of non-nested <i>maker</i> functions. For
* example, in the original code below, a new instance of
* <tt>incr</tt> is created each time <tt>newCounter</tt> is
* called. All share the code of <tt>incr</tt>, but each captures a
* distinct <tt>count</tt> variable. We translate the nested
* <tt>incr</tt> to the separately evaluable source for a non-nested
* <tt>make_incr___</tt>. Thus, once any one <tt>incr</tt> stub faults
* in <tt>make_incr___</tt>, all the other <tt>incr</tt> stubs can
* just call it to make the real <tt>incr</tt> that they then delegate
* to. Once <tt>make_incr___</tt> has been faulted in, any further
* calls to <tt>newCounter</tt> will make real <tt>incr</tt>s
* directly, with no intervening stub.
* <p>
* The sketch here uses the simplest possible fault handler, which
* assumes the <tt>makers___</tt> starts fully populated, in which case
* Esperanza would be pointless. Unshown is the harder work:
* accumulating fault-order statistics, and then splitting the
* populating of this array into the parts that happen early vs later
* or on demand. However, all these differences (including the
* fault-order intrumentation and reporting) are expressed in a more
* complex fault-handler, but using the same glaroon.
* <p>
* The <i>Glaroon</i> originally appeared in the Robert Heinlein short
* story "They", and then briefly reappeared in Heinlein's novel "Job:
* A Comedy of Justice". He was a god that almost perfectly
* orchestrated the on-demand construction of a world, in order to
* fool that world's one sentient inhabitant into thinking that this
* world already exists and functions independently of his
* observations.
* <p>
* From <pre>
* function newCounter(count) {
* function incr() { return count++; }
* function decr() { return count--; }
* incr();
* return [incr, decr];
* }
* </pre> to <pre>
* // Declare all top level declared variables
* var newCounter;
*
* (function(){
* // For the ith original function, initialize makers___[i] with
* // the source to a translated maker for making instances of
* // that function. The maker's parameters represent the
* // lexical variable captures of the original function. When a
* // non-global variable is shared
* // and mutated, then its capture is a Slot object whose v
* // property represents that variable. Otherwise, the variable's
* // capture can just be the current value of the variable.
* var makers___ = [
* 'function make_newCounter___() {
* function newCounter(count) {
* var countSlot___ = {v: count};
* var incr = makeFunc___(1, [countSlot___]);
* var decr = makeFunc___(2, [countSlot___]);
* // incr() would also work, but will be slower if incr is
* // a stub.
* (true && incr.REALME___)();
* return [incr, decr];
* }
* return newCounter;
* }',
* 'function make_incr___(countSlot___) {
* function incr() { countSlot___.v++; }
* return incr;
* }',
* 'function make_decr___(countSlot___) {
* function decr() { countSlot___.v--; }
* return decr;
* }'
* ];
* var makeFunc___ = glaroon___(
* makers___,
* // The simplest faultHandler, which assumes that all sources
* // are already locally available. Note that the eval is done
* // in the scope containing this module's makeFunc___.
* function(i___) { makers___[i___] = eval(makers___[i___]); });
*
* // Translating the original's top level as if it were a
* // function body
* newCounter = makeFunc___(0, []);
*
* }).call(this);
* </pre>
*
* Known non-transparencies<ul>
* <li>We disallow <tt>with</tt>, <tt>delete <i>identifier</i></tt>,
* and <tt>eval</tt>, since they prevent lexical scope
* analysis. All these are prohibited by caja as well. The first
* two are also prohibited in ES3.1-strict. ES3.1-strict
* restricts <tt>eval</tt> so that it doesn't disrupt lexical
* scope analysis, but supporting <tt>eval</tt> would require a
* client-side Esperanza translator.
* <li>The <tt>length</tt> of the stub will not be the length of the
* original. We could partially fix this by provide pre-made stubs
* for the first N arities.
* <li>Non-standard reflective access to the call chain, such as
* Function.prototype.caller. These are also prohibited by
* ES3.1-strict (which is quite a trick, since they are not
* otherwise specified).
* <li>Certain variables ending in "___". This constraint is already
* enforced by Caja. The cajoler does emit names ending in "___",
* but none of these conflict with the names reserved by
* Esperanza.
* </ul>
*
* @author Mark S. Miller eri...@gmail.com
*/
function glaroon___(makers, faultHandler) {
function makeFunc(i, captures) {
if (typeof makers[i] === 'function') {
return makers[i].apply(USELESS, captures);
}
function stub(var_args) {
touch();
return stub.REALME___.apply(this, arguments);
}
stub.REALME___ = stub;
stub.toString = function() {
touch();
return stub.REALME___.toString.apply(stub.REALME___, arguments);
}
function touch() {
if (stub.REALME___ === stub) {
if (typeof makers[i] !== 'function') {
faultHandler(i);
}
stub.REALME___ = makers[i].apply(USELESS, captures);
}
}
return stub;
}
return makeFunc;
}
Mark S. Miller
In thinking about how to address some of the performance penalties of
caja, the following ideas arose from an initial conversation between
Mark Miller, Kevin Brown and Louis Ryan. These are useful to wider
javascript community but work especially well for programs written in
caja.
--
Cheers,
--MarkM
Mark Miller
transformations needed for Esperanza and those explained at
<http://google-caja.googlecode.com/svn/trunk/doc/html/cajitaOptimization/index.html>.
We have not yet explored this issue.