5 ms·

As an interesting counterpoint, Paul Tyma has a really excellent presentation on how NIO in Java actually allows considerably less throughput than thread-per-co

by lemming 17y ago

As an interesting counterpoint, Paul Tyma has a really excellent presentation on how NIO in Java actually allows considerably less throughput than thread-per-connection and has a much more complicated programming model: http://paultyma.blogspot.com/2008/03/writing-java-multithreaded-servers.html 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.

barrkel 17y ago
The annoying thing to me, as a guy who works on the compiler side of things, is that transformation of linear synchronous code to continuation-passing style (CPS) suitable for asynchronous code can be done mechanically by the compiler. There isn't a technical reason why it needs to be as hard as it is; lots of details to get right, especially when inter-operating with stack-oriented languages, etc., but in principle it's very possible.
- etherealG 17y ago
  how would you manage to figure out the order of execution for an arbitrary set of events firing when the program is defined as a direct linear series of operations? surely the paradigm is so vastly different that getting a compiler to figure it out would be impossible?
  - barrkel 17y ago
    CPS transformation is mechanical; don't take my word for it, there's plenty of documentation: http://www.springerlink.com/content/dk7n7mbjx7blbelj/ http://www.springerlink.com/content/dk7n7mbjx7blbelj/ http://moscova.inria.fr/~xleroy/publi/cps-dargaye-leroy.pdf http://moscova.inria.fr/~xleroy/publi/cps-dargaye-leroy.pdf http://muaddibspace.blogspot.com/2009/02/cps-transformation-using-delimited.html 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 CPS form: def A(x,continuation): B(x, result => { x = result C(x,continuation) }) def B(x,continuation): AsyncCall(result => { factor = result continuation(x * factor) }) Things are actually more complicated than they look here, you may need more than one continuation for things like exceptions etc., but hopefully you get the gist. 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.
    - etherealG 17y ago
      wow, that's really interesting. thanks. do you know of any production level languages that feature this kind of approach?
      - barrkel 17y ago
        Scheme is implemented via a CPS transform, so a server built around this approach ought to be quite possible on a good Scheme implementation, or a Lisp implementation that supports the moral equivalent of call/cc. 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-methods-and.html http://blog.barrkel.com/2006/07/fun-with-asynchronous-method... (I've been banging on this drum quietly for some time now...)
      - silentbicycle 17y ago
        Just as a minor addition to what barrkel says below, there's a good explanation of CPS transformation, and its use in compiling, in the first edition of EOPL. 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.
    - kd5bjo 17y ago
      Twisted's @inlineCallbacks decorator basically does this for you; whenever you yield a deferred (Twisted's representation of an ongoing operation), the rest of the generator is registered as the callback for when the operation is finished. Your example becomes: @defer.inlineCallbacks def A(x): x = yield B(x) C(x) @defer.inlineCallbacks def B(x): factor = yield AsyncCall() defer.returnValue(x * factor)
- TimothyFitz 17y ago
  The CLR (.NET Runtime) kinda does this. The host can substitute threading and I/O implementations. Msft's SQL Server actually does this; when you build C# stored procedures they're actually running on NT Fibers (green threads) with async I/O.

by lemming 17y ago

barrkel 17y ago

The annoying thing to me, as a guy who works on the compiler side of things, is that transformation of linear synchronous code to continuation-passing style (CPS) suitable for asynchronous code can be done mechanically by the compiler. There isn't a technical reason why it needs to be as hard as it is; lots of details to get right, especially when inter-operating with stack-oriented languages, etc., but in principle it's very possible.

etherealG 17y ago
how would you manage to figure out the order of execution for an arbitrary set of events firing when the program is defined as a direct linear series of operations? surely the paradigm is so vastly different that getting a compiler to figure it out would be impossible?
- barrkel 17y ago
  CPS transformation is mechanical; don't take my word for it, there's plenty of documentation: http://www.springerlink.com/content/dk7n7mbjx7blbelj/ http://www.springerlink.com/content/dk7n7mbjx7blbelj/ http://moscova.inria.fr/~xleroy/publi/cps-dargaye-leroy.pdf http://moscova.inria.fr/~xleroy/publi/cps-dargaye-leroy.pdf http://muaddibspace.blogspot.com/2009/02/cps-transformation-using-delimited.html 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 CPS form: def A(x,continuation): B(x, result => { x = result C(x,continuation) }) def B(x,continuation): AsyncCall(result => { factor = result continuation(x * factor) }) Things are actually more complicated than they look here, you may need more than one continuation for things like exceptions etc., but hopefully you get the gist. 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.
  - etherealG 17y ago
    wow, that's really interesting. thanks. do you know of any production level languages that feature this kind of approach?
    - barrkel 17y ago
      Scheme is implemented via a CPS transform, so a server built around this approach ought to be quite possible on a good Scheme implementation, or a Lisp implementation that supports the moral equivalent of call/cc. 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-methods-and.html http://blog.barrkel.com/2006/07/fun-with-asynchronous-method... (I've been banging on this drum quietly for some time now...)
    - silentbicycle 17y ago
      Just as a minor addition to what barrkel says below, there's a good explanation of CPS transformation, and its use in compiling, in the first edition of EOPL. 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.
  - kd5bjo 17y ago
    Twisted's @inlineCallbacks decorator basically does this for you; whenever you yield a deferred (Twisted's representation of an ongoing operation), the rest of the generator is registered as the callback for when the operation is finished. Your example becomes: @defer.inlineCallbacks def A(x): x = yield B(x) C(x) @defer.inlineCallbacks def B(x): factor = yield AsyncCall() defer.returnValue(x * factor)
TimothyFitz 17y ago
The CLR (.NET Runtime) kinda does this. The host can substitute threading and I/O implementations. Msft's SQL Server actually does this; when you build C# stored procedures they're actually running on NT Fibers (green threads) with async I/O.