Removing *_owned methods

[ghost]

Have a look at the following methods on Atomic<T> we currently implement:

Click to expand

impl<T> Atomic<T> {
    pub fn store(&self, new: Ptr<T>, ord: Ordering) {
        self.data.store(new.data, ord);
    }

    pub fn store_owned(&self, new: Owned<T>, ord: Ordering) {
        let data = new.data;
        mem::forget(new);
        self.data.store(data, ord);
    }

    pub fn swap<'scope>(&self, new: Ptr<T>, ord: Ordering, _: &'scope Scope) -> Ptr<'scope, T> {
        Ptr::from_data(self.data.swap(new.data, ord))
    }

    pub fn compare_and_set<'scope, O>(
        &self,
        current: Ptr<T>,
        new: Ptr<T>,
        ord: O,
        _: &'scope Scope,
    ) -> Result<(), Ptr<'scope, T>>
    where
        O: CompareAndSetOrdering,
    {
        match self.data.compare_exchange(
            current.data,
            new.data,
            ord.success(),
            ord.failure(),
        ) {
            Ok(_) => Ok(()),
            Err(previous) => Err(Ptr::from_data(previous)),
        }
    }

    pub fn compare_and_set_owned<'scope, O>(
        &self,
        current: Ptr<T>,
        new: Owned<T>,
        ord: O,
        _: &'scope Scope,
    ) -> Result<Ptr<'scope, T>, (Ptr<'scope, T>, Owned<T>)>
    where
        O: CompareAndSetOrdering,
    {
        match self.data.compare_exchange(
            current.data,
            new.data,
            ord.success(),
            ord.failure(),
        ) {
            Ok(_) => {
                let data = new.data;
                mem::forget(new);
                Ok(Ptr::from_data(data))
            }
            Err(previous) => Err((Ptr::from_data(previous), new)),
        }
    }
}

It's interesting that swap_owned is missing, although it is not stricly speaking necessary: a.swap_owned(o, ord, scope) would be equivalent to a.swap(o.into_ptr(scope), ord, scope). But, for the sake of consistency and convenience, we should probably have swap_owned as well.

There's a lot of duplication. We have one set of functions for Ptr and another for Owned. Let's try to unify them. First, we could introduce a trait that is implemented by Ptr and Owned:

/// A trait implemented by `Owned<T>` and `Ptr<T>`.
pub trait OwnedOrPtr<T> {
    fn into_data(self) -> usize;
    unsafe fn from_data(data: usize) -> Self;
}

impl<T> OwnedOrPtr<T> for Owned<T> {
    fn into_data(self) -> usize {
        let data = self.data;
        mem::forget(self);
        data
    }

    unsafe fn from_data(data: usize) -> Self {
        Owned::from_data(data)
    }
}

impl<'scope, T> OwnedOrPtr<T> for Ptr<'scope, T> {
    fn into_data(self) -> usize {
        self.data
    }

    unsafe fn from_data(data: usize) -> Self {
        Ptr::from_data(data)
    }
}

Second, let's clarify the return value of compare_and_set_owned. Instead of returning

Result<Ptr<'scope, T>, (Ptr<'scope, T>, Owned<T>)>

we could return something like

Result<Ptr<'scope, T>, CompareAndSetError<'scope, T>>

But let's make the error type a little bit more generic:

pub struct CompareAndSetError<'scope, T: 'scope, N> {
    /// The previous value in the `Atomic<T>`.
    pub previous: Ptr<'scope, T>,
    /// The new value that the compare-and-set operation failed to write.
    pub new: N,
}

Finally, now we're ready to eliminate all those *_owned functions. The new set of store/swap/compare-and-set functions is much smaller than the one at the beginning of this comment.

impl<T> Atomic<T> {
    pub fn store<N>(&self, new: N, ord: Ordering)
    where
        N: OwnedOrPtr<T>,
    {
        self.data.store(new.into_data(), ord);
    }

    pub fn swap<'scope, N>(&self, new: N, ord: Ordering, _: &'scope Scope) -> Ptr<'scope, T>
    where
        N: OwnedOrPtr<T>,
    {
        Ptr::from_data(self.data.swap(new.into_data(), ord))
    }

    pub fn compare_and_set<'scope, N, O>(
        &self,
        current: Ptr<T>,
        new: N,
        ord: O,
        _: &'scope Scope,
    ) -> Result<Ptr<'scope, T>, CompareAndSetError<'scope, T, N>>
    where
        N: OwnedOrPtr<T>,
        O: CompareAndSetOrdering,
    {
        let new_data = new.into_data();
        match self.data.compare_exchange(
            current.data,
            new_data,
            ord.success(),
            ord.failure(),
        ) {
            Ok(_) => Ok(Ptr::from_data(new_data)),
            Err(previous) => Err(CompareAndSetError {
                previous: Ptr::from_data(previous),
                new: unsafe { N::from_data(new_data) },
            })
        }
    }
}

The obvious downside is that the OwnedOrPtr<T> trait makes function signatures slightly more complicated. But maybe it's not too bad...? Maybe it's worth it in the end? What do you think?

[jeehoonkang]

How about removing all *_owned() methods, but leaving others as-is?

First of all, in my experience, *_owned() methods are not actually very useful. For example, store_owned() doesn't give you a Ptr back, but you will most likely need a Ptr to the stored object. compare_and_set_owned() gives you Owned<T> when it fails, but you will most likely retry the CAS with the Owned<T>. In this case, it's not that useful to have Owned<T> instead of Ptr<T>.

Second, if you really need a *_owned() method's functionality, which I guess will be rare, you can encode it with Owned::into_ptr() and Ptr::into_owned(). You may need to additionally use unsafe functions (i.e. unprotected() for getting a scope for Owned::into_ptr() and Ptr::into_owned() itself), but I guess that's probably fine.

[ghost]

It is true that store_owned and swap_owned are very rarely used. In fact, I don't think we've ever used those yet.

But I definitely don't want to give up on compare_and_set_owned. This one is handy when you want to install a node in a CAS loop, but don't know for sure if you'll really install it in the end. For example, that is the case when you want to insert something into a skiplist:

fn insert(&self, key: K, value: V) {
    epoch::pin(|scope| {
        let (found, mut left, mut right) = self.search(&key, scope);
        if found {
            return;
        }

        let height = self.random_height();
        let mut new = Owned::new(Node::new(key, value, height));

        let p = loop {
            new.tower[0].store(right[0], Relaxed);
            match left[0].tower[0].compare_and_set_owned(right[0], new, SeqCst, scope) {
                Ok(p) => break p,
                Err((_, n)) => new = n,
            }

            let (found, l, r) = self.search(&new.key, scope);
            if found {
                // Here, `new` is automatically destroyed.
                return;
            } else {
                left = l;
                right = r;
            }
        };

        // Continue building the tower of `p`...
    })
}

I think the only reason we haven't needed compare_and_set_owned yet is because we've only touched stacks, queues, and deques. It will be useful with sets/maps/etc.

[jeehoonkang]

In your use case, why not first converting an Owned into Ptr, and then loop until you successfully CAS on the Ptr?

[ghost]

It's possible, but then I have to manually destroy the Ptr (new.into_owned()) at the line // Here, `new` is automatically destroyed. This is like the difference between smart pointers and manual malloc/free.

Another nice thing about Owned I forgot to mention... It gives you mutable access to the data before you install the node. For example, I envision someone might implement delta chain consolidation in a Bw-Tree like this:

let mut new = Owned::new(Node::new(Block::new()));
self.traverse_chain(&mut new.block, node, scope);

loop {
    match page.node.compare_and_set_owned(node, new, SeqCst, scope) {
        Ok(_) => return,
        Err((prev, n)) => {
            node = prev;
            new = n;
        }
    }

    // The CAS operation failed. Now we have to traverse the delta chain from scratch and refill
    // the block.

    // Here we have mutable access to `new.block`, which wouldn't be possible with `Ptr`.
    new.block.clear();
    self.traverse_chain(&mut new.block, node, scope);
}

[jeehoonkang]

I'm convinced with your "delta chain consolidation" example (of which I don't know the details, though).

I would suggest:

• removing store_owned() and swap_owned() (or not introducing it), as it seems they are not that necessary. CAS differs from them because it may fail, in which case the result depends on the input object.

• leaving both compare_and_set() and compare_and_set_owned() as-is. I think the difference between them is big enough that we can expose two methods.

• introducing CompareAndSetError, as it's clearer than the current API.

