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

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.

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.