feat: merge Semaphore permits

[domodwyer]

Is your feature request related to a problem? Please describe.

When implementing resource limits using semaphores, it's common to try_acquire() a permit for each request, and drop it when the "work" is complete. However when the "work" involves batching together payloads and doing all the work at once (potentially some time after the actual request has completed), I find myself writing code like this:

struct WorkBatch {
    permits: Vec<OwnedSemaphorePermit>,
    work_items: Vec<()>, // Stub for requests/payloads/tasks/etc
}

impl WorkBatch {
    fn add_work(&mut self, permits: OwnedSemaphorePermit, item: ()) {
        self.permits.push(permits);
        self.work_items.push(item);
    }

    fn do_work(mut self) {
        // Do work here.

        // Now the work is done, release all the permits.
        drop(self.permits);
    }
}

This is unfortunate, because we have to allocate a Vec for the permits, and grow it as more work is added in order to hold onto the permits. Maintaining this Vec incurs both a memory, and add_work() latency cost.

Describe the solution you'd like

Instead I'd love to be able to eliminate the Vec (and it's allocations) by merging OwnedSemaphorePermit instances together, with one instance holding all the permits:

struct WorkBatch {
    permits: OwnedSemaphorePermit,
    work_items: Vec<()>, // Stub for requests/payloads/tasks/etc
}

impl WorkBatch {
    fn add_work(&mut self, permit: OwnedSemaphorePermit, item: ()) {
        // Merge the permits! No need to store both.
        self.permits.merge(permit);

        self.work_items.push(item);
    }

    fn do_work(mut self) {
        // Do work here.

        // Now the work is done, release all the permits.
        drop(self.permits);
    }
}

On the OwnedSemaphorePermit, this would look like:

pub fn merge(&mut self, mut other: Self)

An identical impl would be added to the regular SemaphorePermit too.

Describe alternatives you've considered

• Maintaining a Vec<Permit> as above, and pre-allocating space to avoid the re-allocations - this trades off (potentially wasted) memory for lack of grow latency, and can be hard to size correctly.
• Storing permits in a linked list - workable, but pointer-chasing overhead at drop time.
• Rolling my own primitive.

Additional context

A Semaphore supports acquiring both owned and regular permits from the same instance, but this proposal doesn't support merging the two types together. For example, the following is not possible:

async fn merge_fail() {
    let sem = Arc::new(Semaphore::new(2));

    let mut p1 = sem.acquire().await.unwrap();
    let p2 = sem.clone().acquire_owned().await.unwrap();

    p1.merge(p2);
    //
    // p1.merge(p2);
    //    ----- ^^ expected struct `SemaphorePermit`, found struct `OwnedSemaphorePermit`
    //    |
    //    arguments to this function are incorrect
    //
}

[Darksonn]

My main question is what should happen if the permits come from two different semaphores.

[domodwyer]

Good point!

I guess we could use a global, monotonic counter to tag each Semaphore instance with a unique counter value, and panic if self.counter_value != other.counter_value.

This is a more invasive change than I was hoping for though - I am unsure of the implications of this :(

[Darksonn]

I mean, we wouldn't need a counter for that. The permit holds a pointer to the semaphore, so we can compare their address.

However, perhaps a better solution is to call the function something like transfer_permits_to or take_permits_from that emphasizes that the permits are moved, and to make it clear that the permits are moved to a different semaphore in this situation.

[domodwyer]

I have pushed a commit that prevents merging of unrelated Semaphore permits - the pointer check is a great idea.

As for the name, I hold no strong opinions. I went with merge() as conceptually it in my head you're not taking / destroying anything - you're combining them, 2 into 1. Any clear name is fine with me.

[domodwyer]

Done in #4948.