Re: classpath ./ChangeLog java/util/AbstractList.ja...
Eric Blake wrote: > > I dunno - I'm hesitant to add unspecified public methods to public > classes, even though as you point out they will not destroy binary > compatibility. I've always been under the impression that it's absolutely fine to add an overridden method for a method that's declared in a superclass; I think of the fact that Sun does or doesn't do this in certain situations as an implementation detail that's mistakenly published in the javadoc. It's guaranteed to not break source or binary compatibility and it's exactly what object orientation is all about. Another Collections case that has a similar potential optimization is LinkedList.subList(); the iterator() method on the sublist class would normally be inherited from AbstractList, which calls list.iterator(startIndex). On a linked list, iterator(n) is O(n). But if the LinkedList sublist were to store the starting and ending Entry objects, you can make this operation O(1). Since creating an iterator is a pre-requisite for many many other operations, I think making such an optimization for LinkedList sublists is worth doing. Last I checked (which admittedly was at 1.2 release time) Sun didn't do this. My old Classpath LinkedList implementation did, but that was vaporized by the libgcj merge (and no great loss, because in most other ways it sucked). Stuart. ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
Re: classpath ./ChangeLog java/util/AbstractList.ja...
Eric Blake wrote: >Bryce McKinlay wrote: > >>I also looked at your implementations of removeAll/retainAll in Vector >>-- nice. But don't you think its odd that there would be optimized >>implementations in Vector but not ArrayList? I wonder if we should put >>those in ArrayList as well. In the past I have avoided including any >>public methods that wern't part of the Javadoc spec, but that was more >>to help ensure that the implementation worked similarly to Sun's rather >>than for any real correctness reasons, since of course adding extra >>virtual methods should not effect binary compatibility in any way in >>Java. What do you think? >> > >I dunno - I'm hesitant to add unspecified public methods to public >classes, even though as you point out they will not destroy binary >compatibility. > >I think Sun didn't notice the possibility for my optimization. I guess >Vector has removeAll when ArrayList doesn't simply because Vector needs >to be synchronized. Which is odd, because Sun didn't allow for iterator >or listIterator in Vector, so I was unable to create iterators which >were properly synchronized. Maybe we could use package-private hooks to >work around these spec shortcomings while still maintaining the public >API: > There is no need to synchronize the Vector iterator. Its made pretty clear in the docs that iterators should never be shared among different threads (hence the ConcurrentModificationException), and of course any operations you actually perform on the iterator are still synchronized internally against the underlying Vector. Note also that there is no Collections.synchronizedIterator - it doesn't make sense because even if it were synchronized it still wouldn't be thread-safe. >It was a little easier working with the nested classes in Collections. >For example, I added methods like Collections.EmptySet.toArray, which >Sun did not implement > Actually I think these particular "optimizations" are very dubious!! ;-). We should definatly try to optimize when the default behaviour can take quadratic time etc, but in this case I think the methods are not performance critical and don't justify the extra code. Your comment says that they "provide a performance advantage by not allocating unnecessary iterators in AbstractList", but I don't see why an iterator ever needs to be allocated. Why not just have a single, static empty iterator like before? regards Bryce. ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
Re: classpath ./ChangeLog java/util/AbstractList.ja...
Bryce McKinlay wrote: > I also looked at your implementations of removeAll/retainAll in Vector > -- nice. But don't you think its odd that there would be optimized > implementations in Vector but not ArrayList? I wonder if we should put > those in ArrayList as well. In the past I have avoided including any > public methods that wern't part of the Javadoc spec, but that was more > to help ensure that the implementation worked similarly to Sun's rather > than for any real correctness reasons, since of course adding extra > virtual methods should not effect binary compatibility in any way in > Java. What do you think? I dunno - I'm hesitant to add unspecified public methods to public classes, even though as you point out they will not destroy binary compatibility. I think Sun didn't notice the possibility for my optimization. I guess Vector has removeAll when ArrayList doesn't simply because Vector needs to be synchronized. Which is odd, because Sun didn't allow for iterator or listIterator in Vector, so I was unable to create iterators which were properly synchronized. Maybe we could use package-private hooks to work around these spec shortcomings while still maintaining the public API: AbstractList.java: public boolean removeAll(Collection c) { return internalRemoveAll(c); } boolean internalRemoveAll(Collection c) { // existing implementation } public Iterator iterator() { return internalIterator(); } Iterator internalIterator() { // existing implementation } ArrayList.java: boolean internalRemoveAll(Collection c) { // optimized implementation } Vector.java: Iterator internalIterator() { // synchronized implementation } It was a little easier working with the nested classes in Collections. For example, I added methods like Collections.EmptySet.toArray, which Sun did not implement (of course, I tested this using only java.lang.reflect, and not by decompiling or looking at JDK source). But in those nested classes, I did not feel guilty adding public methods because the entire class is private and undocumented except for its serializable nature. -- This signature intentionally left boring. Eric Blake [EMAIL PROTECTED] BYU student, free software programmer ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
Re: classpath ./ChangeLog java/util/AbstractList.ja...
Eric Blake wrote: >Agreed, and I just committed a patch. > >Thanks for the feedback - it's nice to know my work has an audience. > You're welcome! I also looked at your implementations of removeAll/retainAll in Vector -- nice. But don't you think its odd that there would be optimized implementations in Vector but not ArrayList? I wonder if we should put those in ArrayList as well. In the past I have avoided including any public methods that wern't part of the Javadoc spec, but that was more to help ensure that the implementation worked similarly to Sun's rather than for any real correctness reasons, since of course adding extra virtual methods should not effect binary compatibility in any way in Java. What do you think? regards Bryce. ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
Re: classpath ./ChangeLog java/util/AbstractList.ja...
Agreed, and I just committed a patch. Thanks for the feedback - it's nice to know my work has an audience. Bryce McKinlay wrote: > > Hi Eric, > > Thanks!! > > > (rangeExclusive, rangeInclusive): Add common methods for bounds > > check. > > > > These should really be called checkBoundsInclusive and > checkBoundsExclusive for consistency with AbstractList (plus, it makes > it clearer what they actually do when reading the code...) > -- This signature intentionally left boring. Eric Blake [EMAIL PROTECTED] BYU student, free software programmer ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath