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

[forax at univ-mlv.fr]

----- Original Message -----
> From: "Stuart Marks" <stuart.marks at oracle.com>
> To: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "core-libs-dev" <core-libs-dev at openjdk.org>
> Sent: Saturday, October 29, 2022 2:16:06 AM
> Subject: Re: [External] : Re: New candidate JEP: 431: Sequenced Collections

[...]

> 
> 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.

All collections have an order the one of their iterator.

[...]

> 
> 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.

How this is different to saying the encounter order is the one of the iterator ?

> 
> 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.

The example shows that add() does not add() at the end of a SequencedSet, the order defined SequencedSet is at best surprising, it's all i'm saying.

That why i think SequencedCollection as an interface does not worth the trouble because you can not offer more guarantees than saying the order is the order of the iterator.
But at least if the operations are defined on java.util.Collection, people will not fall into the trap of thinking that "sequenced" means that add() adds at the end of the sequence.

> 
>>>> - 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.

You do not need any shifting if either you use a tombstone in the array that maintain the encounter order (you can clean them at the same time you rehash) or if you define that removing an entry replace it by the last entry (like Zig let you do).

> 
>> 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().

You think that people will never loop on addFirst() ? This is exactly the same issue.

> 
> s'marks

Rémi