Roadmap

[ghost]

This is the first RFC. It proposes an overall strategy and points of focus for the near future.

Rendered

Reviewers, please accept the PR when you don't have any objections blocking the proposal.

[jeehoonkang]

Thank you for leading us! It is a very detailed and plausible roadmap. I hope this will be the first accepted RFC. I generally agree with your roadmap, but I have some comments.

I have a different viewpoint on the targeted users of the Crossbeam library. (Let's focus on the core, not on the data structures built on top of it.) IMO, it is the users who are implementing non-blocking data structures and should reason about the race-freedom and the correctness (e.g. linearizability) of the data structures. So I think Crossbeam API should be opted for flexibility and optimization, rather than ease of use (of course it's better to have all, but I am talking about the priority). Note that this is a generalization of the discussion on the Atomic API (https://github.com/stjepang/coco/pull/2) @stjepang and I had.

I like the alternative "holistic approach" (Drawbacks and alternatives). Provided that a data structure is proven correct and well-tested, I have no reason to accept it. (I don't have a particular opinion on whether to create a sub-crate or not.) Yes, in this case, we need to provide a detailed guideline for data structure users, who may not use the Crossbeam core and not be experts on concurrency.

Having said of time estimation, it would be nice if we could say how to do it: how to reach a decision? who will implement/review/merge a proposed change? IMO we can stick to some ad-hoc administration because we don't have too many people right now..

[arthurprs]

I see crossbeam akin to what tokio-core & futures are for async io. So something more barebones with a sound atomic api and 1 or 2 memory reclamation algorithms.

Otherwise, how we define what goes in the crate and what goes out? That's a hard and opinionated matter. I could get behind providing the most common/useful data-structures though.

But for example, a selectable mpmc is not a data-structure (queue != channel) as it also involves blocking threads and a select interface. So a channel should probably live outside IMHO. Maybe one day crossbeam could evolve and also expose a select interface and then it could be brought in along with that (same reasoning for the data-structures).

[ghost]

So I think Crossbeam API should be opted for flexibility and optimization, rather than ease of use (of course it's better to have all, but I am talking about the priority).

Agreed. The core is intended for advanced users anyway, so it's important for it to allow as much flexibility and optimization as could possibly be needed. Regarding the Atomic API, we'll figure out an API that doesn't sacrifice performance.

The "performance second" sentiment was expressed more in the context of higher-level data structures. An interesting phenomenon about this area of research is that you can find a ton of materials on lock-free programming on the internet, even a lot of proof-of-concept implementations, but at the same time very few implementations that are accessible to mere mortals and actually usable. :) I think this is the biggest challenge: making stuff practical and accessible.

Having said of time estimation, it would be nice if we could say how to do it: how to reach a decision? who will implement/review/merge a proposed change? IMO we can stick to some ad-hoc administration because we don't have too many people right now..

I'll follow up with several RFCs so that we can have a discussion on the upcoming milestones. I think for now we can stick with an ad-hoc approach and talk about it in the IRC channel. :) As soon as we improve the core of Crossbeam, splitting the work will get much eaiser.

I see crossbeam akin to what tokio-core & futures are for async io. So something more barebones with a sound atomic api and 1 or 2 memory reclamation algorithms.

That sounds reasonable.

Otherwise, how we define what goes in the crate and what goes out? That's a hard and opinionated matter.

How about splitting Crossbeam into the following crates?

• crossbeam-core - scoped threads, epoch GC
• crossbeam-channel
• crossbeam-deque
• crossbeam-skiplist

and so forth. Those crate names are a bit verbose, though. :)

[arthurprs]

We can bike-shed naming at a later point but that's doable despite being a bit long.

Two other benefits of splitting crates:

• improved discoverability, as they're indexed better in crates.io (meaningful names, more tags)
• more user friendly (user is not exposed to the entire crossbeam ecosystem and they also don't fell that they're pulling unnecessary stuff into the binary)

[aturon]

@stjepang This is a beautifully-written RFC; thanks for starting us off with such a strong first step!

I agree with the basic roadmap laid out here, and in particular with the selection of the first data structures/channel abstractions to provide. I would probably defer work on select to a later phase, but think the rest is spot on.

I'm also a fan of thinking of Crossbeam as a project/organization, rather than a single crate. The split you propose (with crossbeam-core, crossbeam-deque etc) sounds great. The key is that all of these crates are collectively under the same umbrella and RFC process, so that we can impose some global constraints (e.g., making sure not to provide too many highly similar data structures, as you mention). A couple of further thoughts here:

• We might want to go with crossbeam-epoch rather than crossbeam-core, since we intend to explore other memory-management options.

• We should reserve the crossbeam crate name for, potentially, a crate that gathers together the "most common" concurrent data structures -- a bit akin to std::sync.

• Over time, we'll need to think about the purview of the Crossbeam project as a whole. My hope was for it to become a centralized place to do all kinds of scalable concurrent data structures, not tied to any particular methodology. I think that aligns well with the long-term ideas you sketch out.

Finally, while this doesn't need to be reflected in the current RFC, I'd strongly advocate for tackling some concurrent map next after the milestones you've given. I think that's the next most commonly requested data structure.

Thanks again for the great work! I'm so delighted by the way things are heading.

[arthurprs]

That's a very good point, separating crossbeam-epoch into another crate. I guess core will end up only having the Atomic interface.

[ghost]

@aturon Thanks for the kind words! :) I agree with all your comments.

Finally, while this doesn't need to be reflected in the current RFC, I'd strongly advocate for tackling some concurrent map next after the milestones you've given. I think that's the next most commonly requested data structure.

If you perhaps know who needs a map and what for, that'd be of great help. I'm always looking for concrete use cases to study them.

[nikomatsakis]

It'd be interesting to have some way to survey what kinds of things people are looking for. For example, I was surprised (for some reason...) to hear that so many people want an MPMC channel; it's nothing I've ever wanted, I guess. (Unlike say flat-combining...)

[ghost]

@schets Any comments on this? Can we merge the RFC?