but while implementing the enqueue function, i am getting this error
cannot move out of **curr_head which is behind a mutable reference
move occurs because **curr_head has type Box<queue::Node<T>>, which does not implement the Copy trait
/// enqueue via head and dequeue via tail
pub fn enqueue<'b>(&mut self, elem: &'b mut Box<Node<T>>) where 'b: 'a {
// let mut new_node = Box::new(Node::new(elem));
match &mut self.head {
None => {
self.head = Some(elem);
self.tail = Some(elem);
}
Some(curr_head) => {
elem.next = Box::into_raw(**curr_head); // error here
}
}
}
how should i minimize the use of unsafe, and at the same time implement this function?
Please be aware that implementing a linked list when initially learning Rust is usually a mistake, since it is a problematic area in Rust. See here for more about this, including a link to techniques for implementing linked lists in Rust that should answer your question if you really want to proceed anyway.
&Box<T> is T**, and it's a useless type in Rust, because it requires useless ownership (loan of owned T instead of being simplified to loan of T, or a double reference).
Don't confuse Rust's references with pointers or storing by reference. References are temporary loans, usually bound to a scope of a variable they are borrowing from, and their purpose is to forbid storing the data. This makes them completely inappropriate for linked lists and generally highly problematic when used in structs. Box is a reference type that doesn't have the temporary loan baggage.
note that Box is a pointer without use of & or *. Rust has many of these, and also &str and &[] which are structs {ptr,len} passed by value, not plain pointers. Your syntax expectations from C will lead you astray in Rust.
thanks for the tip...
but nodes of graphs also require pointers right...
issue in rust starts when two pointers point to the same address....thats where raw pointers help i guess.... thats why i used it....
@kornel thanks for the insight...
lets forget linked list.... i just need answer for one simple question
lets say i need to have two mutable pointers pointing to a single address (like raw pointers).... this can be achieved safely by using Rc, RefCell, etc,. but this induces a slight overhead in performance than raw pointers...
which is the best approach to implement two mutable pointers to single address with safety and performance in rust?
Indexes can also be used instead of pointers, to avoid unsafe code. The petgraph crate is extremely popular for building various types of graphs. It uses both techniques (pointers and indexes).
There's no single best safe approach to shared mutability (that is having multiple mutable pointers to the same piece of data):
indices work nicely when you can have a central shared structure from which you can borrow the data when you need it (the downside is that you always need mutable access to this shared data structure in order to mutate, moreover disjoint borrows become a problem);
Cell is another nice alternative for when the data you're trying to mutate is Copy, however that's also a pretty big restriction (as a sidenote, I wish this restriction was lifted to types with a "pure" implementation of Clone, like Rc and Arc)
RefCell has a little more overhead but allows you to have fully dynamically checked borrows
GhostCell has less overhead than indicies (no bound checks) but still has the same disjoint borrows problem; moreover its lifetimes are very infectious.
You simply store elements in a Vec and refer to them using their index in the Vec rather than using pointers/references. When you want to mutate you just index into the vec and mutate that value.
I don't have a specific article to point you to, though I remember this blogpost being the one that introduced me to this idea. Since then I've seen it being brought up a lot, so it's basically common knowledge among seasoned Rust programmers.
Now that I think about it I forgot to mention slotmap, which extends this pattern and prevents issues around reuses of indicies.
Implementing data structures in Rust ends up being pretty different from how you'd implement them in C++, even though they're both low-level languages with similar performance characteristics.
In Rust you think about ways to do it without having a general graph of nodes all pointing at each other.
For a double-ended queue, you'd most likely hit on either a two-vectors approach or a ring buffer (which is what VecDeque does). As it happens, these approaches use less memory than a doubly linked list, require fewer allocations, and give better memory locality.
It's certainly possible to do the whole thing as a doubly-linked list, with a safe API, but you'll unavoidably use unsafe code throughout the implementation.
That's not million dollars question, not even billion dollars question, more like trillion dollars question.
The answer is simple yet short: don't. That's just simply NOT POSSIBLE.
Yes, just like that, with capitalization and bold.
Forget about Rust, recall that memory access is not O(1) in today's world.
Each CPU could only change something quickly if it's exclusive owner of that data.
That's just physics, not even math.
That means that if you really need shared mutability you have to accept that you would have some overhead, in general or alternatively would need to adopt some solution that works for some cases but not for all.
That's why there are so many answers: when one, single, one-size-fits-all “best” answer is impossible we have many possibilities because we have to pick different nodes on the “safety/speed” scale.
It is possible. The confusion is caused by a wrong name for the &mut reference, because it's not about mutability, but about exclusive access.
Rust allows shared mutability, when it can't cause data races. &Cell<T> is a pointer, and there can be many of them pointing to the same cell, and being able to mutate the same data.
There's even a handy as_slice_of_cells that converts &mut [T] to &[Cell<T>], which enables mutable aliasing.
If you do that, your CPU cores are start playing ping-pong with cache lines.
This doesn't change what I'm talking about: mutable shared access is slow and unreliable in general, even if Rust is not involved.
There are no silver bullet which would make it possible to go back half-century when even the fastest computer in the world had to had very peculiar form to deal with physical limitations, but could provide two mutable pointers to single address with safety and performance.
At the end of XX century CPUs have become fast enough that it's no longer possible and people that care about speed started avoiding shared mutability because it's both unsafe (it's hard to ensure that your data structure invariants are not broken and it's impossible to make such access fast in an era of CPU cores with gigahertz speeds)
That's why Rust could declare it exceptional situation and offer many tools that handle it: people have already learned that they had to avoid it whenever possible, simply because it couldn't be efficient, but, of course, you couldn't forbid it entirely, on many programs would be impossible to write thus the end result is many tools that Rust offers to deal with it when it's really needed.
But you couldn't go back to what text books written half-century ago tech, to that era of O(1) memory access and/or easily shared memory.
Well, you could, of course, just make CPUs 100 times slower to ensure memory would be fast, in comparison, again… but that's not what people that are seeking two mutable pointers to single address with safety and performance want.
That is unrelated to whether aliased or non-aliased pointers are used in Rust. Rust's pointer uniqueness is not communicated to the CPU. Cell can't be shared between threads anyway (ignoring OS scheduler moving program between cores, which affects &mut the same). As long as aliasing doesn't prevent optimizations, use of shared pointers may not have any effect at all.
mutable shared access is slow and unreliable in general, even if Rust is not involved.
First of all, if you're talking about issues not affected by Rust, then your very strong reaction is not relevant to this discussion. Memory is slow, and hardware pays the cost of supporting shared RAM and consistent caches anyway. That won't change in the foreseeable future.
But shared vs exclusive mutability in Rust is a separate issue. These are abstract concepts that exist in Rust, and aren't directly communicated to the hardware. Rust's exclusive references have many ways of creating problematic memory access patterns that look like shared mutability to the hardware, e.g. byte_slice.par_iter_mut().for_each(|x| *x += 1). Hardware doesn't care if there exist many pointers to the same memory location, and Rust's &mut doesn't even prevent that, because reborrowing can duplicate &mut pointers.
The biggest problem with shared pointers is purely on the software side, where aliased pointers can prevent optimizations (such as autovectorization or elimination of redundant loads). But this is application-specific, and isn't automatically a disaster. For a linked list it may not matter at all, and for slices cells.iter() may be faster than exclusively_owned_slice[i] thanks to elimination of bounds checks.
No, it's not. Rust, in a sense, is XXI century language not because it uses some idea that weren't possible in XX century, but because it piggy-backs in that requirement to reduce shared mutability as much as possible that predates it.
But only serendipity of desire to reduce shared mutability and the acute, pressing need to do the same in a post-O(1) era made Rust viable.
All these software-driven issues were presented and advocated by academy for decades, but people adopted the “reduce shared mutable state as much as possible” mindset only when hardware made them do that.
And after they adopted it Rust have become viable. It was possible to create something like Rust long ago, but it only because feasible when people started avoiding shared mutability like a plague because of different, entirely unrelated to Rust, reasons.
Shared xor mutable is a very useful pattern, but you're grossly exaggerating problems with Cell. You're throwing at it problems with hardware architecture, and generalizations about language design, that are only tangentially related. You're overlooking the fact that shared mutability means different things in different contexts, and one instance of it does not necessarily have all the flaws of all kinds of shared mutability. You're very strongly presenting exclusive access as one true way, with zero subtlety and pragmatism about it.
Specifically, &Cell isn't as damaging as arbitrarily pointers that Hoare was talking about. It still has type safety and lifetimes checked, and can alias only other cells. To continue Hoare's analogy, it's more like a jump with while than a goto.
Note also that the quote you're bringing up is not just about shared mutable access, but also about reference types in general. The fragment prior:
Unlike all other values (integers, strings, arrays, files, etc.) references have no meaning independent of a particular run of a program. They cannot be input as data, and they cannot be output as results. If either data or references to data have to be stored on files or backing stores, the problems are immense. And on many machines they have a surprising overhead on performance, for example they will clog up instruction pipelines, data lookahead, slave stores, and even paging systems.
All of this applies equally to &mut and Box. It's not even wrong. These observations are accurate still true today. And yet, they are useful despite these issues.
You should also check out Hoare's later paper about imperfect pragmatic approaches working, despite not living up to the ideals of formal methods: https://blog.regehr.org/archives/820
