8143850: retrofit ArrayDeque to implement List

Tue Jul 31 19:10:53 UTC 2018

Hi Alex,

I can do that for you ....

-Patrick

Am 31.07.2018 um 21:08 schrieb Alex Foster:
> Sure, I don't mind. I would have done that myself but I don't think I have access to upload to cr.openjdk.java.net.
>
>
> Alex
>
> ________________________________
> From: Stuart Marks <stuart.marks at oracle.com>
> Sent: July 31, 2018 2:40 PM
> To: Alex Foster
> Cc: core-libs-dev at openjdk.java.net
> Subject: Re: 8143850: retrofit ArrayDeque to implement List
>
>
> OK, great.
>
>
> It looks like a heavily modified version of ArrayDeque.java. This makes it a bit difficult to understand what the changes are. Would you mind if I rehosted this to cr.openjdk.java.net and generated a webrev for it?
>
>
> Thanks,
>
>
> s'marks
>
> On 7/28/18 11:05 PM, Alex Foster wrote:
>
> Hi,
>
>
> Here's my current proposal: https://pastebin.com/EABgwLYS
>
>
> Alex
>
>
> ________________________________
> From: Stuart Marks <stuart.marks at oracle.com><mailto:stuart.marks at oracle.com>
> Sent: July 28, 2018 8:11 PM
> To: Martin Buchholz; Alex Foster
> Cc: Doug Lea; core-libs-dev at openjdk.java.net<mailto:core-libs-dev at openjdk.java.net>
> Subject: Re: 8143850: retrofit ArrayDeque to implement List
>
> Hi, I finally got some time to get my head around this.
>
> Conceptually, I like the idea of a List that's stored in a circular array, like
> ArrayDeque. The best way to manifest this in the API isn't obvious though. I
> filed the bug as "retrofit ArrayDeque to implement List" but of course it
> doesn't have to be this way.
>
> I also think we want to reuse an existing implementation as much as possible.
> There's already too much duplication between ArrayList and ArrayDeque; we don't
> want a third similar implementation that will need to be maintained in parallel.
>
> To Martin's points:
>
> * Adding List-like methods to ArrayDeque without it implementing List is indeed
> odd, but not necessarily fatal. It does seem to raise the question "Isn't there
> a better way?" though.
>
> * I don't want to have to add null support if at all possible, for the reasons
> Martin mentioned. Also, it's an implementation and maintenance headache. Of
> course the implementations like ArrayList and HashMap are proof that it can be
> done. But each time HashMap has been enhanced significantly, there's been a bug
> tail where null checking was missed in certain cases.
>
> * Growth policy. The shared null array setup for ArrayList was added when we
> observed that a significant number of ArrayLists are created with the default
> constructor and then never populated. Allocating the backing array lazily
> resulted in a considerable space savings. I think this would be a good idea to
> do for ArrayDeque, but this is somewhat orthogonal to the current "retrofit
> List" discussion.
>
> * Regarding nestmates, I don't think the use of nestmates has any advantage or
> disadvantage over package-level access between top-level classes in the same
> package. I think we should decide what we want the API to look like first, and
> then figure out how to factor things so that we can get the code sharing and
> coupling that we want. We might not be forced into contorting the API in order
> to get better sharing/coupling, but let's wait to cross that bridge if we come
> to it.
>
> --
>
> Alex, I'm not sure where your current proposal stands. Have you sent an update
> since the head of the thread? If you had included something as an attachment, it
> has likely been stripped.
>
> Thanks,
>
> s'marks
>
>
>
>
>
> On 7/23/18 8:46 PM, Martin Buchholz wrote:
>> (As usual, I don't have enough time to devote to this at the moment)
>>
>> I sort of like the idea of adding all of those List methods to ArrayDeque, but
>> it's __weird__ for java code to do that, and remove(int) is a problem when you
>> have ArrayDeque<Integer>, so it will probably end up rejected.
>>
>> ---
>>
>> Similarly, the idea of an ArrayDeque subclass that accepts nulls will be
>> unpopular - null elements have fallen out of favor.
>>
>> While|Deque|implementations are not strictly required to prohibit the insertion
>> of null elements, they are strongly encouraged to do so. Users of
>> any|Deque|implementations that do allow null elements are strongly
>> encouraged/not/to take advantage of the ability to insert nulls. This is so
>> because|null|is used as a special return value by various methods to indicate
>> that the deque is empty.
>>
>> ---
>>
>> It makes some sense for ArrayDeque's growth policy to be very similar to
>> ArrayList's - that should be done as an independent change.  Are there any
>> lessons to be learned from ArrayList's experience?  Is the world filled with
>> empty ArrayDeques that could share a common backing array?
>>
>> ---
>>
>> I do like the idea of having ArrayDeque's List-implementing subclass be a
>> nestmate of ArrayDeque, to share implementation details and to help discovery
>> and naming.  I'm not thrilled with reusing "List" in ArrayDeque.List but I don't
>> have a great alternative to suggest.
>>
>>
>> On Mon, Jul 16, 2018 at 10:36 AM, Alex Foster <alexfoster at hotmail.ca<mailto:alexfoster at hotmail.ca>
>> <mailto:alexfoster at hotmail.ca>> wrote:
>>
>>     Hi again,
>>
>>     I updated ArrayDeque with your last idea (adding all list methods but not
>>     implementing List) and added a subclass ArrayDeque.List which overrides
>>     equals and hashcode and implements List. There is also a subclass
>>     ArrayDeque.WithNulls that accepts null elements. ArrayDeque has removeAt(int
>>     index) instead of remove(index) to avoid overloading remove(Object).
>>
>>     I also added shared empty arrays similar to Arraylist, and a reallocate
>>     method which can do the same things as trimToSize and ensure capacity in
>>     Arraylist. It also allows you to trim to a specific capacity other than the
>>     size or skip trimming if the capacity is within a specified distance of the
>>     target capacity.
>>
>>     Also the bulk add methods call collection.toArray, then check the array for
>>     illegal elements, then add the array, which means that a collection could
>>     keep the array it returns from toArray and modify it from another thread
>>     after it has been checked but before it has been added which could lead to
>>     illegal elements being added to the ArrayDeque. We could maybe avoid this by
>>     cloning the array or checking the elements after adding them but I'm not
>>     sure if it's worth it...
>>
>>     What do you think?
>>
>>     I also changed the WhiteBox test a bit:
>>
>>     --- a/test/jdk/java/util/ArrayDeque/WhiteBox.java
>>     +++ b/test/jdk/java/util/ArrayDeque/WhiteBox.java
>>     @@ -88,7 +88,10 @@
>>
>>           @Test
>>           public void defaultConstructor() {
>>     -        checkCapacity(new ArrayDeque(), 16);
>>     +        ArrayDeque d = new ArrayDeque();
>>     +        d.add(new Object());
>>     +        d.clear();
>>     +        checkCapacity(d, 16);
>>           }
>>
>>           @Test
>>     @@ -131,7 +134,7 @@
>>                   if (rnd.nextBoolean()) d.add(99);
>>                   ArrayDeque clone = serialClone(d);
>>                   assertInvariants(clone);
>>     -            assertNotSame(elements(d), elements(clone));
>>     +            assertTrue(d.isEmpty() || elements(d) != elements(clone));
>>                   assertEquals(d, clone);
>>               }
>>           }
>>
>>     Alex
>>
>>