Skip to content

Commit 5e7ce82

Browse files
bbakermanbbakerman
committed
FpKit now longer uses streams for performance reasons
1 parent 5fc58fb commit 5e7ce82

3 files changed

Lines changed: 163 additions & 49 deletions

File tree

‎src/main/java/graphql/util/FpKit.java‎

Lines changed: 67 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99
import java.lang.reflect.Array;
1010
import java.util.ArrayList;
1111
import java.util.Collection;
12+
import java.util.Collections;
1213
import java.util.Iterator;
1314
import java.util.LinkedHashMap;
1415
import java.util.List;
@@ -18,69 +19,87 @@
1819
import java.util.OptionalInt;
1920
import java.util.Set;
2021
import java.util.concurrent.CompletableFuture;
21-
import java.util.function.BiFunction;
2222
import java.util.function.BinaryOperator;
2323
import java.util.function.Function;
2424
import java.util.function.Predicate;
2525
import java.util.function.Supplier;
26-
import java.util.stream.Collectors;
2726
import java.util.stream.Stream;
2827

2928
import static java.util.Collections.singletonList;
30-
import static java.util.function.Function.identity;
31-
import static java.util.stream.Collectors.mapping;
3229

3330
@Internal
3431
public class FpKit {
3532

3633
//
3734
// From a list of named things, get a map of them by name, merging them according to the merge function
3835
public static <T> Map<String, T> getByName(List<T> namedObjects, Function<T, String> nameFn, BinaryOperator<T> mergeFunc) {
39-
return namedObjects.stream().collect(Collectors.toMap(
40-
nameFn,
41-
identity(),
42-
mergeFunc,
43-
LinkedHashMap::new)
44-
);
36+
return toMap(namedObjects, nameFn, mergeFunc);
37+
}
38+
39+
//
40+
// From a collection of keyed things, get a map of them by key, merging them according to the merge function
41+
public static <T, NewKey> Map<NewKey, T> toMap(Collection<T> collection, Function<T, NewKey> keyFunction, BinaryOperator<T> mergeFunc) {
42+
Map<NewKey, T> resultMap = new LinkedHashMap<>();
43+
for (T obj : collection) {
44+
NewKey key = keyFunction.apply(obj);
45+
if (resultMap.containsKey(key)) {
46+
T existingValue = resultMap.get(key);
47+
T mergedValue = mergeFunc.apply(existingValue, obj);
48+
resultMap.put(key, mergedValue);
49+
} else {
50+
resultMap.put(key, obj);
51+
}
52+
}
53+
return resultMap;
4554
}
4655

4756
// normal groupingBy but with LinkedHashMap
4857
public static <T, NewKey> Map<NewKey, ImmutableList<T>> groupingBy(Collection<T> list, Function<T, NewKey> function) {
49-
return list.stream().collect(Collectors.groupingBy(function, LinkedHashMap::new, mapping(Function.identity(), ImmutableList.toImmutableList())));
58+
return filterAndGroupingBy(list, t -> true, function);
5059
}
5160

61+
@SuppressWarnings("unchecked")
5262
public static <T, NewKey> Map<NewKey, ImmutableList<T>> filterAndGroupingBy(Collection<T> list,
5363
Predicate<? super T> predicate,
5464
Function<T, NewKey> function) {
55-
return list.stream().filter(predicate).collect(Collectors.groupingBy(function, LinkedHashMap::new, mapping(Function.identity(), ImmutableList.toImmutableList())));
56-
}
65+
//
66+
// The cleanest version of this code would have two maps, one of immutable list builders and one
67+
// of the built immutable lists. BUt we are trying to be performant and memory efficient so
68+
// we treat it as a map of objects and cast like its Java 4x
69+
//
70+
Map<NewKey, Object> resutMap = new LinkedHashMap<>();
71+
for (T item : list) {
72+
if (predicate.test(item)) {
73+
NewKey key = function.apply(item);
74+
// we have to use an immutable list builder as we built it out
75+
((ImmutableList.Builder<Object>) resutMap.computeIfAbsent(key, k -> ImmutableList.builder()))
76+
.add(item);
77+
}
78+
}
79+
if (resutMap.isEmpty()) {
80+
return Collections.emptyMap();
81+
}
82+
// Convert builders to ImmutableLists in place to avoid an extra allocation
83+
// yes the code is yuck - but its more performant yuck!
84+
resutMap.replaceAll((key, builder) ->
85+
((ImmutableList.Builder<Object>) builder).build());
5786

58-
public static <T, NewKey> Map<NewKey, ImmutableList<T>> groupingBy(Stream<T> stream, Function<T, NewKey> function) {
59-
return stream.collect(Collectors.groupingBy(function, LinkedHashMap::new, mapping(Function.identity(), ImmutableList.toImmutableList())));
87+
// make it the right shape - like as if generics were never invented
88+
return (Map<NewKey, ImmutableList<T>>) (Map<?, ?>) resutMap;
6089
}
6190

62-
public static <T, NewKey> Map<NewKey, T> groupingByUniqueKey(Collection<T> list, Function<T, NewKey> keyFunction) {
63-
return list.stream().collect(Collectors.toMap(
64-
keyFunction,
65-
identity(),
66-
throwingMerger(),
67-
LinkedHashMap::new)
68-
);
91+
public static <T, NewKey> Map<NewKey, T> toMapByUniqueKey(Collection<T> list, Function<T, NewKey> keyFunction) {
92+
return toMap(list, keyFunction, throwingMerger());
6993
}
7094

71-
public static <T, NewKey> Map<NewKey, T> groupingByUniqueKey(Stream<T> stream, Function<T, NewKey> keyFunction) {
72-
return stream.collect(Collectors.toMap(
73-
keyFunction,
74-
identity(),
75-
throwingMerger(),
76-
LinkedHashMap::new)
77-
);
78-
}
95+
96+
private static final BinaryOperator<Object> THROWING_MERGER_SINGLETON = (u, v) -> {
97+
throw new IllegalStateException(String.format("Duplicate key %s", u));
98+
};
7999

80100
private static <T> BinaryOperator<T> throwingMerger() {
81-
return (u, v) -> {
82-
throw new IllegalStateException(String.format("Duplicate key %s", u));
83-
};
101+
//noinspection unchecked
102+
return (BinaryOperator<T>) THROWING_MERGER_SINGLETON;
84103
}
85104

86105

@@ -240,11 +259,6 @@ public static <T> List<T> valuesToList(Map<?, T> map) {
240259
return new ArrayList<>(map.values());
241260
}
242261

243-
public static <K, V, U> List<U> mapEntries(Map<K, V> map, BiFunction<K, V, U> function) {
244-
return map.entrySet().stream().map(entry -> function.apply(entry.getKey(), entry.getValue())).collect(Collectors.toList());
245-
}
246-
247-
248262
public static <T> List<List<T>> transposeMatrix(List<? extends List<T>> matrix) {
249263
int rowCount = matrix.size();
250264
int colCount = matrix.get(0).size();
@@ -272,10 +286,12 @@ public static <T> List<T> flatList(Collection<List<T>> listLists) {
272286
}
273287

274288
public static <T> Optional<T> findOne(Collection<T> list, Predicate<T> filter) {
275-
return list
276-
.stream()
277-
.filter(filter)
278-
.findFirst();
289+
for (T t : list) {
290+
if (filter.test(t)) {
291+
return Optional.of(t);
292+
}
293+
}
294+
return Optional.empty();
279295
}
280296

281297
public static <T> T findOneOrNull(List<T> list, Predicate<T> filter) {
@@ -292,10 +308,13 @@ public static <T> int findIndex(List<T> list, Predicate<T> filter) {
292308
}
293309

294310
public static <T> List<T> filterList(Collection<T> list, Predicate<T> filter) {
295-
return list
296-
.stream()
297-
.filter(filter)
298-
.collect(Collectors.toList());
311+
List<T> result = new ArrayList<>();
312+
for (T t : list) {
313+
if (filter.test(t)) {
314+
result.add(t);
315+
}
316+
}
317+
return result;
299318
}
300319

301320
public static <T> Set<T> filterSet(Collection<T> input, Predicate<T> filter) {
@@ -352,9 +371,10 @@ public static <T> Supplier<T> interThreadMemoize(Supplier<T> delegate) {
352371
/**
353372
* Faster set intersection.
354373
*
355-
* @param <T> for two
374+
* @param <T> for two
356375
* @param set1 first set
357376
* @param set2 second set
377+
*
358378
* @return intersection set
359379
*/
360380
public static <T> Set<T> intersection(Set<T> set1, Set<T> set2) {

‎src/main/java/graphql/util/NodeMultiZipper.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -62,7 +62,7 @@ public T toRootNode() {
6262
Map<T, ImmutableList<NodeZipper<T>>> sameParent = zipperWithSameParent(deepestZippers);
6363

6464
List<NodeZipper<T>> newZippers = new ArrayList<>();
65-
Map<T, NodeZipper<T>> zipperByNode = FpKit.groupingByUniqueKey(curZippers, NodeZipper::getCurNode);
65+
Map<T, NodeZipper<T>> zipperByNode = FpKit.toMapByUniqueKey(curZippers, NodeZipper::getCurNode);
6666
for (Map.Entry<T, ImmutableList<NodeZipper<T>>> entry : sameParent.entrySet()) {
6767
NodeZipper<T> newZipper = moveUp(entry.getKey(), entry.getValue());
6868
Optional<NodeZipper<T>> zipperToBeReplaced = Optional.ofNullable(zipperByNode.get(entry.getKey()));

‎src/test/groovy/graphql/util/FpKitTest.groovy‎

Lines changed: 95 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
package graphql.util
22

3-
3+
import com.google.common.collect.ImmutableList
44
import spock.lang.Specification
55

66
import java.util.function.Supplier
@@ -98,6 +98,100 @@ class FpKitTest extends Specification {
9898
l == ["Parrot"]
9999
}
100100

101+
class Person {
102+
String name
103+
String city
104+
105+
Person(String name) {
106+
this.name = name
107+
}
108+
109+
Person(String name, String city) {
110+
this.name = name
111+
this.city = city
112+
}
113+
114+
String getName() {
115+
return name
116+
}
117+
118+
String getCity() {
119+
return city
120+
}
121+
}
122+
123+
def a = new Person("a", "New York")
124+
def b = new Person("b", "New York")
125+
def c1 = new Person("c", "Sydney")
126+
def c2 = new Person("c", "London")
127+
128+
def "getByName tests"() {
129+
130+
when:
131+
def map = FpKit.getByName([a, b, c1, c2], { it -> it.getName() })
132+
then:
133+
map == ["a": a, "b": b, c: c1]
134+
135+
when:
136+
map = FpKit.getByName([a, b, c1, c2], { it -> it.getName() }, { it1, it2 -> it2 })
137+
then:
138+
map == ["a": a, "b": b, c: c2]
139+
}
140+
141+
def "groupingBy tests"() {
142+
143+
when:
144+
Map<String, ImmutableList<Person>> map = FpKit.groupingBy([a, b, c1, c2], { it -> it.getCity() })
145+
then:
146+
map == ["New York": [a, b], "Sydney": [c1], "London": [c2]]
147+
148+
when:
149+
map = FpKit.filterAndGroupingBy([a, b, c1, c2], { it -> it != c1 }, { it -> it.getCity() })
150+
then:
151+
map == ["New York": [a, b], "London": [c2]]
152+
153+
}
154+
155+
def "toMapByUniqueKey works"() {
156+
157+
when:
158+
Map<String, Person> map = FpKit.toMapByUniqueKey([a, b, c1], { it -> it.getName() })
159+
then:
160+
map == ["a": a, "b": b, "c": c1]
161+
162+
when:
163+
FpKit.toMapByUniqueKey([a, b, c1, c2], { it -> it.getName() })
164+
then:
165+
def e = thrown(IllegalStateException.class)
166+
e.message.contains("Duplicate key")
167+
}
168+
169+
def "findOne test"() {
170+
when:
171+
def opt = FpKit.findOne([a, b, c1, c2], { it -> it.getName() == "c" })
172+
then:
173+
opt.isPresent()
174+
opt.get() == c1
175+
176+
when:
177+
opt = FpKit.findOne([a, b, c1, c2], { it -> it.getName() == "d" })
178+
then:
179+
opt.isEmpty()
180+
181+
when:
182+
opt = FpKit.findOne([a, b, c1, c2], { it -> it.getName() == "a" })
183+
then:
184+
opt.isPresent()
185+
opt.get() == a
186+
}
187+
188+
def "filterList works"() {
189+
when:
190+
def list = FpKit.filterList([a, b, c1, c2], { it -> it.getName() == "c" })
191+
then:
192+
list == [c1, c2]
193+
}
194+
101195
def "set intersection works"() {
102196
def set1 = ["A","B","C"] as Set
103197
def set2 = ["A","C","D"] as Set

0 commit comments

Comments
 (0)