[rust-dev] Vectors, mutability & vec::dedup

Tom Lee rust-dev at tomlee.co
Mon Dec 17 22:53:22 PST 2012

Alright, brace yourself for more stupid questions, Graydon. :)

On Thu, Dec 13, 2012 at 10:52 AM, Graydon Hoare <graydon at mozilla.com> 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 another blog post. :)

Thanks for taking the time to respond in detail!

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20121217/57eb0003/attachment-0001.html>

More information about the Rust-dev mailing list