[10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

classic Classic list List threaded Threaded
28 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Claes Redestad
Hi,

please help review this patch to consolidate the number of
implementation classes returned by the static collection factories:

http://cr.openjdk.java.net/~redestad/8193128/open.00/

I set out to explore options for addressing small inefficiencies we've
been running into, the latest after replacing use of @Stable arrays in
java.lang.invoke with List.of() (JDK-8184777):

- List.indexOf deferred to the iterator in AbstractList, which check for
concurrent modification
- Warmup takes a bit longer due to having to warm up four different
classes and associated methods
- Slowdowns in certain code paths attributable to certain calls becoming
megamorphic

Microbenchmark:
http://cr.openjdk.java.net/~redestad/scratch/less_immutables/ListMorphism.java
http://cr.openjdk.java.net/~redestad/scratch/less_immutables/benchmarks.jar

The benchmark explores how call-sites behave when performing some naive
operations on a few different Lists.

For every benchmark using List.of() there's a variant using ArrayList
for comparison:

Baseline:

Benchmark                             Mode  Cnt    Score Error   Units
ListMorphism.finalGetFromArrayList   thrpt   25   92.659 ±  3.058 ops/us
ListMorphism.finalGetFromList        thrpt   25  335.245 ±  0.244 ops/us
# 3.6x
ListMorphism.finalSumSizesArrayList  thrpt   25  245.020 ±  0.106 ops/us
ListMorphism.finalSumSizesList       thrpt   25  335.107 ±  0.439 ops/us
# 1.4x
ListMorphism.getFromArrayList        thrpt   25   70.343 ±  0.972 ops/us
ListMorphism.getFromList             thrpt   25   37.121 ±  0.135 ops/us
# 0.53x
ListMorphism.getFromArrayList12      thrpt   25 109.890 ±  0.286  ops/us
ListMorphism.getFromList12           thrpt   25  109.552 ± 6.972  ops/us
# 1.0x
ListMorphism.sumSizesArrayList       thrpt   25  131.467 ±  4.672 ops/us
ListMorphism.sumSizesList            thrpt   25   57.877 ±  0.102 ops/us
# 0.45x
ListMorphism.sumSizesArrayList12     thrpt   25 208.652 ± 11.294  ops/us
ListMorphism.sumSizesList12          thrpt   25  227.269 ± 0.961  ops/us
# 1.1x

The good: When dealing with List literals (the final* benchmarks),
List.of() allows really nice speed-ups compared to ArrayList.

The bad: When not used as a literal, List.of() implementations at
call-sites can cause a substantial slowdown (megamorphic dispatch)

The ugly:

After some explorations[1], I narrowed in on the following experiment:
http://cr.openjdk.java.net/~redestad/scratch/less_immutables/webrev/

Basically: Merge List1 and List2 into a single class, List12, merge
List0 into ListN (List0 has a singleton instance, so might as well be an
instance of ListN). Same for Set0,1,2,N. Map0 is merged into MapN.

This strikes a balance between throughput, footprint and slightly better
startup/warmup behavior.

According to jol estimates[2] the size of List12 is the same as both
List1 and List2 in the current JDK implementation. Set12 is footprint
neutral compared to Set2 on all platforms but lose a few bytes on 64-bit
VMs compared to Set1.

Benchmark                             Mode  Cnt    Score   Error Units
ListMorphism.finalGetFromArrayList   thrpt   25   93.046 ± 0.569 ops/us
ListMorphism.finalGetFromList        thrpt   25  335.280 ± 0.154 ops/us
# 3.6x
ListMorphism.finalSumSizesArrayList  thrpt   25  244.595 ± 1.085 ops/us
ListMorphism.finalSumSizesList       thrpt   25  303.351 ± 0.182 ops/us
# 1.2x
ListMorphism.getFromArrayList        thrpt   25   70.631 ± 0.070 ops/us
ListMorphism.getFromList             thrpt   25   73.258 ± 2.955 ops/us
# 1.04x
ListMorphism.getFromArrayList12      thrpt   25 109.921 ± 0.096  ops/us
ListMorphism.getFromList12           thrpt   25  127.392 ± 0.088  ops/us
# 1.16x
ListMorphism.sumSizesArrayList       thrpt   25  131.393 ± 4.882 ops/us
ListMorphism.sumSizesList            thrpt   25  107.686 ± 5.286 ops/us
# 0.82x
ListMorphism.sumSizesArrayList12     thrpt   25  212.350 ± 0.134  ops/us
ListMorphism.sumSizesList12          thrpt   25  198.778 ± 0.479  ops/us
# 0.94x

The experiment has a flag to change number of specialized List/Set/Map
classes (-Djdk.ImmutableCollections.specializations=0|1|2, default=2).

1 specialization (List1 + ListN, Set1 + SetN) is more or less the same
as 2, some ~1-2% improvements, mainly in sumSizes micros.

0 specializations (List-, Set, MapN only) achieves a small increase in
throughput on some micros by ensuring callsites stay monomorphic, but
it's not very substantial by my measures (~5%, but mostly in sumSizes
micros).

Keeping the footprint more or less the same, while evening out a few
rough edges and improving startup and static footprint seems like the
overall best option. An alternative would be to keep the experimental
flag, but I don't think a 5% gain on micros warrants the extra
maintenance burden and testing that entails.

The proposed patch is more or less this experiment with 2
specializations, but having removed the flag and code movement needed to
support it removed (along with a fix in the writeReplace methods of
List12/Set12)

Thanks!

/Claes

[1] Older experiments:
http://cr.openjdk.java.net/~redestad/immutable/list12N.0/
  -- simply merge L0 into LN (still have L1, L2 and LN) - nothing really
changed, though

http://cr.openjdk.java.net/~redestad/immutable/list1N.0/
  -- L0 merged into LN, drop L2. Substantial performance boost on
micros. Footprint drop for 2-element lists.

http://cr.openjdk.java.net/~redestad/immutable/listNdouble.0/
  -- L0+L1+L2+LN merged into one implementation. Same footprint with a
single class, but loses a lot on throughput in micros.

