Threading in JavaScript 1.7

Amongst the many new features contained in Firefox 2 you’ll find JavaScript 1.7 support, a small but significant language enhancement that includes python style generators.

A generator allows you to suspend a function’s execution and resume it at a later time. While typically used for advanced looping constructs, a generator can also be flipped inside-out and used as a rudimentary coroutine.

At first glance, this may not look very impressive, especially since generators are unable to yield across multiple frames in the callstack. However, with the help of a technique called trampolining generators can be used to write code in a style similar to threaded programming.

The way trampolining works is that a scheduler object (written in JavaScript) manages the execution of a series of generators, cobbling together a stack-like execution. Here’s how it works: The scheduler sets the starting generator as the base “frame” in the call stack. The scheduler then calls next() on the generator to obtain a yield value. If the yielded value is itself a generator, the scheduler pushes this new generator on the stack and calls next() on it, again obtaining a yield value. This continues until the top generator yields a non-generator value. This value could be a special directive to the scheduler (for example, a SUSPEND value that tells the scheduler to freeze execution of the “stack” of generators we’ve piled up). If not, the scheduler treats it as a return value. The scheduler then pops and closes the now complete generator and sends the return value back into the next generator in the stack.

Sound confusing? It’s a mind-bender — I had to read a trampolining description and its sample code a few times before I understood how it works.

The coding style when trampolining is a little awkward. You need to yield any function call that will suspend execution of the stack. Here’s a contrived example:

  function myThreadedCall() {
     while (!ready) {
       yield sleep(100);
     }
     yield waitForInput();
     if ((yield post(getInput())) != null ) {
       yield animateUI();
     }
   }

In this way, using generators to trampoline is a very explicit form of concurrency. It’s verbose (unlike, say, Lua-style coroutines), but that verbosity has the upside of execution clarity — it’s much easier to see on visual inspection where race conditions can occur.

(Those of you with sharp eyes will notice that the technique described here is not true threading, but fancy coroutines. That’s the underlying implementation; to the programmer using this technique, it looks a lot like threading.)

No discussion like this would be complete without a pointless example, and this post is no exception. Check out this example (only works in Firefox 2), along with the example source and the threading library.

The use of generators and trampoling isn’t a panacea for concurrency in JavaScript. The technique renders code essentially “stackless” as far as the JavaScript interpreter is concerned, which means that you won’t get a meaningful stack trace if an error occurs. Thus debugging can be a bit painful.

However, it’s worth noting that the trampolining Thread.js is a slim 4K (uncompressed). And there’s no pre-compilation, no parsing, no AST manipulation, and no code generation. Simple. That’s the benefit of native language features.

All in all, I wish JavaScript had a more directly supported concurrency mechanism. I raised the topic on the ES4/JavaScript 2 discussion list, but in the end it was decided that the inability to yield through native C stack frames at the implementation level made it infeasible for some embeddings (such as cell phones and other devices). We’ll see what happens in later versions. (Brendan Eich has hinted that JS3 will be ready for multicore desktops.)

23 thoughts on “Threading in JavaScript 1.7

  1. Chris says:

    What’s “this._stack.pop().close()”? I don’t see where you define close(), so I assume “this._stack.pop()” is of a predefined class. The only close() I know of is in Window and Google doesn’t find another.

  2. Chris says:

    Scratch that. For the reader’s benefit, it’s Generator.close() (http://developer.mozilla.org/en/docs/New_in_JavaScript_1.7#Closing_a_generator)

  3. Michael says:

    Thanks for your nice post! Keep it up

  4. Yoric says:

    I raised the topic on the ES4/JavaScript 2 discussion list, but in the end it was decided that the inability to yield through native C stack frames at the implementation level made it infeasible for some embeddings (such as cell phones and other devices). We’ll see what happens in later versions. (Brendan Eich has hinted that JS3 will be ready for multicore desktops.)

    It was hinted to me that concurrency is in the program for JS2, but at a later stage.

  5. [...] Graveley has built Er.js, a library that “piggybacks on Neil Mix’s Thread.js which fakes threading in JavaScript 1.7 using coroutines and nested generator continuations. The [...]

  6. Tom Trenka says:

    Yikes!

    @Chris: it’s the damnedest thing; every time I think references to f(m) are dead, someone like you pops up with a link to it =) Bottom line on that one is that that code has nothing to do with Internet Explorer; it’s pure Javascript and can be run in any browser (including NN4).

    Though I’m not releasing that code any more, and haven’t since 2005 or so.

    You can find a version of it in the Dojo Toolkit (in the DojoX project, look under /timing).

    regards,
    trt

  7. [...] Graveley has built Er.js, a library that “piggybacks on Neil Mix’s Thread.js which fakes threading in JavaScript 1.7 using coroutines and nested generator continuations. The [...]

  8. [...] Neil Mix » Blog Archive » Threading in JavaScript 1.7 (tags: javascript programming concurrency threading generators thread concurrent advanced web development webdev) [...]

  9. sajeev says:

    can this thread library work with IE……..please reply

  10. [...] is largely linear? It’s pretty pointless at the moment, I suppose. But with the advent of multithreaded Javascript, there might be some value in controlling code execution this [...]

  11. Is it work with Internet Explorer 7 ?

  12. Matt S says:

    I’m really sorry to ask for clarification on this – I wrote an algorithm that creates an rtf javascript editor in a web page. The editor works flawlessly when the javascript file unminified is < 1000 lines. The work around I found for parsing large scripts was to setinterval and time my execution. If it took too long I’d set an interval to release the thread and reenter such that the browser wouldn’t display the unresponsive script error.

    Are you saying this threading code will unlock the HTML ui layer and allow background processing to occur? If what you say is true, and the previous comment about ie supporting a variant of this is true, you could have just rocked my world – let me know.

    M

  13. Neil says:

    @Matt: yes, a suspended generator unlocks the interpreter for other script processing. However, AFAIK there’s no generator support in IE as of IE8 beta 2. Who knows what the future will bring.

  14. [...] [toolness.com] and Client APIs [wiki.mozilla.org]. Also, Weave is written with a pattern called Trampolining Generators [neilmix.com]. This basically lets you use asynchronous calls synchronously and get something more [...]

  15. NYWebTeam says:

    Thanks for the tip.
    F.

  16. Guido Naudts says:

    Hallo,
    trying to understand Thread.js I added an alert:
    retval = this._stack[this._stack.length-1][method](arg);
    alert(“retval= ” + [retval]);

    in order to see the return values.
    The system goes into an infinite loop, but that seems normal.
    The first return value I recieve however is:
    [object Generator]
    I absolutely fail to understand where this comes from.
    Got any ideas?
    With kind regards,

  17. Neil says:

    @Guido: that’s how generator functions work. You call them, and they return a generator object which encapsulates the function state. See more about them here: https://developer.mozilla.org/en/New_in_javascript_1.7#Generators_and_iterators

  18. iresha says:

    javascript multi-threading doesn’t have to be a pointless exercise. Here is a fantastic example.

    http://codediaries.blogspot.com/2009/12/real-javascript-multithreading-using.html

  19. [...] clever usage of generator functions (the yield keyword). From things like speeding up your UI, to implementing thread pools, or computing prime numbers and infinite sequences, they’re always interesting. Last week, [...]

  20. [...] Javascript1.7版有一个非常类似Python生成器(generator)的特性;而类似Lua协程风格的变体在经过长期讨论以后被拒绝(参考http://www.neilmix.com/2007/02/07/threading-in-javascript-17/ ) [...]

Comments are closed.