Rate limiting function calls

Question

I wanted to write a function that when applied to another would rate limit it, but permit all calls to eventually make it through.

Comments and criticism welcome.

var MAX_RUNS_PER_WINDOW = 10;
var RUN_WINDOW = 1000;

function limit(fn) {
    var callQueue = [], 
      invokeTimes = Object.create(circularQueue), 
      waitId = null;
    
    function limited() {        
        callQueue.push(() => {
            invokeTimes.unshift(performance.now())
            fn.apply(this, arguments);
        });
                
        if (mayProceed()) {
            return dequeue();
        }
        
        if (waitId === null) {
            waitId = setTimeout(dequeue, timeToWait());
        }
    }

    limited.cancel = function() {
      clearTimeout(waitId);
    };

    return limited;
    
    function dequeue() {
        waitId = null ;
        clearTimeout(waitId);
        callQueue.shift()();
        
        if (mayProceed()) {
            return dequeue();
        }
        
        if (callQueue.length) {
            waitId = setTimeout(dequeue, timeToWait());
        }
    }
    
    function mayProceed() {
        return callQueue.length && (timeForMaxRuns() >= RUN_WINDOW);
    }
    
    function timeToWait() {        
        var ttw = RUN_WINDOW - timeForMaxRuns();
        return ttw < 0 ? 0 : ttw;
    }

    function timeForMaxRuns() {
        return (performance.now() - (invokeTimes[MAX_RUNS_PER_WINDOW - 1] || 0));
    }
}

var circularQueue = [];
var originalUnshift = circularQueue.unshift;

circularQueue.MAX_LENGTH = MAX_RUNS_PER_WINDOW;

circularQueue.unshift = function(element) {
    if (this.length === this.MAX_LENGTH) {
        this.pop();
    }
    return originalUnshift.call(this, element);
}

var printLetter = limit(function(letter) {
    document.write(letter);
});

['A', 'B', 'C', 'D', 'E', 'F', 'G', 
'H', 'I', 'J', 'K', 'L', 'M', 'N', 
'O', 'P', 'Q', 'R', 'S', 'T', 'U', 
'V', 'X', 'Y', 'Z'].forEach(printLetter);

Answer 1

Not bad. Here are some suggestions:

var circularQueue = [];
var originalUnshift = circularQueue.unshift;
circularQueue.unshift = function(element) {
    if (this.length === this.MAX_LENGTH) {
        this.pop();
    }
    return originalUnshift.call(this, element);
}

I think overriding the unshift function here is an overkill here, as it's used only once. You can use a regular array in limit and define an unshift function there. Also, circularQueue won't be visible outside limit this way.

waitId = null ;
clearTimeout(waitId);

You're calling clearTimeout with null as an argument, which has no effect. You don't need to clear the timeout here anyway, it has already expired (you're inside the callback it has triggered).

function dequeue() {
    callQueue.shift()();

    if (mayProceed()) {
        return dequeue();
    }

    if (callQueue.length) {
        waitId = setTimeout(dequeue, timeToWait());
    }
}

There's a hidden do-while loop here. Since mayProceed() is known to be true when dequeue is called, this can be made a while loop:

while (mayProceed()) {
    callQueue.shift()();
}

The relation between the mayProceed() condition and the callQueue.length condition isn't obvious, which makes it hard to understand this function. It'll be easier to understand if it's obvious that the first condition is the-second-condition-and-something-else. This can be accomplished after introducing some helper functions:

function dequeue() {
    while (callsPending() && canCallNow()) {
        callQueue.shift()();
    }

    if (callsPending()) {
        waitId = setTimeout(dequeue, timeToWait());
    }
}

function limited() {        
    callQueue.push(() => {
        invokeTimes.unshift(performance.now())
        fn.apply(this, arguments);
    });

It'll be simpler to just store the arguments lists in an array, instead of having an array of anonymous functions. You can update invokeTimes when you shift the callQueue in dequeue.

    if (mayProceed()) {
        return dequeue();
    }

    if (waitId === null) {
        waitId = setTimeout(dequeue, timeToWait());
    }
}

This logic is implemented in dequeue now. You can just call it.

function timeToWait() {        
    var ttw = RUN_WINDOW - timeForMaxRuns();
    return ttw < 0 ? 0 : ttw;
}

The ternary expression can be replaced with Math.max(0, ttw).

limited.cancel = function() {
  clearTimeout(waitId);
};

This cancels scheduled calls to the function, but they will be performed after calling the function again. Is this intended?

---

The code of limit after applying these suggestions:

function limit(fn) {
    var argumentLists = [], 
      invokeTimes = [], 
      waitId = null;

    function dequeue() {
        while (callsPending() && canCallNow()) {
            logInvocation(performance.now());
            fn.apply(this, argumentLists.shift());
        }

        if (callsPending()) {
            waitId = setTimeout(dequeue, timeToWait());
        }
    }

    function limited() {        
        argumentLists.push(arguments);
        dequeue();
    }

    limited.cancel = function() {
      clearTimeout(waitId);
    };

    return limited;

    function logInvocation(time) {
        if (invokeTimes.length === MAX_RUNS_PER_WINDOW) {
            invokeTimes.pop();
        }
        return invokeTimes.unshift(time);
    }

    function callsPending() {
        return argumentLists.length > 1;
    }

    function canCallNow() {
        return timeToWait() === 0;
    }

    function timeToWait() {        
        var now = performance.now();
        var timeOfInvocation = invokeTimes[MAX_RUNS_PER_WINDOW - 1] || 0;
        var ttw = timeOfInvocation + RUN_WINDOW - now;
        return Math.max(0, ttw);
    }
}

It would be nice to make MAX_RUNS_PER_WINDOW and RUN_WINDOW arguments of limit instead of constants.