Patent ID: 8713258

Claim:
A method performed by one or more data processing apparatus, the method comprising: initializing a current estimate value for an estimate of a stack distance of a later access to an address in a cache, the current estimate value indicating an estimate of a number of accesses to the cache having unique addresses between the later access to the address and an earlier access to the address; initializing, for each of K buckets wherein K is greater than zero, a minimum value and a maximum value for the bucket, wherein each bucket corresponds to a range of possible fingerprint values for the accesses, and wherein the minimum value for the bucket is based at least partly on a lowest fingerprint value in the range corresponding to the bucket and the maximum value for the bucket is based at least partly on a highest fingerprint value in the range corresponding to the bucket; and processing at least a first access between the earlier access and the later access to update the current estimate value, including: determining a first fingerprint value for the first access; identifying a first bucket of the K buckets for the first access based on the first fingerprint value; determining that the first fingerprint value is between the minimum value and the maximum value for the first bucket; and responsive to determining that the first fingerprint value is between the minimum value and the maximum value for the first bucket, increasing the current estimate value and adjusting the minimum value or the maximum value for the first bucket.