Does the current API work well enough if we swapped default libs with hypothetical unbounded channels? Do we need to hash out what changes would be necessary, before any implementing?
At some point code will be more valuable than more emails... Kevin On Mon, Dec 30, 2013 at 8:40 PM, Christian Ohler <oh...@gnu.org> wrote: > A few thoughts on this: > > > (1) Unbounded vectors are safe; unbounded channels are unsafe, since > scheduling is nondeterministic. > > (2) Use of bounded channels and blocking send is what makes scheduling > "deterministic enough" to be safe. > > (3) I'm not worried that bounded channels and blocking sends will > cause deadlocks out of nowhere. > > (4) Servo should implement web semantics without pushing them as > requirements into libstd. > > > > In more detail: > > (1) Unbounded vectors are safe; unbounded channels are unsafe, since > scheduling is nondeterministic. > > The number of elements in a vector is determined by the algorithm, > which the programmer controls. The number of elements in a channel > is, in many cases, determined by the scheduler, which is not under the > programmer's direct control – from the programmer's perspective, > scheduling is nondeterministic. This makes unbounded channels unsafe. > > Example: Even if the scheduling is perfectly fair and assigns the same > number of cycles to a producing task and the corresponding consuming > task, the producer can still outrun the consumer if producing a > message takes fewer cycles than consuming one, leading to memory > exhaustion if the channel is unbounded. > > Vectors don't have such problems. We can construct programs where the > size of a vector becomes dependent on scheduling or other > nondeterministic runtime behavior; but channels are inherently tied to > inter-task communication and scheduling, and vectors are not. > > > (2) Use of bounded channels and blocking send is what makes scheduling > "deterministic enough" to be safe. > > A simple way to avoid the above memory exhaustion is making the > channel bounded and blocking on send, so that the scheduler stops the > producer when appropriate, and runs the consumer instead. Without > blocking on send, the scheduler has no way of knowing that the > consumer should be assigned more cycles than the producer; blocking on > send is the tool that lets the programmer influence the scheduler's > behavior. (Blocking on receive plays a symmetrical role, but is a > less subtle requirement because of the data dependency.) > > Scheduling is nondeterministic, but blocking the sender when the > receiver can't keep up limits the set of possible schedulings to a > safe subset. (This is a simple example of backpressure and how it > helps.) > > Finding the right channel buffer size is a performance tuning problem > similar to finding a good size for a cache. > > > (3) I'm not worried that bounded channels and blocking sends will > cause deadlocks out of nowhere. > > Unbounded channels are unsafe because they make memory consumption > unbounded and outside of the programmer's control; but bounded > channels and blocking sends can lead to deadlocks, so aren't they also > unsafe? > > This concern about potential deadlocks was something that really > worried me for a while, but I now suspect that task communication can > usually be structured in patterns that avoid dead ends in the task > communication state machines, eliminating the possibility of > deadlocks. Bounded channels and blocking sends are unsafe in the > sense that rustc won't be able to reliably detect deadlocks, but the > program design can ensure their absence. > > For example, processing might happen in stages, and data flows "left > to right", where tasks are either ready to receive any message from > the left, or blocked sending a specific message to the right. Since > there is never a mismatch in what the receiver expects and what the > sender sends, nor is there a cycle in the blocking sends, there won't > be deadlocks. > > Other code might follow a request-response pattern where a task T > sends requests to a task M that manages a resource, and T passes in a > size-1 response channel with each request and waits for M's response > on that channel. T blocks until M's request channel is ready to > receive, but the response channel will be used for only one message > and is guaranteed to have room for it, so M's send will not block. > Since M's send will not block, M will only block waiting for requests, > never deadlocking with T. > > I haven't thought this through completely, and don’t have a formal > argument, but I am finding these patterns in systems that I’m working > on. Perhaps this is analogous to how we are generally not worried > that language features like unrestricted function calls and > higher-order functions will make it difficult to avoid infinite > recursion: Programmers have a mental model of how their system is > layered, and they know that calls generally go from higher layers into > lower layers, with few exceptions that they structure in ways that > avoid infinite recursion. > > > (4) Servo should implement web semantics without pushing them as > requirements into libstd. > > Servo needs an unbounded UI event queue, but that doesn't mean libstd > needs to provide unbounded channels. Mapping the UI event queue > directly to a libstd channel may be a neat match right now, but it > seems prudent to leave servo product features decoupled from libstd > features and being prepared to introduce intermediate layers, since > servo's product requirements can shift. > _______________________________________________ > Rust-dev mailing list > Rust-dev@mozilla.org > https://mail.mozilla.org/listinfo/rust-dev _______________________________________________ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
