VecDeque should expose head via head_index() (or similarly named)

1

VecDeque (sensibly) uses indexing to index in queue order, so deque.get(0) is always identical to deque.front(). However, this makes it almost impossible to index consistently into the physical buffer - if you wish to keep a handle to a piece of data inside the deque (and references are out because of borrow-checking limitations), you need to (re)do math on the logical index to remap to the physical index.

Doing this math requires knowing the position of the head of the deque, which the data structure obviously knows. The best way I've found to attempt to track it is this, which has big limitations:

    let mut foo = VecDeque::<i32>::with_capacity(32);
    // Need an element to use front(). AFAICT, there is no way to get a reference to the beginning
    // of the physical buffer without inserting at least one item.
    foo.push_back(0);
    let head: *const i32 = foo.front().unwrap();
    foo.pop_front();
    foo.push_back(10);
    println!("Current head_index is {}", unsafe {
        (foo.front().unwrap() as *const i32).offset_from(head)
    });

Aside from requiring unsafe, this breaks if the buffer is reallocated between capturing head and using it in offset_from(), which may be hard to guard against, depending on your application.

Exposing the head index would be a very simple addition, and I don't think it would lock the data structure into any invariants it doesn't already have. Can we get this accessor?

2

Why are you indexing into the physical buffer instead of reusing get? Your proposed head_index also doesn't survive reallocations.

3

Second part first: Of course head_index() would survive reallocations. Its implementation would simply be

pub fn head_index(&self) -> usize {
  self.head
}

Since reallocations don't invalidate head, they wouldn't invalidate head_index().

I am using get, just from the perspective of physical-relative access instead of logical-relative access. Let me give some more motivating use-cases, which might explain the situation better.

