[rust-dev] problems with adding an element to a ' @' vector.

Nathan nejucomo at gmail.com
Mon Dec 10 16:27:55 PST 2012


On Mon, Dec 10, 2012 at 4:13 PM, Nathan <nejucomo at gmail.com> wrote:
> On Mon, Dec 10, 2012 at 4:03 PM, Patrick Walton <pwalton at mozilla.com> wrote:
>> On 12/10/12 3:49 PM, arkaitzj at gmail.com wrote:
>>>
>>> Aren't both ~vector and @vector dynamic memory? why can we append to a
>>> ~vector but not to a @vector?
>>
>>
>> Because the pointer points to an object that looks like this:
>>
>>     ---> [ length ] [ element 1 ] [ element 2 ] [ element 3 ]
>>
>> Now suppose that the allocator didn't leave any room for more elements after
>> it. In general we have to assume this, because we can't leave an infinite
>> amount of space after our arrays. Thus in general appending to a vector
>> requires reallocating the entire vector and move it to some new location in
>> memory. The problem is that, after we do that, we have to update all the
>> pointers to point to the new location.
>>
>> In the case of ~[T] this is easy. There is only one pointer, and it was
>> passed into push(), so we can just update it. With @[T] it's not so easy
>> though. We have no idea at compile time how many pointers there are to the
>> vector, and even at runtime finding all the pointers and updating them would
>> be a quite complex and expensive operation. So we have to copy the array.
>>
>
>
> I just read Patrick Walton's response, and I wanted to respond with a
> different take, based on types and mutability instead of performance:
>
>
> Caveat emptor: I'm a semi-lurker on the sidelines of rust, so consider
> every assertion that follows as suspect.  I'd like feedback on the
> correctness so we can put this kind of clarification in the tutorial:
>
>
> @[T] is a reference to a local-heap, transitively immutable vector
> where each element is a T.
>
> @[mut T] is a reference to a local-heap mutable vector.  Each element
> is a mutable T, and the vector itself can be mutated.  As Patrick
> described, operations like "extend this vector with new elements"
> might be expensive to implement.
>
> ~[mut T] is a reference to a shared-heap mutable vector, which can be
> mutated along the same lines as @[mut T].
>
> ~[T] is a funny type.  Let's think about it by looking at vec::push's signature:
>
> pub fn push<T>(v: &mut ~[T], initval: T) { ... }
>
> When the caller of push passes a ~[T], the code is allowing push to
> borrow a *mutable reference*.  Because this is the only reference at
> the time of the call, it is safe to mutate the v parameter.
>
> So if such mutable borrowing is possible, then what's the difference
> between ~[mut T] and ~[T]?  I think the answer is probably nothing, or
> maybe there are weird discrepancies.  The similarities are so close,
> that I believe ~[mut T] is actually being deprecated as a type
> specification.
>
> The distinction between ~[mut T] and ~T also applies to just ~T and ~mut T.
>
>
>>
>> Patrick
>>
>> _______________________________________________
>> Rust-dev mailing list
>> Rust-dev at mozilla.org
>> https://mail.mozilla.org/listinfo/rust-dev
>
> Regards,
> Nathan Wilcox
>
> ps: Nicholas Matsakis describes the rational around mutability and
> types in some blog posts.  These are two relevant posts:
>
> http://smallcultfollowing.com/babysteps/blog/2012/05/28/moving-mutability-into-the-type/
>
> http://smallcultfollowing.com/babysteps/blog/2012/07/24/generalizing-inherited-mutability/
>
> I'm not certain if everything proposed there defines the future of
> rust.  The second blog post really helped me understand the motivation
> for this design.


Here's another thought:

For those of us coming from languages with uniform representation and
aliasable references all over the place (think python lists or java
Vectors), we may be confused into believing this:

type T1 = @[mut T]

-is actually something like this:

type T2 = @{ mut v: @[mut @T] }

Basically I believe T2 is similar to a python list reference, which I
believe contains a sequential array of references.  Lengthening the
array may involve reassigning v to a new address, but in python land
all references to the list are a T2 (whose value is an address), not
the address in v.

Also, in T2 every element is itself a reference, and each of these
references may be reassigned.  (That's why I have the second "mut".
Is this necessary?)


Is this comparison a. accurate, and b. helpful to those familiar with
java Vectors or python lists?



Nathan Wilcox


More information about the Rust-dev mailing list