After reading the current API, I'd like to suggest one more API change to CAS. How about using struct CompareAndSetOrdering instead of trait CompareAndSetOrdering? The struct is basically a tuple of two orderings, one of which is for the success case and the other for the failure case. For ergonomics, we implement Into<CompareAndSetOrdering> for Ordering. Then we can remove where O: CompareAndSetOrdering from the CAS methods. I think this change a little bit simplifies the API, while not incurring the runtime overhead after compiler optimizations.

[ghost]

introducing CompareAndSetError, as it's clearer than the current API.

Would CompareAndSetError be returned by compare_and_set_owned only, or also by compare_and_set?

For ergonomics, we implement Into for Ordering.

I guess we would implement it for (Ordering, Ordering) as well, right?

Then we can remove where O: CompareAndSetOrdering from the CAS methods.

Does this mean one would have to write a.compare_and_set(b, c, SeqCst.into(), scope)? Or do we keep O: Into<CompareAndSetOrdering>?

[jeehoonkang]

• CompareAndSetError seems a clearer interface for both compare_and_set and compare_and_set_owned.

• On SeqCst.into(): I was confused with the Into trait. I thought incorrectly that a.compare_and_set(b, c, SeqCst, scope) would work. If we need to put .into() every time, it's not that ergonomic, I think.

  In any case, I think Into<CompareAndSetOrdering> for (Ordering, Ordering) is not necessary. Specifying both success and failure ordering is an advanced API usage, and I think we can mandate users to use CompareAndSetOrdering in this case.

[ghost]

I'm a bit torn on this. On one hand, it is true that store_owned and swap_owned are not very commonly used. After giving it some thought, I'd even be okay with getting rid of store_owned.

But on the other hand, if store and swap could accept both Ptr and Owned, that'd just be really neat. :) Then Owned would be a first-class citizen in Atomic's API and not just "that thing used in compare_and_set_owned".

@Vtec234, what do you think about all this?

In any case, I think Into<CompareAndSetOrdering> for (Ordering, Ordering) is not necessary. Specifying both success and failure ordering is an advanced API usage, and I think we can mandate users to use CompareAndSetOrdering in this case.

I'm afraid that would get a little bit too verbose:

let ord = CompareAndSetOrdering {
    success: SeqCst,
    failure: Relaxed,
};
a.compare_and_set(b, c, ord, scope);

C++ solves this problem simply by using overloaded compare_exchange_{weak,strong} functions. I see the way we currently accept both (Ordering) and (Ordering, Ordering) as just some kind of imitation of function overloading.

[jeehoonkang]

Sorry for delay :)

• Yes, creating a CompareAndSetOrdering on our own hand is a little bit verbose. Now I like the current interface for CompareAndSetOrdering.

• On OwnedOrPtr: I feel the name is a little bit verbose. I like the idea of trait for from_data() and to_data().

  Can we rename things a little bit? I'd propose renaming (Ptr, OwnedOrPtr) into (Shared, Ptr). Anyway, Owned is also a pointer :)

[ghost]

On OwnedOrPtr: I feel the name is a little bit verbose.

Maybe. But I don't think a user will ever have to explicitly type it, just like they don't have to type a CompareAndSetOrdering (which is even longer). The trait is only used as a bound on generic methods.

Can we rename things a little bit? I'd propose renaming (Ptr, OwnedOrPtr) into (Shared, Ptr). Anyway, Owned is also a pointer :)

I was actually thinking of the same thing - that would be a very nice naming scheme. :)
But maybe I would also change Ptr to Pointer - it's a rarely used concept so it doesn't benefit from a very short name, especially not shorter than Owned and Shared.

[jeehoonkang]

I agree. Let's go for Shared and Pointer :)

[Vtec234]

I'm okay with the changes as long as the API stays as expressive as it is, i.e. nothing that was previously possible becomes impossible or appreciably more difficult to express. One thing to note is that Shared will conflict with std::ptr::Shared, but arguably that type isn't very widely used. The tradeoff here seems to be whether we want a few more specific methods or a few less generic ones, so probably generic is the way to go, since it will make it easier to possibly add new types later.

[jeehoonkang]

By the way, I think it's better to resolve this issue before reaching 0.1.0, because it will break API too much :) If we're agreed upon the changes, I can prepare a PR. @stjepang do you have a working branch?

[ghost]

@jeehoonkang I don't have a working branch. If you'd like to implement this - feel free to go ahead!