Stream: t-lang/wg-unsafe-code-guidelines

Topic: "fixed" vector


gnzlbg (Nov 29 2018 at 13:38, on Zulip):

I wrote a vector with O(1) push (non-amortized), for which self.push(x) does never invalidate any references to any vector elements. I was wondering if I can exploit this somehow for a better API.

gnzlbg (Nov 29 2018 at 13:39, on Zulip):

AFAICT the answer is no: the API of Vec::push cannot be improved if one adds to it the guarantee that it never invalidates any references to any pre-existing vector elements

RalfJ (Nov 29 2018 at 13:42, on Zulip):

you could have a push(&self)

RalfJ (Nov 29 2018 at 13:43, on Zulip):

would require some UnsafeCell somewhere, for the length field or whatever other metadata you have

gnzlbg (Nov 29 2018 at 13:43, on Zulip):

The only "improvement" that I would think worth pursuing here is changing push to push(&self, T) instead of &mut self.

gnzlbg (Nov 29 2018 at 13:43, on Zulip):

But doing so comes at the cost of making &Vec<T>: !Sync.

gnzlbg (Nov 29 2018 at 13:47, on Zulip):

@RalfJ yeah, i was thinking along those lines, but then I can't make &Vec<T>: Sync without adding internal synchronization right ?

RalfJ (Nov 29 2018 at 13:47, on Zulip):

yeah

gnzlbg (Nov 29 2018 at 13:47, on Zulip):

e.g. that would allow two concurrent threads to call push(&self), and they would modify the length concurrently and append elements in some order

RalfJ (Nov 29 2018 at 13:48, on Zulip):

you could also have an iterator that supports insertion. Like, have a push method on the iterator. not sure if that's useful.

gnzlbg (Nov 29 2018 at 13:48, on Zulip):

yeah, this iterator would then just be !Sync

rkruppe (Nov 29 2018 at 13:51, on Zulip):

there are a lot of vague proposals floating around for annotating methods or their parameters with "what parts of the struct" they access. those variants which don't tie this to fields but introduce a more abstract notion of "disjoint pieces of this value" could maybe allow signatures that say "push needs exclusive access to the Vec's len+capacity but no access to its elements" and "get needs shared access to all of the Vec" which is a bit more precise

gnzlbg (Nov 29 2018 at 13:51, on Zulip):

that might be useful:

let mut vec: MyVec;
let it = vec.iter();
for i in it {
  if foo(i) {
    it.push(baz(i));
  }
}
rkruppe (Nov 29 2018 at 13:53, on Zulip):

um, actually, to get anything out of that separation you need different lifetimes for the access to the len+cap vs the access to the elements (e.g. to allow pushing while holding references to elements)

gnzlbg (Nov 29 2018 at 13:55, on Zulip):

@rkruppe only shared references are involved there

rkruppe (Nov 29 2018 at 13:55, on Zulip):

I am talking about an alternative where you don't use UnsafeCell and are thus still Sync

gnzlbg (Nov 29 2018 at 13:55, on Zulip):

Ah!

rkruppe (Nov 29 2018 at 13:56, on Zulip):

(assuming a very far-fetched future language feature)

gnzlbg (Nov 29 2018 at 13:56, on Zulip):

yeah, I don't think that's possible right now, I am not sure if that would be possible with such a feature either

gnzlbg (Nov 29 2018 at 13:57, on Zulip):

even if capacity is not mutated, if the type is Sync, and push(&self), then two threads can insert into the vector concurrently, so they have to mutate len and the data behind ptr atomically

gnzlbg (Nov 29 2018 at 13:58, on Zulip):

so AFAICT that would need some kind of extra synchronization

rkruppe (Nov 29 2018 at 14:12, on Zulip):

push would take a mutable reference _to the len+capacity_, without touching the elements. then if get() only touches len+capacity during the get() call and the long-term loan tied to the returned reference only covers the elements, you can push while having

gnzlbg (Nov 29 2018 at 14:15, on Zulip):

:s i'm not sure I fully follow how that would work, if push takes a mutable reference to the length and capacity, then you can't call it concurrently via &Vec, right ?

rkruppe (Nov 29 2018 at 14:19, on Zulip):

Well yeah, you need &mut Vec. But you can take references to the elements of the vec -- in straw syntax this borrows (*vec).$elements -- while still pushing to it -- which borrows only (*vec).$metadata in straw syntax.

rkruppe (Nov 29 2018 at 14:19, on Zulip):

In the same way you can currently have p: &mut Point where struct Point(i32, i32); and borrow p.0 while modifying p.1

gnzlbg (Nov 29 2018 at 14:21, on Zulip):

Ah, yeah, i was thinking about something else.

gnzlbg (Nov 29 2018 at 14:22, on Zulip):

That would be cool, and it would be nice for my vector, because push does not invalidate references.

rkruppe (Nov 29 2018 at 14:25, on Zulip):

however this is a very elaborate version of a feature that people are already reluctant to introduce in its simplest forms because it seems niche and rather complex for what it enables. though perhaps this sort of data structure is a convincing motivating example?

gnzlbg (Nov 29 2018 at 14:26, on Zulip):

No I don't think so. If this would work for Vec, then that might be a motivating example, but because Vec::push invalidates all references, then this cannot work there. A Vec that never invalidates references of push is certainly useful, but too niche.

RalfJ (Nov 29 2018 at 14:30, on Zulip):

yeah, this iterator would then just be !Sync

I was thinking of IterMut, and its push method could take &mut self, so it could still be Sync

gnzlbg (Nov 29 2018 at 14:31, on Zulip):

then I don't follow, I thought the goal was inserting into the vector via the iterator while iterating. If it is IterMut, then it returns &mut T, so one cannot call push(&mut T) through the iterator while having a &mut T to an element inside the loop, or what am I missing? Maybe some pseudo-code would be helpful.

RalfJ (Nov 29 2018 at 14:32, on Zulip):

IterMut::next returns a long-lived &mut, doesn't it?

RalfJ (Nov 29 2018 at 14:32, on Zulip):

https://doc.rust-lang.org/beta/std/slice/struct.IterMut.html#method.next

RalfJ (Nov 29 2018 at 14:32, on Zulip):

mind the lifetime

RalfJ (Nov 29 2018 at 14:33, on Zulip):

so, let f = it.next(); it.push(...); *f = 5; is actually allowed

gnzlbg (Nov 29 2018 at 14:33, on Zulip):

ah the lifetime of &mut T does not have anything to do with the lifetime of the iterator

RalfJ (Nov 29 2018 at 14:33, on Zulip):

just like let f1 = it.next(): let f2 = it.next(); *f1 = 5; is allowed

gnzlbg (Nov 29 2018 at 14:34, on Zulip):

yeah, that sounds good

RalfJ (Nov 29 2018 at 14:34, on Zulip):

the more ergonomic variant would probably be an iterator yielding cursors that DerefMut to T but also can push, or so

RalfJ (Nov 29 2018 at 14:34, on Zulip):

so that you can still do for ... in

RalfJ (Nov 29 2018 at 14:34, on Zulip):

but that's a detail

Last update: Nov 20 2019 at 13:00UTC