RFR: updated draft API for JEP 269 Convenience Collection Factories
Peter Levart
peter.levart at gmail.com
Sat Nov 7 15:41:21 UTC 2015
Hi Michael,
The comparison between explicit and varargs is not fair. Varargs is using
arraycopy, which I think prevents vararg array allocation to be eliminated.
Try to use a switch on varargs array length and then directly reference
it's elements with constant indices for each case and construct list arrays
as you do in explicit methods. Let's see if this performs any better.
Regards, Peter
On Nov 7, 2015 9:43 AM, "Michael Hixson" <michael.hixson at gmail.com> wrote:
> (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