Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.lang.python > #78217 > unrolled thread

Dynamically swapping between two algorithms

Started bySteven D'Aprano <steve+comp.lang.python@pearwood.info>
First post2014-09-24 00:48 +1000
Last post2014-09-25 20:11 -0700
Articles 9 — 9 participants

Back to article view | Back to comp.lang.python


Contents

  Dynamically swapping between two algorithms Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-24 00:48 +1000
    Re: Dynamically swapping between two algorithms Chris Angelico <rosuav@gmail.com> - 2014-09-24 01:24 +1000
    Re: Dynamically swapping between two algorithms emile <emile@fenx.com> - 2014-09-23 08:33 -0700
    Re: Dynamically swapping between two algorithms MRAB <python@mrabarnett.plus.com> - 2014-09-23 16:42 +0100
    Re: Dynamically swapping between two algorithms Terry Reedy <tjreedy@udel.edu> - 2014-09-23 15:21 -0400
    Re: Dynamically swapping between two algorithms C Smith <illusiontechniques@gmail.com> - 2014-09-23 13:54 -0700
    Re: Dynamically swapping between two algorithms dieter <dieter@handshake.de> - 2014-09-24 09:44 +0200
    Re: Dynamically swapping between two algorithms Cameron Simpson <cs@zip.com.au> - 2014-09-26 10:30 +1000
    Re: Dynamically swapping between two algorithms Ethan Furman <ethan@stoneleaf.us> - 2014-09-25 20:11 -0700

#78217 — Dynamically swapping between two algorithms

FromSteven D'Aprano <steve+comp.lang.python@pearwood.info>
Date2014-09-24 00:48 +1000
SubjectDynamically swapping between two algorithms
Message-ID<54218831$0$29979$c3e8da3$5496439d@news.astraweb.com>
I have a certain calculation which can be performed two radically different
ways. With the first algorithm, let's call it SHORT, performance is very
fast for small values of the argument, but terrible for large values. For
the second algorithm, LARGE, performance is quite poor for small values,
but excellent for large values.

To add to the complexity, I perform this calculation repeatedly, in a loop:

value = 1
while True:
    x = SHORT(value)  # Or should I use LARGE? Decisions, decisions...
    process(x)
    value += some_increment()
    if condition: break

Luckily, the value never gets smaller. So if I could somehow determine a
cut-over point, CUTOFF, I might write my loop like this:

value = 1
while True:
    f = SHORT if value < CUTOFF else LARGE
    x = f(value)
    process(x)
    value += some_increment()
    if condition: break

alas, the CUTOVER point is likely to be machine-dependent. Take it as a
given that inserting a fixed CUTOVER point into the source code (say,
``CUTOVER = 123456``) is not likely to be very effective, and dynamically
calculating it at import time is impractical.

*If* Python was a different language, I would spawn two threads, one using
SHORT and the other using LARGE, then which ever completes first, I'd just
kill the other. Alas, this won't work because (1) the GIL and (2) you
cannot forcibly kill threads, only ask them to die and hope they listen.

I am seeking other ideas for dynamically swapping between the two
algorithms, based on runtime information. Any thoughts?


(1) I can't tell in advance how many loops I will make.

(2) Both SHORT and LARGE get slower as the size of their argument increases.
This is unavoidable due to the nature of the problem.

(3) SHORT starts off relatively speedy, significantly faster than LARGE for
the first few tens of thousands of loops. I'm not talking about trivial
micro-optimizations here, I'm talking about the difference between 0.1
second for SHORT versus 10 seconds for LARGE.

(4) But as the size of the argument increases, SHORT suffers catastrophic
quadratic slowdown, while LARGE slows down only linearly. (Give or take.)

(5) Consequently, by the time I reach a few million loops, the difference is
now between (say) 5 minutes for LARGE versus 15 hours for SHORT.

(6) There is no single algorithm which performs acceptably across the entire
range of values I'm expecting to process in practice.