This one is not my use-case, but it is simple to explain. The docs for VecDeque in std::collections - Rust say: "This never needs to re-allocate, but does need to do O(n) data movement if the circular buffer doesn’t happen to be at the beginning of the allocation." However, there is no (safe) way to observe "is the circular buffer at the beginning of the allocation" without my proposed head_index(). as_slices() only lets you observe if the buffer is contiguous, not if it is at the beginning. make_contiguous() also does not guarantee to put the range at the start of the allocation (and doesn't always, in practice).

My actual use-case: I have a mutex-protected circular ring buffer (plus adjacent state) that acts as a communication point for multiple threads. Threads copy a unit of work out of the buffer, unlock and do some heavy processing, and then regain the lock and update the buffer with their results. This involves copying their unit of work back and possibly adjusting adjacent units of work, which is why a vector-like structure is needed and not a mpsc queue.

Being a ring-buffer makes VecDeque the obvious choice for data structure. However, the need to update the same physical index makes this challenging - the unit of work that "belongs" to a thread won't have moved in the physical backing store, but its logical index may have changed because various pop_front operations may have occurred while the thread didn't have the lock. (The invariants of the algorithm guarantee that the thread's work itself will still exist in the deque.)

I can do the physical-to-logical remapping, but as I said in the first post, it requires knowing the head_index. That can be tracked separately (cumbersome, redundant), gotten via unsafe pointer manipulation (the best that can be done today), or an accessor can be added.

4

This isn't part of VecDeque's stable guarantee. It might be true in the current implementation, but it's certainly not "an invariant it already has".

I do think your use case is a reasonable one in abstract, and I don't think it's necessarily wrong to ask for stable identifiers for the items in a VecDeque, which would only be invalidated under certain conditions. I'm not 100% sure this is the API I would use to present that, but if you agree that some other feature with that description would satisfy your needs, maybe people will have additional alternatives? I'm very wary of anything that still requires you to reach directly into the VecDeque's raw storage, even if it can be a checked access.

(Also, I'm not a libs-team member or anything, just another Rust user with ideas.)

5

Maybe I'm not sure what you mean by would/wouldn't invalidate head_index()?

I'm not claiming that head_index() never changes across a reallocation. Indeed, in certain shrink_to_fit scenarios I'm pretty sure that it must. But the old value is not "invalid" in the sense of pointer invalidation - it's still a valid number, although it won't be correct for use in indexing operations.

But that is the whole point of head_index() - you don't expect it to be stable because you don't want it to be. What you want to be stable is the value (current_logical_item_index + head_index()) % capacity() - because that's the physical index. And I believe that stability is guaranteed right now, within certain limitations (no using make_contiguous, no reallocations). You can even get stable identifiers across reallocations, although it might be relying on reasonable implementation details instead of explicitly guaranteed properties.

Edit: And yes, I'd take anything else that gave similar access to stable identifiers. This just seemed like the obviously simplest approach, that doesn't impose additional constraints or lots of extra baggage on the type.

6

Except it's not, from the perspective of a particular VecDeque you could have done any number of .pop_front/.push_front/whatever operations in between acquiring current_logical_item_index and using it.

Taking a step back, what you're describing is a separate datastructure. With a little extra bookkeeping and some judicious use of VecDeque::as_slices it is reasonable functionality to implement on top of a VecDeque, but I don't think introducing indexes makes sense for the version in std.

7

current_logical_item_index is not meant to be a storage location, but a shorthand for an operation that doesn't have a simple function. It is the inverse of get() - it is element_offset(), if that existed on VecDeque. (That would have been better wording.)

The fact that you mention as_slices makes me think you don't understand my usecase. What I would implement would never use as_slices, since that defeats the whole purpose of using a VecDeque. I would be using get and/or indexing, only - but adjusted by an offset so that I could stably refer to specific items.

Taking a step back, as you say: VecDeque is a random-access collection. You can access the elements by index, but this index is (necessarily) relative to the start of the buffer. If the start moves, the indices move (relative to the items). The only thing preventing you from continuing to access the same item is knowing where the start is.

8

Ah. You can get the start of the buffer with deq.as_slices().1.as_ptr_range().start, so:

unsafe { // SAFETY: this isn't safe.
let (head, tail) = deq.as_slices();
let start_of_buffer = tail.as_ptr_range().start;
let head = head.as_ptr_range().start;
let head_index = head.offset_from(start_of_buffer) as usize;

// Later we can get it back by that index
let start_of_buffer = deq.as_slices().1.as_ptr_range().start;
let head = &*(start_of_buffer.add(head_index));
}

An empty tail pointing to the front of the buffer is not guaranteed. But if we pretend for a moment that it is guaranteed, can you write a concrete version of the API you're proposing? If it's just returning head_index as above, it doesn't seem useful in the face of any sort of mutation. But if it's some more complicated struct, maybe.

9

Wouldn't an Arena be a better data structure for that?

10

No? An Arena has basically none of the properties I want - it is neither a ring buffer, nor does it provide access to adjacent elements.

"An empty tail pointing to the front of the buffer is not guaranteed" is exactly the problem I have - plus the fact that your approach (like my initial one) requires unsafe, and in your case is relying on undocumented implementation details.

The point of head_index() is that it does change with mutations. Since element_offset() + head_index() remains fixed for a given item (within certain limitations, such as no make_contiguous or shrink_to_fit), in my application I would record this value as physical_idx when I first get the item under the mutex. Later, when I have reacquired the mutex I would assign let current_idx = (physical_idx - head_index() + capacity()) % capacity. Now I can get(current_idx), as well as look up adjacent items with simple arithmetic. (Modular arithmetic/bounds checking isn't needed anymore - as long as I can guarantee that the items I am looking for exist, adding/subtracting from current_idx won't have issues.)

11

I think the problem is that you want control/inspection into the internal workings of this datastructure. Access to head index alone isn't enough. There is no equivalent accessor for it. deq.get(0) is the same as deq.front(), and indexing works well enough from that.

Essentially what you're requesting is for VecDeque to open up a very narrow part of what it guarantees to the outside world, via some API.

This can be reasonable! Vec is a very useful building block for other datastructures. But sometimes implementing a datastructure on top of another datastructure requires being able to dig into its implementation, and requires the building block datastructure to guarantee more about exactly how it works. For Vec this API looks like RawVec, but it also takes the form of into_parts/from_parts/into_raw_parts/from_raw_parts.

I don't think it would be unreasonable for VecDeque to guarantee its whole implementation and expose its internal bits so that it can be used as a better building block for more complicated datastructures. I also don't think that API would look like pub fn head_index(&self) -> usize.

12

I don't think I'm trying to peer into implementation details here. I explicitly don't want to mess around with internals, in the sense that I want to avoid things like unsafe and as_ranges.

The things that I want guaranteed are already guaranteed:

  • pop_front increases head_index by one. (Guaranteed by VecDeque being a ring buffer. The existence of as_ranges forces this to be an increment, and not a decrement, since ranges have a direction built-in.)
  • push_front decreases head_index by one.
  • pushing doesn't reallocate if there is space. (I believe this is already guaranteed by with_capacity)
  • The items aren't moved, aside from methods that explicitly say they will. (Methods that talk about their running time are nonsensical without this.)
  • get() operates over the elements linearly, wrapping at the end of the buffer. (This is guaranteed by the requirements of push and pop - since they add items sequentially, it follows that get(1) must be next to get(0), modulo capacity. This is also guaranteed by the existence of as_ranges.)

Given those things, all that's needed is access to head_index. If there's a flaw in my reasoning, I'd like to know where.

Edit: In the posts above, I have mentioned physical_idx, and perhaps that confused you? Although it's true that that is the location in the physical backing store, I don't actually care about that fact. All I care about is that it is a stable value that I can use to recover a logical index from, later. I believe the stability of it is already guaranteed by the points I outlined above.

13
  • pop_front could reset the head to 0 if that was the last item.
  • push_front could keep the head at 0 if this is the first item.

We don't do either of these things now, if only because they would need extra branches, but it would be within the realm of our stated guarantees.

2 Likes
14

That would be fine for me - if there are no items to reference, there can't be any stable identity needed. This is similar to how clear sets head to 0, but is not obligated to.

However, I take your point that it feels awkward to expose an accessor to something that has intentionally loose guarantees on its values.

15

Those two could also occasionally re-rotate the internal buffer if they wanted. We don't seem to explicitly document complexity guarantees, but even if we did, amortized constant time could be achieved if the re-rotation is done rarely enough I think. And asymptotic constant time could be achieved if the re-rotation is only done when the size is below some constant value such as 2 or 5 or 1000.

That would be silly, but the point many are making in this thread is that you're asking for a lot more implementation details to be exposed than what the documentation currently talks about.

FWIW, you can get a stable physical location identifier without new APIs and in safe code with something like ptr::from_ref(foo.get(0)).addr(). That changes when the VecDeque is resized, but the same is true for head_index so that shouldn't be a problem. I haven't understood your use-case well enough to judge whether that is of any use to you. (I tried, but it seems extremely strange and unlike anything I've seen before. And I've seen my share of concurrent data structures.)

There's a trivial safe replacement for your unsafe snippet -- just cast to integer (or better, use addr()) and do the subtraction there.

1 Like
16

Ah, of course! Although it needs to use sizeof to work properly, at least it can be done.