How do we kick our synchronous addiction?
eflorenzano.com
eflorenzano.com
In our network-connected, cpu-is-millions-of-times-faster-than-disk world, asynchronous programming is really important for building a responsive desktop application.
One of our engineers blogged about the task system at http://thespeedbump.livejournal.com/63798.html and http://thespeedbump.livejournal.com/64053.html
The source is available at http://imvu.svn.sourceforge.net/viewvc/imvu/imvu_open_source...
def handleBlogPostRequest(request, response, postSlug):
db = yield DBClient()
post = yield getBlogPost(postSlug)
comments = yield db.getComments(post.id)
html = template.render('blog/post.html',
{'post': post, 'comments': comments});
response.write(html)
response.close()
http://www.imvu.com/jobs/index_eng.php
chad@imvu.com
Well, yes, but really no. Within a single process, everything is synchronous. Deployments in the real world are asynchronous via use of multiple processes, shared nothing architecture, and a few forms of interprocess communication. (The database is pretty common, though I guess that means shared-something. Let MySQL programmers deal with the semaphores. I can't even spell semaphore and I've got customers to satisfy.)
In real deployment scenarios, you can achieve I-can't-believe-its-not-asynchronous-processing by layering the same programming techniques and battle-tested, well-supported libraries you already use.
One hacky solution which works well in practice: give the browser as much as you can, have it AJAX poll for anything you don't have ready. In practice, since page rendering is Very Effing Slow relative to many other things you want to do, this increases user perception of speed considerably.
For example, hypothetically say you want to do a word count on 47 blogs and display that to the user (I don't know why you would want to do this, but it looks like his example). No problem. Check your cache for any of the blogs you've already calculated and spit that right into the response HTML. Have the browser poll you for the rest of them via AJAX. Meanwhile, you kick off the HTTP access and subsequent word count operation to any arbitrary number of worker processes, and after you're done with them, write them to the cache (or db, etc).
One of the more confusing things that I've experienced recently is that some programmers get a little fuzzy when you ask if an HTTP request is synchronous. That is, is the body of an HTTP response considered synchronous communication with the client. In my view of the system, HTTP (sans keep-alive) supports a single synchronous message and response, whereas some people try to assert that the response happens after the completion of the request is sent, so the communication is actually asynchronous.
From that point of view, I can see how the terminology is vague. However, if we are talking about program control flow and say that blocking on a function call is synchronous and various other forms of deferred evaluation are asynchronous, then the HTTP lifecycle starts to fit the "synchronous" model more closely (note that I'm not talking about http client libraries here.)
Anyway, this does lead into one of my favorite interview questions: "Is JavaScript multithreaded?" Many people get hung up on AJAX and setTimeout... but these are the same people that don't really get the tech at a fundamental level.
On the server side, the merit of asynchronous processing depends on the goal. I'm quite happy to spin up multiple processes and have each process synchronous process a single request on the server - my time is too valuable to debug the alternatives at the moment.
I'm quite happy to admit that my HTTP requests are processed synchronously by Apache, mod_python and django. Even the out-of-band requests from ajax also tend to be synchronously processed. On my power dashboard, I handle ongoing comms using Twisted and totally asynchronously - pushing data to the user through Orbited. This gives our system an extremely fast response rate.
Event loop driven code is the key to decent firmware performance. It is how we ensured that the responsiveness our our hardware solutions in the past (such as the Kiddie Kart) was very good.
http://paultyma.blogspot.com/2008/03/writing-java-multithrea...
I've written a fair amount of asynchronous network code in my time, and it really is more difficult to write and debug - developers are generally used to being able to see a linear flow in their code. Event driven code in general IMO is much harder to follow and reason about than linear code. In my current project we have a fully asynchronous multiplexing network component - I'm about to replace it with a simpler, synchronous model because both the client code and the code of the component itself will be much simpler. Even if I take a performance hit the easier maintenance and fewer bugs will be worth it.
http://www.springerlink.com/content/dk7n7mbjx7blbelj/ http://moscova.inria.fr/~xleroy/publi/cps-dargaye-leroy.pdf http://muaddibspace.blogspot.com/2009/02/cps-transformation-...
There is data tying the whole program together: the continuation, which is a closure.
Assuming a bastardised version of Python with C#-style lambdas, so that () => {} is a function taking no arguments and that has no statements in its body, and result => {} is a function taking a single argument, etc:
Direct form:
def A(x):
x = B(x)
C(x)
def B(x):
factor = SyncCall()
return x * factor
def A(x,continuation):
B(x, result => {
x = result
C(x,continuation)
})
def B(x,continuation):
AsyncCall(result => {
factor = result
continuation(x * factor)
})
Key things in CPS:
* Method calls aren't actually method calls; they are jumps with arguments. There is no call stack - the return location is itself passed to the method you're calling
* This means that the stack is implied in the variables that the continuation closures capture. So, the caller of A, where it has to return to when it's done, is stored in the "continuation" argument; and that location needs to be captured such that it is part of the state of the closure passed to B, so that it can ultimately be passed to C.
* Since the stack is stored implicitly in the closure, it is simple for the implementation of AsyncCall to initiate the I/O, stuff the return location (the last argument, "continuation" I've called it above) away such that it can be retrieved when the I/O completes, and then go off and do some other productive work - such as check for completed I/Os and call their continuations.
If you have green threads, the state for the continuation is implicitly part of the stack, only with green threads, you own the data that forms the stack, and can reliably do interesting things with it. The stack itself is a kind of argument that gets implicitly passed around in imperative programs, e.g. it is passed in the ESP register on x86. The top of the stack contains the continuation pointer; and 'RET' is the jump instruction which jumps to the continuation. But using the stack for an implied kind of CPS limits some of the other things you can do with continuations, as it enforces a contiguous linear flow, rather than what you can do with call/cc etc. when the closure data that's part of the continuation is stored on the heap instead.
@defer.inlineCallbacks
def A(x):
x = yield B(x)
C(x)
@defer.inlineCallbacks
def B(x):
factor = yield AsyncCall()
defer.returnValue(x * factor)In twisted, all code in normal functions is executed atomically, and code in @inlineCallbacks functions is only interrupted at yield statements. If any random function could release control to the scheduler without notice to its callers, certain classes of bug would require digging through all of the callee's code to figure out what's going on. I rely on that atomicity far more often than I change a function from nonblocking to blocking, so in my case, the tradeoff is a favorable one.
Also, if you don't care about the response, there's no fiddling necessary. Just call the function and drop the result; the operation will still happen at the right time, and the result will get dropped on the floor, just as you expected.
[EDIT: changed "blocking" to "atomic", since that's what I'm really talking about.]
For example, consider switching between a non-blocking in-memory DB (perhaps flushed in a background thread) and communicating with a database across the network. Why would a module communicating with such a DB need to advertise in its contract which DB it is communicating with?
The point being, a context switch can still occur at any moment, so it's not you get the kind of atomicity you seem to be aiming for in general, unless you are operating in a shared-nothing single-threaded environment.
Saying that all functions are non-atomic is certainly a reasonable policy, and one that is used in many situations. Personally, I find it more convenient to program in an environment that does have this distinction. Apparently, your tastes are different than mine.
In a multithreaded world, synchronous code storing its state on the stack, and asynchronous code derived from a CPS transform of direct style (thus storing its state in continuations), seem equivalent for the purposes of "atomicity"; since the OS scheduler can come in and reschedule the synchronous thread at any point (and will definitely context switch if the thread blocks), it seems no different to the CPS transformed case (OS may choose to context switch at any time).
Things like mutex locks do work differently in the CPS case, but it's rather that they are asynchronous too: blocking on a mutex means handing the continuation off to the mutex to continue when it's available to be acquired. And things like thread-local storage work differently - the logical thread of control may change physical threads in the CPS async case, but a runtime or compiler (which will be aware of the CPS transformation) can abstract this away.
So, what do you mean by "atomic"?
Because I can do so much without having to worry about other threads of execution seeing my internal state, I rarely have to bother with locks at all, even when dealing with globals. I'm not using threads at all; if I need to take advantage of multiple CPUs, I run multiple distinct processes.
[Edit: clarifying single-threaded]
From the "inside", a thread of execution, and a CPS-transformed chain of continuation calls (originally written in direct style), "feel" exactly the same - precisely because there is a mechanical translation from one to the other with no loss in semantics.
Here's what I suspect you're trying to get at: you're coming from a single-threaded perspective, where Twisted's partially-automated CPS transform is in effect emulating green threads under a cooperative scheduling model, where the "yield" represents yielding control of the current "thread" to potentially other "threads". Your concern over fully automating the transform is because it may introduce further cooperative threading "yield"s that you cannot control.
My point is that under a preemptively threaded environment, any thread could at any time hijack the CPU and mutate your state - and this is no different whether the code is synchronous or CPS-transformed. A "yield" may occur randomly at any point in your code. Hence, the requirement to annotate methods to permit CPS transformation on preemptively multithreaded direct code is a chore; the extra information in the contract doesn't have semantic value, in the same way as it does for the cooperatively-scheduled Twisted approach.
Yes, that's exactly the case. To scale to multiple CPUs, I use distinct processes, not threads. Shared memory and preemptive execution require a lot of programming effort to play nicely together that I don't care to expend.
The GIL in python means that threads generally won't ever let you use more than a single CPU anyway.
Functional languages are also frequently implemented using CPS as an intermediate form.
Smalltalk also supports continuations, as I understand it; the Seaside framework for Smalltalk is a server implementation oriented towards continuations, though I think they use it for picking up where you left off in between multiple request/responses, not necessarily for I/O optimization. I could be mistaken.
F# has a feature it calls async workflows; I haven't delved into it much, but it looks like it's trying to make writing async code as close to direct style code as possible. But the full benefit comes from the compiler being able to rewrite all functions on the call chain between you and the function that performs the I/O, so I suspect it may be limited. Ideally, the CLR itself would support CPS transformation into its Begin/End-style async support, like I advocate here:
http://blog.barrkel.com/2006/07/fun-with-asynchronous-method...
(I've been banging on this drum quietly for some time now...)
I've heard the second and third editions had some of that material cut (too advanced?) - I don't know if that's true, but the first edition is typically much cheaper. FWIW.
If you look at Erlang (which the article mentions), I don't feel like I ever do the kind of Async programming he talks about here. I break the work flow into a pipeline of processes that do a specific job. I never have a process send a message to another process and waits for the answer. Every process receives some message, does it's job and then forwards the resulting message to another process.
I guess I just find this style of coding easier to reason about because every part of the pipeline is completely stateless and has a straightforward job.
http://code.naeseth.com/swirl/
However, if your async call actually happens somewhere in a library function, you have to yield also calling that function - it's not transparent for the caller whether the library function is synchronous or not.
Your scheduler may be as simple as a bunch of threads using work-stealing queues to grab jobs; a job is scheduled by adding it to a queue.
With asynchronous programming, it's fairly constant. You have to think about things as you go, and once you get the hang of it, there are little surprises.
With synchronous programming you have the illusion that it is easier - fork() ! magic!. So you can get a lot done quickly. But then you have the realization that as things get more complex, you'll have to deal with locking,concurrency,scaling issues, etc. But by that time it may be too late to change architecture.
It's probably best though for programmers to work on a big synchronous system, realize just how much code you're writing to cope with the fact you asked the OS to execute your code in random order, and then hopefully realize that telling the OS to execute your code in an explicit order is probably a better idea.
>> If we look at Django or Ruby on Rails, arguably the two most promising new web application frameworks to emerge in the past few years
I'd also disagree with that. They're probably the most hyped up, but that's something entirely different. Once again, likely lazy programmers who want a framework for this, a framework for that. How about just make your own framework.
== Sync ==
Thread 1: Do A -> block -> Do B Thread 2: Do C -> block -> Do D
eg Tell the OS to execute your code in random order, then build a ton of code to cope with that.
== async ==
while(true) { // do some of A, or if that's complete, do some of B // do some of C, or if that's complete, do some of D }
Personally, if I have a DAG of tasks to do, I prefer to encode that DAG in the structure of my code by breaking independent chains into separate tasks/threads/whatever and feeding that to some piece of software to do the scheduling for me, rather than roll my own scheduling in a potentially bug-prone and unscalable way. For the example shown, either is perfectly fine, but if you have hundreds of outstanding jobs with a more complex dependence structure, I'd rather not deal with scheduling myself.
The E language takes the different approach of supporting event-loop concurrency with built-in syntax (eventual sends and when-catch):
@defer.inlineCallbacks # Python2.5 and up
def login_and_do_something(args):
server = yield factory.login(username, password)
rval = yield server.callRemote(args))
print rval
Admittedly, they're talking about different kinds of "support": it's harder to do asynchronous programming in a lot of languages, but it's even harder than that to do synchronous programming efficiently, because the toolchains don't support the optimizations that would be necessary (but which you can do by hand in an asynchronous programming style).
Unfortunately, our current model has threading a bit like a bull in a China shop as it creates a whole host of concurrency problems in anything more complex than a trivial example. The 'select' call is a reasonable half-measure, as your 'read' call is non-blocking when you get to it.
I question the threading model, as it definitely has problems, but in terms of having multiple tasks, and an event loop, and scheduling those tasks, the operating system already has that, should we really re-implement it?
Ideally your task scheduling framework will have as many threads as the machine has processors, and will use e.g. work-stealing queues to dispatch work without needing a kernel transition that a thread or process context switch would require. But if every running process implements its own task scheduling framework, and creates as many threads as there are processors, there will be too many threads running around. The OS needs to help out with balancing the load.
Or maybe I'm getting this wrong.
Also, Lua doesn't have macros, at least not in the sense that Lisp and Prolog do. It just has eval.
Macros and coroutines don't solve the same problem here. Macros provide wrappers that make "callbacks" implicit; coroutines provide scheduling.
>Also, Lua doesn't have macros, at least not in the sense that Lisp and Prolog do. It just has eval.
I object!
I haven't done that much with Metalua - I don't really feel that Lua's lacking macros is a major problem, really, though I like the author's views on metaprogramming ("Make it obvious when something interesting happens", etc.). I remember looking at it a year or so ago, but didn't get into it.
I just gave it a quick stab at porting, and I remember why - "Prerequisites - a 32 bits, little endian CPU" - I tend to switch back and forth between a couple OSs and hardware platforms, and Lua's portability is a big bonus for me. Adding a couple ML-ish features to Lua would be tempting, though.
There's a patch by Mike Pall to add coroutine copying for simulating multi-shot continuations, though.
Javascript is my favorite language right now.
Mozilla.org has some wikipages related to JavaScript, but there is no offline documentation (I was able to find a request for an offline version from a few years ago, but the response was "we don't have the resources right now, but we will at a later point in time unless you want to do it right now").
{edit} Here's what I'm talking about:
* "Javascript Core Guide" and "Javascript Core Reference." Both are marked as published back in 2000. http://devedge-temp.mozilla.org/library/manuals/
* Wikipages:
- https://developer.mozilla.org/en/Core_JavaScript_1.5_Guide
- https://developer.mozilla.org/en/Core_JavaScript_1.5_Referen...
So you can look at updated docs, but you don't have any offline docs... One would think that it would be somewhat trivial since they are wiki pages.
Since he wrote that, he's also come out with his own book, JavaScript: The Good Parts.
Disclaimer, I have not read either book, but I highly recommend his website: http://www.crockford.com
Seriously, this is an almost solved problem. You don't have to deal with threads explicitly.
I have seen a huge uptake of clojure, scala, haskell and F# recently (and possibly ocaml, I haven't been watching, and possibly common lisp and scheme, too)
http://en.wikipedia.org/wiki/Communicating_sequential_proces...
described in 1978 by C.A.R. Haore in the now eBook http://www.usingcsp.com/