Do we need crossbeam-stack?

[jeehoonkang]

Currently, the crossbeam crate provides the Treiber stack. In order for crossbeam to be backward-compatible as much as possible, when we're rebasing it on top of crossbeam-epoch, I think we need to implement crossbeam-stack.

It can be just the Treiber stack at first, but maybe in the future, we want to implement the elimination-backoff stack or another more advanced stacks. For now, we can just copy-and-paste the code from crossbeam or coco.

[ghost]

I'm in favor of moving the stack into crossbeam-stack. I'd also suggest doing some research and writing simple a RFC for it, which should answer the following questions:

1. In what situations is concurrent stack a useful data structure? How are concurrent stacks typically used, not just in Rust but in other languages as well?
2. What are examples of implementations of concurrent stacks in other languages?
3. What methods should a concurrent stack have?

Here are some additional methods I've thought of that might be useful to have in a lock-free stack:

fn swap(&mut self, other: &Stack<T>);
fn merge_from(&self, other: &Stack<T>);
fn drain(&self) -> Stack<T>;
fn extend(&self, other: impl IntoIterator<Item = T>);
fn into_iter() -> impl Iterator<Item = T>;

.NET provides a concurrent stack. Perhaps we could take some ideas for it? https://msdn.microsoft.com/en-us/library/dd267331(v=vs.110).aspx

And here are some actual uses of TreiberStack on GitHub, although there aren't many: https://github.com/search?l=Rust&q=crossbeam%3A%3Async%3A%3ATreiberStack&type=Code&utf8=%E2%9C%93

[Amanieu]

I use a variant of the Treiber stack in parking_lot: https://github.com/Amanieu/parking_lot/blob/master/core/src/word_lock.rs#L24

However this is a very low-level and customized implementation and it wouldn't make sense to use a generic data structure implementation from crossbeam there.