Re: Best way to implement LRU cache?
Re: Best way to implement LRU cache?
- Subject: Re: Best way to implement LRU cache?
- From: Andrei Tchijov <email@hidden>
- Date: Fri, 27 Oct 2006 20:38:13 -0400
Instead of implementing strict LRU do "lazy" version. Remember time
when particular entry was used last time. Every so often, when cache
size grew bigger than predefined threshold, run "cleaner" procedure
which will delete predefined number of "old" entries. You can
actually put all entries in the Array, sort by last time used and
delete "n" oldest or you can just decide that anything older then "m"
seconds is too old and delete it.
Basically, the idea is that if you do not have to spend extra time on
EACH operation to enforce LRU, you can afford spend some-what
significant amount of time ONCE IN A WHILE to keep you cache size
under control. Unless your application is targeted to VERY resource
constrained hardware (and these days it must be something embedded
into toaster to qualify as resource constrained ) you do not have to
be too precise in cache size enforcement. As soon as it is not going
to grow endlessly it can fluctuate.
All above could be completely wrong. To come up with best solution,
one need to consider a lot of details:
- once object was used is it more-probable of less-probable that it
will be used again soon?
- are you going to cache bunch of small objects or few big?
- do some of the objects get used much more often then others?
- does it really take a lot of CPU cycles to construct the object?
- are all object of the same size? and are they "linear" - consist of
single chunk of memory?
...
list goes on.
just my $0.02
On Oct 27, 2006, at 8:05 PM, Daniel Gobera wrote:
Hi.
I'm trying to find a good way to implement an object cache for a
Core Data-based application. I would like to use the LRU policy, so
the least recently used object is discarded when the cache is full.
Objects are uniquely identified and retrieved by a "name" attribute.
I'll need a way to quickly tell if an object is cached and retrieve
it, so a hash table by "name" would ideally fit here
(NSDictionary). The problem is that a Dictionary is unordered, so
there's no way to know which is the oldest object.
I'm guessing I'll need a second structure, a List. An NSArray would
normally be a good choice here, as it's internally implemented as a
list and allows to remove objects from any part an inexpensively
insert at the beginning or end. The problem here would be to keep
both structures in sync.
When an object is accessed by its "name", I'll need to remove it
from its current array position and insert it in the top again
(make it the most recently used one). But how to find it in the
array? I don't want to linearly traverse it every time (if this is
what indexOfObject: does). If in the dictionary I keep a
correspondence between "names" and index in the array, I'll need to
update all indexes when an object from the middle of the array is
removed and all subsequent indexes are decreased.
A Java HashList class would be ideal for this, but there's no
equivalent in Cocoa (there's not even a list or queue). I think
I'll have to implement my own. I'll still use an NSDictionary, but
instead of an array, I'll implement a own double-linked list to
eliminate the indexes problem. Does that sound reasonable? I'm sure
this is an old, solved problem, any suggestions?
Thanks,
Daniel
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden