(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.ma...@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;
}
}
}
