Re: [rust-dev] Vectors, mutability & vec::dedup
Alright, brace yourself for more stupid questions, Graydon. :) On Thu, Dec 13, 2012 at 10:52 AM, Graydon Hoare wrote: > On 12-12-13 12:17 AM, Tom Lee wrote: > > > It looks like the 'move' operations here are directly modifying the > > contents of the vector by moving data around in the vector. This > > strikes me as kind of strange. I've allocated an immutable vector on > > the exchange stack and so make the assumption that the contents of the > > vector is in effect fixed. Is that assumption cast to the wind as soon > > as I start working with a mutable, borrowed pointer to that same > > vector? > > More or less. Mutability "inherits" (not sure I love that term, but it's > what we're using) along the ownership path to a memory cell. I'm still not sure I grok the terminology, sorry. :) Specifically, I'm not sure what you mean by an "ownership path". Presumably ownership relates to something like this: // 1. x "owns" the memory on the RHS, and so the RHS "inherits" the mutability of x? let mut x = ~[1, 2, 3]; So here, though the data type of the RHS is immutable, the underlying memory is *not* because the "owner" of that memory is mutable? So while -- > operationally -- you and I both know that there's a difference between: > >// "Mutating a cell in a vector" >foo[0] = 1 > > and > >// "Mutating the vector variable" >foo = [1] + foo[1..] > > The _observational_ difference, on an owned value (i.e. you're the only > person who can even see the vector in question) is really just that the > latter would do a bunch of allocation, copying and freeing, and wind up > pointing to a different place containing exactly the same result. From > the perspective of the surrounding code, if it's not actually paying > attention to pointer values, those two lines are identical. So after much struggling with library idiom evaluation, we decided that > differentiating the two in the type system was more cost than benefit -- > it meant we had to have two different paths for a lot of code that > differed only in where the obligatory word 'mut' showed up -- and > rearranged mutability so that it "inherits" through the ownership path. > That brings with it the significant benefit that we can often toggle the > mutability from the entire datatype by assigning it to a read-only or > read-write owner. Are you talking about something like this? // x is the owner & thus the underlying memory is mutable. let mut x = ~[1, 2, 3]; x[0] = 10; // ok, x[0] is reassigned // y is the owner & the underlying memory is now immutable. let y = move x; y[0] = 10; // compile time error: y is immutable. Okay, I think that answers a few of my questions. I'm guessing when you talk about mutability being "inherited" here, you're referring to the fact the type system will enforce things like borrowed pointers? Something like: let mut x = ~[1, 2, 3]; foo(&mut x); // ok: x is mutable, mutable borrowed pointer let mut y = ~[4, 5, 6]; foo(&mut y); // compile error: y is immutable, but we want a mutable borrowed pointer I think that makes sense. The only question I'd have here is why we need to be specific about whether the borrowed pointer is immutable or not? Couldn't it be inferred from the underlying variable? What do we gain by being explicit? > Or is this just the consequence of a bit of a sleazy optimization, > > where the function signature makes it *look* like we're going to > > return the deduped result in 'v' when in fact we're modifying it > > in-place? > > More or less. One person's sleazy optimization is another person's > essential one. De-dupe might be a bit surprising but for a lot of > operations (mostly vector operations -- it's the "arbitrary size" type > after all), doing them "in place" is the difference between acceptable > performance and "ugh, I'll just go do this in C". Our goal is to > minimize the number of cases where users feel they have to switch to C > "for performance reasons". > Argh, I just spent another hour being confused because I was somehow looking at what must have been an old implementation of vec::dedup with a type signature that implied no mutability at all. :) Oh I totally get that, I only say "sleazy" because my understanding of 'mut' at the time was flawed (or I was looking at the wrong code again :)). Makes perfect sense now. > > I'm not sure there's a coherent question here, but I feel like I'm > > missing something. Hopefully somebody can understand what I'm rambling > > on about & shed some light :) > > Rambling questions -- so long as they're not too hostile! -- are good. > They point out a need for docs that clarify and make-explicit. We'll > need a lot more discussion about this in the docs eventually. Keep > pointing out things that don't make sense and we'll try to make sure > they're well covered. > > Will do! I think I understand things a little better, but still got a way to go. Phew. I think this deserves
Re: [rust-dev] Reading shared immutable data
On 12/17/12 6:27 PM, Michael Neumann wrote: Am 18.12.2012 03:11, schrieb Patrick Walton: * Use unsafe code by casting to an unsafe pointer and sending the unsafe pointer over a channel; do this only as a last resort. But don't I get into problems with GC when I do that? So I create the data structure heap allocated in one thread, then get an unsafe pointer to it and sent this to all other threads. Of course in the originating thread I need to keep the reference to the data, otherwise the unsafe pointer will point to garbage. Right. You'd need to keep a reference to it alive. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Reading shared immutable data
Am 18.12.2012 03:11, schrieb Patrick Walton: On 12/17/12 6:03 PM, Michael Neumann wrote: Hi, We have a very huge immutable data structure that we want to share (read-only) between many light-weight threads. From what I have seen, I should use Arc. Is there any other way to share the data between threads? You can also: * Use a reader-writer lock (RWLock). This is still safe. I will look into this. * Use unsafe code by casting to an unsafe pointer and sending the unsafe pointer over a channel; do this only as a last resort. But don't I get into problems with GC when I do that? So I create the data structure heap allocated in one thread, then get an unsafe pointer to it and sent this to all other threads. Of course in the originating thread I need to keep the reference to the data, otherwise the unsafe pointer will point to garbage. * Turn your shared state into a task and have other tasks access the data by sending it messages. This is the classical actor model solution, but usually ARC will be more efficient. But this doesn't allow for parallelism, and that's what we want. And when using Arc, can I access the data in parallel by all threads? Yes. The only synchronization cost you'll pay is the cost of an atomic CPU instruction whenever you send the data. I would just send the data once at thread creation. Hm, I have to play with that. Thanks a lot! Michael ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Reading shared immutable data
On 12/17/12 6:03 PM, Michael Neumann wrote: Hi, We have a very huge immutable data structure that we want to share (read-only) between many light-weight threads. From what I have seen, I should use Arc. Is there any other way to share the data between threads? You can also: * Use a reader-writer lock (RWLock). This is still safe. * Use unsafe code by casting to an unsafe pointer and sending the unsafe pointer over a channel; do this only as a last resort. * Turn your shared state into a task and have other tasks access the data by sending it messages. This is the classical actor model solution, but usually ARC will be more efficient. And when using Arc, can I access the data in parallel by all threads? Yes. The only synchronization cost you'll pay is the cost of an atomic CPU instruction whenever you send the data. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
[rust-dev] Reading shared immutable data
Hi, We have a very huge immutable data structure that we want to share (read-only) between many light-weight threads. From what I have seen, I should use Arc. Is there any other way to share the data between threads? And when using Arc, can I access the data in parallel by all threads? Best regards, Michael ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
Is it important for `traverse` to pass along an option type? Is it
important to inform end users that a key has been deleted? Or is that
implementation specific? If so, I suggest rewriting `traverse` to something
like this (assuming this actually works):
impl RBMap: iter::BaseIter<(&K, &V)> {
pure fn each(f: fn(&(&K, &V))) {
match *self {
Leaf => (),
Tree(_, left, ref key, maybe_value, right) => {
left.traverse(f);
match maybe_value {
Some(ref value) => f(&(key, value)),
None => {},
}
right.traverse(f);
}
}
}
}
On Mon, Dec 17, 2012 at 11:46 AM, Graydon Hoare wrote:
> On 12-12-17 11:28 AM, Graydon Hoare wrote:
> > On 12-12-14 03:51 PM, Steve Jenson wrote:
> >> I recently ported Matt Might's Scala port of Okasaki's purely functional
> >> red-black tree to Rust and am looking for some feedback.
> >>
> >> https://github.com/stevej/rustled/blob/master/red_black_tree.rs
> >>
> >> I've written this for 0.4 and will update it with other feedback I've
> >> received for 0.5 when that lands.
> >
> > Nice! The only things I'd ask are:
> >
> > - I can't tell at a glance (sorry, RB-trees are always very subtle)
> > whether this is an LLRB. If not, could you make it so? It's likely
> > just a simplification to a couple of the functions.
>
> Er, except of course, there's also:
>
> https://github.com/fawek/llrbt.rs
>
> I think we need some better coordination of library development :)
>
> -Graydon
>
> ___
> 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
Re: [rust-dev] purely function red-black tree
On 12-12-17 11:28 AM, Graydon Hoare wrote: > On 12-12-14 03:51 PM, Steve Jenson wrote: >> I recently ported Matt Might's Scala port of Okasaki's purely functional >> red-black tree to Rust and am looking for some feedback. >> >> https://github.com/stevej/rustled/blob/master/red_black_tree.rs >> >> I've written this for 0.4 and will update it with other feedback I've >> received for 0.5 when that lands. > > Nice! The only things I'd ask are: > > - I can't tell at a glance (sorry, RB-trees are always very subtle) > whether this is an LLRB. If not, could you make it so? It's likely > just a simplification to a couple of the functions. Er, except of course, there's also: https://github.com/fawek/llrbt.rs I think we need some better coordination of library development :) -Graydon ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
On 12-12-14 03:51 PM, Steve Jenson wrote: > I recently ported Matt Might's Scala port of Okasaki's purely functional > red-black tree to Rust and am looking for some feedback. > > https://github.com/stevej/rustled/blob/master/red_black_tree.rs > > I've written this for 0.4 and will update it with other feedback I've > received for 0.5 when that lands. Nice! The only things I'd ask are: - I can't tell at a glance (sorry, RB-trees are always very subtle) whether this is an LLRB. If not, could you make it so? It's likely just a simplification to a couple of the functions. - Would you mind, once all feedback is incorporated, if we pull this into the stdlib? We have a bug open discussing cleanup and (re)organization of the container types, fwiw, over here: https://github.com/mozilla/rust/issues/3863 Thanks for taking an interest in this. -Graydon ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] simple hash map for storing structs that contain ~str and/or ~[]
On 12/17/2012 04:42 PM, Patrick Walton wrote:
> Try returning a reference from find() instead. It's warning you that
> find() is copying out the data (since it returns V and not &V).
I read up on borrowed pointers and made find() return &self/V. After
turning this:
impl LinearMap: Map {
into this:
impl LinearMap: Map {
(removing the Copy trait from V) it all worked as expected. Thanks for
leading me into the right direction!
- Tim
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] simple hash map for storing structs that contain ~str and/or ~[]
On 12/17/2012 04:42 PM, Patrick Walton wrote: > On 12/17/12 6:42 AM, Tim Taubert wrote: >> Is there anything I can do about this other than using managed boxes? I >> really don't want to force people to use GC. > > Try returning a reference from find() instead. It's warning you that > find() is copying out the data (since it returns V and not &V). Sorry, to clarify: rustc shows the same warnings for insert() and remove(), so it's not only find(). > Incidentally, that warning may be turned off by default in the future, > since it's incompatible with the new Clone trait and can be annoying in > cases like this. > > Patrick > > ___ > 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
Re: [rust-dev] simple hash map for storing structs that contain ~str and/or ~[]
On 12/17/12 6:42 AM, Tim Taubert wrote: Is there anything I can do about this other than using managed boxes? I really don't want to force people to use GC. Try returning a reference from find() instead. It's warning you that find() is copying out the data (since it returns V and not &V). Incidentally, that warning may be turned off by default in the future, since it's incompatible with the new Clone trait and can be annoying in cases like this. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
[rust-dev] simple hash map for storing structs that contain ~str and/or ~[]
I'm trying to create simple hash map with an interface like this:
trait Map {
fn find(&const self, k: &K) -> Option;
fn insert(&mut self, k: K, +v: V);
fn remove(&mut self, k: &K);
}
The implementation itself is subject to change and I'll experiment with
that a bit. I copied some of the parts from send_map and tried the
following:
struct Item {
v: uint
}
fn test() {
let item = Item {v: 0};
let mut map = LinearMap::new();
map.insert(~"foo", item);
assert map.find(&~"foo") == Some(item);
}
This works fine until I try to store structs that contain a ~str or ~[].
I'm getting this error:
warning: instantiating copy type parameter with a not implicitly
copyable type
assert map.find(&~"foo") == None;
Is there anything I can do about this other than using managed boxes? I
really don't want to force people to use GC.
Thanks,
- Tim
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
