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);

• Pavlo: You mean that the function should be limited by the maximum number of calls AND execution time? E.g. printLetter should be called 10 times or less.
• 52d6c6af: I mean that the limited function should only execute the function logic a maximum of, say, ten times in one second. Any other function invocations (possibly made "too fast" to be serviced immediately) should run as soon as possible without breaking the rate limit (in this example, ten in a second).
• Flambino: I can't get this to run. It looks like it has some ES6 in exactly one place (callQueue.push(() => ...), but if I run it with Traceur, it just prints undefined indicating that the throttling isn't quite working...
• 52d6c6af: The code as-written is printing to the DOM. You may be missing the output. The code works on 46.0.2490.86 (64-bit) Chrome on OSX.
• Spike: The code doesn't work with Firefox 42.0, because Firefox incorrectly thinks arguments (line 12) refers to the anonymous arrow function's arguments, and not limited's arguments. It'll be fixed in Firefox 43.0. The code works on Chrome.

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.