Skip to content

Commit cdcd91f

Browse files
lowassercgdecker
lowasser
authored and
cgdecker
committed
Eliminate EmptyImmutableSet, replacing it with a RegularImmutableSet with a null hash table.
Related: google#1268 ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=89625833
1 parent 402ab06 commit cdcd91f

File tree

8 files changed

+103
-186
lines changed

8 files changed

+103
-186
lines changed

‎guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/EmptyImmutableSet.java

Lines changed: 0 additions & 32 deletions
This file was deleted.

‎guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/ImmutableSet.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,7 @@ public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements
4343
// Casting to any type is safe because the set will never hold any elements.
4444
@SuppressWarnings({"unchecked"})
4545
public static <E> ImmutableSet<E> of() {
46-
return (ImmutableSet<E>) EmptyImmutableSet.INSTANCE;
46+
return (ImmutableSet<E>) RegularImmutableSet.EMPTY;
4747
}
4848

4949
public static <E> ImmutableSet<E> of(E element) {

‎guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/RegularImmutableSet.java

Lines changed: 4 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -16,8 +16,7 @@
1616

1717
package com.google.common.collect;
1818

19-
import static com.google.common.base.Preconditions.checkArgument;
20-
19+
import java.util.Collections;
2120
import java.util.Set;
2221

2322
/**
@@ -26,11 +25,10 @@
2625
* @author Hayward Chan
2726
*/
2827
final class RegularImmutableSet<E> extends ForwardingImmutableSet<E> {
28+
static final RegularImmutableSet<Object> EMPTY = new RegularImmutableSet<Object>(
29+
Collections.emptySet());
30+
2931
RegularImmutableSet(Set<E> delegate) {
3032
super(delegate);
31-
32-
// Required for GWT deserialization because the server-side implementation
33-
// requires this.
34-
checkArgument(delegate.size() >= 2);
3533
}
3634
}

‎guava-gwt/src/com/google/common/collect/EmptyImmutableSet_CustomFieldSerializer.java

Lines changed: 0 additions & 41 deletions
This file was deleted.

‎guava-tests/benchmark/com/google/common/collect/MultipleSetContainsBenchmark.java

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
/*
2+
* Copyright (C) 2015 The Guava Authors
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+
17+
package com.google.common.collect;
18+
19+
import com.google.caliper.BeforeExperiment;
20+
import com.google.caliper.Benchmark;
21+
import com.google.caliper.Param;
22+
import com.google.caliper.api.SkipThisScenarioException;
23+
24+
import java.util.Random;
25+
26+
/**
27+
* A benchmark that tries invoking {@code Set.contains} on many different sets.
28+
*/
29+
public class MultipleSetContainsBenchmark {
30+
31+
@Param({"0.0", "0.1", "0.7", "1.0"})
32+
double emptySetProportion;
33+
34+
@Param({"0.0", "0.1", "0.7", "1.0"})
35+
double singletonSetProportion;
36+
37+
@Param({"0.2", "0.8"})
38+
double hitRate;
39+
40+
static final Object PRESENT = new Object();
41+
static final Object ABSENT = new Object();
42+
43+
@SuppressWarnings("unchecked")
44+
private final ImmutableSet<Object>[] sets = new ImmutableSet[0x1000];
45+
46+
private final Object[] queries = new Object[0x1000];
47+
48+
@BeforeExperiment void setUp() {
49+
if (emptySetProportion + singletonSetProportion > 1.01) {
50+
throw new SkipThisScenarioException();
51+
}
52+
53+
Random rng = new Random();
54+
for (int i = 0; i < 0x1000; i++) {
55+
double setSize = rng.nextDouble();
56+
if (setSize < emptySetProportion) {
57+
sets[i] = ImmutableSet.of();
58+
} else if (setSize < emptySetProportion + singletonSetProportion) {
59+
sets[i] = ImmutableSet.of(PRESENT);
60+
} else {
61+
sets[i] = ImmutableSet.of(PRESENT, new Object());
62+
}
63+
64+
if (rng.nextDouble() < hitRate) {
65+
queries[i] = PRESENT;
66+
} else {
67+
queries[i] = ABSENT;
68+
}
69+
}
70+
}
71+
72+
@Benchmark public boolean contains(int reps) {
73+
ImmutableSet<Object>[] sets = this.sets;
74+
Object[] queries = this.queries;
75+
boolean result = false;
76+
for (int i = 0; i < reps; i++) {
77+
int j = i & 0xFFF;
78+
result ^= sets[j].contains(queries[j]);
79+
}
80+
return result;
81+
}
82+
83+
}

‎guava/src/com/google/common/collect/EmptyImmutableSet.java

Lines changed: 0 additions & 97 deletions
This file was deleted.

‎guava/src/com/google/common/collect/ImmutableSet.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ public abstract class ImmutableSet<E> extends ImmutableCollection<E>
4949
*/
5050
@SuppressWarnings({"unchecked"}) // fully variant implementation (never actually produces any Es)
5151
public static <E> ImmutableSet<E> of() {
52-
return (ImmutableSet<E>) EmptyImmutableSet.INSTANCE;
52+
return (ImmutableSet<E>) RegularImmutableSet.EMPTY;
5353
}
5454

5555
/**

‎guava/src/com/google/common/collect/RegularImmutableSet.java

Lines changed: 14 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,8 @@
1919
import com.google.common.annotations.GwtCompatible;
2020
import com.google.common.annotations.VisibleForTesting;
2121

22+
import javax.annotation.Nullable;
23+
2224
/**
2325
* Implementation of {@link ImmutableSet} with two or more elements.
2426
*
@@ -27,7 +29,10 @@
2729
@GwtCompatible(serializable = true, emulated = true)
2830
@SuppressWarnings("serial") // uses writeReplace(), not default serialization
2931
final class RegularImmutableSet<E> extends ImmutableSet<E> {
30-
private final Object[] elements;
32+
static final RegularImmutableSet<Object> EMPTY = new RegularImmutableSet<Object>(
33+
ObjectArrays.EMPTY_ARRAY, 0, null, 0);
34+
35+
private final transient Object[] elements;
3136
// the same elements in hashed positions (plus nulls)
3237
@VisibleForTesting final transient Object[] table;
3338
// 'and' with an int to get a valid table index.
@@ -42,16 +47,17 @@ final class RegularImmutableSet<E> extends ImmutableSet<E> {
4247
this.hashCode = hashCode;
4348
}
4449

45-
@Override public boolean contains(Object target) {
46-
if (target == null) {
50+
@Override public boolean contains(@Nullable Object target) {
51+
Object[] table = this.table;
52+
if (target == null || table == null) {
4753
return false;
4854
}
49-
for (int i = Hashing.smear(target.hashCode()); true; i++) {
50-
Object candidate = table[i & mask];
55+
for (int i = Hashing.smearedHash(target);; i++) {
56+
i &= mask;
57+
Object candidate = table[i];
5158
if (candidate == null) {
5259
return false;
53-
}
54-
if (candidate.equals(target)) {
60+
} else if (candidate.equals(target)) {
5561
return true;
5662
}
5763
}
@@ -76,7 +82,7 @@ int copyIntoArray(Object[] dst, int offset) {
7682

7783
@Override
7884
ImmutableList<E> createAsList() {
79-
return new RegularImmutableAsList<E>(this, elements);
85+
return (table == null) ? ImmutableList.<E>of() : new RegularImmutableAsList<E>(this, elements);
8086
}
8187

8288
@Override

0 commit comments

Comments
 (0)