RandomAccess Interface and List Heirarchy

[forax at univ-mlv.fr]

----- Mail original -----
> De: "Peter Levart" <peter.levart at gmail.com>
> À: "Remi Forax" <forax at univ-mlv.fr>, "Cyrus Vafadari" <cvafadari at gmail.com>
> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>
> Envoyé: Samedi 28 Septembre 2019 10:38:43
> Objet: Re: RandomAccess Interface and List Heirarchy

> On 9/25/19 12:15 PM, Remi Forax wrote:
>> that said, i believe we should deprecate LinkedList (and any other List
>> implementation that doesn't implement RandomAccess) because there are too much
>> code out there that suppose that list.get() is O(1).
> 
> Hi Remi,
> 
> Deprecating LinkedList as a whole is maybe to harsh. LinkedList is a
> List, but it is also the only JDK implementation of single-threaded
> linked Deque, which, although a retrofitted feature, is a perfectly
> fitted feature of LinkedList. That brings me to the question: Is it
> possible and how to deprecate only one aspect of a particular
> implementation - in this case the List interface of the LinkedList? In
> this concrete case, and also because it would be strange to have a class
> called LinkedList implementing only Deque interface, it may be an
> alternative to 1st create a replacement in the form of LinkedDeque
> implements Deque, and then deprecating the whole LinkedList.
> 
> As always there are pros and cons to a particular "solution":
> 
> 1. Do nothing
> pros:
> - no refactoring of old code needed
> cons:
> - performance problems continue as inexperienced programmers couple
> LinkedList with typical indexed accesses of List interface
> - hard discoverability of single-threaded "linked" Deque implementation
> continues - LinkedList is not a name that comes to mind when searching
> for Deque implementation - this is less of a problem nowadays as we have
> tools like Ctrl-H in IDEA, ...
> 
> 2a. Deprecate the List aspect of LinkedList and eventually remove the
> List interface from the LinkedList
> pros:
> - performance problems eventually solved
> - at least some of the usages of LinkedList would remain valid: Deque<T>
> d = new LinkedList<>();
> cons:
> - compatibility risk - all uses of LinkedList that assume it implements
> List interface will have to be refactored
> - hard discoverability of single-threaded "linked" Deque implementation
> continues - LinkedList is not a name that comes to mind
> 
> 2b. Deprecate the List aspect of LinkedList with not planned removal of
> the List interface from the LinkedList
> pros:
> - performance problems eventually solved
> - at least some of the usages of LinkedList would remain valid: Deque<T>
> d = new LinkedList<>(); not even warnings suppression would be needed
> - no immediate compatibility risk - only suppressing warnings may be
> needed in short term
> cons:
> - hard discoverability of single-threaded "linked" Deque implementation
> continues - LinkedList is not a name that comes to mind
> 
> 3. Create a replacement LinkedDeque implementation of Deque and
> deprecate LinkedList (with no planned removal)
> pros:
> - performance problems eventually solved as new code typically would
> refrain from using LinkedList for the List purpose and would start using
> LinkedDeque for the Deque purpose
> - no refactoring of old code needed (at least not in the near future)
> - better discoverability of single-threaded "linked" Deque implementation
> cons:
> - new type to learn
> - code using new type would not compile/run on old JDKs - adoption rate
> of new type would be slow
> 
> 
> 2b is most promising IMO. But is there an effective way to deprecate the
> List aspect of the LinkedList? What would be needed is a particular use
> of @Deprecated annotation that would cause usages like this:
> 
>     List<T> l = new LinkedList<>();
> 
> produce compile-time deprecation warnings, but usages like this:
> 
>    Deque<T> d = new LinkedList<>();
> 
> not produce warnings.
> 
> The 1st thing that comes to mind is adding a TYPE_USE to the list of
> @Target(s) of the @Deprecated annotation and then using it like this:
> 
> public class LinkedList<E>
>     extends AbstractSequentialList<E>
>     implements @Deprecated List<E>, Deque<E>, Cloneable,
> java.io.Serializable
> 
> 
> Would this make sense?

For 2b, you don't have to have a syntax for that, it can be one line of code in the compiler.
Introducing an exotic syntax for an exotic use case is generally not a good idea, it's better to solve it in an ad hoc way.

I don't think we need to find a replacement to LinkedList seen as a Deque given that perf wise it's always better to use an ArrayDeque instead.
But i may be wrong.

so i'm more for option 0, deprecate LinkedList, provide no replacement for LinkedList as a Deque.

> 
> 
> Regards, Peter

regards,
Rémi