Yes, it is. But why 'the worst' aspects of each, though? I see it as the opposite: linked lists built on top of vectors combine good cache efficiency of vectors with algorithmic benefits of linked lists (many operations become O(1), or at least in the amortized sense).
Of course, arenas do have tradeoffs - I'll try to summarize.
Pros:
- Completely safe.
- More ergonomic than dealing with `Rc<RefCell<T>>`.
- Improved cache efficiency of linked data structures.
- Fast node allocation and deallocation.
Cons:
- Any two simultaneous node accesses must be immutable.
- Accessing a node incurs the cost of a bound and liveness check.
- Vector growth can be costly and cause a spike in latency.
- Vector growth moves all nodes in memory.
- Removing a node creates a hole in the vector, possibly wasting memory.
Generally speaking, I think anyone learning Rust and trying to implement a graph data structure should first do it on top of a vector. It's easier than other commonly suggested approaches and it's not a bad one either. In fact, that's how rustc builds some of its data structures, how conrod (a GUI toolkit) represents its widget graph, and how Way Cooler (a window manager) manages window tilings.
It's fairly easy to do this kind of thing using an arena and indices instead of pointers. Here's a simple splay tree with uplinks implemented this way:
Absolutely - there are cases when branch misprediction is not the bottleneck. It depends on a lot of factors.
Another such case is when sorting strings because every comparison causes a potential cache miss and introduces even more branching, and all that would dwarf that one misprediction.
If comparison is cheap (e.g. when sorting integers), pdqsort wins because it copies less data around and the instructions are less data-dependency-heavy.
If comparison is expensive (e.g. when sorting strings), timsort is usually a tiny bit faster (around 5% or less) because it performs a slightly smaller total number of comparisons.
Author here. Yes, this is an interesting problem TimSort used to have. A counterexample to incorrect TimSort is sequence "120, 80, 25, 20, 30". This simple sequence could have been easily discovered by generating sequences randomly and verifying that the TimSort invariants hold on it. The fact that it took 13 years to discover the bug (using formal verification!) is just silly :)
Fortunately, the problem is easy to fix and there's a brief mention of it in the comments: https://is.gd/txKd4I
To transfer ownership, you would wrap the object in Mutex<T>, send it via Sender<T>, use some other synchronization primitive, or simply pass it over at the moment the thread is spawned.
It's up to the synchronization primitives to ensure memory barriers are executed, not the language. So e.g. a Mutex<T> would execute a memory barrier when locking and unlocking. Rust then allows you to pass ownership in a trusted manner only, i.e. through those primitives.
Of course, you can also create an unsafe block and say: "Rust, trust me, I know what I'm doing, don't bother me, and these are the invariants I want you to enforce in safe code..." Mutexes are implemented this way.
If your function returns Result<T, Box<Error>>, then you can use try! or ? operator to return any kind of error. It will be automatically boxed and converted into the generic Box<Error>.
This works for two reasons:
1) try! and ? don't simply return Err(err) on error case as one might think. They actually return Err(From::from(err)).
2) The standard library has: impl<'a, E: Error + 'a> From<E> for Box<Error + 'a> { ... }