Method and apparatus for dynamically adapting cache size based on estimated cache performance

1. A method of dynamically adjusting sizes of cache partitions of a cache, comprising:

using an eviction list data structure and potential hit gain counter to determine a potential cache partition hit rate increase of a first of the cache partitions if a size of the first of the cache partitions is increased by a first amount; and

using a potential hit loss counter to sum cache hits that occur in a tail portion of a second of the cache partitions to determine a potential cache partition hit decrease of the second of the cache partitions if a size of the second of the cache partitions is reduced by a second amount;

wherein using the potential hit loss counter to sum cache hits that occur in the tail portion of the second of the cache partitions to determine the potential cache partition hit decrease comprises determining, for each cache hit, where the cache hit occurred in the second of the cache partitions, and if the cache hit occurred in the tail portion of the second of the cache partitions, incrementing the potential hit loss counter.

2. The method of claim 1 , wherein the second amount is equal to the first amount.

3. The method of claim 1 , wherein the step of using the eviction list data structure to determine the potential cache partition hit rate increase of the first of the cache partitions comprises:

maintaining the eviction list data structure, the eviction list data structure containing an ordered list of addresses evicted from the first of the cache partitions, and maintaining a Potential Hit Gain (PHGa) counter data structure;

in connection with eviction of a first address from the first of the cache partitions, determining whether the first address is contained in the eviction list data structure; and

if the first address is contained in the eviction list data structure, incrementing the PHGa counter, and if the first address is not contained in the eviction list data structure, not incrementing the PHGa counter.

4. The method of claim 3 , wherein the eviction list data structure is implemented as a linked list of addresses, and each address has an eviction value indicating when it was evicted from the cache.

5. The method of claim 4 , further comprising a hash table of addresses contained in the eviction list data structure, and wherein the step of determining whether the first address is contained in the eviction list data structure comprises determining whether the address is contained in the hash table.

6. The method of claim 4 , wherein the step of maintaining an eviction list data structure comprises adding recently evicted addresses to the eviction list data structure and removing addresses from the eviction list data structure that have eviction values greater than a threshold from an eviction counter.

7. The method of claim 6 , wherein the eviction counter has a value indicative of a number of evictions that have occurred from the first of the cache partitions.

8. The method of claim 1 , wherein the tail portion of the second of the cache partitions is a range of addresses equal to the second amount.

9. The method of claim 1 , further comprising dynamically increasing the size of the first of the cache partitions and reducing the size of the second of the cache partitions if the determined potential cache partition hit rate increase associated with increasing the size of the first of the cache partitions exceeds the determined potential cache partition hit decrease of decreasing the size of the second of the cache partitions.

10. A method of dynamically adjusting a size of a cache, comprising:

determining a first amount of cache slots that can be added to the cache;

using an eviction list data structure and potential hit gain counter to determine a potential hit rate increase if the size of the cache is increased by the first amount;

increasing the cache size by the first amount if the potential hit rate increase is greater than a first threshold;

determining a second amount of cache slots that can be removed from the cache;

using a potential hit loss counter to sum cache hits that occur in a tail portion of the cache to determine a potential hit rate decrease if the size of the cache is reduced by the second amount; and

reducing the cache size by the second amount if the potential hit rate decrease is less than a second threshold and the potential hit rate increase is less than the first threshold.

11. The method of claim 10 , wherein if the potential hit rate increase is less than the first threshold and the potential hit rate decrease is greater than a second threshold, not adjusting the cache size.

12. The method of claim 10 , wherein if the potential hit rate increase is greater than the first threshold and the potential hit rate decrease is less than a second threshold, increasing the size of the cache by the first amount.

13. A method of dynamically adjusting a size of a cache, comprising:

determining a first amount of cache slots that can be added to the cache;

using an eviction list data structure and potential hit gain counter to determine a potential hit rate increase if the size of the cache is increased by the first amount; and increasing the cache size by the first amount if the potential hit rate increase is greater than a first threshold;

wherein the eviction list data structure is implemented as a linked list of addresses, and each entry has an eviction value indicating when it was evicted from the cache; and

wherein the step of maintaining the eviction list data structure comprises adding recently evicted addresses to the eviction list data structure and removing addresses from the eviction list data structure that have eviction values greater than a threshold from an eviction counter.

14. The method of claim 13 , wherein the eviction counter has a value indicative of a number of evictions that have occurred from the cache.

15. The method of claim 10 , wherein the tail portion of the cache is a range of addresses equal to the second amount.