Best way to implement LRU cache?

  • Hi.
    I'm trying to find a good way to implement an object cache for my
    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 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 my own double-linked list. Does that
    sound reasonable? I'm sure this is an old, solved problem, any
    suggestions?

    Thanks,
    Daniel
  • 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
  • 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      (<Cocoa-dev...>)
    > Help/Unsubscribe/Update your Subscription:
    > http://lists.apple.com/mailman/options/cocoa-dev/<andrei...>
    >
    > This email sent to <andrei...>
previous month october 2006 next month
MTWTFSS
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
Go to today