ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 28 Oct 2021 21:45:54 +0200concurrent computation of a functionhttps://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/ Suppose I have two functions `f1(x)` and `f2(x)` that compute the same entity. Depending on the value of `x` one may be much faster than the other, or vice versa. It's apriori unknown which of the two functions will be faster for a given `x`.
So, I'd like like to run the two functions on the given `x` concurrently in parallel, and as soon as one produces an answer, I'd like to terminate the other function as well and return that answer. Please help me to design such a parallelized function `concurrent_run(f1,f2,x)` in Sage.
Tue, 26 Oct 2021 01:13:57 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/Answer by David Coudert for <p>Suppose I have two functions <code>f1(x)</code> and <code>f2(x)</code> that compute the same entity. Depending on the value of <code>x</code> one may be much faster than the other, or vice versa. It's apriori unknown which of the two functions will be faster for a given <code>x</code>.</p>
<p>So, I'd like like to run the two functions on the given <code>x</code> concurrently in parallel, and as soon as one produces an answer, I'd like to terminate the other function as well and return that answer. Please help me to design such a parallelized function <code>concurrent_run(f1,f2,x)</code> in Sage.</p>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?answer=59494#post-id-59494A simple solution proposed [here](https://trac.sagemath.org/ticket/12379#comment:3) using the `@parallel` decorator. It can easily be extended to other cases.
def use_all(f, algorithms):
@parallel(len(algorithms), verbose=False)
def h(alg):
return f(algorithm=alg)
for input, output in h(algorithms):
return output, input[0][0]
and then
sage: set_random_seed(0)
sage: g = graphs.RandomGNP(20, .5)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.61 ms, sys: 15.3 ms, total: 17.9 ms
Wall time: 63.4 ms
(6, 'DLX')
sage: g = graphs.RandomGNP(50, .3)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.03 ms, sys: 11.8 ms, total: 13.8 ms
Wall time: 124 ms
(6, 'MILP')
Wed, 27 Oct 2021 14:09:21 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?answer=59494#post-id-59494Comment by William Stein2 for <p>A simple solution proposed <a href="https://trac.sagemath.org/ticket/12379#comment:3">here</a> using the <code>@parallel</code> decorator. It can easily be extended to other cases.</p>
<pre><code>def use_all(f, algorithms):
@parallel(len(algorithms), verbose=False)
def h(alg):
return f(algorithm=alg)
for input, output in h(algorithms):
return output, input[0][0]
</code></pre>
<p>and then</p>
<pre><code>sage: set_random_seed(0)
sage: g = graphs.RandomGNP(20, .5)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.61 ms, sys: 15.3 ms, total: 17.9 ms
Wall time: 63.4 ms
(6, 'DLX')
sage: g = graphs.RandomGNP(50, .3)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.03 ms, sys: 11.8 ms, total: 13.8 ms
Wall time: 124 ms
(6, 'MILP')
</code></pre>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59509#post-id-59509It might work due to garbage collection killing the other spawned processes. I think @parallel uses fork rather than threads to avoid problems with Python's GIL. For what it's worth, I actually wrote the @parallel decorator in the first place, but can barely remember how it works. I just remember trying to find a simple-to-use "notation" at a Sage Days that would make it easy to do things in parallel in Sage, and @parallel seemed easy to sell :-).Thu, 28 Oct 2021 09:38:31 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59509#post-id-59509Comment by Max Alekseyev for <p>A simple solution proposed <a href="https://trac.sagemath.org/ticket/12379#comment:3">here</a> using the <code>@parallel</code> decorator. It can easily be extended to other cases.</p>
<pre><code>def use_all(f, algorithms):
@parallel(len(algorithms), verbose=False)
def h(alg):
return f(algorithm=alg)
for input, output in h(algorithms):
return output, input[0][0]
</code></pre>
<p>and then</p>
<pre><code>sage: set_random_seed(0)
sage: g = graphs.RandomGNP(20, .5)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.61 ms, sys: 15.3 ms, total: 17.9 ms
Wall time: 63.4 ms
(6, 'DLX')
sage: g = graphs.RandomGNP(50, .3)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.03 ms, sys: 11.8 ms, total: 13.8 ms
Wall time: 124 ms
(6, 'MILP')
</code></pre>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59496#post-id-59496I've tested this approach and it seems to work fine (ie. terminates the running threads upon return from the caller).Wed, 27 Oct 2021 16:04:33 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59496#post-id-59496Comment by Max Alekseyev for <p>A simple solution proposed <a href="https://trac.sagemath.org/ticket/12379#comment:3">here</a> using the <code>@parallel</code> decorator. It can easily be extended to other cases.</p>
<pre><code>def use_all(f, algorithms):
@parallel(len(algorithms), verbose=False)
def h(alg):
return f(algorithm=alg)
for input, output in h(algorithms):
return output, input[0][0]
</code></pre>
<p>and then</p>
<pre><code>sage: set_random_seed(0)
sage: g = graphs.RandomGNP(20, .5)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.61 ms, sys: 15.3 ms, total: 17.9 ms
Wall time: 63.4 ms
(6, 'DLX')
sage: g = graphs.RandomGNP(50, .3)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.03 ms, sys: 11.8 ms, total: 13.8 ms
Wall time: 124 ms
(6, 'MILP')
</code></pre>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59495#post-id-59495What's happening with the running threads upon return from the caller (`use_all`)? I suspect they may still be running in background until their normal completion, which would be a waste of resources.Wed, 27 Oct 2021 14:41:33 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59495#post-id-59495Answer by Max Alekseyev for <p>Suppose I have two functions <code>f1(x)</code> and <code>f2(x)</code> that compute the same entity. Depending on the value of <code>x</code> one may be much faster than the other, or vice versa. It's apriori unknown which of the two functions will be faster for a given <code>x</code>.</p>
<p>So, I'd like like to run the two functions on the given <code>x</code> concurrently in parallel, and as soon as one produces an answer, I'd like to terminate the other function as well and return that answer. Please help me to design such a parallelized function <code>concurrent_run(f1,f2,x)</code> in Sage.</p>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?answer=59490#post-id-59490After some googling and reading documentation, I have found that this can be done via standard Python's module `multiprocessing` as explained below.
First, we need our functions to store their results in a given queue, which can be done via a wrapper:
def func_wrapper(queue, func, x):
queue.put( func(x) )
Then the concurrent run of `f1` and `f2` on `x` can be implemented as follows:
def concurrent_run(f1,f2,x):
q = multiprocessing.Queue()
p1 = multiprocessing.Process(target=func_wrapper, args=(q,f1,x))
p2 = multiprocessing.Process(target=func_wrapper, args=(q,f2,x))
p1.start()
p2.start()
res = q.get()
p1.terminate()
p2.terminate()
return res
PS. Perhaps, we can simply use `return q.get()` without explicitly calling `.terminate()` methods and letting the corresponding Process classes to take care of a clean-up. On the other hand, for unresponsive processes we can use `.kill()` instead of `.terminate()` to force their shutdown.Wed, 27 Oct 2021 00:42:15 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?answer=59490#post-id-59490Answer by tmonteil for <p>Suppose I have two functions <code>f1(x)</code> and <code>f2(x)</code> that compute the same entity. Depending on the value of <code>x</code> one may be much faster than the other, or vice versa. It's apriori unknown which of the two functions will be faster for a given <code>x</code>.</p>
<p>So, I'd like like to run the two functions on the given <code>x</code> concurrently in parallel, and as soon as one produces an answer, I'd like to terminate the other function as well and return that answer. Please help me to design such a parallelized function <code>concurrent_run(f1,f2,x)</code> in Sage.</p>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?answer=59483#post-id-59483You can have a look at https://doc.sagemath.org/html/en/reference/parallel/index.htmlTue, 26 Oct 2021 09:07:41 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?answer=59483#post-id-59483Comment by tmonteil for <p>You can have a look at <a href="https://doc.sagemath.org/html/en/reference/parallel/index.html">https://doc.sagemath.org/html/en/refe...</a></p>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59518#post-id-59518It is not described in @david-coudert either, `@parallel` just works.Thu, 28 Oct 2021 21:45:54 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59518#post-id-59518Comment by Max Alekseyev for <p>You can have a look at <a href="https://doc.sagemath.org/html/en/reference/parallel/index.html">https://doc.sagemath.org/html/en/refe...</a></p>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59515#post-id-59515Yes, and I've accepted his solution. I've also added my own solution (based on multiprocessing module) above. Your link alone was not sufficient as the tricky part (terminating processes) is not described there.Thu, 28 Oct 2021 19:38:33 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59515#post-id-59515Comment by tmonteil for <p>You can have a look at <a href="https://doc.sagemath.org/html/en/reference/parallel/index.html">https://doc.sagemath.org/html/en/refe...</a></p>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59513#post-id-59513Apparently, @david-coudert was able to derive a simple solution from the `@parallel` decorator that was pointed by this link (the other process get interrupted once the first returns a result). Did you ever try ?Thu, 28 Oct 2021 19:03:48 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59513#post-id-59513Comment by Max Alekseyev for <p>You can have a look at <a href="https://doc.sagemath.org/html/en/reference/parallel/index.html">https://doc.sagemath.org/html/en/refe...</a></p>
https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59486#post-id-59486I do not see there how to implement what I need. E.g. how to interrupt all parallelism as soon as one thread produced a result?Tue, 26 Oct 2021 12:57:26 +0200https://ask.sagemath.org/question/59480/concurrent-computation-of-a-function/?comment=59486#post-id-59486