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