http://cr.openjdk.java.net/~redestad/immutable/listNsingle.0/
  -- L0+L1+LN merged, drop L2. Simplification of the previous. Like the
list1N.0 experiment in footprint, but a loss in throughput on all measures.

No approach seemed a win across the board here: we either had to accept
a footprint reduction, or see throughput suffer dramatically.

[2] http://openjdk.java.net/projects/code-tools/jol/
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Jonathan Bluett-Duncan
Hi Claes,

Looking at
http://cr.openjdk.java.net/~redestad/8193128/open.00/src/java.base/share/classes/java/util/ImmutableCollections.java.cdiff.html,
there are sections labelled --- 646,657 ---- and --- 834,845 ---- where
lines like `Objects.requireNonNull(0 /* zero */);` are written. I believe
that they were supposed to be either removed or made to be written like
`Objects.requireNonNull(o /* lowercase o */)`. Is my belief/understanding
correct?

Cheers,
Jonathan

On 6 December 2017 at 20:21, Claes Redestad <[hidden email]>
wrote:

> Hi,
>
> please help review this patch to consolidate the number of implementation
> classes returned by the static collection factories:
>
> http://cr.openjdk.java.net/~redestad/8193128/open.00/
>
> I set out to explore options for addressing small inefficiencies we've
> been running into, the latest after replacing use of @Stable arrays in
> java.lang.invoke with List.of() (JDK-8184777):
>
> - List.indexOf deferred to the iterator in AbstractList, which check for
> concurrent modification
> - Warmup takes a bit longer due to having to warm up four different
> classes and associated methods
> - Slowdowns in certain code paths attributable to certain calls becoming
> megamorphic
>
> Microbenchmark: http://cr.openjdk.java.net/~re
> destad/scratch/less_immutables/ListMorphism.java
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables
> /benchmarks.jar
>
> The benchmark explores how call-sites behave when performing some naive
> operations on a few different Lists.
>
> For every benchmark using List.of() there's a variant using ArrayList for
> comparison:
>
> Baseline:
>
> Benchmark                             Mode  Cnt    Score Error   Units
> ListMorphism.finalGetFromArrayList   thrpt   25   92.659 ±  3.058 ops/us
> ListMorphism.finalGetFromList        thrpt   25  335.245 ±  0.244 ops/us
> # 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  245.020 ±  0.106 ops/us
> ListMorphism.finalSumSizesList       thrpt   25  335.107 ±  0.439 ops/us
> # 1.4x
> ListMorphism.getFromArrayList        thrpt   25   70.343 ±  0.972 ops/us
> ListMorphism.getFromList             thrpt   25   37.121 ±  0.135 ops/us
> # 0.53x
> ListMorphism.getFromArrayList12      thrpt   25 109.890 ±  0.286  ops/us
> ListMorphism.getFromList12           thrpt   25  109.552 ± 6.972  ops/us
> # 1.0x
> ListMorphism.sumSizesArrayList       thrpt   25  131.467 ±  4.672 ops/us
> ListMorphism.sumSizesList            thrpt   25   57.877 ±  0.102 ops/us
> # 0.45x
> ListMorphism.sumSizesArrayList12     thrpt   25 208.652 ± 11.294  ops/us
> ListMorphism.sumSizesList12          thrpt   25  227.269 ± 0.961  ops/us
> # 1.1x
>
> The good: When dealing with List literals (the final* benchmarks),
> List.of() allows really nice speed-ups compared to ArrayList.
>
> The bad: When not used as a literal, List.of() implementations at
> call-sites can cause a substantial slowdown (megamorphic dispatch)
>
> The ugly:
>
> After some explorations[1], I narrowed in on the following experiment:
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/webrev/
>
> Basically: Merge List1 and List2 into a single class, List12, merge List0
> into ListN (List0 has a singleton instance, so might as well be an instance
> of ListN). Same for Set0,1,2,N. Map0 is merged into MapN.
>
> This strikes a balance between throughput, footprint and slightly better
> startup/warmup behavior.
>
> According to jol estimates[2] the size of List12 is the same as both List1
> and List2 in the current JDK implementation. Set12 is footprint neutral
> compared to Set2 on all platforms but lose a few bytes on 64-bit VMs
> compared to Set1.
>
> Benchmark                             Mode  Cnt    Score   Error Units
> ListMorphism.finalGetFromArrayList   thrpt   25   93.046 ± 0.569 ops/us
> ListMorphism.finalGetFromList        thrpt   25  335.280 ± 0.154 ops/us #
> 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  244.595 ± 1.085 ops/us
> ListMorphism.finalSumSizesList       thrpt   25  303.351 ± 0.182 ops/us #
> 1.2x
> ListMorphism.getFromArrayList        thrpt   25   70.631 ± 0.070 ops/us
> ListMorphism.getFromList             thrpt   25   73.258 ± 2.955 ops/us #
> 1.04x
> ListMorphism.getFromArrayList12      thrpt   25 109.921 ± 0.096  ops/us
> ListMorphism.getFromList12           thrpt   25  127.392 ± 0.088  ops/us
> # 1.16x
> ListMorphism.sumSizesArrayList       thrpt   25  131.393 ± 4.882 ops/us
> ListMorphism.sumSizesList            thrpt   25  107.686 ± 5.286 ops/us #
> 0.82x
> ListMorphism.sumSizesArrayList12     thrpt   25  212.350 ± 0.134  ops/us
> ListMorphism.sumSizesList12          thrpt   25  198.778 ± 0.479  ops/us
> # 0.94x
>
> The experiment has a flag to change number of specialized List/Set/Map
> classes (-Djdk.ImmutableCollections.specializations=0|1|2, default=2).
>
> 1 specialization (List1 + ListN, Set1 + SetN) is more or less the same as
> 2, some ~1-2% improvements, mainly in sumSizes micros.
>
> 0 specializations (List-, Set, MapN only) achieves a small increase in
> throughput on some micros by ensuring callsites stay monomorphic, but it's
> not very substantial by my measures (~5%, but mostly in sumSizes micros).
>
> Keeping the footprint more or less the same, while evening out a few rough
> edges and improving startup and static footprint seems like the overall
> best option. An alternative would be to keep the experimental flag, but I
> don't think a 5% gain on micros warrants the extra maintenance burden and
> testing that entails.
>
> The proposed patch is more or less this experiment with 2 specializations,
> but having removed the flag and code movement needed to support it removed
> (along with a fix in the writeReplace methods of List12/Set12)
>
> Thanks!
>
> /Claes
>
> [1] Older experiments:
> http://cr.openjdk.java.net/~redestad/immutable/list12N.0/
>  -- simply merge L0 into LN (still have L1, L2 and LN) - nothing really
> changed, though
>
> http://cr.openjdk.java.net/~redestad/immutable/list1N.0/
>  -- L0 merged into LN, drop L2. Substantial performance boost on micros.
> Footprint drop for 2-element lists.
>
> http://cr.openjdk.java.net/~redestad/immutable/listNdouble.0/
>  -- L0+L1+L2+LN merged into one implementation. Same footprint with a
> single class, but loses a lot on throughput in micros.
>
> http://cr.openjdk.java.net/~redestad/immutable/listNsingle.0/
>  -- L0+L1+LN merged, drop L2. Simplification of the previous. Like the
> list1N.0 experiment in footprint, but a loss in throughput on all measures.
>
> No approach seemed a win across the board here: we either had to accept a
> footprint reduction, or see throughput suffer dramatically.
>
> [2] http://openjdk.java.net/projects/code-tools/jol/
>
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Martin Buchholz-3
In reply to this post by Claes Redestad
Guava struggled with this as well with their immutable collections.  You
could look at their revision history (I haven't). Maybe they got rid of
SingletonImmutableList for the same reason?

On Wed, Dec 6, 2017 at 12:21 PM, Claes Redestad <[hidden email]>
wrote:

> Hi,
>
> please help review this patch to consolidate the number of implementation
> classes returned by the static collection factories:
>
> http://cr.openjdk.java.net/~redestad/8193128/open.00/
>
> I set out to explore options for addressing small inefficiencies we've
> been running into, the latest after replacing use of @Stable arrays in
> java.lang.invoke with List.of() (JDK-8184777):
>
> - List.indexOf deferred to the iterator in AbstractList, which check for
> concurrent modification
> - Warmup takes a bit longer due to having to warm up four different
> classes and associated methods
> - Slowdowns in certain code paths attributable to certain calls becoming
> megamorphic
>
> Microbenchmark: http://cr.openjdk.java.net/~re
> destad/scratch/less_immutables/ListMorphism.java
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables
> /benchmarks.jar
>
> The benchmark explores how call-sites behave when performing some naive
> operations on a few different Lists.
>
> For every benchmark using List.of() there's a variant using ArrayList for
> comparison:
>
> Baseline:
>
> Benchmark                             Mode  Cnt    Score Error   Units
> ListMorphism.finalGetFromArrayList   thrpt   25   92.659 ±  3.058 ops/us
> ListMorphism.finalGetFromList        thrpt   25  335.245 ±  0.244 ops/us
> # 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  245.020 ±  0.106 ops/us
> ListMorphism.finalSumSizesList       thrpt   25  335.107 ±  0.439 ops/us
> # 1.4x
> ListMorphism.getFromArrayList        thrpt   25   70.343 ±  0.972 ops/us
> ListMorphism.getFromList             thrpt   25   37.121 ±  0.135 ops/us
> # 0.53x
> ListMorphism.getFromArrayList12      thrpt   25 109.890 ±  0.286  ops/us
> ListMorphism.getFromList12           thrpt   25  109.552 ± 6.972  ops/us
> # 1.0x
> ListMorphism.sumSizesArrayList       thrpt   25  131.467 ±  4.672 ops/us
> ListMorphism.sumSizesList            thrpt   25   57.877 ±  0.102 ops/us
> # 0.45x
> ListMorphism.sumSizesArrayList12     thrpt   25 208.652 ± 11.294  ops/us
> ListMorphism.sumSizesList12          thrpt   25  227.269 ± 0.961  ops/us
> # 1.1x
>
> The good: When dealing with List literals (the final* benchmarks),
> List.of() allows really nice speed-ups compared to ArrayList.
>
> The bad: When not used as a literal, List.of() implementations at
> call-sites can cause a substantial slowdown (megamorphic dispatch)
>
> The ugly:
>
> After some explorations[1], I narrowed in on the following experiment:
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/webrev/
>
> Basically: Merge List1 and List2 into a single class, List12, merge List0
> into ListN (List0 has a singleton instance, so might as well be an instance
> of ListN). Same for Set0,1,2,N. Map0 is merged into MapN.
>
> This strikes a balance between throughput, footprint and slightly better
> startup/warmup behavior.
>
> According to jol estimates[2] the size of List12 is the same as both List1
> and List2 in the current JDK implementation. Set12 is footprint neutral
> compared to Set2 on all platforms but lose a few bytes on 64-bit VMs
> compared to Set1.
>
> Benchmark                             Mode  Cnt    Score   Error Units
> ListMorphism.finalGetFromArrayList   thrpt   25   93.046 ± 0.569 ops/us
> ListMorphism.finalGetFromList        thrpt   25  335.280 ± 0.154 ops/us #
> 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  244.595 ± 1.085 ops/us
> ListMorphism.finalSumSizesList       thrpt   25  303.351 ± 0.182 ops/us #
> 1.2x
> ListMorphism.getFromArrayList        thrpt   25   70.631 ± 0.070 ops/us
> ListMorphism.getFromList             thrpt   25   73.258 ± 2.955 ops/us #
> 1.04x
> ListMorphism.getFromArrayList12      thrpt   25 109.921 ± 0.096  ops/us
> ListMorphism.getFromList12           thrpt   25  127.392 ± 0.088  ops/us
> # 1.16x
> ListMorphism.sumSizesArrayList       thrpt   25  131.393 ± 4.882 ops/us
> ListMorphism.sumSizesList            thrpt   25  107.686 ± 5.286 ops/us #
> 0.82x
> ListMorphism.sumSizesArrayList12     thrpt   25  212.350 ± 0.134  ops/us
> ListMorphism.sumSizesList12          thrpt   25  198.778 ± 0.479  ops/us
> # 0.94x
>
> The experiment has a flag to change number of specialized List/Set/Map
> classes (-Djdk.ImmutableCollections.specializations=0|1|2, default=2).
>
> 1 specialization (List1 + ListN, Set1 + SetN) is more or less the same as
> 2, some ~1-2% improvements, mainly in sumSizes micros.
>
> 0 specializations (List-, Set, MapN only) achieves a small increase in
> throughput on some micros by ensuring callsites stay monomorphic, but it's
> not very substantial by my measures (~5%, but mostly in sumSizes micros).
>
> Keeping the footprint more or less the same, while evening out a few rough
> edges and improving startup and static footprint seems like the overall
> best option. An alternative would be to keep the experimental flag, but I
> don't think a 5% gain on micros warrants the extra maintenance burden and
> testing that entails.
>
> The proposed patch is more or less this experiment with 2 specializations,
> but having removed the flag and code movement needed to support it removed
> (along with a fix in the writeReplace methods of List12/Set12)
>
> Thanks!
>
> /Claes
>
> [1] Older experiments:
> http://cr.openjdk.java.net/~redestad/immutable/list12N.0/
>  -- simply merge L0 into LN (still have L1, L2 and LN) - nothing really
> changed, though
>
> http://cr.openjdk.java.net/~redestad/immutable/list1N.0/
>  -- L0 merged into LN, drop L2. Substantial performance boost on micros.
> Footprint drop for 2-element lists.
>
> http://cr.openjdk.java.net/~redestad/immutable/listNdouble.0/
>  -- L0+L1+L2+LN merged into one implementation. Same footprint with a
> single class, but loses a lot on throughput in micros.
>
> http://cr.openjdk.java.net/~redestad/immutable/listNsingle.0/
>  -- L0+L1+LN merged, drop L2. Simplification of the previous. Like the
> list1N.0 experiment in footprint, but a loss in throughput on all measures.
>
> No approach seemed a win across the board here: we either had to accept a
> footprint reduction, or see throughput suffer dramatically.
>
> [2] http://openjdk.java.net/projects/code-tools/jol/
>
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Claes Redestad
In reply to this post by Jonathan Bluett-Duncan
Hi Jonathan,

On 2017-12-06 21:58, Jonathan Bluett-Duncan wrote:

> Hi Claes,
>
> Looking at
> http://cr.openjdk.java.net/~redestad/8193128/open.00/src/java.base/share/classes/java/util/ImmutableCollections.java.cdiff.html 
> <http://cr.openjdk.java.net/%7Eredestad/8193128/open.00/src/java.base/share/classes/java/util/ImmutableCollections.java.cdiff.html>,
> there are sections labelled --- 646,657 ---- and --- 834,845
> ---- where lines like `Objects.requireNonNull(0 /* zero */);` are
> written. I believe that they were supposed to be either removed or
> made to be written like `Objects.requireNonNull(o /* lowercase o */)`.
> Is my belief/understanding correct?

nice catch! That was two fun little typos on my part (now why did we
ever make 0 box to an Object...). Fixing in-place.

Thanks!

/Claes
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Remi Forax
In reply to this post by Claes Redestad
Hi Claes,
- both constructors of SubList should be package private,
- in listIterator, i can be declared outside of the ListIterator as a local variable that would be captured by the anonymous class,
  so index is not used inside the anonymous class. Also you can use the diamond syntax for anonymous class now.

  public ListIterator<E> listIterator(int index) {
    rangeCheck(index);
    ListIterator<E> i = root.listIterator(offset + index);
    return new ListIterator<>() {
      ...

- you can move "new IndexOutOfBoundsException" out of rangeCheck into outOfBoundsMsg, so the bytecode size of rangeCheck() will be smaller.

- in Itr, please declare the constructor after the declaration of the fields,
  and assigning the cursor to zero is useless.

- in equals, the code is weirdly asymmetric because e1 is typed as an Iterator<E>, declaring it as an Iterator<?> will make the code more symmetric.

- in List12, you have a lot of useless @SuppressWarnings("unchecked") ??
  in size(), get(), contains(), hashCode(), writeReplace().

- in ListN, again some useless @SuppressWarnings("unchecked") ??
  in  size(), get(), contains(), hashCode(), writeReplace()

- the constructor of MapN(K,V) can be made a little more efficient (less getfield opcodes) if written like this
   
  MapN(K key, V value) {
      table = new Object[] { key, value };
      size = 1;
  }

  and i do not understand why the field size is not declared @Stable anymore,
  ok, it can be equals to zero, but in that case the JIT will emit a move
  so it's better than always asking for a move (or i do not understand the semantics of @Stable ?)

cheers,
Rémi


----- Mail original -----
> De: "Claes Redestad" <[hidden email]>
> À: "core-libs-dev" <[hidden email]>, "Stuart Marks" <[hidden email]>
> Envoyé: Mercredi 6 Décembre 2017 21:21:55
> Objet: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

> Hi,
>
> please help review this patch to consolidate the number of
> implementation classes returned by the static collection factories:
>
> http://cr.openjdk.java.net/~redestad/8193128/open.00/
>
> I set out to explore options for addressing small inefficiencies we've
> been running into, the latest after replacing use of @Stable arrays in
> java.lang.invoke with List.of() (JDK-8184777):
>
> - List.indexOf deferred to the iterator in AbstractList, which check for
> concurrent modification
> - Warmup takes a bit longer due to having to warm up four different
> classes and associated methods
> - Slowdowns in certain code paths attributable to certain calls becoming
> megamorphic
>
> Microbenchmark:
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/ListMorphism.java
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/benchmarks.jar
>
> The benchmark explores how call-sites behave when performing some naive
> operations on a few different Lists.
>
> For every benchmark using List.of() there's a variant using ArrayList
> for comparison:
>
> Baseline:
>
> Benchmark                             Mode  Cnt    Score Error   Units
> ListMorphism.finalGetFromArrayList   thrpt   25   92.659 ±  3.058 ops/us
> ListMorphism.finalGetFromList        thrpt   25  335.245 ±  0.244 ops/us
> # 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  245.020 ±  0.106 ops/us
> ListMorphism.finalSumSizesList       thrpt   25  335.107 ±  0.439 ops/us
> # 1.4x
> ListMorphism.getFromArrayList        thrpt   25   70.343 ±  0.972 ops/us
> ListMorphism.getFromList             thrpt   25   37.121 ±  0.135 ops/us
> # 0.53x
> ListMorphism.getFromArrayList12      thrpt   25 109.890 ±  0.286  ops/us
> ListMorphism.getFromList12           thrpt   25  109.552 ± 6.972  ops/us
> # 1.0x
> ListMorphism.sumSizesArrayList       thrpt   25  131.467 ±  4.672 ops/us
> ListMorphism.sumSizesList            thrpt   25   57.877 ±  0.102 ops/us
> # 0.45x
> ListMorphism.sumSizesArrayList12     thrpt   25 208.652 ± 11.294  ops/us
> ListMorphism.sumSizesList12          thrpt   25  227.269 ± 0.961  ops/us
> # 1.1x
>
> The good: When dealing with List literals (the final* benchmarks),
> List.of() allows really nice speed-ups compared to ArrayList.
>
> The bad: When not used as a literal, List.of() implementations at
> call-sites can cause a substantial slowdown (megamorphic dispatch)
>
> The ugly:
>
> After some explorations[1], I narrowed in on the following experiment:
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/webrev/
>
> Basically: Merge List1 and List2 into a single class, List12, merge
> List0 into ListN (List0 has a singleton instance, so might as well be an
> instance of ListN). Same for Set0,1,2,N. Map0 is merged into MapN.
>
> This strikes a balance between throughput, footprint and slightly better
> startup/warmup behavior.
>
> According to jol estimates[2] the size of List12 is the same as both
> List1 and List2 in the current JDK implementation. Set12 is footprint
> neutral compared to Set2 on all platforms but lose a few bytes on 64-bit
> VMs compared to Set1.
>
> Benchmark                             Mode  Cnt    Score   Error Units
> ListMorphism.finalGetFromArrayList   thrpt   25   93.046 ± 0.569 ops/us
> ListMorphism.finalGetFromList        thrpt   25  335.280 ± 0.154 ops/us
> # 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  244.595 ± 1.085 ops/us
> ListMorphism.finalSumSizesList       thrpt   25  303.351 ± 0.182 ops/us
> # 1.2x
> ListMorphism.getFromArrayList        thrpt   25   70.631 ± 0.070 ops/us
> ListMorphism.getFromList             thrpt   25   73.258 ± 2.955 ops/us
> # 1.04x
> ListMorphism.getFromArrayList12      thrpt   25 109.921 ± 0.096  ops/us
> ListMorphism.getFromList12           thrpt   25  127.392 ± 0.088  ops/us
> # 1.16x
> ListMorphism.sumSizesArrayList       thrpt   25  131.393 ± 4.882 ops/us
> ListMorphism.sumSizesList            thrpt   25  107.686 ± 5.286 ops/us
> # 0.82x
> ListMorphism.sumSizesArrayList12     thrpt   25  212.350 ± 0.134  ops/us
> ListMorphism.sumSizesList12          thrpt   25  198.778 ± 0.479  ops/us
> # 0.94x
>
> The experiment has a flag to change number of specialized List/Set/Map
> classes (-Djdk.ImmutableCollections.specializations=0|1|2, default=2).
>
> 1 specialization (List1 + ListN, Set1 + SetN) is more or less the same
> as 2, some ~1-2% improvements, mainly in sumSizes micros.
>
> 0 specializations (List-, Set, MapN only) achieves a small increase in
> throughput on some micros by ensuring callsites stay monomorphic, but
> it's not very substantial by my measures (~5%, but mostly in sumSizes
> micros).
>
> Keeping the footprint more or less the same, while evening out a few
> rough edges and improving startup and static footprint seems like the
> overall best option. An alternative would be to keep the experimental
> flag, but I don't think a 5% gain on micros warrants the extra
> maintenance burden and testing that entails.
>
> The proposed patch is more or less this experiment with 2
> specializations, but having removed the flag and code movement needed to
> support it removed (along with a fix in the writeReplace methods of
> List12/Set12)
>
> Thanks!
>
> /Claes
>
> [1] Older experiments:
> http://cr.openjdk.java.net/~redestad/immutable/list12N.0/
>  -- simply merge L0 into LN (still have L1, L2 and LN) - nothing really
> changed, though
>
> http://cr.openjdk.java.net/~redestad/immutable/list1N.0/
>  -- L0 merged into LN, drop L2. Substantial performance boost on
> micros. Footprint drop for 2-element lists.
>
> http://cr.openjdk.java.net/~redestad/immutable/listNdouble.0/
>  -- L0+L1+L2+LN merged into one implementation. Same footprint with a
> single class, but loses a lot on throughput in micros.
>
> http://cr.openjdk.java.net/~redestad/immutable/listNsingle.0/
>  -- L0+L1+LN merged, drop L2. Simplification of the previous. Like the
> list1N.0 experiment in footprint, but a loss in throughput on all measures.
>
> No approach seemed a win across the board here: we either had to accept
> a footprint reduction, or see throughput suffer dramatically.
>
> [2] http://openjdk.java.net/projects/code-tools/jol/
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Claes Redestad
In reply to this post by Martin Buchholz-3
Hi,

On 2017-12-06 22:20, Martin Buchholz wrote:
> Guava struggled with this as well with their immutable collections. 
> You could look at their revision history (I haven't). Maybe they got
> rid of SingletonImmutableList for the same reason?

I've not looked at guava sources, but I've seen comments alluding to
similar issues there, yes.

There's definitely different trade-offs here, and I'm making the
conservative choice of taking the one that is in effect and trying to
make it just a bit better.

/Claes
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Claes Redestad
In reply to this post by Remi Forax
Hi Rémi,

On 2017-12-06 23:57, Remi Forax wrote:
> Hi Claes,
> - both constructors of SubList should be package private,

deal!

> - in listIterator, i can be declared outside of the ListIterator as a local variable that would be captured by the anonymous class,
>    so index is not used inside the anonymous class. Also you can use the diamond syntax for anonymous class now.
>
>    public ListIterator<E> listIterator(int index) {
>      rangeCheck(index);
>      ListIterator<E> i = root.listIterator(offset + index);
>      return new ListIterator<>() {
>        ...

Sure.

> - you can move "new IndexOutOfBoundsException" out of rangeCheck into outOfBoundsMsg, so the bytecode size of rangeCheck() will be smaller.

I had already done so for the outer class, and realized I had forgotten
to clean this part up:

SubList is now final, inherits from AbstractImmutableList instead of
AbstractList and reuses more of the shared code.

I also moved 'implements Serializable' from AbstractImmutableList to
List12 and ListN respectively to not
change the behavior that List.of(0,1) is serializable while
List.of(0,1).subList(0,1) isn't.

> - in Itr, please declare the constructor after the declaration of the fields,
>    and assigning the cursor to zero is useless.

Done.

>
> - in equals, the code is weirdly asymmetric because e1 is typed as an Iterator<E>, declaring it as an Iterator<?> will make the code more symmetric.

I also realized I had missed an opportunity to take advantage of the
fact that elements returned from e1 are guaranteed to
be non-null. Might as well.

>
> - in List12, you have a lot of useless @SuppressWarnings("unchecked") ??
>    in size(), get(), contains(), hashCode(), writeReplace().
>
> - in ListN, again some useless @SuppressWarnings("unchecked") ??
>    in  size(), get(), contains(), hashCode(), writeReplace()

I don't know how these snuck in, but my IDE was pleasantly hiding these
away. I think I cleaned out all the useless ones.

> - the constructor of MapN(K,V) can be made a little more efficient (less getfield opcodes) if written like this
>    
>    MapN(K key, V value) {
>        table = new Object[] { key, value };
>        size = 1;
>    }

Oops, this was a leftover from my experiment where I adapted MapN to
implement Map1 when setting specializers=0. Removed.

>
>    and i do not understand why the field size is not declared @Stable anymore,
>    ok, it can be equals to zero, but in that case the JIT will emit a move
>    so it's better than always asking for a move (or i do not understand the semantics of @Stable ?)

Hmm, I'm under the impression @Stable brings no additional value to a
final non-array fields (definitely important for arrays).

I might have been guilty of adding @Stable to more fields than necessary
in these implementations in the first place. I've
reverted this removal and will add a note to investigate separately if
we can more systematically clean them up.

http://cr.openjdk.java.net/~redestad/8193128/open.01/

Thanks!

/Claes
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Paul Sandoz


> On 6 Dec 2017, at 16:12, Claes Redestad <[hidden email]> wrote:
>>
>>   and i do not understand why the field size is not declared @Stable anymore,
>>   ok, it can be equals to zero, but in that case the JIT will emit a move
>>   so it's better than always asking for a move (or i do not understand the semantics of @Stable ?)
>
> Hmm, I'm under the impression @Stable brings no additional value to a final non-array fields (definitely important for arrays).
>

It can, since final fields are not treated as really final (unless in java.lang.invoke package, where it’s as if all such fields are annotated with @Stable). C2 will treat the field value a constant value if the collection is held in a static final field.

Paul.

> I might have been guilty of adding @Stable to more fields than necessary in these implementations in the first place. I've
> reverted this removal and will add a note to investigate separately if we can more systematically clean them up.
>
> http://cr.openjdk.java.net/~redestad/8193128/open.01/
>
> Thanks!
>
> /Claes

Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

John Rose-3


> On Dec 6, 2017, at 5:16 PM, Paul Sandoz <[hidden email]> wrote:
>
> It can, since final fields are not treated as really final (unless in java.lang.invoke package, where it’s as if all such fields are annotated with @Stable). C2 will treat the field value a constant value if the collection is held in a static final field.

We could tweak the semantics of @Stable to omit the zero corner case for a final field. Then the annotation on a non-array field would mean “trust this final”.

It would be yet another stop gap before that far-off day when we fix finals (and arrays). Such new uses of @Stable would have to be evaluated for any interaction with deserialization, so it’s not a simple decision.



Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Remi Forax
You have also the problem of people doing a lot of things in the constructor, by example

class Foo {
  @Stable final int x;

  Foo() {
    m();
    x = 3;
    m();
  }

  void m() {
    for(...) {
      // use x here
    }
  }
}

here, m() can be JITed with x equals to 0 as a constant and the code of m() be re-use for the second call even if the value of x has changed in the middle.
in that case, either you need to maintain dependency between the JITed code and the field 'x' or have a bit saying if an object is fully initialized or not, this bit will be true at the end of the constructor and can be set for the de-serialization too.

Rémi

----- Mail original -----
> De: "John Rose" <[hidden email]>
> À: "Paul Sandoz" <[hidden email]>
> Cc: "core-libs-dev" <[hidden email]>
> Envoyé: Jeudi 7 Décembre 2017 20:50:01
> Objet: Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

>> On Dec 6, 2017, at 5:16 PM, Paul Sandoz <[hidden email]> wrote:
>>
>> It can, since final fields are not treated as really final (unless in
>> java.lang.invoke package, where it’s as if all such fields are annotated with
>> @Stable). C2 will treat the field value a constant value if the collection is
>> held in a static final field.
>
> We could tweak the semantics of @Stable to omit the zero corner case for a final
> field. Then the annotation on a non-array field would mean “trust this final”.
>
> It would be yet another stop gap before that far-off day when we fix finals (and
> arrays). Such new uses of @Stable would have to be evaluated for any
> interaction with deserialization, so it’s not a simple decision.
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

John Rose-3
On Dec 7, 2017, at 12:05 PM, Remi Forax <[hidden email]> wrote:
>
> have a bit saying if an object is fully initialized or not, this bit will be true at the end of the constructor and can be set for the de-serialization too

Yes, that's the hard part of fixing final.  Sometimes we call this the "slushy bit".
It would almost always be false, but would be true for those unusual objects
which are in the process of deserialization, and also (perhaps) objects which
may escape into the optimizer while undergoing normal construction. The
latter version of "slushy" is probably a statically computable condition,
unlike "slushy during deserialization".

Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Claes Redestad
In reply to this post by Claes Redestad


On 2017-12-07 01:12, Claes Redestad wrote:
> SubList is now final, inherits from AbstractImmutableList instead of
> AbstractList and reuses more of the shared code.
>
> I also moved 'implements Serializable' from AbstractImmutableList to
> List12 and ListN respectively to not
> change the behavior that List.of(0,1) is serializable while
> List.of(0,1).subList(0,1) isn't.

While doing this, I realized a few issues with my patch around the
subList mechanics:

- I had "optimized" AbstractImmutable::subList to return self or
emptyList if appropriate, which sounded nice, but is in fact an
incompatible change (some subLists become Serializable).
- the ListFactories test didn't explicitly verify that sublists
retrieved from various List.of() impls aren't Serializable. Added tests
to check no sub-list is Serializable,
and as a bonus this test now verifies that List.of(...).subList(...)
behave like their List.of(..) counterparts in most other ways.
- fixed range check in AbstractImmutableList.listIterator(0) to not
throw IOOBE if the list is empty

http://cr.openjdk.java.net/~redestad/8193128/open.02/

Thanks!

/Claes
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Andrej Golovnin-2
Hi Claes,

> http://cr.openjdk.java.net/~redestad/8193128/open.02/

I think you should provide specialised implementations of the
#indexOf() and #lastIndexOf() methods in the classes List12 and ListN.
Using an iterator in List12 is an overkill. But even in ListN using a
simple for loop would be much better. In any case please take look at
the implementation of the #lastIndexOf() method in the
AbstractImmutableList class. It looks like a copy of
AbstractImmutableList#indexOf() and this is wrong.

Best regards,
Andrej Golovnin
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Claes Redestad
Hi,

On 2017-12-08 07:54, Andrej Golovnin wrote:
> Hi Claes,
>
>> http://cr.openjdk.java.net/~redestad/8193128/open.02/
> I think you should provide specialised implementations of the
> #indexOf() and #lastIndexOf() methods in the classes List12 and ListN.
> Using an iterator in List12 is an overkill. But even in ListN using a
> simple for loop would be much better.

it's somewhat ironic that I started looking at this *because*
indexOf was slow due use of iterators[1], but then never got
around to specialize them in this patch.

> In any case please take look at
> the implementation of the #lastIndexOf() method in the
> AbstractImmutableList class. It looks like a copy of
> AbstractImmutableList#indexOf() and this is wrong.

Nice catch! Quite the embarrassing copy-paste that...

- Specialized the index/lastIndexOf methods for List12, ListN
- Fixed implementation of lastIndexOf in AbstractImmutableList.
- As AbstractImmutableList.indexOf/lastIndexOf are now only used
by AbstractImmutableList.SubList, I moved them there with some
commentary since it's not clear JDK-8191418 should add null
checkson the input for SubList or not.
- Added sanity tests of indexOf/lastIndexOf that touches all
the new implementations:

http://cr.openjdk.java.net/~redestad/8193128/open.03/

Thanks!

/Claes

[1] https://bugs.openjdk.java.net/browse/JDK-8191442
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Martin Buchholz-3
Should there be changes to general purpose collection testing classes like
test/jdk/java/util/concurrent/tck/CollectionTest.java
test/jdk/java/util/Collection/MOAT.java
that would have caught this bug?
(although those are mostly designed for mutable collections, but I think
some immutable collections (nCopies?) get tested somewhere.

On Fri, Dec 8, 2017 at 7:13 AM, Claes Redestad <[hidden email]>
wrote:

> Hi,
>
> On 2017-12-08 07:54, Andrej Golovnin wrote:
>
>> Hi Claes,
>>
>> http://cr.openjdk.java.net/~redestad/8193128/open.02/
>>>
>> I think you should provide specialised implementations of the
>> #indexOf() and #lastIndexOf() methods in the classes List12 and ListN.
>> Using an iterator in List12 is an overkill. But even in ListN using a
>> simple for loop would be much better.
>>
>
> it's somewhat ironic that I started looking at this *because*
> indexOf was slow due use of iterators[1], but then never got
> around to specialize them in this patch.
>
> In any case please take look at
>> the implementation of the #lastIndexOf() method in the
>> AbstractImmutableList class. It looks like a copy of
>> AbstractImmutableList#indexOf() and this is wrong.
>>
>
> Nice catch! Quite the embarrassing copy-paste that...
>
> - Specialized the index/lastIndexOf methods for List12, ListN
> - Fixed implementation of lastIndexOf in AbstractImmutableList.
> - As AbstractImmutableList.indexOf/lastIndexOf are now only used
> by AbstractImmutableList.SubList, I moved them there with some
> commentary since it's not clear JDK-8191418 should add null
> checkson the input for SubList or not.
> - Added sanity tests of indexOf/lastIndexOf that touches all
> the new implementations:
>
> http://cr.openjdk.java.net/~redestad/8193128/open.03/
>
> Thanks!
>
> /Claes
>
> [1] https://bugs.openjdk.java.net/browse/JDK-8191442
>
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

John Rose-3
In reply to this post by Claes Redestad
On Dec 7, 2017, at 3:41 PM, Claes Redestad <[hidden email]> wrote:
>
> - the ListFactories test didn't explicitly verify that sublists retrieved from various List.of() impls aren't Serializable. Added tests to check no sub-list is Serializable,
> and as a bonus this test now verifies that List.of(...).subList(...) behave like their List.of(..) counterparts in most other ways.

List::subList is a view into a backing list.  But the
story is different for the value-based lists produced
by List.of.

If L is a value-based class, then it seems to me
a meaningless (therefore useless) distinction to
call L::subList a "view".  A slice of a value-based list
can only be another value-based list, because there
is nothing else to slice, besides the component values
of the original list.

So I think we should move forward more confidently
with subList here, and say that List.of(a,b,c).subList(1,2)
is equivalent in all ways to List.of(b,c), and so on.

Can anyone point out a reason why the value based
lists of List.of() should serialize while the value based
lists of List.of().subList() should not?  Or is there some
reason we should not allow subList to produce value
based lists?

— John
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

John Rose-3
In reply to this post by Claes Redestad
On Dec 8, 2017, at 7:13 AM, Claes Redestad <[hidden email]> wrote:
>
> http://cr.openjdk.java.net/~redestad/8193128/open.03/
>
+            for (int i = elements.length - 1; i > 0; i--) {

There's an OBOE in this line; should be i >= 0.

Errors like this are a risk of hand-specializing code.
It's probably worth it here, but it's still a risk.

For immutable lists, it would be reasonable to recode
the generic algorithms to use for-loops with integer
indexes and get(int) access.  That will remove
the unused generality of iterators, and keep only
the abstraction across get().  The benefits of customized
inlining (to fold up the funny specialized get methods)
can probably be obtained like this:

class AbsImmList {
  @ForceInline int indexOf(Object x) {
    for (int i = 0, s = size(); i < s; i++)  if (x.equals(this.get(i))) return i;
  }
}
final class List12 {
  int indexOf(Object x) { return super.indexOf(x); }  // specialize size/get
}
final class ListN {
  int indexOf(Object x) { return super.indexOf(x); }  // specialize size/get
}

The optimization of the funny 1/2 loop for List12 should
unfold into the same code you'd write by hand; if not it's
a bug to fix in C2.  Likewise for the loop in ListN.

— John

P.S. If you are going to hand-specialize, it might be
easier on the optimizer if you would add in this line
as needed:

  final E[] elements = this.elements;  // cache field

Usually C2 gets the same answer, but not always,
since final fields are not fully trustable, and "might"
(in some hypothetical system which C2 can't rule out)
change over a call to Object::equals.  OTOH, generic
coding as above is preferable, and we can fix C2
to hoist the @Stable elements field if it doesn't already.

P.P.S. Why does ListN have arity 1 and arity 2 constructors?

Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

John Rose-3
In reply to this post by John Rose-3
On Dec 8, 2017, at 4:45 PM, John Rose <[hidden email]> wrote:
>
> Can anyone point out a reason why the value based
> lists of List.of() should serialize while the value based
> lists of List.of().subList() should not?  Or is there some
> reason we should not allow subList to produce value
> based lists?

This gets to the heart of a question about how thoroughly we are going
to adopt the concept of value-based.  I think we want to accept that a
sub-collection derived from a value-based collection is itself
value-based, whether or not the API point (designed *before* value
based data structures) is supposed to deliver a “view” or not.  I.e.,
a view of a value-based collection is indistinguishable from a
non-view, and there are performance costs to maintaining a pretended
distinction, so let’s tune our spec. to avoid those costs.

If I'm right about this, perhaps the most natural way to balance Claes's
design is to add an offset field to ListN, and allow ListN to project arbitrary
slices out of a backing array.

Then we have only two classes (ListN, List12) even when folks are
slicing all around their lists.  That strikes me as (in terms of number
of loaded classes) much more economical than the stuff with a new
bespoke SubList class, with it's own new bespoke iterator class.
And I think the extra int field (in ListN) will melt into the noise.

— John
Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

John Rose-3
In reply to this post by Martin Buchholz-3
+1 (there should)

On Dec 8, 2017, at 9:44 AM, Martin Buchholz <[hidden email]> wrote:
>
> Should there be changes to general purpose collection testing classes like
> test/jdk/java/util/concurrent/tck/CollectionTest.java
> test/jdk/java/util/Collection/MOAT.java
> that would have caught this bug?
> (although those are mostly designed for mutable collections, but I think
> some immutable collections (nCopies?) get tested somewhere.


Reply | Threaded
Open this post in threaded view
|

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

Claes Redestad
In reply to this post by John Rose-3
Hi John,

On 2017-12-09 02:20, John Rose wrote:

> On Dec 8, 2017, at 4:45 PM, John Rose <[hidden email]
> <mailto:[hidden email]>> wrote:
>>
>> Can anyone point out a reason why the value based
>> lists of List.of() should serialize while the value based
>> lists of List.of().subList() should not?  Or is there some
>> reason we should not allow subList to produce value
>> based lists?
>
> This gets to the heart of a question about how thoroughly we are going
> to adopt the concept of value-based.  I think we want to accept that a
> sub-collection derived from a value-based collection is itself
> value-based, whether or not the API point (designed *before* value
> based data structures) is supposed to deliver a “view” or not.  I.e.,
> a view of a value-based collection is indistinguishable from a
> non-view, and there are performance costs to maintaining a pretended
> distinction, so let’s tune our spec. to avoid those costs.
>
> If I'm right about this, perhaps the most natural way to balance Claes's
> design is to add an offset field to ListN, and allow ListN to project
> arbitrary
> slices out of a backing array.
>
> Then we have only two classes (ListN, List12) even when folks are
> slicing all around their lists.  That strikes me as (in terms of number
> of loaded classes) much more economical than the stuff with a new
> bespoke SubList class, with it's own new bespoke iterator class.
> And I think the extra int field (in ListN) will melt into the noise.
>
> — John

I think one can interpret the @implSpec in AbstracList::subList to suggest
that the implementation retrieved will subclass AbstractList, which implies
it's *not* Serializable. As we move away from AbstractList then we can of
course choose our own spec, but since it's established behavior I tried as
best I could to retrofit behavior...

As time is likely up for getting this into 10 then I guess we might as well
take a step back and do this right for 11. I suspect we'll need a CSR for
this RFE regardless.

Keeping it all down to two classes as you suggest allows any mixed usage to
stay in the realm of bimorphism which might bring a considerable speedup
in some cases, and the reduction in number of implementation classes
loaded is a boon. Having all methods in ListN account for the offset might
cost us a few percent here and there, though.

An int offset on ListN would actually be footprint neutral compared to the
pre-existing implementation which pulls in the int modCount from
AbstractList.

Thanks!

/Claes
12