[
https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12893262#action_12893262
]
stack commented on HBASE-2663:
------------------------------
bq. You'd still have to iterate the entire list and calculate the total sizes
for each priority and you'll still need the hash map, right?
The traversal can be avoided by keeping a running size that gets updated on
adds and removes?
bq. ...you also need a [thread-safe] constant time operation like
removeAndPushToFront..
This'd be the interesting bit.
FYI, this change, 674cf0d9b0648d146d5a67d95443826f1298b27a, got rid of the
creation of an array of CachedBlocks -- instead we just return the just-made LL
instead and iterate that. e.g.
{code}
@@ -414,10 +419,10 @@ public class LruBlockCache implements BlockCache,
HeapSize {
}
public long free(long toFree) {
- CachedBlock [] blocks = queue.get();
+ LinkedList<CachedBlock> blocks = queue.get();
long freedBytes = 0;
- for(int i=0; i<blocks.length; i++) {
- freedBytes += evictBlock(blocks[i]);
+ for(CachedBlock cb: blocks) {
+ freedBytes += evictBlock(cb);
if(freedBytes >= toFree) {
return freedBytes;
}
{code}
> LRU cache makes needless datastructure copies during eviction
> -------------------------------------------------------------
>
> Key: HBASE-2663
> URL: https://issues.apache.org/jira/browse/HBASE-2663
> Project: HBase
> Issue Type: Improvement
> Components: regionserver
> Reporter: Todd Lipcon
>
> Was browsing the LRU eviction code and came upon some very inefficient code.
> When we do eviction, BlockBucket.free() calls queue.get() which first inserts
> everything from the PriorityQueue<Block> into a LinkedList, then copies that
> entire linked list into an array. We then iterate over usually just a small
> percentage of the array to free some blocks until we have freed the requested
> amount.
> We ought to be able to just pull items out of the PriorityQueue directly and
> avoid all the churn.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
