You are viewing a plain text version of this content. The canonical link for it is here.
Posted to jcs-dev@jakarta.apache.org by "Maxim Gordienko (JIRA)" <ji...@apache.org> on 2008/06/10 15:28:45 UTC
[jira] Created: (JCS-43) 3 new eviction policies
3 new eviction policies
-----------------------
Key: JCS-43
URL: https://issues.apache.org/jira/browse/JCS-43
Project: JCS
Issue Type: Improvement
Components: Composite Cache
Affects Versions: jcs-1.3
Reporter: Maxim Gordienko
Assignee: Aaron Smuts
Patch attached to this issue contains three new eviction policies:
LFU - least frequently used item is removed on cache overflow
FIFO - the oldest item is removed
Expire - item with closest expiration time is removed
also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Commented: (JCS-43) 3 new eviction policies
Posted by "Aaron Smuts (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619124#action_12619124 ]
Aaron Smuts commented on JCS-43:
--------------------------------
The priority list throw a null pointer exception if you remove an element that isn't present. That's not good. A one line unit test exposed this.
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Commented: (JCS-43) 3 new eviction policies
Posted by "Maxim Gordienko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619141#action_12619141 ]
Maxim Gordienko commented on JCS-43:
------------------------------------
My primary concern was run time performance not memory efficiency.
Double linked list is not suitable for binary search, there is no O(1) index positioning in it. We have to traverse it element by element to find correct position for new one.
Priority list based lists outperform reference LRU implementation by the way. included performance tests show this.
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Commented: (JCS-43) 3 new eviction policies
Posted by "Aaron Smuts (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619127#action_12619127 ]
Aaron Smuts commented on JCS-43:
--------------------------------
The expiration memory cache is inefficient. Each different create time will require a different Set in the priority list. 10k items created at different times will require 10k HashSets. That's too much.
It would be slower but more memory efficient to keep a list sorted by time to live, rather than to try to put them in buckets.
You could use a double linked list, keep the last and the first ttl, then do binary search on insertion to find the spot. Then simply remove the last when we fill up. . ..
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Commented: (JCS-43) 3 new eviction policies
Posted by "Aaron Smuts (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619115#action_12619115 ]
Aaron Smuts commented on JCS-43:
--------------------------------
I'm looking into this now. These changes are extensive. There are changes to the synchronization in the LRU memory cache that will require careful scrutiny.
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Commented: (JCS-43) 3 new eviction policies
Posted by "Aaron Smuts (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619120#action_12619120 ]
Aaron Smuts commented on JCS-43:
--------------------------------
A few small things. This patch doesn't conform to JCS code style. It's not just that it is formatted differently, it lacks comments. All methods and variables need proper javadocs. I'll fix this.
This will take a while.
Thanks for the patch.
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Commented: (JCS-43) 3 new eviction policies
Posted by "Aaron Smuts (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619128#action_12619128 ]
Aaron Smuts commented on JCS-43:
--------------------------------
The LFU implementation has the same problem as the Expiration implementation. If all the items have different times accessed values, then they will require different Sets.
The priority list is too inefficient for these kinds of common use cases.
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Updated: (JCS-43) 3 new eviction policies
Posted by "Maxim Gordienko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Maxim Gordienko updated JCS-43:
-------------------------------
Attachment: expiration-strategies.patch
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Updated: (JCS-43) 3 new eviction policies
Posted by "Maxim Gordienko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Maxim Gordienko updated JCS-43:
-------------------------------
Attachment: (was: expiration-strategies.patch)
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Closed: (JCS-43) 3 new eviction policies
Posted by "Aaron Smuts (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Aaron Smuts closed JCS-43.
--------------------------
Resolution: Won't Fix
Thanks for the patch, but I can't take it as is. This patch has useful elements, but it is too big. There were too many unexplained changes to the abstract memory cache. The methods lacked useful comments, the code was not formatted in JCS style, the unit tests were insufficient, I found at least one bug, and the new memory caches were too memory inefficient. I'd like to see them as individual patches, perhaps. We should talk about how best to implement the LFU.
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Commented: (JCS-43) 3 new eviction policies
Posted by "Maxim Gordienko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619144#action_12619144 ]
Maxim Gordienko commented on JCS-43:
------------------------------------
We can implement both LFU and Expiration caches with ArrayList and binary search. But it will be much slower than current implementation.
Do we need another eviction policy almost as slow as current MRU?
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org
[jira] Updated: (JCS-43) 3 new eviction policies
Posted by "Maxim Gordienko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/JCS-43?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Maxim Gordienko updated JCS-43:
-------------------------------
Attachment: expiration-strategies.patch
> 3 new eviction policies
> -----------------------
>
> Key: JCS-43
> URL: https://issues.apache.org/jira/browse/JCS-43
> Project: JCS
> Issue Type: Improvement
> Components: Composite Cache
> Affects Versions: jcs-1.3
> Reporter: Maxim Gordienko
> Assignee: Aaron Smuts
> Attachments: expiration-strategies.patch
>
>
> Patch attached to this issue contains three new eviction policies:
> LFU - least frequently used item is removed on cache overflow
> FIFO - the oldest item is removed
> Expire - item with closest expiration time is removed
> also patch refactors MemoryCache hierarchy to allow easier extension
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org