diff options
author | cpovirk <cpovirk@google.com> | 2024-04-30 11:40:32 -0700 |
---|---|---|
committer | Google Java Core Libraries <jake-team+copybara@google.com> | 2024-04-30 11:43:01 -0700 |
commit | fddc95d79ae7b26efe6d63d0e003cbd73f92e66f (patch) | |
tree | dc3419f0b155598d70547faf434f372639ed69f2 | |
parent | 70a98115d828f17d8c997b43347b4ce989130bce (diff) | |
download | guava-fddc95d79ae7b26efe6d63d0e003cbd73f92e66f.tar.gz |
Micro-optimize `singletonIterator` one more time.
I messed up the benchmarks, so there's a chance that cl/626542813 actually made things worse. The impact is probably still small, and it's hard to actually tell what will work better in practice. But this is largely an educational experience for me, so it continues....
RELNOTES=n/a
PiperOrigin-RevId: 629480444
4 files changed, 144 insertions, 56 deletions
diff --git a/android/guava-tests/test/com/google/common/collect/IteratorsTest.java b/android/guava-tests/test/com/google/common/collect/IteratorsTest.java index aba34944c..20e542f7c 100644 --- a/android/guava-tests/test/com/google/common/collect/IteratorsTest.java +++ b/android/guava-tests/test/com/google/common/collect/IteratorsTest.java @@ -20,6 +20,7 @@ import static com.google.common.collect.CollectPreconditions.checkRemove; import static com.google.common.collect.Iterators.advance; import static com.google.common.collect.Iterators.get; import static com.google.common.collect.Iterators.getLast; +import static com.google.common.collect.Iterators.singletonIterator; import static com.google.common.collect.Lists.newArrayList; import static com.google.common.collect.testing.IteratorFeature.MODIFIABLE; import static com.google.common.collect.testing.IteratorFeature.UNMODIFIABLE; @@ -800,21 +801,19 @@ public class IteratorsTest extends TestCase { } public void testConcatPartiallyAdvancedSecond() { - Iterator<String> itr1 = - Iterators.concat(Iterators.singletonIterator("a"), Iterators.forArray("b", "c")); + Iterator<String> itr1 = Iterators.concat(singletonIterator("a"), Iterators.forArray("b", "c")); assertEquals("a", itr1.next()); assertEquals("b", itr1.next()); - Iterator<String> itr2 = Iterators.concat(Iterators.singletonIterator("d"), itr1); + Iterator<String> itr2 = Iterators.concat(singletonIterator("d"), itr1); assertEquals("d", itr2.next()); assertEquals("c", itr2.next()); } public void testConcatPartiallyAdvancedFirst() { - Iterator<String> itr1 = - Iterators.concat(Iterators.singletonIterator("a"), Iterators.forArray("b", "c")); + Iterator<String> itr1 = Iterators.concat(singletonIterator("a"), Iterators.forArray("b", "c")); assertEquals("a", itr1.next()); assertEquals("b", itr1.next()); - Iterator<String> itr2 = Iterators.concat(itr1, Iterators.singletonIterator("d")); + Iterator<String> itr2 = Iterators.concat(itr1, singletonIterator("d")); assertEquals("c", itr2.next()); assertEquals("d", itr2.next()); } @@ -976,7 +975,7 @@ public class IteratorsTest extends TestCase { } public void testPartition_badSize() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); try { Iterators.partition(source, 0); fail(); @@ -991,7 +990,7 @@ public class IteratorsTest extends TestCase { } public void testPartition_singleton1() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); Iterator<List<Integer>> partitions = Iterators.partition(source, 1); assertTrue(partitions.hasNext()); assertTrue(partitions.hasNext()); @@ -1000,7 +999,7 @@ public class IteratorsTest extends TestCase { } public void testPartition_singleton2() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); Iterator<List<Integer>> partitions = Iterators.partition(source, 2); assertTrue(partitions.hasNext()); assertTrue(partitions.hasNext()); @@ -1047,7 +1046,7 @@ public class IteratorsTest extends TestCase { } public void testPaddedPartition_badSize() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); try { Iterators.paddedPartition(source, 0); fail(); @@ -1062,7 +1061,7 @@ public class IteratorsTest extends TestCase { } public void testPaddedPartition_singleton1() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); Iterator<List<Integer>> partitions = Iterators.paddedPartition(source, 1); assertTrue(partitions.hasNext()); assertTrue(partitions.hasNext()); @@ -1071,7 +1070,7 @@ public class IteratorsTest extends TestCase { } public void testPaddedPartition_singleton2() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); Iterator<List<Integer>> partitions = Iterators.paddedPartition(source, 2); assertTrue(partitions.hasNext()); assertTrue(partitions.hasNext()); @@ -1537,13 +1536,38 @@ public class IteratorsTest extends TestCase { assertEquals(3, Iterators.frequency(list.iterator(), null)); } + public void testSingletonIteratorBasic() { + Iterator<Integer> i = singletonIterator(1); + assertThat(i.hasNext()).isTrue(); + assertThat(i.next()).isEqualTo(1); + assertThat(i.hasNext()).isFalse(); + } + + public void testSingletonNullIteratorBasic() { + Iterator<@Nullable Integer> i = singletonIterator(null); + assertThat(i.hasNext()).isTrue(); + assertThat(i.next()).isEqualTo(null); + assertThat(i.hasNext()).isFalse(); + } + @GwtIncompatible // slow (~4s) - public void testSingletonIterator() { + public void testSingletonIteratorWithIteratorTester() { new IteratorTester<Integer>( 3, UNMODIFIABLE, singleton(1), IteratorTester.KnownOrder.KNOWN_ORDER) { @Override protected Iterator<Integer> newTargetIterator() { - return Iterators.singletonIterator(1); + return singletonIterator(1); + } + }.test(); + } + + @GwtIncompatible // slow (~4s) + public void testSingletonNullIteratorWithIteratorTester() { + new IteratorTester<@Nullable Integer>( + 3, UNMODIFIABLE, singleton(null), IteratorTester.KnownOrder.KNOWN_ORDER) { + @Override + protected Iterator<@Nullable Integer> newTargetIterator() { + return singletonIterator(null); } }.test(); } diff --git a/android/guava/src/com/google/common/collect/Iterators.java b/android/guava/src/com/google/common/collect/Iterators.java index 3b4a2b293..6cbb2f17c 100644 --- a/android/guava/src/com/google/common/collect/Iterators.java +++ b/android/guava/src/com/google/common/collect/Iterators.java @@ -1100,34 +1100,54 @@ public final class Iterators { */ public static <T extends @Nullable Object> UnmodifiableIterator<T> singletonIterator( @ParametricNullness T value) { - return new SingletonIterator<>(value); + if (value != null) { + return new SingletonIterator<>(value); + } + @SuppressWarnings("nullness") // For `value` to be null, T must be a nullable type. + UnmodifiableIterator<T> result = (UnmodifiableIterator<T>) new SingletonNullIterator<T>(); + return result; } private static final class SingletonIterator<T extends @Nullable Object> extends UnmodifiableIterator<T> { - private @Nullable Object valueOrThis; + private @Nullable T valueOrNull; - SingletonIterator(T value) { - this.valueOrThis = value; + SingletonIterator(@NonNull T value) { + this.valueOrNull = value; } @Override public boolean hasNext() { - return valueOrThis != this; + return valueOrNull != null; } @Override - @ParametricNullness - public T next() { - Object result = valueOrThis; - valueOrThis = this; + public @NonNull T next() { + T result = valueOrNull; + valueOrNull = null; // We put the common case first, even though it's unlikely to matter if the code is run much: // https://shipilev.net/jvm/anatomy-quarks/28-frequency-based-code-layout/ - if (result != this) { - // The field held either a `T` or `this`, and it turned out not to be `this`. - @SuppressWarnings("unchecked") - T t = (T) result; - return t; + if (result != null) { + return result; + } + throw new NoSuchElementException(); + } + } + + private static final class SingletonNullIterator<T> extends UnmodifiableIterator<@Nullable T> { + private boolean returned; + + @Override + public boolean hasNext() { + return !returned; + } + + @Override + public @Nullable T next() { + if (!returned) { + // common case first, as in SingletonIterator + returned = true; + return null; } throw new NoSuchElementException(); } diff --git a/guava-tests/test/com/google/common/collect/IteratorsTest.java b/guava-tests/test/com/google/common/collect/IteratorsTest.java index 7e173ab6a..837e64eeb 100644 --- a/guava-tests/test/com/google/common/collect/IteratorsTest.java +++ b/guava-tests/test/com/google/common/collect/IteratorsTest.java @@ -20,6 +20,7 @@ import static com.google.common.collect.CollectPreconditions.checkRemove; import static com.google.common.collect.Iterators.advance; import static com.google.common.collect.Iterators.get; import static com.google.common.collect.Iterators.getLast; +import static com.google.common.collect.Iterators.singletonIterator; import static com.google.common.collect.Lists.newArrayList; import static com.google.common.collect.testing.IteratorFeature.MODIFIABLE; import static com.google.common.collect.testing.IteratorFeature.UNMODIFIABLE; @@ -800,21 +801,19 @@ public class IteratorsTest extends TestCase { } public void testConcatPartiallyAdvancedSecond() { - Iterator<String> itr1 = - Iterators.concat(Iterators.singletonIterator("a"), Iterators.forArray("b", "c")); + Iterator<String> itr1 = Iterators.concat(singletonIterator("a"), Iterators.forArray("b", "c")); assertEquals("a", itr1.next()); assertEquals("b", itr1.next()); - Iterator<String> itr2 = Iterators.concat(Iterators.singletonIterator("d"), itr1); + Iterator<String> itr2 = Iterators.concat(singletonIterator("d"), itr1); assertEquals("d", itr2.next()); assertEquals("c", itr2.next()); } public void testConcatPartiallyAdvancedFirst() { - Iterator<String> itr1 = - Iterators.concat(Iterators.singletonIterator("a"), Iterators.forArray("b", "c")); + Iterator<String> itr1 = Iterators.concat(singletonIterator("a"), Iterators.forArray("b", "c")); assertEquals("a", itr1.next()); assertEquals("b", itr1.next()); - Iterator<String> itr2 = Iterators.concat(itr1, Iterators.singletonIterator("d")); + Iterator<String> itr2 = Iterators.concat(itr1, singletonIterator("d")); assertEquals("c", itr2.next()); assertEquals("d", itr2.next()); } @@ -976,7 +975,7 @@ public class IteratorsTest extends TestCase { } public void testPartition_badSize() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); try { Iterators.partition(source, 0); fail(); @@ -991,7 +990,7 @@ public class IteratorsTest extends TestCase { } public void testPartition_singleton1() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); Iterator<List<Integer>> partitions = Iterators.partition(source, 1); assertTrue(partitions.hasNext()); assertTrue(partitions.hasNext()); @@ -1000,7 +999,7 @@ public class IteratorsTest extends TestCase { } public void testPartition_singleton2() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); Iterator<List<Integer>> partitions = Iterators.partition(source, 2); assertTrue(partitions.hasNext()); assertTrue(partitions.hasNext()); @@ -1047,7 +1046,7 @@ public class IteratorsTest extends TestCase { } public void testPaddedPartition_badSize() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); try { Iterators.paddedPartition(source, 0); fail(); @@ -1062,7 +1061,7 @@ public class IteratorsTest extends TestCase { } public void testPaddedPartition_singleton1() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); Iterator<List<Integer>> partitions = Iterators.paddedPartition(source, 1); assertTrue(partitions.hasNext()); assertTrue(partitions.hasNext()); @@ -1071,7 +1070,7 @@ public class IteratorsTest extends TestCase { } public void testPaddedPartition_singleton2() { - Iterator<Integer> source = Iterators.singletonIterator(1); + Iterator<Integer> source = singletonIterator(1); Iterator<List<Integer>> partitions = Iterators.paddedPartition(source, 2); assertTrue(partitions.hasNext()); assertTrue(partitions.hasNext()); @@ -1537,13 +1536,38 @@ public class IteratorsTest extends TestCase { assertEquals(3, Iterators.frequency(list.iterator(), null)); } + public void testSingletonIteratorBasic() { + Iterator<Integer> i = singletonIterator(1); + assertThat(i.hasNext()).isTrue(); + assertThat(i.next()).isEqualTo(1); + assertThat(i.hasNext()).isFalse(); + } + + public void testSingletonNullIteratorBasic() { + Iterator<@Nullable Integer> i = singletonIterator(null); + assertThat(i.hasNext()).isTrue(); + assertThat(i.next()).isEqualTo(null); + assertThat(i.hasNext()).isFalse(); + } + @GwtIncompatible // slow (~4s) - public void testSingletonIterator() { + public void testSingletonIteratorWithIteratorTester() { new IteratorTester<Integer>( 3, UNMODIFIABLE, singleton(1), IteratorTester.KnownOrder.KNOWN_ORDER) { @Override protected Iterator<Integer> newTargetIterator() { - return Iterators.singletonIterator(1); + return singletonIterator(1); + } + }.test(); + } + + @GwtIncompatible // slow (~4s) + public void testSingletonNullIteratorWithIteratorTester() { + new IteratorTester<@Nullable Integer>( + 3, UNMODIFIABLE, singleton(null), IteratorTester.KnownOrder.KNOWN_ORDER) { + @Override + protected Iterator<@Nullable Integer> newTargetIterator() { + return singletonIterator(null); } }.test(); } diff --git a/guava/src/com/google/common/collect/Iterators.java b/guava/src/com/google/common/collect/Iterators.java index 3b4a2b293..6cbb2f17c 100644 --- a/guava/src/com/google/common/collect/Iterators.java +++ b/guava/src/com/google/common/collect/Iterators.java @@ -1100,34 +1100,54 @@ public final class Iterators { */ public static <T extends @Nullable Object> UnmodifiableIterator<T> singletonIterator( @ParametricNullness T value) { - return new SingletonIterator<>(value); + if (value != null) { + return new SingletonIterator<>(value); + } + @SuppressWarnings("nullness") // For `value` to be null, T must be a nullable type. + UnmodifiableIterator<T> result = (UnmodifiableIterator<T>) new SingletonNullIterator<T>(); + return result; } private static final class SingletonIterator<T extends @Nullable Object> extends UnmodifiableIterator<T> { - private @Nullable Object valueOrThis; + private @Nullable T valueOrNull; - SingletonIterator(T value) { - this.valueOrThis = value; + SingletonIterator(@NonNull T value) { + this.valueOrNull = value; } @Override public boolean hasNext() { - return valueOrThis != this; + return valueOrNull != null; } @Override - @ParametricNullness - public T next() { - Object result = valueOrThis; - valueOrThis = this; + public @NonNull T next() { + T result = valueOrNull; + valueOrNull = null; // We put the common case first, even though it's unlikely to matter if the code is run much: // https://shipilev.net/jvm/anatomy-quarks/28-frequency-based-code-layout/ - if (result != this) { - // The field held either a `T` or `this`, and it turned out not to be `this`. - @SuppressWarnings("unchecked") - T t = (T) result; - return t; + if (result != null) { + return result; + } + throw new NoSuchElementException(); + } + } + + private static final class SingletonNullIterator<T> extends UnmodifiableIterator<@Nullable T> { + private boolean returned; + + @Override + public boolean hasNext() { + return !returned; + } + + @Override + public @Nullable T next() { + if (!returned) { + // common case first, as in SingletonIterator + returned = true; + return null; } throw new NoSuchElementException(); } |