Async closure for binary_search_by_key

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?

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>
    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:
        if cmp == Less {
            left = mid + 1;
        } else if cmp == Greater {
            right = mid;
        } else {
            return Ok(mid);

        size = right - left;

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

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

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


1 Like

@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

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>
    F: FnMut(&T) -> R,
    R: Future,
    R::Output: Ord,
    slice.binary_search_by_key(elem, move |it| block_on(key(it)))
1 Like

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.