#5612

Committed 11 Jul 2026 03:47PM UTC coverage: 71.292% (-28.7%) from 100.0%

Build # #5612

Build Type

push

github

Committed by

ben-manes

Commit Message

Preserve timestamps on a raced same-instance refresh

The automatic refreshIfNeeded path checked for an equal-value reload
before the ABA/ownership check and returned without preserving the
timestamps, so a reload completing after a concurrent put(k,
sameInstance) did a full update — shifting the entry's expiration
forward by the reload's in-flight duration and stomping the write.
Mirror the explicit-refresh fix: check ownership first. An owned
reload installs the value (refreshing metadata even for a same
instance), while a raced reload preserves the write's timestamps and
only notifies REPLACED when the value differs.

Coverage Stats

2957 of 4134 branches covered (71.53%)

3 of 3 new or added lines in 1 file covered. (100.0%)

2408 existing lines in 53 files now uncovered.

5980 of 8388 relevant lines covered (71.29%)

0.71 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.59

/caffeine/src/main/java/com/github/benmanes/caffeine/cache/FrequencySketch.java

/*
 * Copyright 2015 Ben Manes. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.benmanes.caffeine.cache;

import static com.github.benmanes.caffeine.cache.Caffeine.requireArgument;

import com.google.errorprone.annotations.Var;

/**
 * A probabilistic multiset for estimating the popularity of an element within a time window. The
 * maximum frequency of an element is limited to 15 (4-bits) and an aging process periodically
 * halves the popularity of all elements.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 */
@SuppressWarnings({"ConstantValue", "NotNullFieldNotInitialized"})
final class FrequencySketch {

  /*
   * This class maintains a 4-bit CountMinSketch [1] with periodic aging to provide the popularity
   * history for the TinyLfu admission policy [2]. The time and space efficiency of the sketch
   * allows it to cheaply estimate the frequency of an entry in a stream of cache access events.
   *
   * The counter matrix is represented as a single-dimensional array holding 16 counters per slot. A
   * fixed depth of four balances the accuracy and cost, resulting in a width of four times the
   * length of the array. To retain an accurate estimation, the array's length equals the maximum
   * number of entries in the cache, increased to the closest power-of-two to exploit more efficient
   * bit masking. This configuration results in a confidence of 93.75% and an error bound of
   * e / width.
   *
   * To improve hardware efficiency, an item's counters are constrained to a 64-byte block, which is
   * the size of an L1 cache line. This differs from the theoretical ideal where counters are
   * uniformly distributed to minimize collisions. In that configuration, the memory accesses are
   * not predictable and lack spatial locality, which may cause the pipeline to need to wait for
   * four memory loads. Instead, the items are uniformly distributed to blocks, and each counter is
   * uniformly selected from a distinct 16-byte segment. While the runtime memory layout may result
   * in the blocks not being cache-aligned, the L2 spatial prefetcher tries to load aligned pairs of
   * cache lines, so the typical cost is only one memory access.
   *
   * The frequency of all entries is aged periodically using a sampling window based on the maximum
   * number of entries in the cache. This is referred to as the reset operation by TinyLfu and keeps
   * the sketch fresh by dividing all counters by two and subtracting based on the number of odd
   * counters found. The O(n) cost of aging is amortized, ideal for hardware prefetching, and uses
   * inexpensive bit manipulations per array location.
   *
   * [1] An Improved Data Stream Summary: The Count-Min Sketch and its Applications
   * http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf
   * [2] TinyLFU: A Highly Efficient Cache Admission Policy
   * https://dl.acm.org/citation.cfm?id=3149371
   * [3] Hash Function Prospector: Three round functions
   * https://github.com/skeeto/hash-prospector#three-round-functions
   */

  static final long RESET_MASK = 0x7777777777777777L;
  static final long ONE_MASK = 0x1111111111111111L;
  static final int MIN_SKETCH_SIZE = 256;

  int sampleSize;
  int blockMask;
  long[] table;
  int size;

  /**
   * Creates a lazily initialized frequency sketch, requiring {@link #ensureCapacity} be called
   * when the maximum size of the cache has been determined.
   */
  @SuppressWarnings("NullAway.Init")
  public FrequencySketch() {}

