RFR: updated draft API for JEP 269 Convenience CollectionFactories
Michael Hixson
michael.hixson at gmail.com
Sat Nov 7 22:43:16 UTC 2015
Hi Timo,
This was 64-bit. Here are some other details if you're curious:
OS Name Microsoft Windows 10 Pro
Version 10.0.10240 Build 10240
System Type x64-based PC
Processor Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz, 3501 Mhz, 4
Core(s), 8 Logical Processor(s)
$ java -version
java version "1.8.0_45"
Java(TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode)
One thing I didn't explicitly point out was explicit_00 and
explicit_01 were optimized to use Collections.emptyList/singletonList,
whereas the varargs version was not. I'll follow up soon with a
modified benchmark that takes Peter Levart's suggestion of
switch(args.length) into account.
-Michael
On Sat, Nov 7, 2015 at 5:16 AM, Timo Kinnunen <timo.kinnunen at gmail.com> wrote:
> Hi,
>
>
>
> I plotted the data and noticed a couple of things. First, for explicit
> arguments, performance looks to scale linearly only for 0, 1 and 2
> arguments. After that, something changes and performance continues to scale
> linearly but in groups of two. Essentially, every even argument is passed
> for free(1). The same thing can be observed with varargs starting with
> arguments 1 and 2. I think this indicates Hotspot is starting to spill
> values from registers to stack at that point.
>
>
>
> Also, it looks like the gap between varargs and explicit arguments keeps
> widening, like Stuart Marks suspected. On the other hand, the low inflection
> point means a Hotspot optimization allowing vararg array contents to use the
> same storage as explicit arguments would bring the performance of both into
> parity for all but the most frequently used method variants.
>
>
>
> BTW, was this on 64-bit or 32-bit?
>
>
>
>
>
>
>
> (1) Actually, it almost looks like even arguments are more than free and
> come with a small discount. Passing a dummy argument to make the number even
> doesn’t look like it would hurt.
>
>
>
>
>
>
>
> Sent from Mail for Windows 10
>
>
>
>
>
>
> From: Michael Hixson
> Sent: Saturday, November 7, 2015 09:43
> To: Stuart Marks
> Cc: core-libs-dev
> Subject: Re: RFR: updated draft API for JEP 269 Convenience
> CollectionFactories
>
>
>
>
>
> (Oops, forgot to cc the mailing list)
>
>
>
> Thanks for the explanations, Stuart. That all sounds reasonable and
>
> makes sense to me.
>
>
>
> I have some additional thoughts inline below, because this is
>
> interesting and I can't resist, but you could ignore them and not hurt
>
> any feelings.
>
>
>
> I also wrote up some quick benchmarks comparing explicit versus
>
> varargs implementations just to see the impact for myself. The output
>
> and source code are included at the end of the email.
>
>
>
> -Michael
>
>
>
>
>
> On Fri, Nov 6, 2015 at 10:28 AM, Stuart Marks <stuart.marks at oracle.com>
> wrote:
>
>> On 11/6/15 5:12 AM, Michael Hixson wrote:
>
>>>
>
>>> + static <E> List<E> of(E... es) {
>
>>> + for (E e : es) {
>
>>> + Objects.requireNonNull(e);
>
>>> + }
>
>>> + // NOTE: this can allow a null element to slip through
>
>>> + return Collections.unmodifiableList(Arrays.asList(es));
>
>>> + }
>
>>>
>
>>> Even as a skeletal implementation, this one has to be changed to be
>
>>> truly immutable, right? It currently returns a view of the (mutable)
>
>>> argument array rather than new storage. Sorry for not providing a
>
>>> proper test:
>
>>
>
>>
>
>> Good catch! Funnily I had noticed the TOCTOU case that allowed null
>> elements
>
>> in the array to slip through, but not that the array itself was still
>
>> modifiable from the outside. Anyway, I'll fix this. No worries about the
>
>> test.
>
>>
>
>>> Has anyone been able to quantify the advantage of having these
>
>>> overloads as opposed to having the varargs versions only? Is it a
>
>>> matter of performance?
>
>>>
>
>>> I ask because the overloads seem like warts on the APIs (which is a
>
>>> shame -- List and Set are such important APIs). I'm imagining a
>
>>> future where:
>
>>>
>
>>> 1. We add these overloads for performance gains now.
>
>>> 2. But they're all skeletal implementations that aren't that perfomant
>
>>> anyway. Efficient versions don't make it into Java SE 9. People that
>
>>> care a lot about performance avoid using these ones.
>
>>> 3. A few years later, varargs performance or some other language / VM
>
>>> / compiler-level change renders the overloads obsolete.
>
>>
>
>>
>
>> Yeah, the overloads seem like warts on the API, though probably necessary
>
>> ones.
>
>>
>
>> At present, and for the forseeable future, varargs calls allocate an array
>
>> on the heap, whereas fixed-args calls do not. I don't know how to quantify
>
>> the difference though. Certainly the cost of allocation and initialization
>
>> is borne in-line. Then there is the cost of collection. Collecting
>
>> short-lived objects is cheap (but not free). There is also the possibility
>
>> of escape analysis eliminating the allocation. This seems unlikely to me;
>
>> certainly not something to be relied upon.
>
>>
>
>> The most likely possible future optimization is "frozen arrays," part of
>> the
>
>> "Arrays 2.0" stuff that John Rose has talked about. This is basically
>> about
>
>> immutable arrays. Here, the possibility is to eliminate the defensive
>> copy,
>
>> if the array created to hold the varargs arguments is made immutable.
>> (This
>
>> will require some adjustment on the callee side, as yet unspecified.)
>
>> There's still an array, though. And a defensive copy would still have to
>> be
>
>> made if the caller passes an actual array, as opposed to a varargs list.
>
>
>
> (Realizing that we're discussing details of a feature that doesn't
>
> exist (frozen arrays)...)
>
>
>
> It seems to me that as long as the callee invoked the method with
>
> comma-separated arguments instead of an array, then the callee can
>
> automatically be opted into frozen arrays. They never had access to
>
> the array box in the first place.
>
>
>
> It also seems like the varargs method could defensively call
>
> array.clone() and expect a no-op (return this) implementation if the
>
> array was already frozen, and so both sides could automatically
>
> benefit from frozen arrays without recompilation. No?
>
>
>
>>
>
>> While I can't quantify it, I do think there's an expense to creating the
>
>> varargs array, and there is only a possibility to reduce (but not
>> eliminate)
>
>> its cost in future JDK releases. This cost is entirely avoided by
>> fixed-args
>
>> overloads. (There is the cost of cluttering up the API, though.)
>
>
>
> I asked "Is it a matter of performance?" because I thought the
>
> justification for similar overloads in other APIs was different. I
>
> thought EnumSet and Guava (for example) provided the overloads because
>
> @SafeVarargs did not exist at the time, and they didn't want to scare
>
> callers away with those silly warnings.
>
>
>
> Put another way: if the justification for these new overloads is
>
> simply "the other APIs did it", I hope those original motivations are
>
> not being wrongly applied here. It sounds like this is strictly about
>
> performance, though.
>
>
>
>>
>
>> Turning to the skeletal vs. optimized implementation, my plan is certainly
>
>> to ensure that the optimized implementations get into JDK 9. Of course,
>
>> plans can change. If the APIs get in without the optimized
>> implementations,
>
>> I think the big attractor will still be the convenience of using these
>
>> static factory methods as opposed to conventional code. They're no slower
>
>> than conventional code, and the space consumed is the same. So I think
>
>> they'll be popular even if the space efficiency benefits aren't there
>
>> initially.
>
>
>
> For some reason I thought the optimized implementations had already
>
> been moved out of scope for Java 9. I'm glad I was wrong!
>
>
>
>>
>
>> When the optimized implementations do get in, callers will benefit, even
>
>> without recompilation. Thus there is some present value added based on
>
>> potential future benefits.
>
>>
>
>> There is always the set of possible future events that cause something not
>
>> to work out, but I think pursuing the approach I've outlined has a good
>
>> chance of benefiting the platform in the long term.
>
>>
>
>> s'marks
>
>
>
>
>
> ----------------------------------------
>
>
>
> Benchmark Mode Cnt Score Error Units
>
> ListOf.explicit_00 avgt 40 2.564 ± 0.007 ns/op
>
> ListOf.explicit_01 avgt 40 7.859 ± 0.022 ns/op
>
> ListOf.explicit_02 avgt 40 15.808 ± 0.338 ns/op
>
> ListOf.explicit_03 avgt 40 19.145 ± 0.978 ns/op
>
> ListOf.explicit_04 avgt 40 18.558 ± 0.314 ns/op
>
> ListOf.explicit_05 avgt 40 23.457 ± 1.069 ns/op
>
> ListOf.explicit_06 avgt 40 21.398 ± 0.255 ns/op
>
> ListOf.explicit_07 avgt 40 25.307 ± 0.672 ns/op
>
> ListOf.explicit_08 avgt 40 24.137 ± 0.376 ns/op
>
> ListOf.explicit_09 avgt 40 27.418 ± 0.560 ns/op
>
> ListOf.explicit_10 avgt 40 26.871 ± 0.506 ns/op
>
> ListOf.varargs_00 avgt 40 13.520 ± 0.177 ns/op
>
> ListOf.varargs_01 avgt 40 23.740 ± 0.346 ns/op
>
> ListOf.varargs_02 avgt 40 23.435 ± 0.321 ns/op
>
> ListOf.varargs_03 avgt 40 29.564 ± 0.744 ns/op
>
> ListOf.varargs_04 avgt 40 29.640 ± 1.329 ns/op
>
> ListOf.varargs_05 avgt 40 34.552 ± 0.639 ns/op
>
> ListOf.varargs_06 avgt 40 34.249 ± 0.476 ns/op
>
> ListOf.varargs_07 avgt 40 40.656 ± 0.589 ns/op
>
> ListOf.varargs_08 avgt 40 39.900 ± 0.595 ns/op
>
> ListOf.varargs_09 avgt 40 45.060 ± 1.098 ns/op
>
> ListOf.varargs_10 avgt 40 44.546 ± 0.816 ns/op
>
>
>
> ----------------------------------------
>
>
>
> package rnd;
>
>
>
> import org.openjdk.jmh.annotations.Benchmark;
>
> import org.openjdk.jmh.annotations.BenchmarkMode;
>
> import org.openjdk.jmh.annotations.Fork;
>
> import org.openjdk.jmh.annotations.Measurement;
>
> import org.openjdk.jmh.annotations.Mode;
>
> import org.openjdk.jmh.annotations.OutputTimeUnit;
>
> import org.openjdk.jmh.annotations.Scope;
>
> import org.openjdk.jmh.annotations.State;
>
> import org.openjdk.jmh.annotations.Warmup;
>
> import org.openjdk.jmh.runner.Runner;
>
> import org.openjdk.jmh.runner.options.Options;
>
> import org.openjdk.jmh.runner.options.OptionsBuilder;
>
>
>
> import java.util.AbstractList;
>
> import java.util.Collections;
>
> import java.util.List;
>
> import java.util.Objects;
>
> import java.util.concurrent.TimeUnit;
>
>
>
> @State(Scope.Thread)
>
> @BenchmarkMode(Mode.AverageTime)
>
> @OutputTimeUnit(TimeUnit.NANOSECONDS)
>
> @Warmup(iterations = 20)
>
> @Measurement(iterations = 20)
>
> @Fork(2)
>
> public class ListOf {
>
>
>
> private static final String o = "";
>
>
>
> public static void main(String[] args) throws Exception {
>
> Options options = new OptionsBuilder()
>
> .include(ListOf.class.getName())
>
> .build();
>
> new Runner(options).run();
>
> }
>
>
>
> @Benchmark public List<String> explicit_00() { return explicit(); }
>
> @Benchmark public List<String> explicit_01() { return explicit(o); }
>
> @Benchmark public List<String> explicit_02() { return explicit(o,o); }
>
> @Benchmark public List<String> explicit_03() { return explicit(o,o,o); }
>
> @Benchmark public List<String> explicit_04() { return explicit(o,o,o,o); }
>
> @Benchmark public List<String> explicit_05() { return explicit(o,o,o,o,o);
> }
>
> @Benchmark public List<String> explicit_06() { return
> explicit(o,o,o,o,o,o); }
>
> @Benchmark public List<String> explicit_07() { return
>
> explicit(o,o,o,o,o,o,o); }
>
> @Benchmark public List<String> explicit_08() { return
>
> explicit(o,o,o,o,o,o,o,o); }
>
> @Benchmark public List<String> explicit_09() { return
>
> explicit(o,o,o,o,o,o,o,o,o); }
>
> @Benchmark public List<String> explicit_10() { return
>
> explicit(o,o,o,o,o,o,o,o,o,o); }
>
>
>
> @Benchmark public List<String> varargs_00() { return varargs(); }
>
> @Benchmark public List<String> varargs_01() { return varargs(o); }
>
> @Benchmark public List<String> varargs_02() { return varargs(o,o); }
>
> @Benchmark public List<String> varargs_03() { return varargs(o,o,o); }
>
> @Benchmark public List<String> varargs_04() { return varargs(o,o,o,o); }
>
> @Benchmark public List<String> varargs_05() { return varargs(o,o,o,o,o); }
>
> @Benchmark public List<String> varargs_06() { return varargs(o,o,o,o,o,o);
> }
>
> @Benchmark public List<String> varargs_07() { return
> varargs(o,o,o,o,o,o,o); }
>
> @Benchmark public List<String> varargs_08() { return
>
> varargs(o,o,o,o,o,o,o,o); }
>
> @Benchmark public List<String> varargs_09() { return
>
> varargs(o,o,o,o,o,o,o,o,o); }
>
> @Benchmark public List<String> varargs_10() { return
>
> varargs(o,o,o,o,o,o,o,o,o,o); }
>
>
>
> static <E> List<E> explicit() {
>
> return Collections.emptyList();
>
> }
>
>
>
> static <E> List<E> explicit(E e1) {
>
> return Collections.singletonList(Objects.requireNonNull(e1));
>
> }
>
>
>
> static <E> List<E> explicit(E e1, E e2) {
>
> return new ImmutableList<>(new Object[] {
>
> Objects.requireNonNull(e1),
>
> Objects.requireNonNull(e2)
>
> });
>
> }
>
>
>
> static <E> List<E> explicit(E e1, E e2, E e3) {
>
> return new ImmutableList<>(new Object[] {
>
> Objects.requireNonNull(e1),
>
> Objects.requireNonNull(e2),
>
> Objects.requireNonNull(e3)
>
> });
>
> }
>
>
>
> static <E> List<E> explicit(E e1, E e2, E e3, E e4) {
>
> return new ImmutableList<>(new Object[] {
>
> Objects.requireNonNull(e1),
>
> Objects.requireNonNull(e2),
>
> Objects.requireNonNull(e3),
>
> Objects.requireNonNull(e4)
>
> });
>
> }
>
>
>
> static <E> List<E> explicit(E e1, E e2, E e3, E e4, E e5) {
>
> return new ImmutableList<>(new Object[] {
>
> Objects.requireNonNull(e1),
>
> Objects.requireNonNull(e2),
>
> Objects.requireNonNull(e3),
>
> Objects.requireNonNull(e4),
>
> Objects.requireNonNull(e5)
>
> });
>
> }
>
>
>
> static <E> List<E> explicit(E e1, E e2, E e3, E e4, E e5, E e6) {
>
> return new ImmutableList<>(new Object[] {
>
> Objects.requireNonNull(e1),
>
> Objects.requireNonNull(e2),
>
> Objects.requireNonNull(e3),
>
> Objects.requireNonNull(e4),
>
> Objects.requireNonNull(e5),
>
> Objects.requireNonNull(e6)
>
> });
>
> }
>
>
>
> static <E> List<E> explicit(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
>
> return new ImmutableList<>(new Object[] {
>
> Objects.requireNonNull(e1),
>
> Objects.requireNonNull(e2),
>
> Objects.requireNonNull(e3),
>
> Objects.requireNonNull(e4),
>
> Objects.requireNonNull(e5),
>
> Objects.requireNonNull(e6),
>
> Objects.requireNonNull(e7)
>
> });
>
> }
>
>
>
> static <E> List<E> explicit(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E
> e8) {
>
> return new ImmutableList<>(new Object[] {
>
> Objects.requireNonNull(e1),
>
> Objects.requireNonNull(e2),
>
> Objects.requireNonNull(e3),
>
> Objects.requireNonNull(e4),
>
> Objects.requireNonNull(e5),
>
> Objects.requireNonNull(e6),
>
> Objects.requireNonNull(e7),
>
> Objects.requireNonNull(e8)
>
> });
>
> }
>
>
>
> static <E> List<E> explicit(E e1, E e2, E e3, E e4, E e5, E e6, E
>
> e7, E e8, E e9) {
>
> return new ImmutableList<>(new Object[] {
>
> Objects.requireNonNull(e1),
>
> Objects.requireNonNull(e2),
>
> Objects.requireNonNull(e3),
>
> Objects.requireNonNull(e4),
>
> Objects.requireNonNull(e5),
>
> Objects.requireNonNull(e6),
>
> Objects.requireNonNull(e7),
>
> Objects.requireNonNull(e8),
>
> Objects.requireNonNull(e9)
>
> });
>
> }
>
>
>
> static <E> List<E> explicit(E e1, E e2, E e3, E e4, E e5, E e6, E
>
> e7, E e8, E e9, E e10) {
>
> return new ImmutableList<>(new Object[] {
>
> Objects.requireNonNull(e1),
>
> Objects.requireNonNull(e2),
>
> Objects.requireNonNull(e3),
>
> Objects.requireNonNull(e4),
>
> Objects.requireNonNull(e5),
>
> Objects.requireNonNull(e6),
>
> Objects.requireNonNull(e7),
>
> Objects.requireNonNull(e8),
>
> Objects.requireNonNull(e9),
>
> Objects.requireNonNull(e10)
>
> });
>
> }
>
>
>
> @SafeVarargs
>
> static <E> List<E> varargs(E... elements) {
>
> int length = elements.length;
>
> Object[] copy = new Object[length];
>
> System.arraycopy(elements, 0, copy, 0, length);
>
> for (Object e : copy) Objects.requireNonNull(e);
>
> return new ImmutableList<>(copy);
>
> }
>
>
>
> static final class ImmutableList<E> extends AbstractList<E> {
>
> final Object[] array;
>
>
>
> ImmutableList(Object[] array) {
>
> this.array = array;
>
> }
>
>
>
> @Override
>
> @SuppressWarnings("unchecked")
>
> public E get(int index) {
>
> return (E) array[index];
>
> }
>
>
>
> @Override
>
> public int size() {
>
> return array.length;
>
> }
>
> }
>
> }
>
>
>
>
More information about the core-libs-dev
mailing list