binarySearch() with suspending comparison function?

Support
1

How do I do a binary search with a suspending comparison function? e.g.

suspend fun main() {
  // ...
  // Find the minimum input in a..b such that the balance is zero
  (a..b).toList().binarySearch { contributionsYouAreDeducting ->
    // error: suspension functions can be called only within coroutine body
    val newForm = coroutineScope { evalForm(contributionsYouAreDeducting, this) }
    //            ^
    if (newForm.yourReturn.balance() > 0) -1 else 1
  }
}

Replacing coroutineScope() with runBlocking() disappears the error, however I suspect this approach has problems? i.e.

suspend fun main() {
  // ...
  (a..b).toList().binarySearch { contributionsYouAreDeducting ->
    val newForm = runBlocking { evalForm(contributionsYouAreDeducting, this) }
    if (newForm.yourReturn.balance() > 0) -1 else 1
  }
}
2

Why do you need to do this in the first place? Do you need to perform a parallel computing in evalForm()? In that case using runBlocking() or your own coroutine scope does not sound like a bad idea.

Also, remember that you can use binarySearch() only on already sorted lists.

Also2, if this is what you need to do:

Find the minimum input in a…b such that the balance is zero

Then I don’t really see how binarySearch() can help you here. Why won’t you just iterate from a to b and finish when you get 0?

1 Like
3

Yup, exactly.

Thanks for your help! I don’t understand though: what do you mean by your own coroutine scope?

The balance is monotonic (it’s piecewise linear and monotonic). You’re right, that’s significant.

The comparison function (evalForm().yourReturn.balance()) is expensive, so unfortunately iteration isn’t feasible.

4

I meant CoroutineScope, but on the second thought I’m not sure if it makes any sense here.

Note that by default runBlocking() dispatches coroutines in a single thread that invoked it, so it won’t improve the performance. You need to switch to Dispatchers.Default (it uses a shared thread pool for CPU-intensive tasks) or create your own thread pool. You can switch the dispatcher by e.g. runBlocking(Dispatchers.Default) { ... }.

Ahh, ok, that explains everything. I must say this solution is pretty clever. I mean especially that your comparison function never returns 0, so it always finds the first item with balance=0. I really like it.

1 Like
5

On third thought… ok, I give up, we probably need to wait for someone who is more experienced with coroutines. Your main() is marked with suspend, so if this is an entry point to the application then I think this is ok. Main thread will be blocked, no problem here.

My concern is what if we need to use binarySearch() or similar function from any suspend function, so potentially from any coroutine or dispatcher. For example, if we do it from the coroutine running with Dispatchers.Default, we will block one of its threads which we should avoid. I created a simple test:

newFixedThreadPoolContext(2, "my-pool").use { ctx ->
    runBlocking(ctx) {
        runBlocking(ctx) {
            launch {
                println("1: ${Thread.currentThread().name}")
                Thread.sleep(1000)
            }
            launch {
                println("2: ${Thread.currentThread().name}")
                Thread.sleep(1000)
            }
        }
    }
}

First runBlocking() blocks the main thread, second runBlocking() blocks one of two threads in our pool. so both subtasks runs sequentially, not concurrently. If we add a third runBlocking(), it will be a deadlock.

So I don’t really know, how to properly handle such cases in general. I mean cases where we are in suspendable/coroutine context and we need to get through unsuspendable code to get to another suspend function.

I wonder if it would be technically possible for runBlocking() to recognize that it was invoked from the thread that is managed by one of coroutine dispatchers and in that case it would temporarily return the thread to the pool. It does not sound easy, but possible (?). Anyway, it doesn’t seem to do it already, as can be seen in my example.

1 Like
6

:dart: That’s what I’m after. Thanks for explaining the problem with runBlocking(), hopefully someone knows how to do it properly, or is there an existing issue/discussion?

7

This is a good example of the red/blue function problem: What Color is Your Function? – journal.stuffwithstuff.com

The bottom line is that you need a suspending version of binarySearch. The standard library doesn’t provide one, so you’ll have to write your own. It’s not hard:

while(a<b) {
    val test = a+(b-a)/2
    val newForm = evalForm(test, this)
    if (newForm.yourReturn.balance() > 0) {
        a = test+1
    } else {
        b = test
    }
}
1 Like
8

I think this is similar, but not the same. Note that suspending functions are actually synchronous, so we are all in blue here.

Synchronous and asynchronous operations are somewhat incompatible even conceptually, so whatever tools we will create, the problem will remain. I believe the problem with coroutines is strictly technical, it is related to how they were implemented, so maybe there is a room for improvement here.

But the conclusion is probably right: the best we can do is to replace the library or utility function with one that supports suspending.

1 Like
9

Thanks for your help! I found an existing YT for the higher order + suspending function problem and added mention of the binarySearch() case to it.

It sounds like inline would fix the binarySearch() case? In the absence of suspending overloads …