On 10/4/21 12:57, Сергей Цыпанов wrote:
in the code of HashSet(Collection) we have an optimization opportunity:
public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); }
instead of using addAll() inherited from j.u.Collection we can use c.forEach(this::add):
public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); c.forEach(this::add); }
This allows to rid Iterator and use counting loops for e.g. ArrayList instead of hasNext()/next().
Well, perhaps, but this sort of low-level hackery is not IMO something we should reflexively do in the core class libraries.
We are also likely to benefit from this change in case the argument collection is synchronized as it's going to be locked only once.
That's a good point, but would a synchronized collection really lock coarsely around forEach(), rather than in add().
I've used the benchmark [1] to analyze the impact and it demonstrates measurable improvement [2].
What puzzles we a bit is the result for j.u.ArrayList. At warm-up time it demonstrates better results than at measurement time:
length = 10
# Run progress: 4,44% complete, ETA 00:21:41 # Fork: 3 of 5 # Warmup Iteration 1: 134,699 ns/op # Warmup Iteration 2: 115,391 ns/op # Warmup Iteration 3: 130,110 ns/op # Warmup Iteration 4: 114,465 ns/op <---- # Warmup Iteration 5: 114,849 ns/op # Warmup Iteration 6: 115,073 ns/op # Warmup Iteration 7: 113,988 ns/op # Warmup Iteration 8: 115,301 ns/op # Warmup Iteration 9: 115,452 ns/op # Warmup Iteration 10: 124,493 ns/op <---- Iteration 1: 123,776 ns/op Iteration 2: 123,719 ns/op Iteration 3: 123,725 ns/op Iteration 4: 126,892 ns/op Iteration 5: 125,493 ns/op Iteration 6: 124,661 ns/op Iteration 7: 123,783 ns/op Iteration 8: 123,975 ns/op Iteration 9: 124,047 ns/op Iteration 10: 123,899 ns/op
length = 100
# Run progress: 11,11% complete, ETA 00:20:10 # Fork: 1 of 5 # Warmup Iteration 1: 1236,695 ns/op # Warmup Iteration 2: 1069,909 ns/op # Warmup Iteration 3: 1243,852 ns/op # Warmup Iteration 4: 1059,038 ns/op <---- # Warmup Iteration 5: 1057,670 ns/op # Warmup Iteration 6: 1057,117 ns/op # Warmup Iteration 7: 1056,932 ns/op # Warmup Iteration 8: 1054,909 ns/op # Warmup Iteration 9: 1058,106 ns/op # Warmup Iteration 10: 1145,699 ns/op <---- Iteration 1: 1139,155 ns/op Iteration 2: 1141,662 ns/op Iteration 3: 1139,061 ns/op Iteration 4: 1139,306 ns/op Iteration 5: 1138,475 ns/op Iteration 6: 1140,491 ns/op Iteration 7: 1144,017 ns/op Iteration 8: 1139,411 ns/op Iteration 9: 1142,729 ns/op Iteration 10: 1144,042 ns/op
Here I use 1 s warm-up iteration on 2s measurement iteration. It looks like at iteration 4 the code is top-optimized, and later at the end of warm-up a kind of deoptimization happens. There's still visible improvement however.
The benchmark is run with 5 forks, and this deoptimization is visible for length = {10, 100}.
So my two question are: - What is the reason of the deoptimization and can we do something about it?
C2 does this sort of thing all the time: it's a heuristic probabilistic optimizer. I've seen plenty of bimodal examples, where inlining changes and each time a program is run it's either fast or slow, quasi-randomly. If you really want to know, use -prof perfasm in JMH.
- Whether suggested changes is worth implementations?
IMO the gain is too small. Others may disagree. -- Andrew Haley (he/him) Java Platform Lead Engineer Red Hat UK Ltd. <https://www.redhat.com> https://keybase.io/andrewhaley EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671