8143850: retrofit ArrayDeque to implement List
Hi, <https://bugs.openjdk.java.net/browse/JDK-8143850> <https://bugs.openjdk.java.net/browse/JDK-8143850> I did this awhile ago and I'd like to submit it. I believe it needs to be a new class because it changes the behavior of equals and hashcode. My implementation is based off of the java 8 version I think and it has changed a lot since then, I could add some of the improvements if you want. Also I'm not sure if we should make a new Deque + List interface for it to implement or not. Code: https://pastebin.com/suXMfMZW Bug: https://bugs.openjdk.java.net/browse/JDK-8143850 Previous discussion:<https://bugs.openjdk.java.net/browse/JDK-8143850> <https://bugs.openjdk.java.net/browse/JDK-8143850>http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-February/024938.html <https://bugs.openjdk.java.net/browse/JDK-8143850>Alex<http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-February/024938.html>
Thanks, Alex. This has been on my todo list for a long time and I'm more overcommitted than ever. The difficult part is designing of the interface, but then there are many tests to write... I sort of liked ArrayDeque.asList() because at least then the API surface to be added is small. ArrayDeque has changed a little between jdk8 and now. Almost all the code could be shared with the List-implementing class - we don't want to introduce (too much) duplication. On Tue, Jun 26, 2018 at 12:04 PM, Alex Foster <alexfoster@hotmail.ca> wrote:
Hi, <https://bugs.openjdk.java.net/browse/JDK-8143850>
<https://bugs.openjdk.java.net/browse/JDK-8143850>
I did this awhile ago and I'd like to submit it.
I believe it needs to be a new class because it changes the behavior of equals and hashcode.
My implementation is based off of the java 8 version I think and it has changed a lot since then, I could add some of the improvements if you want.
Also I'm not sure if we should make a new Deque + List interface for it to implement or not.
Code:
Bug:
https://bugs.openjdk.java.net/browse/JDK-8143850
Previous discussion:<https://bugs.openjdk.java.net/browse/JDK-8143850>
<https://bugs.openjdk.java.net/browse/JDK-8143850>http:// mail.openjdk.java.net/pipermail/core-libs-dev/2014-February/024938.html
<https://bugs.openjdk.java.net/browse/JDK-8143850>Alex<ht tp://mail.openjdk.java.net/pipermail/core-libs-dev/2014- February/024938.html>
Another question is whether or not it should allow null elements. ArrayDeque currently doesn't but I think it would be useful to support them, which makes having an asList() view or sharing code harder.
On Thu, Jun 28, 2018 at 11:42 PM, Alex Foster <alexfoster@hotmail.ca> wrote:
Another question is whether or not it should allow null elements. ArrayDeque currently doesn't but I think it would be useful to support them, which makes having an asList() view or sharing code harder.
JDK has moved away from null elements in collections. We want the new collection to implement both List and Deque, and the spec says """ While Deque implementations are not strictly required to prohibit the insertion of null elements, they are strongly encouraged to do so. Users of any Dequeimplementations 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. """ --- Another idea is to simply add all of those List-like methods to ArrayDeque without actually implementing List. Then we have maximal efficiency (no wrappers), we don't have to come up with a new name for the class, and a user who wants a genuine 100% List view can do subList(deq, 0, deq.size()). In the past we've been reluctant to do such a strange thing ...
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
(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@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
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@hotmail.ca <mailto:alexfoster@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
Hi, Here's my current proposal: https://pastebin.com/EABgwLYS Alex ________________________________ From: Stuart Marks <stuart.marks@oracle.com> Sent: July 28, 2018 8:11 PM To: Martin Buchholz; Alex Foster Cc: Doug Lea; core-libs-dev@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@hotmail.ca <mailto:alexfoster@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
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 <https://pastebin.com/EABgwLYS>
Alex
-------------------------------------------------------------------------------- *From:* Stuart Marks <stuart.marks@oracle.com> *Sent:* July 28, 2018 8:11 PM *To:* Martin Buchholz; Alex Foster *Cc:* Doug Lea; core-libs-dev@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@hotmail.ca <mailto:alexfoster@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
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@oracle.com> Sent: July 31, 2018 2:40 PM To: Alex Foster Cc: core-libs-dev@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@oracle.com><mailto:stuart.marks@oracle.com> Sent: July 28, 2018 8:11 PM To: Martin Buchholz; Alex Foster Cc: Doug Lea; core-libs-dev@openjdk.java.net<mailto:core-libs-dev@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@hotmail.ca<mailto:alexfoster@hotmail.ca> <mailto:alexfoster@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
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@oracle.com> Sent: July 31, 2018 2:40 PM To: Alex Foster Cc: core-libs-dev@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@oracle.com><mailto:stuart.marks@oracle.com> Sent: July 28, 2018 8:11 PM To: Martin Buchholz; Alex Foster Cc: Doug Lea; core-libs-dev@openjdk.java.net<mailto:core-libs-dev@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@hotmail.ca<mailto:alexfoster@hotmail.ca> <mailto:alexfoster@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
Am 31.07.2018 um 21:10 schrieb Patrick Reinhart:
Hi Alex,
I can do that for you ....
-Patrick
Here it is: http://cr.openjdk.java.net/~reinhapa/reviews/8143850/webrev -Patrick
Thanks, Patrick! This is very helpful. Alex, others, (Meta: I've been at JVMLS and the OpenJDK Committers' Workshop all week, and I'm on vacation next week, so I don't have much time to discuss this right now. However, I am interested in moving this forward.) OK, so the API in this webrev essentially does a combination of the following: 1. Adds some List methods to ArrayDeque without having it implement List; and 2. Adds public ArrayDeque.List implementation of List as an AD subclass. There are a variety of alternative API approaches that I think we should consider. Among them: 3. Add a List *view* of an ArrayDeque instance, e.g. returned by an asList() method. (I believe Martin has suggested this.) 4. Add a new top-level List implementation that is a subclass of ArrayDeque, that thus implements both List and Deque interfaces. 5. Same as 4, a top level class implementing List and Deque, but which contains an ArrayDeque instead of subclassing ArrayDeque. 6. Modify ArrayDeque to implement List, including changing the behavior of equals() and hashCode(). There are a bunch of tradeoffs among these alternatives that I don't have time to discuss right now, but they deserve discussion. I may also have missed some variations. Among the criteria for evaluation are 1) implementation sharing; 2) API footprint; 3) compatibility. (And also probably others.) A couple other points: * I'd like to set aside null support. We've been discouraging nulls in collections for years, so allowing null in a (conceptually) new collection sounds like a step in the wrong direction. * Using an array sentinel to indicate an empty collection with default size, like ArrayList does, is a fine idea, but I think it complicates the discussion and the webrev. I'd suggest that it be factored out and considered separately. As I've said previously, the main thing to decide is what we want the API to look like. A discussion of the pros and cons of the various alternatives I listed above (and others I might have missed) is therefore called for. I can discuss these further after I return, but meanwhile, if anyone has any thoughts in the tradeoffs here, please speak up. Oh, and of course, thanks Alex for putting work into this proposal. s'marks On 7/31/18 12:21 PM, Patrick Reinhart wrote:
Am 31.07.2018 um 21:10 schrieb Patrick Reinhart:
Hi Alex,
I can do that for you ....
-Patrick
Here it is:
http://cr.openjdk.java.net/~reinhapa/reviews/8143850/webrev
-Patrick
Hi all, On 08/04/2018 01:51 AM, Stuart Marks wrote:
Thanks, Patrick! This is very helpful.
Alex, others,
(Meta: I've been at JVMLS and the OpenJDK Committers' Workshop all week, and I'm on vacation next week, so I don't have much time to discuss this right now. However, I am interested in moving this forward.)
OK, so the API in this webrev essentially does a combination of the following:
1. Adds some List methods to ArrayDeque without having it implement List; and
2. Adds public ArrayDeque.List implementation of List as an AD subclass.
There are a variety of alternative API approaches that I think we should consider. Among them:
3. Add a List *view* of an ArrayDeque instance, e.g. returned by an asList() method. (I believe Martin has suggested this.)
4. Add a new top-level List implementation that is a subclass of ArrayDeque, that thus implements both List and Deque interfaces.
5. Same as 4, a top level class implementing List and Deque, but which contains an ArrayDeque instead of subclassing ArrayDeque.
6. Modify ArrayDeque to implement List, including changing the behavior of equals() and hashCode().
There are a bunch of tradeoffs among these alternatives that I don't have time to discuss right now, but they deserve discussion. I may also have missed some variations. Among the criteria for evaluation are 1) implementation sharing; 2) API footprint; 3) compatibility. (And also probably others.)
A couple other points:
* I'd like to set aside null support. We've been discouraging nulls in collections for years, so allowing null in a (conceptually) new collection sounds like a step in the wrong direction.
* Using an array sentinel to indicate an empty collection with default size, like ArrayList does, is a fine idea, but I think it complicates the discussion and the webrev. I'd suggest that it be factored out and considered separately.
As I've said previously, the main thing to decide is what we want the API to look like. A discussion of the pros and cons of the various alternatives I listed above (and others I might have missed) is therefore called for. I can discuss these further after I return, but meanwhile, if anyone has any thoughts in the tradeoffs here, please speak up.
Oh, and of course, thanks Alex for putting work into this proposal.
s'marks
I'm wondering if type inheritance here is a desired property. There are several past "mistakes" that don't play quite well and we have to live with like: Hashtable/Properties, java.util.Date/java.sql.Date | java.sql.Time | java.sql.Timestamp. Creating a subclass of ArrayDeque that implements List might be a compatibility risk that is not much smaller than simply adding List interface to ArrayDeque itself. Sure if the creation/lifecycle of ArrayDeque[.List] instance is contained in the controlled way, the risk is minimized, but if the instance escapes across library boundary, it doesn't matter if List is implemented by a subclass or the ArrayDeque itself. Code using ArrayDeque type might reasonably assume there is a single implementation that behaves in the way it always did. There's an example in existing Java API that allows code re-use but doesn't expose type inheritance: package-private AbstractStringBuilder with public subclasses StringBuffer and StringBuilder. This is similar from API standpoint to Stuart's option #5, but might allow greater code re-use (less boilerplate as there would be no delegation code) and of course would be more space and time efficient. What do you think? Regards, Peter
On 7/31/18 12:21 PM, Patrick Reinhart wrote:
Am 31.07.2018 um 21:10 schrieb Patrick Reinhart:
Hi Alex,
I can do that for you ....
-Patrick
Here it is:
http://cr.openjdk.java.net/~reinhapa/reviews/8143850/webrev
-Patrick
Hi, Compare with sun.awt.util.IdentityLinkedList.java; not likely to be exactly what you are looking for but it is an implementation with similar features. $.02, Roger On 8/4/18 4:11 AM, Peter Levart wrote:
Hi all,
On 08/04/2018 01:51 AM, Stuart Marks wrote:
Thanks, Patrick! This is very helpful.
Alex, others,
(Meta: I've been at JVMLS and the OpenJDK Committers' Workshop all week, and I'm on vacation next week, so I don't have much time to discuss this right now. However, I am interested in moving this forward.)
OK, so the API in this webrev essentially does a combination of the following:
1. Adds some List methods to ArrayDeque without having it implement List; and
2. Adds public ArrayDeque.List implementation of List as an AD subclass.
There are a variety of alternative API approaches that I think we should consider. Among them:
3. Add a List *view* of an ArrayDeque instance, e.g. returned by an asList() method. (I believe Martin has suggested this.)
4. Add a new top-level List implementation that is a subclass of ArrayDeque, that thus implements both List and Deque interfaces.
5. Same as 4, a top level class implementing List and Deque, but which contains an ArrayDeque instead of subclassing ArrayDeque.
6. Modify ArrayDeque to implement List, including changing the behavior of equals() and hashCode().
There are a bunch of tradeoffs among these alternatives that I don't have time to discuss right now, but they deserve discussion. I may also have missed some variations. Among the criteria for evaluation are 1) implementation sharing; 2) API footprint; 3) compatibility. (And also probably others.)
A couple other points:
* I'd like to set aside null support. We've been discouraging nulls in collections for years, so allowing null in a (conceptually) new collection sounds like a step in the wrong direction.
* Using an array sentinel to indicate an empty collection with default size, like ArrayList does, is a fine idea, but I think it complicates the discussion and the webrev. I'd suggest that it be factored out and considered separately.
As I've said previously, the main thing to decide is what we want the API to look like. A discussion of the pros and cons of the various alternatives I listed above (and others I might have missed) is therefore called for. I can discuss these further after I return, but meanwhile, if anyone has any thoughts in the tradeoffs here, please speak up.
Oh, and of course, thanks Alex for putting work into this proposal.
s'marks
I'm wondering if type inheritance here is a desired property. There are several past "mistakes" that don't play quite well and we have to live with like: Hashtable/Properties, java.util.Date/java.sql.Date | java.sql.Time | java.sql.Timestamp.
Creating a subclass of ArrayDeque that implements List might be a compatibility risk that is not much smaller than simply adding List interface to ArrayDeque itself. Sure if the creation/lifecycle of ArrayDeque[.List] instance is contained in the controlled way, the risk is minimized, but if the instance escapes across library boundary, it doesn't matter if List is implemented by a subclass or the ArrayDeque itself. Code using ArrayDeque type might reasonably assume there is a single implementation that behaves in the way it always did.
There's an example in existing Java API that allows code re-use but doesn't expose type inheritance: package-private AbstractStringBuilder with public subclasses StringBuffer and StringBuilder.
This is similar from API standpoint to Stuart's option #5, but might allow greater code re-use (less boilerplate as there would be no delegation code) and of course would be more space and time efficient.
What do you think?
Regards, Peter
On 7/31/18 12:21 PM, Patrick Reinhart wrote:
Am 31.07.2018 um 21:10 schrieb Patrick Reinhart:
Hi Alex,
I can do that for you ....
-Patrick
Here it is:
http://cr.openjdk.java.net/~reinhapa/reviews/8143850/webrev
-Patrick
participants (6)
-
Alex Foster
-
Martin Buchholz
-
Patrick Reinhart
-
Peter Levart
-
Roger Riggs
-
Stuart Marks