[External] : Re: New candidate JEP: 431: Sequenced Collections

[Stuart Marks]

On 10/18/22 8:04 AM, forax at univ-mlv.fr wrote:
>> Introduction of new types always poses a dilemma for library maintainers. They
>> can
>> move forward aggressively and embrace new features, or they can remain on older
>> releases in order to reach a broader audience. That's not a reason to avoid
>> introducing new types.
> 
> I agree in absolute, but in this specific case you want to introduce interfaces deep into the existing hierarchy of interfaces, not on the top.
> The introduction of CharSequence has been painful and very slow, that interface was added in 1.4 but we had to wait 9 more than 10 years later to have parseInt() that takes a CharSequence.
> As an application developer, a decade is the kind of time i will have to wait before i can use a sequenced collection.
> 
> Adding default methods is far faster in term of adoption, computeIfAbsent or removeIf were available at the time of the release of 1.8.
> Default methods have issues too, it only works if a good default implementation exists.

You seem to be talking about introduction of new types in opposition to introduction 
of default methods. This proposal does both. Clearly if you're using an old library, 
you can't use new types with it. But if the old library consumes or produces say, a 
List, new applications can definitely use all the default methods added to List by 
this proposal.

We've previously discussed adding new default methods (getFirst, reversed) to some 
existing type (like Collection) instead of on a new type. The problem is that they 
appear on all collections, even those that have no encounter order. Their 
specifications would thus be so weak as to be meaningless. That's the justification 
for adding a new type: to give these methods meaning.

>>> - LinkedHashMap can be tweaked in two ways, by passing an access order as 3rd
>>> parameter of the constructor or by overriding removeEldesEntry(), in both cases
>>> the resulting LinkedHashMap is at odds with the contract of SequencedMap but
>>> the compiler will happily allow to see those LinkedHashMap as SequencedMap.
>>
>> SequencedMap specifies that entries have an encounter order but it doesn't make
>> any
>> requirements on how that order is established. LinkedHashMap's access-order mode
>> is
>> unusual in that it specifies that specific methods additionally have the side
>> effect
>> of reordering the relevant entry. The removeEldestEntry() method modifies the
>> behavior of mapping-insertion methods to optionally remove the first ("eldest")
>> entry. Neither of these behaviors conflicts with anything in SequencedMap.
> 
> It conflicts with the idea of the first element (or last element)
>    SequencedSet set = ...
>    var first = set.getFirst();
>    assertNotNull(first);
>    set.add("foo");
>    var first2 = set.getFirst();
>    assertEquals(first, first2);   // should always be true, right ?

(LinkedHashSet doesn't have a removeEldestEntry() method; that's only on 
LinkedHashMap. But let's consider the example to be rewritten as if it were about 
LinkedHashMap, or a SequencedSet built from the keySet of a LinkedHashMap.)

See draft specification here:

https://github.com/openjdk/jdk/pull/7387/files#diff-be823ac1fb09a9858a40bdd29359911e534f5d9d3079e69ed31a34e37f72c7a0

There is a definition of encounter order, but there is no specification of how the 
encounter order is established or how it's modified. That's left to implementations 
and subtypes.

This example 1) gets the first element, 2) adds another element, and 3) gets the 
first element again. Step 2 is a modification to the collection, so there's no basis 
for asserting that the element obtained in step 1 always equals the element obtained 
in step 3.

In particular, LinkedHashMap's "removeEldestEntry" feature says that add() 
potentially has additional side effects beyond adding the argument element, 
including of course removing the first element.

Also, in the example, if SequencedSet is a TreeSet<String> containing "x", then 
adding "foo" quite sensibly changes the first element between steps 1 and 3.

>>> - LinkedHashMap/LinkedHashSet are dinosaurs, there are more efficient
>>> implementations of the concepts of ordered set / ordered map both in term of
>>> memory footprint and runtime execution, so adding new interfaces without
>>> exploring new implementations using Valhalla value class and in relation with
>>> the Collection Literal JEP seems premature to me.
>>
>> LinkedHashMap and LinkedHashSet are in fact used fairly frequently. They're not
>> used
>> as much as HashMap, but they're used more than ArrayDeque or TreeMap. Presumably
>> this is because people find LinkedHashMap/Set useful and that the overhead
>> compared
>> to their non-linked counterparts is acceptable for the additional services they
>> provide.
>>
>> The performance and footprint of LinkedHashMap/Set are not impacted either way
>> by
>> the JEP, nor are any potential future performance improvements (including those
>> that
>> might arise because of Valhalla) precluded by the JEP.
> 
> I don't disagree with all you say above, i'm saying that with Valhalla, we need to explore implementations of HashMap based on open addressing to get better cache performance.
> So adding addFirst() to LinkedHashMap now, is a risk.

As the LinkedHashMap implementation stands today (prior to JEP 431) it needs to 
perform a variety of operations that affect the order of the elements. The 
addFirst() method is a new operation, but it's only a small amount of additional 
work, given that there are already other operations that operate on both ends.

In a hypothetical future open-addressed Map, there would need to be some additional 
data structure (likely an array?) that maintains the encounter order. This structure 
would need to support various element shifting and copying operations to maintain 
the ordering; consider what would need to happen with a get() operation on an 
access-ordered map. I don't see any problem with implementing an addFirst() 
operation on this structure.

> Also, addFirst on a sequenced collection is a dangerous method, exactly like List.get() is, depending on the implementation the worst case complexity can be either O(1) or O(n).
> I believe we will all live in a better place if we do not add new methods with such "complexity range".

Not the same at all. The problem with LinkedList.get(i) is that people put it in a 
for-loop over int indexes, which seems like it should be O(n), but as we know it's 
O(n^2). That occurs a lot more frequently than indexed add() or remove().

s'marks