(7) Leaving the choice up to the caller is not an option. I am the caller.




-- 
Steven

[toc] | [next] | [standalone]


#78220

FromChris Angelico <rosuav@gmail.com>
Date2014-09-24 01:24 +1000
Message-ID<mailman.14267.1411485859.18130.python-list@python.org>
In reply to#78217
On Wed, Sep 24, 2014 at 12:48 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> (3) SHORT starts off relatively speedy, significantly faster than LARGE for
> the first few tens of thousands of loops. I'm not talking about trivial
> micro-optimizations here, I'm talking about the difference between 0.1
> second for SHORT versus 10 seconds for LARGE.
>
> (4) But as the size of the argument increases, SHORT suffers catastrophic
> quadratic slowdown, while LARGE slows down only linearly. (Give or take.)
>
> (5) Consequently, by the time I reach a few million loops, the difference is
> now between (say) 5 minutes for LARGE versus 15 hours for SHORT.

Are these figures for a single call to SHORT/LARGE, or for a number of
calls aggregated? How much extra cost would a bit of timing add? If
you're making the decision no more than every 0.1s, you can probably
afford to time every call, but if you're doing a thousand iterations a
second in the early phases, you don't want to add a time-of-day call
every step.

Here's a possibility that won't be perfectly optimal, but it'll sort
itself out over time:

shorttime = -1.0
largetime = 0.0
value = 1
while True:
    t = time.time()
    if shorttime < largetime:
        x = SHORT(value)
        shorttime = time.time() - t
    else:
        x = LARGE(value)
        largetime = time.time() - t
        if largetime < shorttime: break
    process(x)
    value += some_increment()
    if condition: break

# The SHORT algorithm is never going to be better, so
# switch to always using LARGE
while not condition:
    process(x)
   x = LARGE(value)
    value += some_increment()

What it'll do is try one each way, and then use whichever was quicker.
So you waste 10s early on, running the LARGE algorithm when SHORT
would have been better, but then it won't use LARGE again until SHORT
takes at least 10s. At that point, an Achilles/Tortoise race begins:
every time SHORT catches up with LARGE, LARGE takes a leap forward...
until LARGE's leap forward is insufficient for it to "catch up with"
SHORT, at which point we declare SHORT to have won the 'race' and just
run with the LARGE algorithm the whole way.

Downside: Will choose poorly if other things kick in during the timing
tests. Ideally, this should use a "CPU time used by this process"
monitor, but I'm not sure (a) if one is available to Python, and (b)
if it's at all portable, so the above just uses time.time().

(If the code is big and the overhead of merging is insignificant, the
same could be done with a flag instead of breaking out of the loop and
starting another. Take your pick.)

ChrisA

[toc] | [prev] | [next] | [standalone]


#78221

Fromemile <emile@fenx.com>
Date2014-09-23 08:33 -0700
Message-ID<mailman.14268.1411486443.18130.python-list@python.org>
In reply to#78217
Add a timing harness and use a test interval (N) and call LARGE every 
Nth loop until LARGE's timing is better than the prior SHORT's run.

Emile


On 09/23/2014 07:48 AM, Steven D'Aprano wrote:
> I have a certain calculation which can be performed two radically different
> ways. With the first algorithm, let's call it SHORT, performance is very
> fast for small values of the argument, but terrible for large values. For
> the second algorithm, LARGE, performance is quite poor for small values,
> but excellent for large values.
>
> To add to the complexity, I perform this calculation repeatedly, in a loop:
>
> value = 1
> while True:
>      x = SHORT(value)  # Or should I use LARGE? Decisions, decisions...
>      process(x)
>      value += some_increment()
>      if condition: break
>
> Luckily, the value never gets smaller. So if I could somehow determine a
> cut-over point, CUTOFF, I might write my loop like this:
>
> value = 1
> while True:
>      f = SHORT if value < CUTOFF else LARGE
>      x = f(value)
>      process(x)
>      value += some_increment()
>      if condition: break
>
> alas, the CUTOVER point is likely to be machine-dependent. Take it as a
> given that inserting a fixed CUTOVER point into the source code (say,
> ``CUTOVER = 123456``) is not likely to be very effective, and dynamically
> calculating it at import time is impractical.
>
> *If* Python was a different language, I would spawn two threads, one using
> SHORT and the other using LARGE, then which ever completes first, I'd just
> kill the other. Alas, this won't work because (1) the GIL and (2) you
> cannot forcibly kill threads, only ask them to die and hope they listen.
>
> I am seeking other ideas for dynamically swapping between the two
> algorithms, based on runtime information. Any thoughts?
>
>
> (1) I can't tell in advance how many loops I will make.
>
> (2) Both SHORT and LARGE get slower as the size of their argument increases.
> This is unavoidable due to the nature of the problem.
>
> (3) SHORT starts off relatively speedy, significantly faster than LARGE for
> the first few tens of thousands of loops. I'm not talking about trivial
> micro-optimizations here, I'm talking about the difference between 0.1
> second for SHORT versus 10 seconds for LARGE.
>
> (4) But as the size of the argument increases, SHORT suffers catastrophic
> quadratic slowdown, while LARGE slows down only linearly. (Give or take.)
>
> (5) Consequently, by the time I reach a few million loops, the difference is
> now between (say) 5 minutes for LARGE versus 15 hours for SHORT.
>
> (6) There is no single algorithm which performs acceptably across the entire
> range of values I'm expecting to process in practice.
>
> (7) Leaving the choice up to the caller is not an option. I am the caller.
>
>
>
>

[toc] | [prev] | [next] | [standalone]


#78222

FromMRAB <python@mrabarnett.plus.com>
Date2014-09-23 16:42 +0100
Message-ID<mailman.14270.1411487168.18130.python-list@python.org>
In reply to#78217
On 2014-09-23 15:48, Steven D'Aprano wrote:
> I have a certain calculation which can be performed two radically different
> ways. With the first algorithm, let's call it SHORT, performance is very
> fast for small values of the argument, but terrible for large values. For
> the second algorithm, LARGE, performance is quite poor for small values,
> but excellent for large values.
>
> To add to the complexity, I perform this calculation repeatedly, in a loop:
>
> value = 1
> while True:
>      x = SHORT(value)  # Or should I use LARGE? Decisions, decisions...
>      process(x)
>      value += some_increment()
>      if condition: break
>
> Luckily, the value never gets smaller. So if I could somehow determine a
> cut-over point, CUTOFF, I might write my loop like this:
>
> value = 1
> while True:
>      f = SHORT if value < CUTOFF else LARGE
>      x = f(value)
>      process(x)
>      value += some_increment()
>      if condition: break
>
> alas, the CUTOVER point is likely to be machine-dependent. Take it as a
> given that inserting a fixed CUTOVER point into the source code (say,
> ``CUTOVER = 123456``) is not likely to be very effective, and dynamically
> calculating it at import time is impractical.
>
> *If* Python was a different language, I would spawn two threads, one using
> SHORT and the other using LARGE, then which ever completes first, I'd just
> kill the other. Alas, this won't work because (1) the GIL and (2) you
> cannot forcibly kill threads, only ask them to die and hope they listen.
>
> I am seeking other ideas for dynamically swapping between the two
> algorithms, based on runtime information. Any thoughts?
>
>
> (1) I can't tell in advance how many loops I will make.
>
> (2) Both SHORT and LARGE get slower as the size of their argument increases.
> This is unavoidable due to the nature of the problem.
>
> (3) SHORT starts off relatively speedy, significantly faster than LARGE for
> the first few tens of thousands of loops. I'm not talking about trivial
> micro-optimizations here, I'm talking about the difference between 0.1
> second for SHORT versus 10 seconds for LARGE.
>
> (4) But as the size of the argument increases, SHORT suffers catastrophic
> quadratic slowdown, while LARGE slows down only linearly. (Give or take.)
>
> (5) Consequently, by the time I reach a few million loops, the difference is
> now between (say) 5 minutes for LARGE versus 15 hours for SHORT.
>
> (6) There is no single algorithm which performs acceptably across the entire
> range of values I'm expecting to process in practice.
>
> (7) Leaving the choice up to the caller is not an option. I am the caller.
>
How about this:

