Crates.io | rayon-futures |
lib.rs | rayon-futures |
version | 0.1.1 |
source | src |
created_at | 2017-09-09 22:09:28.235297 |
updated_at | 2019-12-22 00:47:55.610922 |
description | (deprecated) Futures integration into Rayon |
homepage | |
repository | https://github.com/rayon-rs/rayon |
max_upload_size | |
id | 31239 |
size | 61,787 |
This crate is now deprecated, because it only supports the obsolete
futures-0.1
. New integration with std::future::Future
will likely
take place directly in rayon-core
, but this is left to the ... future.
NOTE: rayon-futures
currently requires unstable features of
rayon-core
, which may only be enabled with rustc --cfg
,
e.g. by setting RUSTFLAGS=--cfg rayon_unstable
in the environment.
Let's start with a brief coverage of how futures work. Our example will be a simple chain of futures:
F_map -> F_socket
Here F_socket
is a future that maps to a TCP socket. It returns a
Vec<u8>
of data read from that socket. F_map
is a future will take
that data and do some transformation. (Note that the real futures for
reading from sockets etc do not work in this way, this is just an
example.)
The idea of futures is that each future offers a poll()
method. When
poll()
is invoked, the future will attempt to execute. Typically,
this often involves recursively calling poll()
on other futures. So,
in our example, F_map
when it starts would call F_socket.poll()
to
see if the data is ready. The idea is that poll()
returns one of
three values:
Ok(Async::Ready(R))
-- the future has completed, here is the result R
.Err(E)
-- the future has completed and resulted in an error E
.Ok(Async::NotReady)
-- the future is not yet complete.The last one is the most interesting. It means that the future is blocked on some event X, typically an I/O event (i.e., we are waiting for more data to arrive on a TCP socket).
When a future returns NotReady
, it also has one additional job. It
must register the "current task" (think for now of the current thread)
to be re-awoken when the event X has occurred. For most futures, this
job is delegated to another future: e.g., in our example, F_map
invokes F_socket.poll()
. So if F_socket.poll()
returns not-ready,
then it will have registered the current thread already, and hence
F_map
can merely propagates the NotReady
result further up.
A key concept of the futures.rs library is that of an executor. The
executor is the runtime that first invokes the top-level future
(F_map
, in our example). This is precisely the role that Rayon
plays. Note that in any futures system there may be many
interoperating executors though.
Part of an executor's job is to maintain some thread-local storage
(TLS) when a future is executing. In particular, it must setup the
"current task" (basically a unique integer, although it's an opaque
type) as well as an "unpark object" of type
Arc<Unpark>
. The Unpark
trait offers a single method
(unpark()
) which can be invoked when the task should be
re-awoken. So F_socket
might, for example, get the current
Arc<Unpark>
object and store it for use by an I/O thread. The I/O
thread might invoke epoll()
or select()
or whatever and, when it
detects the socket has more data, invoke the unpark()
method.
When you spawn a future of type F
into rayon, the idea is that it is
going to start independently executing in the thread-pool. Meanwhile,
the spawn_future()
method returns to you your own future (let's call
it F'
) that you can use to poll and monitor its progress. Internally
within Rayon, however, we only allocate a single Arc
to represent
both of these things -- an Arc<ScopeFuture<F>>
, to be precise -- and
this Arc
hence serves two distinct roles.
The operations on F'
(the handle returned to the user) are specified
by the trait ScopeFutureTrait
and are very simple. The user can
either poll()
the future, which is checking to see if rayon is done
executing it yet, or cancel()
the future. cancel()
occurs when
F'
is dropped, which indicates that the user no longer has interest
in the result.
Each spawned future is represented by an Arc
. This Arc
actually has
some interesting structure. Each of the edges in the diagram below
represents something that is "kept alive" by holding a ref count (in
some way, usually via an Arc
):
F' ---+ [ deque ] --+
| |
v v
+---> /---------------------\
| | registry: | ------> [rayon registry]
| | contents: --------\ |
| | | scope | | ------> [spawning scope]
| | | this | | --+ (self references)
| | | ... | | |
| | \-----------------/ | |
| \---------------------/ |
+-------------------------------+
Let's walk through them:
F'
represents the edge from the future that was returned
to the caller of spawn_future
. This ensures that the future arc will
not be freed so long as the caller is still interested in looking at
its result.[ deque ]
represents the fact that when the
future is enqueued into a thread-local deque (which it only
sometimes is), that deque holds a ref. This is done by transmuting
the Arc
into a *const Job
object (and hence the *const
logically holds the ref that was owned by the Arc
). When the job
is executed, it is transmuted back and the resulting Arc
is
eventually dropped, releasing the ref.registry
field holds onto an Arc<Registry>
and hence keeps
some central registry alive. This doesn't really do much but prevent
the Registry
from being dropped. In particular, this doesn't
prevent the threads in a registry from terminating while the future
is unscheduled etc (though other fields in the future do).scope
field (of type S
) is the "enclosing scope". This scope
is an abstract value that implements the FutureScope<'scope>
trait
-- this means that it is responsible for ensuring that 'scope
does
not end until one of the FutureScope
methods are invoked (which
occurs when the future has finished executing). For example, if the
future is spawned inside a scope()
call, then the S
will be a
wrapper (ScopeFutureScope
) around a *const Scope<'scope>
. When
the future is created one job is allocated for this future in the
scope, and the scope counter is decremented once the future is
marked as completing.
scope
field is to ensure that the
future type (F
) remains valid. After all, since F: 'scope
, F
is known to be valid until the lifetime 'scope
ends, and that
lifetime cannot end until the scope
methods are invoked, so we
know that F
must stay valid until one of those methods are
invoked.F
is stored in the field spawn
(not
shown here). This field is always set to None
before the scope
counter is decremented. See the section on lifetime safety for more
details.this
field stores an Arc
which is actually
this same future. Thus the future has a ref count cycle
and cannot be freed until this cycle is broken. That field
is actually an Option<Arc<..>>
and will be set
to None
once the future is complete, breaking the cycle and
allowing it to be freed when other references are dropped.Internally, futures go through various states, depicted here:
PARKED <----+
| |
v |
UNPARKED |
| |
v |
EXECUTING --+
| | ^
| v |
| EXECUTING_UNPARKED
|
v
COMPLETE
When they are first created, futures begin as PARKED. A PARKED
future is one that is waiting for something to happen. It is not
scheduled in the deque of any thread. Even before we return from
spawn_future()
, however, we will transition into UNPARKED. An
UNPARKED future is one that is waiting to be executed. It is
enqueued in the deque of some Rayon thread and hence will execute when
the thread gets around to it.
Once the future begins to execute (it itself is a Rayon job), it
transitions into the EXECUTING state. This means that it is busy
calling F.poll()
, basically. While it calls poll()
, it also sets
up its contents.this
field as the current "notify" instance. Hence
if F
returns NotReady
, it will clone the this
field and hold
onto it to signal us the future is ready to execute again.
For now let's assume that F
is complete and hence returns either
Ok(Ready(_))
or Err(_)
. In that case, the future can transition to
COMPLETE
. At this point, many bits of state that are no longer
needed (e.g., the future itself, but also the this
field)
are set to None
and dropped, and the result is stored in the
result
field. (Moreover, we may have to signal other tasks, but that
is discussed in a future section.)
If F
returns Ok(Async::NotReady)
, then we would typically
transition to the PARKED
state and await the call to
notify()
. When notify()
is called, it would move the future into
the UNPARK
state and inject it into the registry.
However, due to the vagaries of thread-scheduling, it can happen
that notify()
is called before we exit the EXECUTING
state. For
example, we might invoke F.poll()
, which sends the Unpark
instance
to the I/O thread, which detects I/O, and invokes notify()
, all
before F.poll()
has returned. In that case, the notify()
method
will transition the state (atomically, of course) to
EXECUTING_UNPARKED
. In that case, instead of transitioning to
PARKED
when F.poll()
returns, the future will simply transition
right back to EXECUTING
and try calling poll()
again. This can
repeat a few times.
Of course, Rayon's signature feature is that it allows you to use a
future F
that includes references, so long as those references
outlive the lifetime of the scope 'scope
. So why is this safe?
The basic idea of why this is safe is as follows. The ScopeFuture
struct holds a ref on the scope itself (via the field scope
).
Until this ref is decremented, the scope will not end (and hence
'scope
is still active). This ref is only decremented while the
future transitions into the COMPLETE state -- so anytime before
then, we know we don't have to worry, the references are still valid.
As we transition into the COMPLETE state is where things get more
interesting. You'll notice that signaling the self.scope
job as done
is the last thing that happens during that transition. Importantly,
before that is done, we drop all access that we have to the type F
:
that is, we store None
into the fields that might reference values
of type F
. This implies that we know that, whatever happens after we
transition into COMPLETE, we can't access any of the references
found in F
anymore.
This is good, because there are still active refs to the
ScopeFuture
after we enter the COMPLETE state. There are two
sources of these: unpark values and the future result.
NotifyHandle values. We may have given away NotifyHandle
values --
these contain trait objects that are actually refs to our
ScopeFuture
. Note that NotifyHandle: 'static
, so these could be
floating about for any length of time (we had to transmute away the
lifetimes to give them out). This is ok because (a) the Arc
keeps
the ScopeFuture
alive and (b) the only thing you can do is to call
notify()
, which will promptly return since the state is COMPLETE
(and, anyhow, as we saw above, it doesn't have access to any
references anyhow).
Future result. The other, more interesting reference to the
ScopeFuture
is the value that we gave back to the user when we
spawned the future in the first place. This value is more interesting
because it can be used to do non-trivial things, unlike the
NotifyHandle
. If you look carefully at this handle, you will see that
its type has been designed to hide the type F
. In fact, it only
reveals the types T
and E
which are the ok/err result types of the
future F
. This is intentonal: suppose that the type F
includes
some references, but those references don't appear in the result. We
want the "result" future to be able to escape the scope, then, to any
place where the types T
and E
are still in scope. If we exposed
F
here that would not be possible. (Hiding F
also requires a
transmute to an object type, in this case an internal trait called
ScopeFutureTrait
.) Note though that it is possible for T
and E
to have references in them. They could even be references tied to the
scope.
So what can a user do with this result future? They have two
operations available: poll and cancel. Let's look at cancel first,
since it's simpler. If the state is COMPLETE, then cancel()
is an
immediate no-op, so we know that it can't be used to access any
references that may be invalid. In any case, the only thing it does is
to set a field to true and invoke notify()
, and we already examined
the possible effects of notify()
in the previous section.
So what about poll()
? This is how the user gets the final result out
of the future. The important thing that it does is to access (and
effectively nullify) the field result
, which stores the result of
the future and hence may have access to T
and E
values. These
values may contain references...so how do we know that they are still in
scope? The answer is that those types are exposed in the user's type
of the future, and hence the basic Rust type system should guarantee
that any references are still valid, or else the user shouldn't be
able to call poll()
. (The same is true at the time of cancellation,
but that's not important, since cancel()
doesn't do anything of
interest.)