  /**
   * Initializes and increases the capacity of this {@code FrequencySketch} instance, if necessary,
   * to ensure that it can accurately estimate the popularity of elements given the maximum size of
   * the cache. This operation forgets all previous counts when resizing.
   *
   * @param maximumSize the maximum size of the cache
   */
  @SuppressWarnings("Varifier")
  public void ensureCapacity(long maximumSize) {
    requireArgument(maximumSize >= 0);
    int maximum = Math.max((int) Math.min(maximumSize, Integer.MAX_VALUE >>> 1), MIN_SKETCH_SIZE);
    if ((table != null) && (table.length >= maximum)) {
      return;
    }

    sampleSize = (int) Math.min(10L * maximum, Integer.MAX_VALUE);
    table = new long[Caffeine.ceilingPowerOfTwo(maximum)];
    blockMask = (table.length >>> 3) - 1;
    size = 0;
  }

  /**
   * Returns if the sketch has not yet been initialized, requiring that {@link #ensureCapacity} is
   * called before it begins to track frequencies.
   */
  public boolean isNotInitialized() {
    return (table == null);
  }

  /**
   * Returns the estimated number of occurrences of an element, up to the maximum (15).
   *
   * @param e the element to count occurrences of
   * @return the estimated number of occurrences of the element; possibly zero but never negative
   */
  @SuppressWarnings("Varifier")
  public int frequency(Object e) {
    if (isNotInitialized()) {
      return 0;
    }

    @Var int frequency = Integer.MAX_VALUE;
    int blockHash = spread(e.hashCode());
    int counterHash = rehash(blockHash);
    int block = (blockHash & blockMask) << 3;
    for (int i = 0; i < 4; i++) {
      int h = counterHash >>> (i << 3);
      int index = (h >>> 1) & 15;
      int offset = h & 1;
      int slot = block + offset + (i << 1);
      int count = (int) ((table[slot] >>> (index << 2)) & 0xfL);
      frequency = Math.min(frequency, count);
    }
    return frequency;
  }

  /**
   * Increments the popularity of the element if it does not exceed the maximum (15). The popularity
   * of all elements will be periodically down sampled when the observed events exceed a threshold.
   * This process provides a frequency aging to allow expired long term entries to fade away.
   *
   * @param e the element to add
   */
  @SuppressWarnings({"ShortCircuitBoolean", "UnnecessaryLocalVariable"})
  public void increment(Object e) {
    if (isNotInitialized()) {
      return;
    }

    int blockHash = spread(e.hashCode());
    int counterHash = rehash(blockHash);
    int block = (blockHash & blockMask) << 3;

    // Loop unrolling improves throughput by 10m ops/s
    int h0 = counterHash;
    int h1 = counterHash >>> 8;
    int h2 = counterHash >>> 16;
    int h3 = counterHash >>> 24;

    int index0 = (h0 >>> 1) & 15;
    int index1 = (h1 >>> 1) & 15;
    int index2 = (h2 >>> 1) & 15;
    int index3 = (h3 >>> 1) & 15;

    int slot0 = block + (h0 & 1);
    int slot1 = block + (h1 & 1) + 2;
    int slot2 = block + (h2 & 1) + 4;
    int slot3 = block + (h3 & 1) + 6;

    boolean added =
          incrementAt(slot0, index0)
        | incrementAt(slot1, index1)
        | incrementAt(slot2, index2)
        | incrementAt(slot3, index3);

    if (added && (++size == sampleSize)) {
      reset();
    }
  }

  /** Applies a supplemental hash function to defend against a poor quality hash. */
  static int spread(@Var int x) {
    x ^= x >>> 17;
    x *= 0xed5ad4bb;
    x ^= x >>> 11;
    x *= 0xac4c1b51;
    x ^= x >>> 15;
    return x;
  }

  /** Applies another round of hashing for additional randomization. */
  static int rehash(@Var int x) {
    x *= 0x31848bab;
    x ^= x >>> 14;
    return x;
  }

  /**
   * Increments the specified counter by 1 if it is not already at the maximum value (15).
   *
   * @param i the table index (16 counters)
   * @param j the counter to increment
   * @return if incremented
   */
  boolean incrementAt(int i, int j) {
    int offset = j << 2;
    long mask = (0xfL << offset);
    if ((table[i] & mask) != mask) {
      table[i] += (1L << offset);
      return true;
    }
    return false;
  }

  /** Reduces every counter by half of its original value. */
  void reset() {
    @Var long count = 0;
    for (int i = 0; i < table.length; i++) {
      count += Long.bitCount(table[i] & ONE_MASK);
      table[i] = (table[i] >>> 1) & RESET_MASK;
    }
    size = (int) ((size - (count >>> 2)) >>> 1);
  }
}

1	/*
2	* Copyright 2015 Ben Manes. All Rights Reserved.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package com.github.benmanes.caffeine.cache;
17
18	import static com.github.benmanes.caffeine.cache.Caffeine.requireArgument;
19
20	import com.google.errorprone.annotations.Var;
21
22	/**
23	* A probabilistic multiset for estimating the popularity of an element within a time window. The
24	* maximum frequency of an element is limited to 15 (4-bits) and an aging process periodically
25	* halves the popularity of all elements.
26	*
27	* @author ben.manes@gmail.com (Ben Manes)
28	*/
29	@SuppressWarnings({"ConstantValue", "NotNullFieldNotInitialized"})
30	final class FrequencySketch {
31
32	/*
33	* This class maintains a 4-bit CountMinSketch [1] with periodic aging to provide the popularity
34	* history for the TinyLfu admission policy [2]. The time and space efficiency of the sketch
35	* allows it to cheaply estimate the frequency of an entry in a stream of cache access events.
36	*
37	* The counter matrix is represented as a single-dimensional array holding 16 counters per slot. A
38	* fixed depth of four balances the accuracy and cost, resulting in a width of four times the
39	* length of the array. To retain an accurate estimation, the array's length equals the maximum
40	* number of entries in the cache, increased to the closest power-of-two to exploit more efficient
41	* bit masking. This configuration results in a confidence of 93.75% and an error bound of
42	* e / width.
43	*
44	* To improve hardware efficiency, an item's counters are constrained to a 64-byte block, which is
45	* the size of an L1 cache line. This differs from the theoretical ideal where counters are
46	* uniformly distributed to minimize collisions. In that configuration, the memory accesses are
47	* not predictable and lack spatial locality, which may cause the pipeline to need to wait for
48	* four memory loads. Instead, the items are uniformly distributed to blocks, and each counter is
49	* uniformly selected from a distinct 16-byte segment. While the runtime memory layout may result
50	* in the blocks not being cache-aligned, the L2 spatial prefetcher tries to load aligned pairs of
51	* cache lines, so the typical cost is only one memory access.
52	*
53	* The frequency of all entries is aged periodically using a sampling window based on the maximum
54	* number of entries in the cache. This is referred to as the reset operation by TinyLfu and keeps
55	* the sketch fresh by dividing all counters by two and subtracting based on the number of odd
56	* counters found. The O(n) cost of aging is amortized, ideal for hardware prefetching, and uses
57	* inexpensive bit manipulations per array location.
58	*
59	* [1] An Improved Data Stream Summary: The Count-Min Sketch and its Applications
60	* http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf
61	* [2] TinyLFU: A Highly Efficient Cache Admission Policy
62	* https://dl.acm.org/citation.cfm?id=3149371
63	* [3] Hash Function Prospector: Three round functions
64	* https://github.com/skeeto/hash-prospector#three-round-functions
65	*/
66
67	static final long RESET_MASK = 0x7777777777777777L;
68	static final long ONE_MASK = 0x1111111111111111L;
69	static final int MIN_SKETCH_SIZE = 256;
70
71	int sampleSize;
72	int blockMask;
73	long[] table;
74	int size;
75
76	/**
77	* Creates a lazily initialized frequency sketch, requiring {@link #ensureCapacity} be called
78	* when the maximum size of the cache has been determined.
79	*/
80	@SuppressWarnings("NullAway.Init")
81	public FrequencySketch() {}	1✔
82
83	/**
84	* Initializes and increases the capacity of this {@code FrequencySketch} instance, if necessary,
85	* to ensure that it can accurately estimate the popularity of elements given the maximum size of
86	* the cache. This operation forgets all previous counts when resizing.
87	*
88	* @param maximumSize the maximum size of the cache
89	*/
90	@SuppressWarnings("Varifier")
91	public void ensureCapacity(long maximumSize) {
92	requireArgument(maximumSize >= 0);	1✔
93	int maximum = Math.max((int) Math.min(maximumSize, Integer.MAX_VALUE >>> 1), MIN_SKETCH_SIZE);	1✔
94	if ((table != null) && (table.length >= maximum)) {	1✔
95	return;	1✔
96	}
97
98	sampleSize = (int) Math.min(10L * maximum, Integer.MAX_VALUE);	1✔
99	table = new long[Caffeine.ceilingPowerOfTwo(maximum)];	1✔
100	blockMask = (table.length >>> 3) - 1;	1✔
101	size = 0;	1✔
102	}	1✔
103
104	/**
105	* Returns if the sketch has not yet been initialized, requiring that {@link #ensureCapacity} is
106	* called before it begins to track frequencies.
107	*/
108	public boolean isNotInitialized() {
109	return (table == null);	1✔
110	}
111
112	/**
113	* Returns the estimated number of occurrences of an element, up to the maximum (15).
114	*
115	* @param e the element to count occurrences of
116	* @return the estimated number of occurrences of the element; possibly zero but never negative
117	*/
118	@SuppressWarnings("Varifier")
119	public int frequency(Object e) {
120	if (isNotInitialized()) {	1!
UNCOV 121	return 0;	×
122	}
123
124	@Var int frequency = Integer.MAX_VALUE;	1✔
125	int blockHash = spread(e.hashCode());	1✔
126	int counterHash = rehash(blockHash);	1✔
127	int block = (blockHash & blockMask) << 3;	1✔
128	for (int i = 0; i < 4; i++) {	1✔
129	int h = counterHash >>> (i << 3);	1✔
130	int index = (h >>> 1) & 15;	1✔
131	int offset = h & 1;	1✔
132	int slot = block + offset + (i << 1);	1✔
133	int count = (int) ((table[slot] >>> (index << 2)) & 0xfL);	1✔
134	frequency = Math.min(frequency, count);	1✔
135	}
136	return frequency;	1✔
137	}
138
139	/**
140	* Increments the popularity of the element if it does not exceed the maximum (15). The popularity
141	* of all elements will be periodically down sampled when the observed events exceed a threshold.
142	* This process provides a frequency aging to allow expired long term entries to fade away.
143	*
144	* @param e the element to add
145	*/
146	@SuppressWarnings({"ShortCircuitBoolean", "UnnecessaryLocalVariable"})
147	public void increment(Object e) {
148	if (isNotInitialized()) {	1✔
149	return;	1✔
150	}
151
152	int blockHash = spread(e.hashCode());	1✔
153	int counterHash = rehash(blockHash);	1✔
154	int block = (blockHash & blockMask) << 3;	1✔
155
156	// Loop unrolling improves throughput by 10m ops/s
157	int h0 = counterHash;	1✔
158	int h1 = counterHash >>> 8;	1✔
159	int h2 = counterHash >>> 16;	1✔
160	int h3 = counterHash >>> 24;	1✔
161
162	int index0 = (h0 >>> 1) & 15;	1✔
163	int index1 = (h1 >>> 1) & 15;	1✔
164	int index2 = (h2 >>> 1) & 15;	1✔
165	int index3 = (h3 >>> 1) & 15;	1✔
166
167	int slot0 = block + (h0 & 1);	1✔
168	int slot1 = block + (h1 & 1) + 2;	1✔
169	int slot2 = block + (h2 & 1) + 4;	1✔
170	int slot3 = block + (h3 & 1) + 6;	1✔
171
172	boolean added =	1✔
173	incrementAt(slot0, index0)	1✔
174	\| incrementAt(slot1, index1)	1✔
175	\| incrementAt(slot2, index2)	1✔
176	\| incrementAt(slot3, index3);	1✔
177
178	if (added && (++size == sampleSize)) {	1✔
179	reset();	1✔
180	}
181	}	1✔
182
183	/** Applies a supplemental hash function to defend against a poor quality hash. */
184	static int spread(@Var int x) {
185	x ^= x >>> 17;	1✔
186	x *= 0xed5ad4bb;	1✔
187	x ^= x >>> 11;	1✔
188	x *= 0xac4c1b51;	1✔
189	x ^= x >>> 15;	1✔
190	return x;	1✔
191	}
192
193	/** Applies another round of hashing for additional randomization. */
194	static int rehash(@Var int x) {
195	x *= 0x31848bab;	1✔
196	x ^= x >>> 14;	1✔
197	return x;	1✔
198	}
199
200	/**
201	* Increments the specified counter by 1 if it is not already at the maximum value (15).
202	*
203	* @param i the table index (16 counters)
204	* @param j the counter to increment
205	* @return if incremented
206	*/
207	boolean incrementAt(int i, int j) {
208	int offset = j << 2;	1✔
209	long mask = (0xfL << offset);	1✔
210	if ((table[i] & mask) != mask) {	1✔
211	table[i] += (1L << offset);	1✔
212	return true;	1✔
213	}
214	return false;	1✔
215	}
216
217	/** Reduces every counter by half of its original value. */
218	void reset() {
219	@Var long count = 0;	1✔
220	for (int i = 0; i < table.length; i++) {	1✔
221	count += Long.bitCount(table[i] & ONE_MASK);	1✔
222	table[i] = (table[i] >>> 1) & RESET_MASK;	1✔
223	}
224	size = (int) ((size - (count >>> 2)) >>> 1);	1✔
225	}	1✔
226	}

ben-manes / caffeine / #5612

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous