Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: jcs-2.0.0
    • Fix Version/s: None
    • Component/s: Composite Cache
    • Labels:
      None
    • Environment:
      current jcs trunk

      Description

      This is a refactoring/reformat of patch introduced in JCS-43.
      Patch is splitted in 6 parts
      1) refactoring memory caches to achieve higher code reuse
      2) refactoring MRU cache to use double linked list instead of LinkedList
      3) introduction of new PriorityList structure
      4-6) new caches FIFO, LFU, Expiration

      1. 0006-added-Expiration-memory-cache.patch
        19 kB
        Maxim Gordienko
      2. 0005-added-LFU-memory-cache.patch
        21 kB
        Maxim Gordienko
      3. 0004-added-new-FIFO-memory-cache.patch
        16 kB
        Maxim Gordienko
      4. 0003-added-new-structure-PriorityList.patch
        18 kB
        Maxim Gordienko
      5. 0002-improve-performance-or-MRU-list.patch
        9 kB
        Maxim Gordienko
      6. 0001-refactored-memory-cache-hierarchy.patch
        34 kB
        Maxim Gordienko

        Activity

        Hide
        Maxim Gordienko added a comment -

        refactored memory cache hierarchy

        moved common functionality (cache overflow, item removal, quiet get)
        to supeclass AbstractMemoryCache. Unified synchronization mutexes - use object
        instance instead of custom mutext.

        Show
        Maxim Gordienko added a comment - refactored memory cache hierarchy moved common functionality (cache overflow, item removal, quiet get) to supeclass AbstractMemoryCache. Unified synchronization mutexes - use object instance instead of custom mutext.
        Hide
        Maxim Gordienko added a comment -

        improve performance or MRU list

        used DoubleLinkedList instead of JVM's LinkedList. LinkedList is not very
        performant in cache usage scenario.

        Show
        Maxim Gordienko added a comment - improve performance or MRU list used DoubleLinkedList instead of JVM's LinkedList. LinkedList is not very performant in cache usage scenario.
        Hide
        Maxim Gordienko added a comment -

        added new structure - PriorityList

        this structure is used to maintain priority based collections (like LFU)

        Show
        Maxim Gordienko added a comment - added new structure - PriorityList this structure is used to maintain priority based collections (like LFU)
        Hide
        Maxim Gordienko added a comment -

        added new FIFO memory cache

        cache using the same eviction strategy as MRU cache, but does not upgrade
        element priority upon cache hit

        Show
        Maxim Gordienko added a comment - added new FIFO memory cache cache using the same eviction strategy as MRU cache, but does not upgrade element priority upon cache hit
        Hide
        Maxim Gordienko added a comment -

        added LFU memory cache

        cache is using PriorityList to store elements based on their hit ratio

        Show
        Maxim Gordienko added a comment - added LFU memory cache cache is using PriorityList to store elements based on their hit ratio
        Hide
        Maxim Gordienko added a comment -

        added Expiration memory cache

        cache is using PriorityList to store elements on the basis of their
        expiration time

        Show
        Maxim Gordienko added a comment - added Expiration memory cache cache is using PriorityList to store elements on the basis of their expiration time
        Hide
        Aaron Smuts added a comment -

        I'm looking over this. I guess we need a style guide. All methods and variables meed javadocs. Not everything has them now but all new things need them.

        I'm not sure why you would do this:

        + if ( value == null )
        +

        { + throw new NullPointerException(); + }

        Why nut just balk or throw and illegal argument exception. I'd prefer doing nothing.

        There are a lot of changes to the core memory cache here. It will take some time.

        Show
        Aaron Smuts added a comment - I'm looking over this. I guess we need a style guide. All methods and variables meed javadocs. Not everything has them now but all new things need them. I'm not sure why you would do this: + if ( value == null ) + { + throw new NullPointerException(); + } Why nut just balk or throw and illegal argument exception. I'd prefer doing nothing. There are a lot of changes to the core memory cache here. It will take some time.
        Hide
        Aaron Smuts added a comment -

        The naming the new abstract methods in the base is inconsistent. Somtimes they are prefixed with do and sometimes there is a suffix. And it looks like there are other methods that children should call, but there is nothing that will make it happen. For instance "getStoredItemQuiet".

        Some of this definitely makes sense though.

        Show
        Aaron Smuts added a comment - The naming the new abstract methods in the base is inconsistent. Somtimes they are prefixed with do and sometimes there is a suffix. And it looks like there are other methods that children should call, but there is nothing that will make it happen. For instance "getStoredItemQuiet". Some of this definitely makes sense though.
        Hide
        Aaron Smuts added a comment -

        Can't you use a TreeMap instead of this priority list? It has log add, remove and contains.

        Show
        Aaron Smuts added a comment - Can't you use a TreeMap instead of this priority list? It has log add, remove and contains.
        Hide
        Maxim Gordienko added a comment -

        if new (abstract) template method was introduces in superclass the method name is prefixed by do-
        if method is a helper method (like getStoredItemQuiet()) intended to be called by subclass - the name has no pefixes or suffixes.
        I followed naming style of spring test framework.

        Show
        Maxim Gordienko added a comment - if new (abstract) template method was introduces in superclass the method name is prefixed by do- if method is a helper method (like getStoredItemQuiet()) intended to be called by subclass - the name has no pefixes or suffixes. I followed naming style of spring test framework.
        Hide
        Maxim Gordienko added a comment -

        TreeMap introduce number of Map.Entry objects. Single new Map.Entry object for every object added to the map.

        The main goal of this patch is to minimize memory consumption, leaving performance at acceptable level.
        The sorted ArrayList is not as efficient as TreeMap for inserts/removes or search but it definitely has smaller memory requirements.

        Show
        Maxim Gordienko added a comment - TreeMap introduce number of Map.Entry objects. Single new Map.Entry object for every object added to the map. The main goal of this patch is to minimize memory consumption, leaving performance at acceptable level. The sorted ArrayList is not as efficient as TreeMap for inserts/removes or search but it definitely has smaller memory requirements.
        Hide
        Aaron Smuts added a comment -

        The thing to do would be to use the tree map and not the outer map. There is no need for two data-structures here. This suggest that the abstract memory cache should not be extended for lfu.

        FIFO is trivial and fixing up the MRU is also trivial. I'll implement those two roughly as you would have. But we can't use this lfu. And I don't want to change so much at once. Let's get a decent LFU and then refactor the base if there is a common base at that point.

        Also, we aren't spring and we don't follow the same conventions. That's not to say that we have the clearest conventions.

        Show
        Aaron Smuts added a comment - The thing to do would be to use the tree map and not the outer map. There is no need for two data-structures here. This suggest that the abstract memory cache should not be extended for lfu. FIFO is trivial and fixing up the MRU is also trivial. I'll implement those two roughly as you would have. But we can't use this lfu. And I don't want to change so much at once. Let's get a decent LFU and then refactor the base if there is a common base at that point. Also, we aren't spring and we don't follow the same conventions. That's not to say that we have the clearest conventions.
        Hide
        Maxim Gordienko added a comment -

        Can not abandon outer map (from AbstractMemoryCache).
        This map is used to find DoubleLinkedListNode for key, and only with this object we can mutate PriorityList.

        If we abandon HashMap from the super class how should we find required element?

        If we want to mutate PriorityList without DoubleLinkedListNode we fell to implementation provided in JCS-43 with a collection as a TreeMap element.

        Show
        Maxim Gordienko added a comment - Can not abandon outer map (from AbstractMemoryCache). This map is used to find DoubleLinkedListNode for key, and only with this object we can mutate PriorityList. If we abandon HashMap from the super class how should we find required element? If we want to mutate PriorityList without DoubleLinkedListNode we fell to implementation provided in JCS-43 with a collection as a TreeMap element.
        Hide
        Aaron Smuts added a comment -

        I don't understand. I wasn't suggesting that we should take the map out of the abstract memory cache. I was suggesting that the LFU implementation not use the abstract memory cache. It doesn't need two maps. Not all memory caches need to extend that base. They simply need to implement the interface.

        Show
        Aaron Smuts added a comment - I don't understand. I wasn't suggesting that we should take the map out of the abstract memory cache. I was suggesting that the LFU implementation not use the abstract memory cache. It doesn't need two maps. Not all memory caches need to extend that base. They simply need to implement the interface.
        Hide
        Aaron Smuts added a comment -

        Another option, is to have the children implement a createMap method. I'm going to do that.

        Show
        Aaron Smuts added a comment - Another option, is to have the children implement a createMap method. I'm going to do that.
        Hide
        Aaron Smuts added a comment -

        I just checked some refactoring of the memory cache. A possible LFU implementation could use a tree map and extend the base layer. I sped up the MRU and added a FIFO memory cache.

        I'll probably have to change the second abstraction layer. I think the MRU will need to remove the last if full then add the new element to the tail. Right now it adds items to the front and then moves them to the back if they are used.

        Show
        Aaron Smuts added a comment - I just checked some refactoring of the memory cache. A possible LFU implementation could use a tree map and extend the base layer. I sped up the MRU and added a FIFO memory cache. I'll probably have to change the second abstraction layer. I think the MRU will need to remove the last if full then add the new element to the tail. Right now it adds items to the front and then moves them to the back if they are used.
        Hide
        Maxim Gordienko added a comment -

        No no, i completely agree with you about base class extension. Contract on memory cache is defined by interface not by base abstract class.

        I was talking about data structure PriorityList. It requires support structure just like DoubleLikedList does.
        Here an example - methods get*(key)/remove(key)
        We have to locate list node by key before we can efficiently modify any of these structures.
        Replacement of super class' HashMap with TreeMap in PriorityList does not solve the problem - we still need the support data structure (now this structure is the HashMap from superclass).

        Show
        Maxim Gordienko added a comment - No no, i completely agree with you about base class extension. Contract on memory cache is defined by interface not by base abstract class. I was talking about data structure PriorityList. It requires support structure just like DoubleLikedList does. Here an example - methods get*(key)/remove(key) We have to locate list node by key before we can efficiently modify any of these structures. Replacement of super class' HashMap with TreeMap in PriorityList does not solve the problem - we still need the support data structure (now this structure is the HashMap from superclass).
        Hide
        Aaron Smuts added a comment -

        I think that you can implement an LFU expiration policy using a treemap alone. You wrap all keys in an object that contains a usage count. You create the treemap with a comparator that checks this value. When you get an item, you update the usage count, remove it, and then put it back into the map. You have to remove it, because the comparator won't be consistent with equals. (I think that this should work). This might be slow. . . If it works, it would allow you to expire items that were less popular. Here popularity would be the popularity over the life of the item. It would be very hard to displace an old item that was once very popular. Elvis might be stuck in the cache forever. . . .

        Show
        Aaron Smuts added a comment - I think that you can implement an LFU expiration policy using a treemap alone. You wrap all keys in an object that contains a usage count. You create the treemap with a comparator that checks this value. When you get an item, you update the usage count, remove it, and then put it back into the map. You have to remove it, because the comparator won't be consistent with equals. (I think that this should work). This might be slow. . . If it works, it would allow you to expire items that were less popular. Here popularity would be the popularity over the life of the item. It would be very hard to displace an old item that was once very popular. Elvis might be stuck in the cache forever. . . .
        Hide
        Maxim Gordienko added a comment -

        We cannot use TreeMap this way. It does not allow multiple values "equals" by comparator (the items with cmp.compare(a,b) == 0 or a.compareTo(b) == 0).
        The only solution is to wrap item in "multi-item" container which will introduce another PriorityList like structure.

        Show
        Maxim Gordienko added a comment - We cannot use TreeMap this way. It does not allow multiple values "equals" by comparator (the items with cmp.compare(a,b) == 0 or a.compareTo(b) == 0). The only solution is to wrap item in "multi-item" container which will introduce another PriorityList like structure.

          People

          • Assignee:
            Aaron Smuts
            Reporter:
            Maxim Gordienko
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development