Re: RandomAccess Interface and List Heirarchy
Thanks for the thoughtful responses. I think my issue with Runtime annotation is that it's just that -- Runtime. Compiletime is highly preferable. I also understand the challenges listed by Peter, and the original intended use of RandomAccess as explained by Remi. I'd like to propose another solution: A new interface that will be similar to "RandomAccess", and be properly in the hierarchy, very similar to RandomAccess but actually inheriting from List. This way, there is no new syntax, no deprecation issues. Users could then (at compile time), require that a function is passed an "IndexableList" (or whatever it ends up being called). Remi points to an issue where every implementer of list will need to declare its type (e.g. "RandomImmutableList"), but I'm not sure I'm convinced by this argument: Guava's ImmutableList, for example, already implements RandomAccess! For Collections' UnmofidfiableList, of course, just returns a view of the generic list it's used with, so there's no issue here. Maybe I misunderstood, but I'm not sure the fanout of interface/class permutations is not really an issue. Thoughts? On Mon, Sep 30, 2019 at 5:41 AM David Lloyd wrote: > On Sat, Sep 28, 2019 at 3:39 AM Peter Levart > wrote: > > > > 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. > > Surely ArrayDeque is almost universally superior to LinkedList for > this use, in the same way that ArrayList has been shown to be almost > universally superior to LinkedList for list use cases? > > See also > https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java > > The salient point being that in most cases the O(1) of LinkedList is > effectively slower than the O(n) of Array*. > > -- > - DML > >
Re: RandomAccess Interface and List Heirarchy
On Sat, Sep 28, 2019 at 3:39 AM Peter Levart wrote: > > 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. Surely ArrayDeque is almost universally superior to LinkedList for this use, in the same way that ArrayList has been shown to be almost universally superior to LinkedList for list use cases? See also https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java The salient point being that in most cases the O(1) of LinkedList is effectively slower than the O(n) of Array*. -- - DML
Re: RandomAccess Interface and List Heirarchy
- Mail original - > De: "Peter Levart" > À: "Remi Forax" , "Cyrus Vafadari" > Cc: "core-libs-dev" > 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 > 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 > 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 l = new LinkedList<>(); > > produce compile-time deprecation warnings, but usages like this: > > Deque 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 > extends AbstractSequentialList > implements @Deprecated List, Deque, 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
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 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 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 l = new LinkedList<>(); produce compile-time deprecation warnings, but usages like this: Deque 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 extends AbstractSequentialList implements @Deprecated List, Deque, Cloneable, java.io.Serializable Would this make sense? Regards, Peter
Re: RandomAccess Interface and List Heirarchy
Hi Cyrus, as the javadoc says RandomAccess is a marker interface, an interface used at runtime to indicate if the implementation provides a fast random access operation or not. "marker interface" is the precursor of a runtime visible annotation. RandomAccess was introduce in 1.4 while annotations were introduced later in 1.5. implementing RandomAccess is equivalent of adding a bit on all implementations of List, so casting an instance to RandomAccess is not how you should using it. More generally, the idea of the collection API is that instead of having a RandomAccessList, a MutableList, an ImmutableList, a RandomImmutableList, etc you have only one type java.util.List and if you want to know more either you do a instanceof check, or call a method that throws UnsuportedOperationException or use a method of the API that does the runtime checks for you, like by example List.copyOf(). 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). Rémi - Mail original - > De: "Cyrus Vafadari" > À: "core-libs-dev" > Envoyé: Mercredi 25 Septembre 2019 05:19:49 > Objet: RandomAccess Interface and List Heirarchy > Hello all, > > *TLDR: Why doesn't RandomAccess interface extend List?* > > I'm maintaining a framework that lets developers build plugins, and > developers implement a `put(List thingList)` in their plugins. > However, I want to guarantee to the implementer that their List will > support RandomAccess. I see Java does support a syntax for declaring that > the argument should implement both List and RandomAccess using the "&" > operator, and I could declare my own interface that extends both, but I am > surprised that RandomAccess itself does not extend List and appear in the > List hierarchy. According to the docs, it only applies to List > implementations anyway, and we use `instanceof` extensively in the code to > bifurcate how we handle both cases. It seems more natural to me for > RandomAccess to extend List, so that I can let my implementer know > explicitly they can rely on RandomAccess. > > I am happy to give more details on my scenario, and very excited to learn > more why this decision was made, and if there is an aspect I am missing or > if improvements could be made! > > Best wishes, > > Cyrus
RandomAccess Interface and List Heirarchy
Hello all, *TLDR: Why doesn't RandomAccess interface extend List?* I'm maintaining a framework that lets developers build plugins, and developers implement a `put(List thingList)` in their plugins. However, I want to guarantee to the implementer that their List will support RandomAccess. I see Java does support a syntax for declaring that the argument should implement both List and RandomAccess using the "&" operator, and I could declare my own interface that extends both, but I am surprised that RandomAccess itself does not extend List and appear in the List hierarchy. According to the docs, it only applies to List implementations anyway, and we use `instanceof` extensively in the code to bifurcate how we handle both cases. It seems more natural to me for RandomAccess to extend List, so that I can let my implementer know explicitly they can rely on RandomAccess. I am happy to give more details on my scenario, and very excited to learn more why this decision was made, and if there is an aspect I am missing or if improvements could be made! Best wishes, Cyrus
