Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement tagged atomics #1

Open
lorentey opened this issue Oct 1, 2020 · 0 comments
Open

Implement tagged atomics #1

lorentey opened this issue Oct 1, 2020 · 0 comments
Labels
enhancement New feature or request

Comments

@lorentey
Copy link
Member

lorentey commented Oct 1, 2020

This package needs to provide convenient support for tagged atomics, where each atomic value carries some additional information (a version counter, a set of bit flags, etc.). Concurrent data structures tend to heavily rely on the ability to encode extra bits into atomic values to e.g. fight ABA issues or to mark obsolete-but-not-yet-unlinked nodes, etc.

This is especially important for atomic pointers, whose use cases are very limited without a way to augment their values with a version number and/or some other flags.

Ideally this would fit into the existing generic infrastructure, perhaps with a syntax like the tagged optional pointer below:

struct Foo { ... }
let taggedPointer = ManagedAtomic<Tagged<UnsafeMutablePointer<Foo>?, Int>>(nil, 0)

Most but not all tagged atomic values correspond to untagged values that implement single-word atomics.

The crucial exceptions are atomic strong references -- these are a particularly important special case, so they need to be tackled in the same effort, although they may end up requiring custom one-off APIs. (The number of bits available for custom tags in atomic strong references is limited by the fact that regular strong references are already double-wide constructs. This may prove too limiting to handle in a single unified Tagged construct. But a design that manages to do it would deserve bonus points!)

One straightforward option is for Tagged<Left, Right> is to require both Left and Right to be single-word AtomicValue types. Sadly this would require a separate type for tagged references.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant