New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
The fixed-size allocation in v7 restricts many previously possible use cases #208
Comments
I could see how that would be useful, and it would be interesting and fun to implement. However, it's also quite a footgun. The performance improvements in version 7 comes largely from the fact that allocation is done all up front, and thus gc is kept to a minimum in hot paths, there are always a deterministic number of reads and writes, never any run-time pauses, and so on. (This is actually somewhat a problem with c++ containers for performance critical applications, as well.) I'm not willing to give up the performance benefits of fixed-size allocation by default for users calling it with a set There are two general approaches I can think of that could be explored: resizing and chaining. In both cases, we'll definitely want to set an "absolute max" size, at which point we refuse to keep growing, and should require that there be a time limit, so that we can have some sense of when to downsize (otherwise the cache size ends up sitting forever at the maximum, so why not just use a big The largest possible absolute max would be
Resizing down is trickier in either case. Let's say whenever Then, once it's compressed (which will be O(n) at best, no way around that), then in the resize case we alloc new smaller arrays and cut over, and in the chain case, we just pop the largest item off the stack. The chaining approach sounds more promising, but it does add a lot of complexity (which can't really be avoided, even in the non-resizing case, unless it's just a whole different module). That complexity will slow it down, because now we are adding an extra bit of math every time we access an index, instead of just getting an integer and knowing that's the final answer. So that's really not a good idea either, I guess. Another approach to the downsizing (which isn't nearly as space-efficient) in the chaining case, would be to keep a count of how many entries are indexed in each range, and drop the buffer at the end of the list only when it is empty. We'd still have to remove those indexes from the Yet another approach, which would not be as fast, I guess, would be to just not use typedarrays at all, don't do any up-front allocation, and rely on the fact that normal javascript Arrays can grow unbounded. That saves most of the complexity, but at the cost of predictably fast behavior. (When you hit the limit of V8's Array optimization, it'll get surprisingly slow.) And you'll most likely want to have TBH, if you really want a boundless time-limited cache, that's maybe a different thing, and you should use a module purpose built for that. Probably the cleanest way to do this would be to implement a pure time-based cache, with no max size and no up-front allocation, autoPrune always on, and Arrays instead of uint typed arrays for index tracking. It won't be "blazing fast cache to speed up anything", but it'd still perhaps be "pretty good cache to speed up ttl-based things". Maybe lru-cache needs a sibling ;) |
Supporting unbound behavior isn't actually that hard, now that I really look at it. Just have to use Array instead of TypedArray everywhere, and it means Maybe this is a dumb question, but in those cases where you'd be having an unbound storage space cache with a ttl, is the recency of use order information actually important? Because this would be about as good performance as you could hope for (significantly better than lru-cache, in fact), and seem to do everything you'd need: class TTLMap extends Map {
constructor ({ ttl }) {
if (!ttl || typeof ttl !== 'number' || ttl !== Math.floor(ttl) || ttl < 1) {
throw new TypeError('ttl must be positive integer')
}
super()
this.ttl = ttl
this.timers = new Map()
}
set (k, v, ttl = this.ttl) {
if (this.timers.has(k)) {
clearTimeout(this.timers.get(k))
}
const timer = setTimeout(() => this.delete(k), ttl)
if (timer && timer.unref) timer.unref()
this.timers.set(k, timer)
return super.set(k, v)
}
delete (k) {
if (this.timers.has(k)) {
clearTimeout(this.timers.get(k))
this.timers.delete(k)
}
return super.delete(k)
}
} |
That's a very good question, actually. I'd say that in those cases, the order doesn't really matter and this simple |
I suppose that makes it clear that the best solution is really pointing to another module for that use case, too bad |
Thinking about this a little bit more... I think if you are primarily concerned with tracking age of entries, then wouldn't you want I was thinking maybe an optimal data structure would be a B-tree mapping the expiration time to the entries expiring at at that time, and then remembered that V8 sorts objects with integer keys numerically.
That's (i believe?) an unspecified impl detail, but it's been around long enough it'll probably break the internet if they ever change it. So with that, you could keep a null-proto object mapping *keys () {
for (const [exp, keys]] of Object.entries(this.expirations)) {
for (const k of keys) {
yield k
}
}
}
purgeStale () {
for (const [exp, keys] of Object.keys(this.expirations)) {
if (exp < now()) {
for (const k of keys) {
this.delete(k)
}
}
}
} |
I don't think I ever needed that but it does make sense. Particularly for purging - having a separate timer per key is something I wasn't really sure about performance-wise but I see lru-cache also does this, at least with |
I wouldn't do it as a fixed interval, but more like a debounce. So if you know a purge is coming soon-ish, you just wait for that, but only schedule when needed. It's a bit of extra bookkeeping, so I skipped it, but if someone asks, it's not too hard to implement, and might improve things somewhat. It's not so bad to assign a bunch of timers to fire at the same ms, because Node stacks them up internally anyway under a single Timer handle. I guess if you have enough of them to matter, you probably have other problems 😅 |
This also prevents setting size=0 if maxSize is set, since that is a recipe for disaster. At least one of max, maxSize, or ttl MUST be set, to prevent unbounded growth of the cache. And really, without ttlAutopurge, it's effectively unsafe and unbounded in that case anyway, *especially* if allowStale is set. This is potentially "unsafe at any speed" territory, so it emits a process warning in that case. If max is not set, then regular Array is used to track items, without setting an initial Array capacity. This will often perform much worse, but in many cases, it's not so bad. Bigger hazard is definitely unbounded memory consumption. Fix: #208
This also prevents setting size=0 if maxSize is set, since that is a recipe for disaster. At least one of max, maxSize, or ttl MUST be set, to prevent unbounded growth of the cache. And really, without ttlAutopurge, it's effectively unsafe and unbounded in that case anyway, *especially* if allowStale is set. This is potentially "unsafe at any speed" territory, so it emits a process warning in that case. If max is not set, then regular Array is used to track items, without setting an initial Array capacity. This will often perform much worse, but in many cases, it's not so bad. Bigger hazard is definitely unbounded memory consumption. Fix: #208
This also prevents setting size=0 if maxSize is set, since that is a recipe for disaster. At least one of max, maxSize, or ttl MUST be set, to prevent unbounded growth of the cache. And really, without ttlAutopurge, it's effectively unsafe and unbounded in that case anyway, *especially* if allowStale is set. This is potentially "unsafe at any speed" territory, so it emits a process warning in that case. If max is not set, then regular Array is used to track items, without setting an initial Array capacity. This will often perform much worse, but in many cases, it's not so bad. Bigger hazard is definitely unbounded memory consumption. Fix: #208
If what you really want is a TTL cache that is more focused on time than storage space and recency of use, you may be interested in using https://www.npmjs.com/package/@isaacs/ttlcache I haven't benchmarked it extensively, but it was possible to make the overall algorithm much simpler, by throwing away all of the use-recency tracking, and leveraging the fact that V8 has some absurdly good optimizations for null-prototype objects with integer-numeric keys, which it keeps sorted. |
Looks good, will give it a try in a few places! |
I've already seen #193 which explains why
max
option is mandatory in v7 and the explanation made me wonder if the allocation is done to themax
capacity right away, or in some increments. Looking at the code, it seems that it really allocates all memory based onmax
right away, which seems rather unfortunate (and something that should be also documented).I understand that the module is called "LRU" cache, so it makes some sense for it to enforce max capacity (without which it isn't really LRU), but since it historically provided a lot of extra functionality on top, and still provides the
maxAge
option, another common usage pattern I've seen is using onlymaxAge
without settingmax
for time-based caching. Particularly in apps where you need a mix of LRU and time-based caching, it's very useful to have both provided by the same module with the same API.A simple workaround many people will probably think of is setting a very high value for
max
but that's not good because of the upfront allocation. To keep the advantages of the new approach, would it make sense to implement optional resizing so that people could opt to dynamic sizing with occasional resize cost (similar to how e.g. c++ containers work)?The text was updated successfully, but these errors were encountered: