I am looking for a Dict-like type which
allows me to keep only the last N values inserted, for some value of N::Int,
is thread-safe.
Background: memoization, where the resulting objects are large and I am unlikely to reuse more than the last N, even though I am doing these calculations M \gg N times and just using a Dict or similar would be wasting/exhausting memory. I don’t need memorization macros etc, just the data structure.
Do we really need thread-safe data structures for memoization? I mean, the operations on data should be idempotent for memoization. I’m not an expert, so tell me if I’m wrong.
Do you need it to store exactly the last N, or can it be probabilistic? that would be a lot easier. Also, what do you mean by thread safe? do you want to support multiple concurrent writers and readers? that will be very hard to do efficiently under heavy contention.
Yes, at least the underlying data structure should be thread-safe, because concurrent writes could corrupt it etc.
Probabilistic would be OK, but since @ericphanson’s solution does exactly what I asked for I am going with that.
No heavy threading or clashing is expected, I just need some basic protections for the possibility of concurrent access.
PS.: I continue to be amazed at Julia’s package ecosystem. 80% of the time when I think of a problem, it turns out that someone has implemented a solution years ago.
This is exactly what I meant by probabilistic. It has capacity N, but doesn’t store the most recent N, it just overwrites old entries in existing slots.
Sorry, I am confused, I thought the LRU implementation was deterministic. “Last” is defined by wall clock time, even if it is threaded. That suits me fine.
Probabilistic may not be quite the right word. LRUs are deterministic, but not in that they store the most recent N elements. That would be fairly expensive to support, so instead, they are just an N element hash table that instead of using separate chaining or probing, will replace the element on insertion.
As such, you end up with N buckets, each of which store the most recent insert into that bucket, which is a reasonable and cheap to maintain approximation of the N most recently stored items, but isn’t exactly the most recent N items. e.g. if you write N items into one, you will only have stored ~0.6*n elements with the rest being duplicates.
I think you’re mixing something up. A LRU (Least Recently Used) cache replaces the element that hasn’t been accessed for the longest time when a new element is inserted. There is nothing probabilistic about it, and there is no bucketing going on. It’s not backed by a hash table.
Note that “time” here is not necessarily true wall-clock time, it can just be an age counter that is incremented.
Wall-clock time is problematic: We live in a relativistic world; events can be time-like (on happens before, one after) or space-like; and any notion of “happens before in wall-clock time” for space-like events is subjective.
This may sound like ridiculous nit-picking, but a clock-cycle is ~6 cm, and intuitions from physics underpin the intuitions we use for concurrency, like e.g. Lamport clocks.
More concretely: If you want “Last” in a shared LRU to be well-defined, then all involved cores need to talk to each other in some way, which costs latency / power. Some of that can be speculated around, but it sucks. The situation becomes much worse when you’re not talking about multiple cores on the same CPU to synchronize on some “sequentially consistent” ordering, but are instead thinking about distributed systems (in these cases, your events have good chance to be actually space-like, not just “effectively space-like because of processing latencies”).
So I think the way to go is to use a lock-free variant of LRUCache.jl, accepting that you sometimes compute a value twice due to races and that “least recently” is a probabilistic guarantee.
LRUCache.jl acquires a single central lock on read-only access, which means that all accesses are sequenced and slow.
If this is good enough for you, then yay, no reason to look further. Just keep in mind that this will scale horribly to many-core CPUs.
Using something like hash(key) % N? And then the same mechanism to retrieve data from the LRU?
You get the 0.6 from a binomial? I’m not sure what you mean by duplicates. Do you mean collisions?