Asynchronous computations: I only want the result that finishes first and then stop the other

I am thinking about a situation in which if have different ways to compute the same thing. I want both calculations to start and when one of them finishes, give me the result. I then can abandon the other calculation.

In other words, I have two functions f and g that mathematically give the same answer, but are implemented differently. It’s not easy to know which would be faster. So I want to run them both in parallel with the same input: f(x) and g(x). When one of them finishes, I have my answer. The other calculation should then be aborted.

I may have more than two functions, or I might have one function that I run simultaneously with different parameters: f(x,a) and f(x,b). Again, whichever is done first is the only one I care about.

Is this possible and, if so, how do I do it?

2 Likes

here’s something that may give you inspiration:

julia> f() = begin sleep(rand()*2); return "f" end
julia> g() = begin sleep(rand()*2); return "g" end

julia> function run()
           ts = map(Task, [f,g])
           schedule.(ts)
           while true
               idx = findfirst(istaskdone, ts)
               !isnothing(idx) && return fetch(ts[idx])
               sleep(0.1)
           end
       end
run (generic function with 1 method)

julia> run()
"f"

julia> run()
"g"
1 Like

Thanks so much. What I don’t see (and wouldn’t know how to implement) is how to force quit the functions that are still running when the first function “wins the race”.

1 Like

there’s no “guarantee nothing would crash” way of doing this, I think the “proper” way is to have each of your task looking at a Channel and if it sees a winner has been selected, immediately return.

In general you cannot safely terminate asynchronous code. You need the code that is to be interrupted to cooperatively respond to messages to terminate. Also, the Task scheduling described above is not concurrent unless this notice in the documentation is out of date.

Currently, all tasks in Julia are executed in a single OS thread co-operatively.

For concurrency, you’d need to spawn threads instead. Multi-Threading · The Julia Language

1 Like

You need to rewrite f and g for doing this in current Julia. For example, you can pass a isdone = Threads.Atomic{Bool}(false) (so-called cancellation token) to f and g which checks isdone[] time to time, to see if it has to quit early. The caller then can do isdone[] = true after one of the function is returned. This is how the cancellation is implemented in JuliaFolds (e.g., used for break from parallel for loop of FLoops.jl).

5 Likes

Just nit-picking but I think the correct terminology is that multiple tasks on a single thread are concurrent but not parallel.

(Also, I couldn’t find the quote on the linked page…)

1 Like

With cooperative multitasking, you can do concurrent I/O with a single thread.

The procedure where several tasks race to connect and the losers are cancelled is called “happy eyeballs”. “Structured concurrency” is designed to make this significantly easier.

I’m sorry for any confusion due to my incorrect terminology. The quote is from this page Tasks · The Julia Language

The simplest thing is to run both tasks to completion, but then to take only the first result. Here is a solution based on a channel:

using .Threads

myChannel = Channel(2)

do_some_work(x) = (sleep(x); x)
f = Threads.@spawn put!(myChannel, do_some_work(1))
g = Threads.@spawn put!(myChannel, do_some_work(2))

res = take!(myChannel)

this will return always 1 after one second from the faster “calculation”.

Normally you have enough idle cores to let them just run. But if for some reason you want to stop the slower tasks, you need to send them stop signals (and handle it there), something along the following lines:

struct Stop end

function do_some_work(s, x, ch)
    for i in  1:x
        sleep(1)                              # do calculate
        if isready(ch) && fetch(ch) == Stop() # check if there is a stop signal
            take!(ch)
            println("$s stopped at $i")
            return
        end
    end
    put!(ch, x)
end

f = Threads.@spawn do_some_work("f", 1, myChannel)
g = Threads.@spawn do_some_work("g", 100, myChannel)

@show res = take!(myChannel)
put!(myChannel, Stop())
fetch(g)  # this is for illustration

This will finish both tasks when the first one is done and give you the result of the faster one:

julia> @time include("2functions.jl")
res = take!(myChannel) = 1
g stopped at 1
  1.044117 seconds (72.96 k allocations: 4.474 MiB, 0.00% compilation time)
2 Likes