Hi!
I was thinking about fork/join-style parallelism and about whether
this can be made to work including the possibility to pass references
(or something similar to references) across task boundaries. So far, I
came up with a little low-level building block that could be of
interest to the community. This basically allows to send
reference-like things across task boundaries without any dangling
pointer issues (I believe).
A use case I had in mind was a divide-and-conquer algorithm where the
recursion could benefit from concurrency because the division produces
independent problems operating on non-overlapping mut slices. In my
case, I tried to parallelize a multibody simulation with this. But you
could also think about a parallelized quicksort if you want. After
partitioning, sorting the two halves can be done independently and
concurrently. But you may wish to avoid splitting one vector into two
and joining them together. Instead you may want different tasks to
work on the same vector but restricted to their non-overlapping
sub-slices.
The basic idea is to erase the lifetime parameter (to make the
reference-like objects sendable) and to keep it safe w.r.t. to
lifetimes by creating a new scope that won't be left by execution
until all the borrowed and life-time erased pseudo-references are
gone. This is done by reference counting and signal/wait on a mutex.
Let me just show you for now how this can be used:
trait IntoSendBorrow<Out> {
unsafe fn into_sendable(self) -> Out;
fn sendable<U>(self, func:|Out|->U) -> U { ... }
}
fn partition_inplace<'a>(s: &'a mut[int]) -> (&'a mut[int],&'a mut[int]) {
...
}
fn main() {
let mut vec = Vec::from_fn(10,|u|-(u as int));
partition_inplace(vec.as_mut_slice()).sendable(|(left,right)|{
// Here, left and right are "sendable slices": SendMutSlice<int>
// A "sendable reference" internally refers to a reference counter
// stored in a mutex and increases/decreases it on clone/drop.
// If the counter reaches zero, it will send a signal.
spawn(proc() {
let mut left = left; // needed for unique borrowing
left.as_mut_slice().sort();
});
let mut right = right; // needed for unique borrowing
right.as_mut_slice().sort();
}); // <-- in case the reference counter is not null, sendable waits
// for the signal and blocks until until it reaches zero.
// This is done within a destructor of a function-local object
// that carries the reference counter as a member.
for i in vec.iter() {
println!("{}", i)
}
}
IntoSendBorrow is simply implemented for all reference-like things
(&T, &mut T, &[T], &mut[T] and tuples of these).
I'm planning on putting the whole source code online on github. Feel
free to comment -- especially if you find this useful. :)
One thing I learned is that it does not seem to be possible to emulate
the behaviour of mutable references and mutable slices perfectly in
the sense that they could be uniquely borrowed without being mutable.
I think, I would have to write something like this:
impl<T> SendMutSlice<T> {
...
fn get<'a>(&'a uniq self, index: uint) -> &'a mut T
...
}
where self is only uniquely borrowed but does not have to be mutable.
At least a unique borrow is needed to avoid returning mutable aliases.
Since this is not possible right now, I have to put a "mut" there
instead and that's why I need the lines
let mut left = left;
let mut right = right;
in the above example.
Cheers!
sg
_______________________________________________
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
