I thought tasks were a type of greenlet, or vice versa. What's your proposal, exactly?
Kevin On Nov 13, 2013 9:06 AM, "Vadim" <[email protected]> wrote: > They don't share state. The language-level semantics of greenlets is the > same as that of tasks, except that they are scheduled cooperatively. All > these games with the stack should be unobservable on Rust level. > > > On Wed, Nov 13, 2013 at 1:01 AM, Eric Reed <[email protected]>wrote: > >> The big issue I see right away (assuming I read this correctly and >> greenlets can still access the stack that existed when they were created), >> is that now mutable state on the stack is *shared* between greenlets and >> therefore can experience *data races* (impossible for tasks b/c they >> don't share memory), so they sound wildly unsafe to me. >> >> There may be some other issues that arise from the shared stack prefix >> property: >> - If a greenlet moves something on the stack, then other greenlets now >> have access to invalidated memory >> - You can no longer assume that you have sole access things pointed to by >> unique pointers, which would probably invalidate a lot of existing >> assumptions. >> >> Eric >> >> >> On Wed, Nov 13, 2013 at 12:02 AM, Vadim <[email protected]> wrote: >> >>> Hi, >>> I would like to float a proposal (or three :-), regarding "greenlets" in >>> Rust. For those unfamiliar with greenlets, they are a tool for writing >>> concurrent code, similar to Rust's tasks, but much more light-weight in >>> terms of memory consumption (especially now that segmented stacks are no >>> more). >>> >>> I think there are some scenarios where low memory consumption per-task >>> is still important, 64-bit address spaces notwithstanding. A typical one >>> would be a pub-sub server, which needs to maintain a massive number of >>> simple I/O workflows, where I/O channels are idle most of the time. >>> >>> So here we go (in the order of increasing craziness): >>> >>> 1. Recently I've learned how Python >>> greenlets<http://greenlet.readthedocs.org/>are >>> implemented <http://stackoverflow.com/a/17447308>. I believe that the >>> same approach could work in Rust: >>> >>> Basically, greenlets are spawned using the same stack as the parent >>> greenlet, just like a normal function call. When a greenlet is suspended, >>> it copies the portion of the stack used up since its' spawning to the >>> heap. When one is re-activated, the saved memory is copied back where it >>> came from (having first saved stack of the previous active greenlet,- if >>> they overlap). >>> >>> Since greenlets don't need to save "red zone" of the stack, the amount >>> of data per instance is precisely what is actually used. >>> >>> There are also downsides, of course: >>> - greenlets are bound to the thread that spawned them, >>> - two memcpy's are needed when switching between them. >>> >>> In the case of Python, though, there's one further optimization: since >>> Python's stack frames live on the heap, in most cases, there nothing on the >>> hardware stack that a greenlet needs saving! As a bonus, it can now be >>> resumed at any stack position, so no saving of previous greenlet's stack is >>> needed. The only time when a full save occurs is when there are foreign >>> stack frames on the stack. >>> >>> >>> 2. Well, can Rust do the same? What if we came up with an attribute, >>> say, [#stackless], which causes a function to allocate it's stack frame on >>> the heap and put all local vars there? The only things on the actual >>> hardware stack would then be the function's arguments, the return address, >>> the saved base pointer and the pointer to that heap-alllocated frame. >>> With the exception of base pointers, all these things are >>> position-independent, I believe. And base pointer chain can be easily >>> fixed up if/when stack is moved. >>> >>> So if we had that, and the whole greenlet's stack consisted of such >>> functions, and there was a way for the "switch_to_greenlet()" function to >>> detect that, then such greenlet's stack would be relocatable and could be >>> resumed at any position in the thread's stack (or even in another thread!) >>> with minimal memory copying, just like in Python. >>> >>> Of course, the [#stackless] functions would be slower than the normal >>> ones, but in the scenario I've outlined in the beginning, it shouldn't be a >>> problem. >>> >>> >>> 3. Unfortunately, in order for the above scheme to work, all I/O >>> methods, (which are typically where yields happen), would need to be marked >>> as [#stackless]... This would affect the performance of "normal" code >>> using the same API, which is undesirable. >>> >>> Okay, but usually there are not *that *many things that point into the >>> stack in a typical program. I can think of only three things: references >>> to stack-allocated buffers, base pointer chains and references to >>> caller-allocated return values. >>> - The first one can be lived without - just allocate buffers on the heap. >>> - The second one - see above. >>> - The last one is more tricky, but for the sake of argument, let's >>> assume that we restricted function signatures such that only >>> register-allocated types can be returned. >>> >>> Let's say we came up with a way to mark up functions that may yield to >>> another greenlet, and also with a way to prohibit taking address of >>> stack-allocated variables for the duration of calls to yielding functions. >>> These restrictions would be annoying, but not overly so, as long as you >>> had to obey them only in functions that are intended to be run in a >>> greenlet. >>> On the plus side, the hardware stack contents would now be relocatable. >>> >>> In this setup, everything could proceed as usual, using the hardware >>> stack, until execution came to a blocking I/O call. At that point, the >>> scheduler would check if running inside a greenlet, copy greenlet's stack >>> to the heap and switch off to another greenlet. Otherwise, it would do the >>> same thing it does now, i.e. switch tasks. >>> >>> >>> So, what do you say, rustafarians? Does any of that make any sense? >>> >>> Vadim >>> >>> >>> On Tue, Nov 5, 2013 at 9:18 AM, Patrick Walton <[email protected]>wrote: >>> >>>> On 11/5/13 8:32 AM, David Piepgrass wrote: >>>> >>>>> Segmented stacks aren't the only solution though. >>>>> >>>>> If the concern is many tasks that block for a long time, I imagine a >>>>> mechanism to bundle a bunch of small, dormant stacks into a single page >>>>> so that the original pages could be released to the OS. >>>>> >>>>> >>>>> >>>>> *If stacks were additionally relocatable (which requires similar >>>>> machinery as precise moving GC, if I'm not mistaken) * >>>> >>>> >>>> This is correct. It's conceivable (although I can't make any promises) >>>> that if and when LLVM supports this, we could experiment with doing what Go >>>> does. >>>> >>>> Patrick >>>> _______________________________________________ >>>> Rust-dev mailing list >>>> [email protected] >>>> https://mail.mozilla.org/listinfo/rust-dev >>>> >>> >>> >>> _______________________________________________ >>> Rust-dev mailing list >>> [email protected] >>> https://mail.mozilla.org/listinfo/rust-dev >>> >>> >> >> _______________________________________________ >> Rust-dev mailing list >> [email protected] >> https://mail.mozilla.org/listinfo/rust-dev >> >> > > _______________________________________________ > Rust-dev mailing list > [email protected] > https://mail.mozilla.org/listinfo/rust-dev > >
_______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
