[gwt-contrib] Re: Lightweight collections. ImmutableArray and MutableArray.freeze() implementation. (issue291801)
http://gwt-code-reviews.appspot.com/291801/show -- http://groups.google.com/group/Google-Web-Toolkit-Contributors To unsubscribe, reply using remove me as the subject.
[gwt-contrib] Re: Lightweight collections. ImmutableArray and MutableArray.freeze() implementation. (issue291801)
http://gwt-code-reviews.appspot.com/291801/diff/4001/5003 File bikeshed/src/com/google/gwt/collections/ImmutableArrayEmptyImpl.java (right): http://gwt-code-reviews.appspot.com/291801/diff/4001/5003#newcode27 bikeshed/src/com/google/gwt/collections/ImmutableArrayEmptyImpl.java:27: Assertions.assertIndexInRange(index, 0, 0); On 2010/03/30 20:25:29, fabbott wrote: this will always fail... is it worth some more specific assertion? Or at least a syntax sugar that reduces to the same, but is clear at this call site that 0 is actually excluded? Done. http://gwt-code-reviews.appspot.com/291801/diff/4001/5004 File bikeshed/src/com/google/gwt/collections/ImmutableArrayImpl.java (right): http://gwt-code-reviews.appspot.com/291801/diff/4001/5004#newcode25 bikeshed/src/com/google/gwt/collections/ImmutableArrayImpl.java:25: private final E[] elems; On 2010/03/30 20:25:29, fabbott wrote: you might consider making this default visibility, to test that we don't copy, since that's the point to some of the hoops we're doing (see comment in ImmutableArrayTest). Done. http://gwt-code-reviews.appspot.com/291801/diff/4001/5004#newcode28 bikeshed/src/com/google/gwt/collections/ImmutableArrayImpl.java:28: Assertions.assertNotNull(elems); On 2010/03/30 20:25:29, fabbott wrote: do you also want to assert that elem.length 0? Not really. length == 0 is OK. It is just that we chose to use ImmutableArrayEmptyImpl for our implementation. Should I also add test cases for the ImmutableX classes? http://gwt-code-reviews.appspot.com/291801/diff/4001/5005 File bikeshed/src/com/google/gwt/collections/MutableArray.java (right): http://gwt-code-reviews.appspot.com/291801/diff/4001/5005#newcode60 bikeshed/src/com/google/gwt/collections/MutableArray.java:60: elems = null; On 2010/03/30 20:25:29, fabbott wrote: Huh?! Can't I keep using my existing MutableArray, post-freeze, so long as I don't change it?! Doesn't this line zero it out (but leave it frozen)? Ah, yes. I guess this was too extreme. The intention was to discourage using MutableArray after freezing. Using ImmutableArray was the way to access in that case. But now that you mention it I can see situations where that may be cumbersome. Removed clearing the backing array. http://gwt-code-reviews.appspot.com/291801/diff/4001/5006 File bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java (right): http://gwt-code-reviews.appspot.com/291801/diff/4001/5006#newcode58 bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java:58: On 2010/03/30 20:25:29, fabbott wrote: I think that if you test ma.size() here, you get an unexpected 0 rather than 2... Done. http://gwt-code-reviews.appspot.com/291801/diff/4001/5006#newcode60 bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java:60: ma.add(1); On 2010/03/30 20:25:29, fabbott wrote: I like 0, 1, many testing in general, but I'm not sure the 1 case helps here. Done. http://gwt-code-reviews.appspot.com/291801/diff/4001/5006#newcode158 bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java:158: On 2010/03/30 20:25:29, fabbott wrote: Something I'd like to test, but we don't have visibility to here, is that we didn't copy... i.e. that ia1.elems === ia2.elems === ma.elems. Done. http://gwt-code-reviews.appspot.com/291801/show -- http://groups.google.com/group/Google-Web-Toolkit-Contributors To unsubscribe, reply using remove me as the subject.
[gwt-contrib] Re: Lightweight collections. ImmutableArray and MutableArray.freeze() implementation. (issue291801)
LGTM http://gwt-code-reviews.appspot.com/291801/diff/1/6 File bikeshed/src/com/google/gwt/collections/MutableArray.java (right): http://gwt-code-reviews.appspot.com/291801/diff/1/6#newcode49 bikeshed/src/com/google/gwt/collections/MutableArray.java:49: * Creates and immutable array based on this one and resets the contents of and - an http://gwt-code-reviews.appspot.com/291801/diff/1/6#newcode97 bikeshed/src/com/google/gwt/collections/MutableArray.java:97: E[] newElems = (E[]) new Object[oldLen + 1]; Perhaps this won't matter once this is implemented in JSNI, but it seems extremely inefficient to reallocate the backing array for every insert and remove. http://gwt-code-reviews.appspot.com/291801/show -- http://groups.google.com/group/Google-Web-Toolkit-Contributors To unsubscribe from this group, send email to google-web-toolkit-contributors+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
[gwt-contrib] Re: Lightweight collections. ImmutableArray and MutableArray.freeze() implementation. (issue291801)
http://gwt-code-reviews.appspot.com/291801/show -- http://groups.google.com/group/Google-Web-Toolkit-Contributors To unsubscribe from this group, send email to google-web-toolkit-contributors+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
[gwt-contrib] Re: Lightweight collections. ImmutableArray and MutableArray.freeze() implementation. (issue291801)
http://gwt-code-reviews.appspot.com/291801/diff/1/6 File bikeshed/src/com/google/gwt/collections/MutableArray.java (right): http://gwt-code-reviews.appspot.com/291801/diff/1/6#newcode49 bikeshed/src/com/google/gwt/collections/MutableArray.java:49: * Creates and immutable array based on this one and resets the contents of On 2010/03/30 16:24:31, Dan Rice wrote: and - an Done. http://gwt-code-reviews.appspot.com/291801/diff/1/6#newcode97 bikeshed/src/com/google/gwt/collections/MutableArray.java:97: E[] newElems = (E[]) new Object[oldLen + 1]; Yes, it is inefficient. I agreed with Bruce writing a simple JRE implementation rather than an optimal one. Using a backing array larger than the actual content (as in ArrayList) we could improve to sub-linear amortized time for add, but we cannot fix inserts or removes (other than removals at the end, which would have constant cost). The trade-off would be wasted space in the form of bigger than necessary backing arrays. I guess we chose the simpler poison. It occurs to me as an option to add a method to grow the array to a chosen length. So something like // N fruits, O(N^2) ma.add(pear); ... ma.add(apple); Becomes // N fruits, O(N) ma.grow(N, null); ma.set(0,pear); ... ma.set(N-1,apple); On 2010/03/30 16:24:31, Dan Rice wrote: Perhaps this won't matter once this is implemented in JSNI, but it seems extremely inefficient to reallocate the backing array for every insert and remove. http://gwt-code-reviews.appspot.com/291801/show -- http://groups.google.com/group/Google-Web-Toolkit-Contributors To unsubscribe from this group, send email to google-web-toolkit-contributors+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
[gwt-contrib] Re: Lightweight collections. ImmutableArray and MutableArray.freeze() implementation. (issue291801)
http://gwt-code-reviews.appspot.com/291801/diff/1/6 File bikeshed/src/com/google/gwt/collections/MutableArray.java (right): http://gwt-code-reviews.appspot.com/291801/diff/1/6#newcode97 bikeshed/src/com/google/gwt/collections/MutableArray.java:97: E[] newElems = (E[]) new Object[oldLen + 1]; Inserts and removes still get faster because they no longer have to allocate (most of the time). They still have to copy, of course. Also, removal of the last element is a not uncommon thing to do (consider implementing a stack using a list). A more standard name for grow() would be setCapacity(). http://gwt-code-reviews.appspot.com/291801/show -- http://groups.google.com/group/Google-Web-Toolkit-Contributors To unsubscribe from this group, send email to google-web-toolkit-contributors+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
[gwt-contrib] Re: Lightweight collections. ImmutableArray and MutableArray.freeze() implementation. (issue291801)
http://gwt-code-reviews.appspot.com/291801/diff/1/6 File bikeshed/src/com/google/gwt/collections/MutableArray.java (right): http://gwt-code-reviews.appspot.com/291801/diff/1/6#newcode97 bikeshed/src/com/google/gwt/collections/MutableArray.java:97: E[] newElems = (E[]) new Object[oldLen + 1]; On 2010/03/30 19:56:49, Dan Rice wrote: Inserts and removes still get faster because they no longer have to allocate (most of the time). They still have to copy, of course. Also, removal of the last element is a not uncommon thing to do (consider implementing a stack using a list). Certainly. Actually may be that is an issue. This implementation is one of an array. But the presence of an add() method can give the impression of providing some list semantics. In reality it provides a poor list behavior. But on the other hand the JSNI add implementation will have different costs. Add is fairly cheap in Javascript, isn't it? A more standard name for grow() would be setCapacity(). ... and it would truncate if the size is smaller. Sounds good to me. http://gwt-code-reviews.appspot.com/291801/show -- http://groups.google.com/group/Google-Web-Toolkit-Contributors To unsubscribe from this group, send email to google-web-toolkit-contributors+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
[gwt-contrib] Re: Lightweight collections. ImmutableArray and MutableArray.freeze() implementation. (issue291801)
The biggie is MutableArray.java:60 http://gwt-code-reviews.appspot.com/291801/diff/4001/5003 File bikeshed/src/com/google/gwt/collections/ImmutableArrayEmptyImpl.java (right): http://gwt-code-reviews.appspot.com/291801/diff/4001/5003#newcode27 bikeshed/src/com/google/gwt/collections/ImmutableArrayEmptyImpl.java:27: Assertions.assertIndexInRange(index, 0, 0); this will always fail... is it worth some more specific assertion? Or at least a syntax sugar that reduces to the same, but is clear at this call site that 0 is actually excluded? http://gwt-code-reviews.appspot.com/291801/diff/4001/5004 File bikeshed/src/com/google/gwt/collections/ImmutableArrayImpl.java (right): http://gwt-code-reviews.appspot.com/291801/diff/4001/5004#newcode25 bikeshed/src/com/google/gwt/collections/ImmutableArrayImpl.java:25: private final E[] elems; you might consider making this default visibility, to test that we don't copy, since that's the point to some of the hoops we're doing (see comment in ImmutableArrayTest). http://gwt-code-reviews.appspot.com/291801/diff/4001/5004#newcode28 bikeshed/src/com/google/gwt/collections/ImmutableArrayImpl.java:28: Assertions.assertNotNull(elems); do you also want to assert that elem.length 0? http://gwt-code-reviews.appspot.com/291801/diff/4001/5005 File bikeshed/src/com/google/gwt/collections/MutableArray.java (right): http://gwt-code-reviews.appspot.com/291801/diff/4001/5005#newcode60 bikeshed/src/com/google/gwt/collections/MutableArray.java:60: elems = null; Huh?! Can't I keep using my existing MutableArray, post-freeze, so long as I don't change it?! Doesn't this line zero it out (but leave it frozen)? http://gwt-code-reviews.appspot.com/291801/diff/4001/5006 File bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java (right): http://gwt-code-reviews.appspot.com/291801/diff/4001/5006#newcode58 bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java:58: I think that if you test ma.size() here, you get an unexpected 0 rather than 2... http://gwt-code-reviews.appspot.com/291801/diff/4001/5006#newcode60 bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java:60: ma.add(1); I like 0, 1, many testing in general, but I'm not sure the 1 case helps here. http://gwt-code-reviews.appspot.com/291801/diff/4001/5006#newcode158 bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java:158: Something I'd like to test, but we don't have visibility to here, is that we didn't copy... i.e. that ia1.elems === ia2.elems === ma.elems. http://gwt-code-reviews.appspot.com/291801/show -- http://groups.google.com/group/Google-Web-Toolkit-Contributors To unsubscribe from this group, send email to google-web-toolkit-contributors+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.