Async closure for binary_search_by_key

help
1

I've seen a handful of posts asking about calling async functions in Iterator closures, and the recommendation being to convert the Iterator into a Stream, and then use similar Stream methods from StreamExt.

How can I go about performing binary_search_by_key on a Vec/slice using a closure that contains a call to an async function?

Simple Playground example: Rust Playground

The best idea (not implemented, could have issues too?) I've come up with is to create a macro binary_search_by_key! which takes in a slice, value to search for, and an async function, then does the search in a similar fashion, but calling .await on the async function. I think this will work, because the macro shouldn't care about passing an async function. Thoughts?

2

I'm not sure what you mean by this exactly. Do you mean implementing binary search inside that macro? If so, you can implement asynchronous binary search in a function as well, doesn't have to be a macro.

For reference, here I took the standard library's implementation of binary_search_by and made it asynchronous:

use std::cmp::Ordering;
use std::future::Future;

async fn binary_search_by<'a, T, F, O>(s: &'a [T], mut f: F) -> Result<usize, usize>
where
    F: FnMut(&'a T) -> O,
    O: Future<Output = Ordering>,
{
    use Ordering::*;

    let mut size = s.len();
    let mut left = 0;
    let mut right = size;
    while left < right {
        let mid = left + size / 2;

        // SAFETY: the while condition means `size` is strictly positive, so
        // `size/2 < size`. Thus `left + size/2 < left + size`, which
        // coupled with the `left + size <= self.len()` invariant means
        // we have `left + size/2 < self.len()`, and this is in-bounds.
        let cmp = f(unsafe { s.get_unchecked(mid) }).await;

        // The reason why we use if/else control flow rather than match
        // is because match reorders comparison operations, which is perf sensitive.
        // This is x86 asm for u8: https://rust.godbolt.org/z/8Y8Pra.
        if cmp == Less {
            left = mid + 1;
        } else if cmp == Greater {
            right = mid;
        } else {
            return Ok(mid);
        }

        size = right - left;
    }
    Err(left)
}

#[tokio::main]
async fn main() {
    let vals = (0u64..10).into_iter().collect::<Vec<_>>();

    let res = binary_search_by(&vals, |v| async move { v.cmp(&3) })
        .await
        .unwrap();

    println!("RES: {:?}", res);
}

Playground.

1 Like
3

@jofas this is the solution! For some reason I had a mental block that I wouldn't be able to define a FnMut type that was async... forgetting that and the end-of-the-day, you just need to specify it returns a Future of the right type. Thanks!

1 Like
4

You simply can't pass an async function to binary_search_by_key(), because the types won't line up. This isn't changed by a macro invocation.

You have to convert your async comparator into a synchronous one, for example by using block_on. This may or may not be acceptable, depending on how expensive/time-consuming the key function is. Playground. There are other alternatives mentioned in the documentation of block_on().

fn binary_search_by_async_key<T, F, R>(slice: &[T], elem: &R::Output, mut key: F) -> Result<usize, usize>
where
    F: FnMut(&T) -> R,
    R: Future,
    R::Output: Ord,
{
    slice.binary_search_by_key(elem, move |it| block_on(key(it)))
}
1 Like
5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.