Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 8 of 8
  1. #1
    Regular Coder
    Join Date
    Feb 2003
    Posts
    638
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Recursion getting incrementally slower?

    Before unloading with a bunch of potentially unnecessary details...

    I'll just ask:
    What would make a recursive function execute slower & slower, the longer it ran?


    Ok, maybe one detail:
    The test involved iterating & outputting thousands of values to a textarea...
    Last edited by swmr; 02-13-2004 at 02:17 AM.
    hmm... ?

  • #2
    Master Coder
    Join Date
    Feb 2003
    Location
    UmeŚ, Sweden
    Posts
    5,575
    Thanks
    0
    Thanked 83 Times in 74 Posts
    Using innerHTML to dynamically change values for each pass of the recursion would, for instance.

    Any code sample?
    liorean <[lio@wg]>
    Articles: RegEx evolt wsabstract , Named Arguments
    Useful Threads: JavaScript Docs & Refs, FAQ - HTML & CSS Docs, FAQ - XML Doc & Refs
    Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards

  • #3
    Regular Coder
    Join Date
    Feb 2003
    Posts
    638
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Here's a generic example.

    Removing the highlighted line will show the difference between accumulating output, and just running the number.

    Code:
    <html>
    <head>
    <title>-</title>
    
    <script type="text/JavaScript">
    
    var i, interval, stop;
    
    function Recurse(startTime, n, oForm){
    var et, ETA, H, M, m, S, s;
    i++;
    
    et = new Date().getTime() - startTime;
    
    if(et % 100 == 0){
    ETA = new Date(((n - i) / (i / et))); 
    H = ETA.getUTCHours();
    M = ETA.getMinutes();
    S = ETA.getSeconds();
    M < 10 ? m = "0" + M : m = M;
    S < 10 ? s = "0" + S : s = S;
    oForm.timeRem.value = H + ":" + m + ":" + s;
    }
    
    oForm.progress.value = i;
    oForm.percentage.value = Math.floor(((i / n) * 100)) + "%";
    
    oForm.txt.value += "Output Value # " + i + "\n";
    
    if (i >= n || stop){controlUpdate("Complete");}
    }
    
    function controlUpdate(callString){
    var oForm, n, startTime;
    oForm = document.testForm;
    
    switch(callString){
    
    case "Start" : 
    n = new Number(oForm.test.value);
    if(isNaN(n) || n < 1){
    alert("loop value must be a number greater than 0. ");
    }
    else{
    i = 0;
    stop = false;
    oForm.cancel.disabled = 0;
    oForm.start.disabled = 1;
    oForm.test.disabled = 1;
    startTime = new Date().getTime();
    interval = setInterval(function(){Recurse(startTime, n, oForm);},1);
    }
    break;
    
    case "Cancel" : 
    clearInterval(interval);
    stop = true;
    oForm.rs.disabled = 0;
    oForm.cancel.disabled = 1;
    break;
    
    case "Complete" : 
    clearInterval(interval);
    oForm.rs.disabled = 0;
    break;
    
    case "Reset" : 
    oForm.cancel.disabled = 1;
    oForm.start.disabled = 0;
    oForm.test.disabled = 0;
    oForm.rs.disabled = 1;
    break;}
    }
    </script>
    
    <style type="text/css">
    form{
    text-align:center
    }
    input{
    text-align:center;vertical-align:middle
    }
    label{
    padding-left:10px;padding-right:5px
    }
    </style>
    
    </head>
    <body>
    
    <form name="testForm" onreset="controlUpdate('Reset')">
    <label>i :</label><input name="progress" size="10" readonly>
    <label>% :</label><input name="percentage" size="10" readonly>
    <label>ETA :</label><input name="timeRem" size="10" readonly>
    <br><br>
    <label>n :</label><input name="test" size="10" value="9999" maxlength="5">
    <input name="start" type="button" value="Start" onclick="controlUpdate('Start')">
    <input name="cancel" type="button" value="Cancel" disabled onclick="controlUpdate('Cancel')">
    <input name="rs" type="reset" disabled>
    <br><br>
    <textarea name="txt" cols="40" rows="20"></textarea>
    </form>
    
    </body>
    </html>
    Of course, I'd probably never end up with such a high number in a collection, but a more involved output would take me a while to demonstrate (without using the Shell Object). The point at which the execution slows is somewhat consistent, though.
    hmm... ?

  • #4
    Senior Coder
    Join Date
    Jun 2002
    Location
    Wichita
    Posts
    3,880
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Each time you += more content onto the string enough free memory has to be found to hold the new longer string and then the shorter string is released to free memory. When the string is short that overhead may not be very noticable but the longer the string gets the more likely that no free memory that the browser already has will be able to hold it so the browser has to go to the OS for more memory. Once it's done that a few times it'll have several chunks of free memory that it'll try to consolodate so there's also overhead in that process.

    If your system is short on physical memory you could also get into a situation where you're swapping the string out to disk and back in which increases the overhead by several magnitudes.
    Check out the Forum Search. It's the short path to getting great results from this forum.

  • #5
    Master Coder
    Join Date
    Feb 2003
    Location
    UmeŚ, Sweden
    Posts
    5,575
    Thanks
    0
    Thanked 83 Times in 74 Posts
    Well, there is another factor. setInterval for the first doesn't execute until the latest run has finished, so it will be stacking runs that were not finished until the first one returns. Second, you use a WAY too low interval. Win9x has an operative system time window of 55 ms, WinNT has a window of 10 ms. Trying to use lower times than those windows WILL lead to stacking and thus reduced speed. I don't know whether MacOS 9, MacOS X and *nix have the same methodology of using operative system wide time windows, but it wouldn't surprise me.
    liorean <[lio@wg]>
    Articles: RegEx evolt wsabstract , Named Arguments
    Useful Threads: JavaScript Docs & Refs, FAQ - HTML & CSS Docs, FAQ - XML Doc & Refs
    Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards

  • #6
    Regular Coder
    Join Date
    Feb 2003
    Posts
    638
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thank you both for the info.

    I can see the difference in memory usage, now -- after trying some DOM methods; and it looks like setTimeout is more useful here, given that it wouldn't allow for stacking to occur (if that's right).

    So, I'm just left wondering if the delay in milliseconds for setTimeout should also be set, at minimum, to the "system time window" -- or does that only apply to setInterval?
    hmm... ?

  • #7
    Master Coder
    Join Date
    Feb 2003
    Location
    UmeŚ, Sweden
    Posts
    5,575
    Thanks
    0
    Thanked 83 Times in 74 Posts
    That applies to both setTimeout and setInterval. It's what you could call a definite lower limit for how often you can call things in an operative system provided environment. The reason for this window is that you don't want these kinds of processes to be allowed to take so much time that actually just polling the times hogs the CPU. You see, what the computer does when timing, is that it continually asks the processor for the system time, then replies to the program, so to know that 10 ms has passed, you esentially have to ask for the time continuously until the set time is reach, at which point you stop polling the system time and start your process. If you use setInterval, a new polling will commence directly after the previous one has stopped. The operative system time windows limits the rate of polling to preserve system responsitivity and reduce system load.
    liorean <[lio@wg]>
    Articles: RegEx evolt wsabstract , Named Arguments
    Useful Threads: JavaScript Docs & Refs, FAQ - HTML & CSS Docs, FAQ - XML Doc & Refs
    Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards

  • #8
    Regular Coder
    Join Date
    Feb 2003
    Posts
    638
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Ah, that's understandable -- which makes it seem odd that a higher minimum delay was not built into the methods.

    Thanks again.
    hmm... ?


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •