Pass `Integer` between `PersistentStringIndexer` and `CompactPersistentActionCache` instead of `int`.
There are three maps involved in the action cache implementation. This allows the same `Integer` instance to be used in all three maps. Previously, for values outside of the `IntegerCache` range (`[-128, 127]`), autoboxing was creating a new instance for each of the three maps.
PiperOrigin-RevId: 625492711
Change-Id: I8e4798c4f44e20f485dd0f9ffb79b149d0e96c24
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java b/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
index ba21a14..cb9ae97 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
@@ -85,7 +85,7 @@
private final PersistentStringIndexer indexer;
private long nextUpdateSecs;
- public ActionMap(
+ ActionMap(
ConcurrentMap<Integer, byte[]> map,
PersistentStringIndexer indexer,
Clock clock,
@@ -346,8 +346,8 @@
@Override
@Nullable
public ActionCache.Entry get(String key) {
- int index = indexer.getIndex(key);
- if (index < 0) {
+ Integer index = indexer.getIndex(key);
+ if (index == null) {
return null;
}
byte[] data = map.get(index);
@@ -366,7 +366,7 @@
@Override
public void put(String key, ActionCache.Entry entry) {
// Encode record. Note that both methods may create new mappings in the indexer.
- int index = indexer.getOrCreateIndex(key);
+ Integer index = indexer.getOrCreateIndex(key);
byte[] content;
try {
content = encode(indexer, entry);
@@ -391,7 +391,10 @@
@Override
public void remove(String key) {
- map.remove(indexer.getIndex(key));
+ Integer index = indexer.getIndex(key);
+ if (index != null) {
+ map.remove(index);
+ }
}
@Override
@@ -652,7 +655,7 @@
}
private static String getStringForIndex(StringIndexer indexer, int index) throws IOException {
- String path = (index >= 0 ? indexer.getStringForIndex(index) : null);
+ String path = index >= 0 ? indexer.getStringForIndex(index) : null;
if (path == null) {
throw new IOException("Corrupted string index");
}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexer.java b/src/main/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexer.java
index 18a401e..58040cf 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexer.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexer.java
@@ -42,7 +42,6 @@
@ConditionallyThreadSafe // Each instance must be instantiated with a different dataPath.
final class PersistentStringIndexer implements StringIndexer {
- private static final int NOT_FOUND = -1;
private static final int INITIAL_ENTRIES = 10000;
/** Instantiates and loads instance of the persistent string indexer. */
@@ -84,35 +83,35 @@
}
@Override
- public int getOrCreateIndex(String s) {
+ public Integer getOrCreateIndex(String s) {
Integer i = stringToInt.get(s);
- if (i == null) {
- s = StringCanonicalizer.intern(s);
- synchronized (this) {
- // First, make sure another thread hasn't just added the entry:
- i = stringToInt.get(s);
- if (i != null) {
- return i;
- }
-
- int ind = intToString.size();
- stringToInt.put(s, ind);
- intToString.put(ind, s);
- return ind;
+ if (i != null) {
+ return i;
+ }
+ s = StringCanonicalizer.intern(s);
+ synchronized (this) {
+ // First, make sure another thread hasn't just added the entry.
+ i = stringToInt.get(s);
+ if (i != null) {
+ return i;
}
- } else {
+
+ i = intToString.size();
+ stringToInt.put(s, i);
+ intToString.put(i, s);
return i;
}
}
@Override
- public int getIndex(String s) {
- return stringToInt.getOrDefault(s, NOT_FOUND);
+ @Nullable
+ public Integer getIndex(String s) {
+ return stringToInt.get(s);
}
@Override
@Nullable
- public String getStringForIndex(int i) {
+ public String getStringForIndex(Integer i) {
return intToString.get(i);
}
diff --git a/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java b/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java
index 28a4f39..e6d992f0 100644
--- a/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java
+++ b/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java
@@ -15,7 +15,13 @@
import javax.annotation.Nullable;
-/** Provides bidirectional string ⇔ unique integer mapping. */
+/**
+ * Provides bidirectional {@link String} ⇔ unique {@link Integer} mapping.
+ *
+ * <p>{@link Integer} is used in place of primitive {@code int} as it is assumed that indices will
+ * be stored in maps. Passing {@link Integer} across API boundaries makes it less likely to store
+ * duplicate instances and create garbage due to autoboxing.
+ */
public interface StringIndexer {
/** Removes all mappings. */
@@ -24,21 +30,19 @@
/** Returns the number of strings in the index. */
int size();
- /**
- * Creates new mapping for the given string if necessary and returns string index. Also, as a side
- * effect, additional mappings may be created for various prefixes of the given string.
- */
- int getOrCreateIndex(String s);
+ /** Creates new mapping for the given string if necessary and returns string index. */
+ Integer getOrCreateIndex(String s);
/**
* Returns the unique index for the given string if one was created via {@link #getOrCreateIndex},
- * or else {@code -1}.
+ * or else {@code null}.
*/
- int getIndex(String s);
+ @Nullable
+ Integer getIndex(String s);
/**
* Returns the string associated with the given index or {@code null} if it is not in the index.
*/
@Nullable
- String getStringForIndex(int i);
+ String getStringForIndex(Integer i);
}
diff --git a/src/test/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexerTest.java b/src/test/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexerTest.java
index 6876590..0d2f486 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexerTest.java
@@ -35,22 +35,22 @@
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;
-/**
- * Test for the PersistentStringIndexer class.
- */
+/** Tests for {@link PersistentStringIndexer}. */
@RunWith(JUnit4.class)
-public class PersistentStringIndexerTest {
+public final class PersistentStringIndexerTest {
private static class ManualClock implements Clock {
private long currentTime = 0L;
- ManualClock() { }
+ ManualClock() {}
- @Override public long currentTimeMillis() {
+ @Override
+ public long currentTimeMillis() {
throw new AssertionError("unexpected method call");
}
- @Override public long nanoTime() {
+ @Override
+ public long nanoTime() {
return currentTime;
}
@@ -59,40 +59,37 @@
}
}
- private PersistentStringIndexer psi;
- private Map<Integer, String> mappings = new ConcurrentHashMap<>();
- private Scratch scratch = new Scratch();
- private ManualClock clock = new ManualClock();
- private Path dataPath;
- private Path journalPath;
+ private final Map<Integer, String> mappings = new ConcurrentHashMap<>();
+ private final Scratch scratch = new Scratch();
+ private final ManualClock clock = new ManualClock();
+ private final Path dataPath = scratch.resolve("/cache/test.dat");
+ private final Path journalPath = scratch.resolve("/cache/test.journal");
+ private PersistentStringIndexer indexer;
@Before
- public final void createIndexer() throws Exception {
- dataPath = scratch.resolve("/cache/test.dat");
- journalPath = scratch.resolve("/cache/test.journal");
- psi = PersistentStringIndexer.create(dataPath, clock);
+ public void createIndexer() throws Exception {
+ indexer = PersistentStringIndexer.create(dataPath, clock);
}
private void assertSize(int expected) {
- assertThat(psi.size()).isEqualTo(expected);
+ assertThat(indexer.size()).isEqualTo(expected);
}
private void assertIndex(int expected, String s) {
- int index = psi.getOrCreateIndex(s);
+ int index = indexer.getOrCreateIndex(s);
assertThat(index).isEqualTo(expected);
mappings.put(expected, s);
}
private void assertContent() {
- for (int i = 0; i < psi.size(); i++) {
- if(mappings.get(i) != null) {
- assertThat(mappings).containsEntry(i, psi.getStringForIndex(i));
+ for (int i = 0; i < indexer.size(); i++) {
+ if (mappings.get(i) != null) {
+ assertThat(mappings).containsEntry(i, indexer.getStringForIndex(i));
}
}
}
-
private void setupTestContent() {
assertSize(0);
assertIndex(0, "abcdefghi"); // Create leafs
@@ -111,13 +108,12 @@
}
/**
- * Writes lots of entries with labels "fooconcurrent[int]" at the same time.
- * The set of labels written is deterministic, but the label:index mapping is
- * not.
+ * Writes lots of entries with labels "fooconcurrent[int]" at the same time. The set of labels
+ * written is deterministic, but the label:index mapping is not.
*/
- private void writeLotsOfEntriesConcurrently(final int numToWrite) throws InterruptedException {
- final int NUM_THREADS = 10;
- final CountDownLatch synchronizerLatch = new CountDownLatch(NUM_THREADS);
+ private void writeLotsOfEntriesConcurrently(int numToWrite) throws InterruptedException {
+ int numThreads = 10;
+ CountDownLatch synchronizerLatch = new CountDownLatch(numThreads);
TestRunnable indexAdder =
() -> {
@@ -126,12 +122,12 @@
synchronizerLatch.await();
String value = "fooconcurrent" + i;
- mappings.put(psi.getOrCreateIndex(value), value);
+ mappings.put(indexer.getOrCreateIndex(value), value);
}
};
Collection<TestThread> threads = new ArrayList<>();
- for (int i = 0; i < NUM_THREADS; i++) {
+ for (int i = 0; i < numThreads; i++) {
TestThread thread = new TestThread(indexAdder);
thread.start();
threads.add(thread);
@@ -143,6 +139,21 @@
}
@Test
+ public void returnsSameIntegerInstance() {
+ int n = 1000; // Greater than the default java.lang.Integer.IntegerCache.high of 127.
+ for (int i = 0; i < n; i++) {
+ String s = "a".repeat(i);
+ Integer index = indexer.getOrCreateIndex(s);
+ assertThat(indexer.getIndex(s)).isSameInstanceAs(index);
+ }
+ }
+
+ @Test
+ public void unindexedStringReturnsNull() {
+ assertThat(indexer.getIndex("absent")).isNull();
+ }
+
+ @Test
public void testNormalOperation() throws Exception {
assertThat(dataPath.exists()).isFalse();
assertThat(journalPath.exists()).isFalse();
@@ -155,12 +166,12 @@
assertThat(dataPath.exists()).isFalse();
assertThat(journalPath.exists()).isTrue();
- psi.save(); // Successful save will remove journal file.
+ indexer.save(); // Successful save will remove journal file.
assertThat(dataPath.exists()).isTrue();
assertThat(journalPath.exists()).isFalse();
// Now restore data from file and verify it.
- psi = PersistentStringIndexer.create(dataPath, clock);
+ indexer = PersistentStringIndexer.create(dataPath, clock);
assertThat(journalPath.exists()).isFalse();
clock.advance(4);
assertSize(10);
@@ -182,7 +193,7 @@
assertThat(journalPath.exists()).isTrue();
// Now restore data from file and verify it. All data should be restored from journal;
- psi = PersistentStringIndexer.create(dataPath, clock);
+ indexer = PersistentStringIndexer.create(dataPath, clock);
assertThat(dataPath.exists()).isTrue();
assertThat(journalPath.exists()).isFalse();
clock.advance(4);
@@ -196,7 +207,7 @@
assertThat(dataPath.exists()).isFalse();
assertThat(journalPath.exists()).isFalse();
setupTestContent();
- psi.save();
+ indexer.save();
assertThat(dataPath.exists()).isTrue();
assertThat(journalPath.exists()).isFalse();
long oldDataFileLen = dataPath.getFileSize();
@@ -208,7 +219,7 @@
assertThat(journalPath.exists()).isTrue();
// Now restore data from file and verify it. All data should be restored from journal;
- psi = PersistentStringIndexer.create(dataPath, clock);
+ indexer = PersistentStringIndexer.create(dataPath, clock);
assertThat(dataPath.exists()).isTrue();
assertThat(journalPath.exists()).isFalse();
assertThat(dataPath.getFileSize())
@@ -224,12 +235,12 @@
assertThat(dataPath.exists()).isFalse();
assertThat(journalPath.exists()).isFalse();
setupTestContent();
- psi.save();
+ indexer.save();
assertThat(dataPath.exists()).isTrue();
assertThat(journalPath.exists()).isFalse();
long oldDataFileLen = dataPath.getFileSize();
- int size = psi.size();
+ int size = indexer.size();
int numToWrite = 50000;
writeLotsOfEntriesConcurrently(numToWrite);
assertThat(journalPath.exists()).isFalse();
@@ -240,7 +251,7 @@
assertThat(journalPath.exists()).isTrue();
// Now restore data from file and verify it. All data should be restored from journal;
- psi = PersistentStringIndexer.create(dataPath, clock);
+ indexer = PersistentStringIndexer.create(dataPath, clock);
assertThat(dataPath.exists()).isTrue();
assertThat(journalPath.exists()).isFalse();
assertThat(dataPath.getFileSize())
@@ -257,7 +268,7 @@
FileSystemUtils.writeContentAsLatin1(journalPath, "bogus content");
IOException e =
assertThrows(
- IOException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+ IOException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
assertThat(e).hasMessageThat().contains("too short: Only 13 bytes");
journalPath.delete();
@@ -273,30 +284,32 @@
byte[] journalContent = FileSystemUtils.readContent(journalPath);
// Now restore data from file and verify it. All data should be restored from journal;
- psi = PersistentStringIndexer.create(dataPath, clock);
+ indexer = PersistentStringIndexer.create(dataPath, clock);
assertThat(dataPath.exists()).isTrue();
assertThat(journalPath.exists()).isFalse();
// Now put back truncated journal. We should get an error.
assertThat(dataPath.delete()).isTrue();
- FileSystemUtils.writeContent(journalPath,
- Arrays.copyOf(journalContent, journalContent.length - 1));
- assertThrows(EOFException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+ FileSystemUtils.writeContent(
+ journalPath, Arrays.copyOf(journalContent, journalContent.length - 1));
+ assertThrows(
+ EOFException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
// Corrupt the journal with a negative size value.
byte[] journalCopy = journalContent.clone();
// Flip this bit to make the key size negative.
journalCopy[95] = -2;
- FileSystemUtils.writeContent(journalPath, journalCopy);
+ FileSystemUtils.writeContent(journalPath, journalCopy);
e =
assertThrows(
- IOException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+ IOException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
assertThat(e).hasMessageThat().contains("corrupt key length");
// Now put back corrupted journal. We should get an error.
journalContent[journalContent.length - 13] = 100;
- FileSystemUtils.writeContent(journalPath, journalContent);
- assertThrows(IOException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+ FileSystemUtils.writeContent(journalPath, journalContent);
+ assertThrows(
+ IOException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
}
@Test
@@ -306,7 +319,7 @@
assertThat(journalPath.exists()).isFalse();
assertIndex(9, "abc1234"); // This should flush journal to disk.
- psi.save();
+ indexer.save();
assertThat(dataPath.exists()).isTrue();
assertThat(journalPath.exists()).isFalse();
@@ -331,7 +344,7 @@
IOException e =
assertThrows(
- IOException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+ IOException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
assertThat(e).hasMessageThat().contains("Corrupted filename index has duplicate entry");
}
@@ -353,7 +366,7 @@
// Subsequent updates should succeed even though journaling is disabled at this point.
clock.advance(4);
assertIndex(10, "another record");
- IOException e = assertThrows(IOException.class, () -> psi.save());
+ IOException e = assertThrows(IOException.class, () -> indexer.save());
assertThat(e).hasMessageThat().contains(journalPath.getPathString() + " (Is a directory)");
}
}