Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.001 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'algorithm': 0.04; 'value,': 0.04; 'argument': 0.05; 'algorithms,': 0.07; 'dynamically': 0.07; 'subject:two': 0.07; 'advance': 0.07; '0.1': 0.09; 'calculating': 0.09; 'caller': 0.09; 'performs': 0.09; 'runtime': 0.09; 'cc:addr:python-list': 0.11; 'python': 0.11; 'jan': 0.12; 'language,': 0.12; '23,': 0.16; 'argument,': 0.16; 'caller.': 0.16; 'complexity,': 0.16; 'decisions,': 0.16; 'expecting': 0.16; 'inserting': 0.16; 'intersection': 0.16; 'loops': 0.16; 'luckily,': 0.16; 'reedy': 0.16; 'spawn': 0.16; 'subject:between': 0.16; 'thoughts?': 0.16; 'threads,': 0.16; 'true:': 0.16; 'wrote:': 0.18; 'starts': 0.20; 'fit': 0.20; 'import': 0.22; 'proposed': 0.22; 'cc:addr:python.org': 0.22; 'large,': 0.24; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; 'source': 0.25; 'first,': 0.26; 'this:': 0.26; 'second': 0.26; 'certain': 0.27; 'values': 0.27; 'gets': 0.27; 'header:In-Reply- To:1': 0.27; 'point': 0.28; 'fixed': 0.29; 'wondering': 0.29; 'am,': 0.29; 'possibility': 0.29; 'nature': 0.30; 'message- id:@mail.gmail.com': 0.30; "i'm": 0.30; 'url:mailman': 0.30; 'work.': 0.31; 'code': 0.31; "d'aprano": 0.31; 'large.': 0.31; 'option.': 0.31; 'sep': 0.31; 'steven': 0.31; 'trivial': 0.31; 'values.': 0.31; 'quite': 0.32; 'url:python': 0.33; "i'd": 0.34; 'could': 0.34; "can't": 0.35; 'problem.': 0.35; '(2)': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'add': 0.35; 'there': 0.35; 'url:listinfo': 0.36; 'possible': 0.36; 'url:org': 0.36; 'should': 0.36; 'seconds': 0.37; 'two': 0.37; 'performance': 0.37; '(3)': 0.38; 'pm,': 0.38; 'short': 0.38; 'url:mail': 0.40; 'how': 0.40; 'algorithms': 0.60; 'tell': 0.60; 'hope': 0.61; 'break': 0.61; 'entire': 0.61; 'range': 0.61; 'first': 0.61; 'reach': 0.63; 'such': 0.63; 'more': 0.64; 'different': 0.65; 'relatively': 0.65; 'talking': 0.65; 'hours': 0.66; 'due': 0.66; 'minutes': 0.67; 'between': 0.67; 'determine': 0.67; 'sound': 0.68; '(5)': 0.74; 'increase': 0.74; 'million': 0.74; 'other.': 0.75; 'algorithm,': 0.84; 'catastrophic': 0.84; 'completes': 0.84; 'short,': 0.84; 'terrible': 0.84 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=n5kI7/ijvSeiSJ0wq8NuOWXBriPR4MK33zryux7H1qI=; b=e1CYh3zbdQu6liHlOZO9wVQdD2+pfmyRRsYOuzlhD5PeUKC1Ofydhb7Jjnt3E+sxZK qc5Ajpgsh1dFvYn7tp6Ro3saOS8+WQSXY7iqyiGuTwEq+4XatERz4caUPcwhMyk3BfZK LjMz9VgTNeFCHfAnduVz8tpe1aJZLcgHTc4Co096dnZqXcSwfJWrPVvYbaSYJmanQPPZ 7JH6sRQtWjZvZwjflegKi7CHjJUkK0Sj07uROvN/XuMSOSWB1WE1vbT7dgNdyK6nus2k SGSg7aQ03s2IhUDp/QLUPNcEFsSCVJ5MsGBMXk52k28ZPrUbDlXJWwcxH+Btqn945V1O 7Y8Q== MIME-Version: 1.0 X-Received: by 10.112.34.143 with SMTP id z15mr1994262lbi.86.1411505694642; Tue, 23 Sep 2014 13:54:54 -0700 (PDT) In-Reply-To: References: <54218831$0$29979$c3e8da3$5496439d@news.astraweb.com> Date: Tue, 23 Sep 2014 13:54:54 -0700 Subject: Re: Dynamically swapping between two algorithms From: C Smith To: Terry Reedy Content-Type: text/plain; charset=UTF-8 X-Mailman-Approved-At: Tue, 23 Sep 2014 22:55:50 +0200 Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 91 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1411505751 news.xs4all.nl 2890 [2001:888:2000:d::a6]:57311 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:78247 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 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