As per my comments under your question, I would suggest that you use some C++ abstractions to do the "heavy" lifting for you. eg don't do your own memory allocation with new
nor your own initialisation with memset
.
Consider using a standard container. If in doubt use std:vector
. You could also use std::make_unique
to initialise an array, but why? Either way you now don't need a destructor. That's a bigger gain than it seems, because without the destructor, you can comply with the "Rule of zero". With the destructor (ie doing your own resource mgmt) you really need to comply with the "Rule of five", and your current code does not, causing potentially serious bugs as @henje nicely demonstrates below.
Use std::chrono
: it's really powerful, makes for easy to read code and allows you to easily adjust the resolution of your RateController
. The overhead is unlikely to be an issue unless you are talking millions of requests per seconds per RateController
.
While testing I found that your code has a bug: in check()
you need to test if the comparison is true before calling push()
, or you constantly overwrite your circular buffer and block the system.
For style designate your member variables by postfixing them with _
or similar so they are easy to identify. I like to put the public interface first in a class, but it's getting heavily subjective now.
Suggested use of C++ abstractions:
#include <chrono>
#include <vector>
class RateController {
using clk_t = std::chrono::system_clock;
using time_point_t = std::chrono::time_point<clk_t>;
public:
RateController(unsigned limit, unsigned long milliseconds)
: n_(limit), milliseconds_(milliseconds),
q(n_, time_point_t()) {}
bool check() {
time_point_t t = clk_t::now();
bool allowed = t - q[i_] >= std::chrono::milliseconds(milliseconds_);
if (allowed) push(t);
return allowed;
}
private:
unsigned n_;
unsigned long milliseconds_;
unsigned i_ = 0;
std::vector<time_point_t> q;
void push(time_point_t t) {
q[i_] = t;
i_ = (i_ + 1) % n_;
}
};
Algorithmically, your circular buffer idea could certainly work well, but it's quite a lot of storage, if you have many requests per interval. It depends on your use case.
If you have many throusands of clients and therefore many RateController
instances then perhaps you don't want to store 1000 x 8byte unsigned long
s (8k) for each one? In that case you could just divide time into predetermined slots (say every 10 minutes) and for each client just keep the time of last request and the number of requests in the current time slice. That would be ~500x less storage? This is similar to what @JerryCoffin was suggesting.
Below is a version which uses the time_slice
idea. It basically revolves around an integer division. No more vector
or other circular buffer. The behaviour is not identical, but I prefer this one.
If you are concerned that thousands of these RateController instances will all unblock at the same time when the new time slice starts and hence cause a load spike, you can address that too. Just generate a random offset in the range [0, time_slice_seconds) during construction and add it to the current time before doing the integer division. If you do this, I can no longer see the advantage of the circular buffer.
#include <chrono>
class RateController {
using clk_t = std::chrono::system_clock;
public:
RateController(unsigned limit, long time_slice_seconds)
: n_(limit), time_slice_(time_slice_seconds) {}
bool check() {
auto duration_since_epoch = clk_t::now().time_since_epoch();
long curr_time_slice =
std::chrono::duration_cast<std::chrono::seconds>(duration_since_epoch).count() /
time_slice_; // integer division!
if (curr_time_slice != last_time_slice_) {
last_time_slice_ = curr_time_slice;
count_ = 0;
}
++count_;
return (count_ <= n_);
}
private:
unsigned n_;
long time_slice_;
long last_time_slice_ = 0;
unsigned count_ = 0;
;
};
std::array
(if size known at compile time) or astd::vector
withreserve
. Maybe a FIFO queue is in fact what you need? iestd::queue
Your code is probably faster, because it's basically "raw C". But it would be "safer and easier" with C++'s abstractions. \$\endgroup\$std::queue
and seeing if it's "fast enough". If it is, leave it. If I had used C, I might have written something very similar to the above. My comment was merely meant to thought provoking, not critical. \$\endgroup\$std::vector
orstd::array
above introduces no overhead but automatically fixes several bugs that your code already has (such not obeying the rule of five). \$\endgroup\$