Try both of them initially, and use the faster one until it takes
longer than the slower one did initially. Then try both of them again.
Repeat.

[toc] | [prev] | [next] | [standalone]


#78241

FromTerry Reedy <tjreedy@udel.edu>
Date2014-09-23 15:21 -0400
Message-ID<mailman.14284.1411500109.18130.python-list@python.org>
In reply to#78217
On 9/23/2014 10:48 AM, Steven D'Aprano wrote:
> I have a certain calculation which can be performed two radically different
> ways. With the first algorithm, let's call it SHORT, performance is very
> fast for small values of the argument, but terrible for large values. For
> the second algorithm, LARGE, performance is quite poor for small values,
> but excellent for large values.
>
> To add to the complexity, I perform this calculation repeatedly, in a loop:
>
> value = 1
> while True:
>      x = SHORT(value)  # Or should I use LARGE? Decisions, decisions...
>      process(x)
>      value += some_increment()
>      if condition: break
>
> Luckily, the value never gets smaller. So if I could somehow determine a
> cut-over point, CUTOFF, I might write my loop like this:
>
> value = 1
> while True:
>      f = SHORT if value < CUTOFF else LARGE
>      x = f(value)
>      process(x)
>      value += some_increment()
>      if condition: break
>
> alas, the CUTOVER point is likely to be machine-dependent. Take it as a
> given that inserting a fixed CUTOVER point into the source code (say,
> ``CUTOVER = 123456``) is not likely to be very effective, and dynamically
> calculating it at import time is impractical.
>
> *If* Python was a different language, I would spawn two threads, one using
> SHORT and the other using LARGE, then which ever completes first, I'd just
> kill the other. Alas, this won't work because (1) the GIL and (2) you
> cannot forcibly kill threads, only ask them to die and hope they listen.
>
> I am seeking other ideas for dynamically swapping between the two
> algorithms, based on runtime information. Any thoughts?
>
>
> (1) I can't tell in advance how many loops I will make.
>
> (2) Both SHORT and LARGE get slower as the size of their argument increases.
> This is unavoidable due to the nature of the problem.
>
> (3) SHORT starts off relatively speedy, significantly faster than LARGE for
> the first few tens of thousands of loops. I'm not talking about trivial
> micro-optimizations here, I'm talking about the difference between 0.1
> second for SHORT versus 10 seconds for LARGE.
>
> (4) But as the size of the argument increases, SHORT suffers catastrophic
> quadratic slowdown, while LARGE slows down only linearly. (Give or take.)

One possibility is to apply both algorithms to a few values below any 
plausible cutoff value, fit curves (line and quadratic), and find 
intersection of extrapolated cutoff.  Possible calculate a few more 
values to verify and refine extrapolation.


> (5) Consequently, by the time I reach a few million loops, the difference is
> now between (say) 5 minutes for LARGE versus 15 hours for SHORT.
>
> (6) There is no single algorithm which performs acceptably across the entire
> range of values I'm expecting to process in practice.
>
> (7) Leaving the choice up to the caller is not an option. I am the caller.
>
>
>
>


-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]


#78247

FromC Smith <illusiontechniques@gmail.com>
Date2014-09-23 13:54 -0700
Message-ID<mailman.14287.1411505751.18130.python-list@python.org>
In reply to#78217
Once the runtime of SHORT starts to increase by a certain threshold,
Such as 2x, 4x, or 16x its last runtime? The other ideas already
proposed sound better, but I am wondering if it would work.

On Tue, Sep 23, 2014 at 12:21 PM, Terry Reedy <tjreedy@udel.edu> wrote:
> On 9/23/2014 10:48 AM, Steven D'Aprano wrote:
>>
>> I have a certain calculation which can be performed two radically
>> different
>> ways. With the first algorithm, let's call it SHORT, performance is very
>> fast for small values of the argument, but terrible for large values. For
>> the second algorithm, LARGE, performance is quite poor for small values,
>> but excellent for large values.
>>
>> To add to the complexity, I perform this calculation repeatedly, in a
>> loop:
>>
>> value = 1
>> while True:
>>      x = SHORT(value)  # Or should I use LARGE? Decisions, decisions...
>>      process(x)
>>      value += some_increment()
>>      if condition: break
>>
>> Luckily, the value never gets smaller. So if I could somehow determine a
>> cut-over point, CUTOFF, I might write my loop like this:
>>
>> value = 1
>> while True:
>>      f = SHORT if value < CUTOFF else LARGE
>>      x = f(value)
>>      process(x)
>>      value += some_increment()
>>      if condition: break
>>
>> alas, the CUTOVER point is likely to be machine-dependent. Take it as a
>> given that inserting a fixed CUTOVER point into the source code (say,
>> ``CUTOVER = 123456``) is not likely to be very effective, and dynamically
>> calculating it at import time is impractical.
>>
>> *If* Python was a different language, I would spawn two threads, one using
>> SHORT and the other using LARGE, then which ever completes first, I'd just
>> kill the other. Alas, this won't work because (1) the GIL and (2) you
>> cannot forcibly kill threads, only ask them to die and hope they listen.
>>
>> I am seeking other ideas for dynamically swapping between the two
>> algorithms, based on runtime information. Any thoughts?
>>
>>
>> (1) I can't tell in advance how many loops I will make.
>>
>> (2) Both SHORT and LARGE get slower as the size of their argument
>> increases.
>> This is unavoidable due to the nature of the problem.
>>
>> (3) SHORT starts off relatively speedy, significantly faster than LARGE
>> for
>> the first few tens of thousands of loops. I'm not talking about trivial
>> micro-optimizations here, I'm talking about the difference between 0.1
>> second for SHORT versus 10 seconds for LARGE.
>>
>> (4) But as the size of the argument increases, SHORT suffers catastrophic
>> quadratic slowdown, while LARGE slows down only linearly. (Give or take.)
>
>
> One possibility is to apply both algorithms to a few values below any
> plausible cutoff value, fit curves (line and quadratic), and find
> intersection of extrapolated cutoff.  Possible calculate a few more values
> to verify and refine extrapolation.
>
>
>> (5) Consequently, by the time I reach a few million loops, the difference
>> is
>> now between (say) 5 minutes for LARGE versus 15 hours for SHORT.
>>
>> (6) There is no single algorithm which performs acceptably across the
>> entire
>> range of values I'm expecting to process in practice.
>>
>> (7) Leaving the choice up to the caller is not an option. I am the caller.
>>
>>
>>
>>
>
>
> --
> Terry Jan Reedy
>
> --
> https://mail.python.org/mailman/listinfo/python-list

[toc] | [prev] | [next] | [standalone]


#78268

Fromdieter <dieter@handshake.de>
Date2014-09-24 09:44 +0200
Message-ID<mailman.14300.1411544681.18130.python-list@python.org>
In reply to#78217
Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:
> ...
> *If* Python was a different language, I would spawn two threads, one using
> SHORT and the other using LARGE, then which ever completes first, I'd just
> kill the other. Alas, this won't work because (1) the GIL

The GIL does not prevent this scenario. The two threads will not
really run in parallel but interleaved - but this should not be a big
problem.

> and (2) you
> cannot forcibly kill threads, only ask them to die and hope they listen.

You can kill threads (though you will need a "C" level function for this)
as long as they execute Python code.
And it is your code: you can make your threads be listening, from time to time
in the computation.

[toc] | [prev] | [next] | [standalone]


#78356

FromCameron Simpson <cs@zip.com.au>
Date2014-09-26 10:30 +1000
Message-ID<mailman.14371.1411691448.18130.python-list@python.org>
In reply to#78217
On 24Sep2014 00:48, Steven D'Aprano <steve+comp.lang.python@pearwood.info> wrote:
>I have a certain calculation which can be performed two radically different
>ways. With the first algorithm, let's call it SHORT, performance is very
>fast for small values of the argument, but terrible for large values. For
>the second algorithm, LARGE, performance is quite poor for small values,
>but excellent for large values.
>
>To add to the complexity, I perform this calculation repeatedly, in a loop:
>
>value = 1
>while True:
>    x = SHORT(value)  # Or should I use LARGE? Decisions, decisions...
>    process(x)
>    value += some_increment()
>    if condition: break
>
>Luckily, the value never gets smaller. So if I could somehow determine a
>cut-over point, CUTOFF, I might write my loop like this:
>
>value = 1
>while True:
>    f = SHORT if value < CUTOFF else LARGE
>    x = f(value)
>    process(x)
>    value += some_increment()
>    if condition: break
>
>alas, the CUTOVER point is likely to be machine-dependent. Take it as a
>given that inserting a fixed CUTOVER point into the source code (say,
>``CUTOVER = 123456``) is not likely to be very effective, and dynamically
>calculating it at import time is impractical.

I have two suggestions. The first suggestion presumes multiple CPUs, and is a 
bit of a brute force hack. If the total runtime domain for SHORT (total runtime 
for when SHORT is better) is small compared to the domain for LARGE it may be 
worthwhile.

FIRST SUGGESTION

Run SHORT and LARGE in subprocesses, flat out. When either stops, kill the 
other. Once LARGE is the first to stop, do not bother with SHORT any more.

FIRST SUGGESTION

Chris Angelico's approach looks pretty cool, but seems unstable (in choices) 
initially.

Are the input values predictable? Or a fixed sequences?

I am wondering if there's any scope for gathering all the values (or all the 
values up to comfortably past the unknown cutover point) before running SHORT 
or LARGE at all?

I was thinking bisecting to find the CUTOFF, but the cost of the wrong 
algorithm for values well over the CUTOFF would be nasty.

Alternatively:

Did you say SHORT becomes quadratic in cost as it grows and LARGE roughtly 
linear? Pretend they really are purely quadratic and linear respectively.

Then you could start with both SHORT and LARGE for your first value.
Run SHORT and LARGE. Measure the elapsed time for each. Compute their ratio.

I think you should be able to estimate the cutover point as the point where the 
two curves intersect. Run the SHORT algorithm until them. Then run both.  
Remeasure. Re-estimate. Repeat until definitely LARGE domain (estimate points 
into the past, maybe with an error margin). Then just use LARGE.

Thoughts?

Cheers,
Cameron Simpson <cs@zip.com.au>

[toc] | [prev] | [next] | [standalone]


#78358

FromEthan Furman <ethan@stoneleaf.us>
Date2014-09-25 20:11 -0700
Message-ID<mailman.14373.1411701105.18130.python-list@python.org>
In reply to#78217
On 09/23/2014 07:48 AM, Steven D'Aprano wrote:
>
> alas, the CUTOVER point is likely to be machine-dependent. Take it as a
> given that inserting a fixed CUTOVER point into the source code (say,
> ``CUTOVER = 123456``) is not likely to be very effective, and dynamically
> calculating it at import time is impractical.

Have your setup script do some timings to figure out where CUTOFF is on any particular machine.  You can then store it 
in a .conf file, or directly modify the source file with the value, or ...

--
~Ethan~

[toc] | [prev] | [standalone]


Back to top | Article view | comp.lang.python


csiph-web