Hello Martin,<br><br>I spent some time this weekend trying to bring out bugs in the implementation; I believe the latest version to be in decent shape.  I have also gathered some data on the performance of ChunkedArrayList over ArrayList using the latest 1.6 JDK, which I've included below (note that the numbers represent the time spent performing the specified operation with ChunkedArrayList over the time spent with ArrayList, so 1.00 indicates equivalent performance, < 1.00 indicates that ChunkedArrayList is less costly and > 1.00 indicates that ArrayList is less costly).  I've noticed relatively significant variability in a few of the numbers when I switch hardware; though, these data do seem to represent rough performance expectations.  For my test I generated x elements and then timed the process of adding them to ArrayList/ChunkedArrayList, then I performed a get operation on each for indices 0 through x-1 and finally I used the iterator mechanism to retrieve the first through xth element (of course, I performed each of these operations multiple times throwing away the timing for the first few iterations to warm up the JVM).<br>

<br>Regarding the question of whether or not this belongs in java.util, I would suggest that if it is desirable from a GC point of view to eliminate the large backing array from ArrayList then your suggestion of achieving this by way of a data structure that is both time and space optimal is a particularly elegant solution as it not only guarantees that no backing array will be larger than sqrt(n) elements but it also provides dynamic shrinking behavior, has less maximum memory overhead than ArrayList, and copies (asymptotically) fewer elements during a resize than ArrayList.  Of course, this data structure does not do everything better than ArrayList; in particular, indexed access is more costly, due to the required decomposition of the index into backing array index and offset and the additional memory indirection, and insertion-at-an-index is more costly, due to the multiple array copies necessary to complete the shift.  That being said, I think that the additional cost of indexed access is partially mitigated by the availability of iterator and listIterator, whose implementations do not use the index decomposition procedure, and the additional cost of insertion-at-an-index is partially mitigated by the fact that insertion-at-an-index is already an undesirable operation on ArrayList due to its linear time complexity.<br>

<br>Kevin<br><br>1000000 elements:<br>Client JVM:<br>Add to ChunkedArrayList over ArrayList: 1.30<br>Indexed access ChunkedArrayList over ArrayList: 1.80<br>Iterator ChunkedArrayList over ArrayList: 0.52<br><br>Server JVM:<br>

Add to ChunkedArrayList over ArrayList: 0.81<br>Indexed access ChunkedArrayList over ArrayList: 2.87<br>Iterator ChunkedArrayList over ArrayList: 1.31<br><br>100000 elements:<br>Client JVM:<br>Add to ChunkedArrayList over ArrayList: 0.96<br>

Indexed access ChunkedArrayList over ArrayList: 1.86<br>Iterator ChunkedArrayList over ArrayList: 0.48<br><br>Server JVM:<br>Add to ChunkedArrayList over ArrayList: 0.96<br>Indexed access ChunkedArrayList over ArrayList: 1.89<br>

Iterator ChunkedArrayList over ArrayList: 2.68<br><br>10000 elements:<br>Client JVM:<br>Add to ChunkedArrayList over ArrayList: 1.04<br>Indexed access ChunkedArrayList over ArrayList: 2.33<br>Iterator ChunkedArrayList over ArrayList: 0.53<br>

<br>Server JVM:<br>Add to ChunkedArrayList over ArrayList: 0.97<br>Indexed access ChunkedArrayList over ArrayList: 2.45<br>Iterator ChunkedArrayList over ArrayList: 2.52<br><br>1000 elements:<br>Client JVM:<br>Add to ChunkedArrayList over ArrayList: 0.99<br>

Indexed access ChunkedArrayList over ArrayList: 2.27<br>Iterator ChunkedArrayList over ArrayList: 0.54<br><br>Server JVM:<br>Add to ChunkedArrayList over ArrayList: 0.84<br>Indexed access ChunkedArrayList over ArrayList: 1.23<br>

Iterator ChunkedArrayList over ArrayList: 1.11<br><br><br><div class="gmail_quote">On Fri, Apr 9, 2010 at 7:42 PM, Martin Buchholz <span dir="ltr"><<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">My feeling on whether to support O(1) at both ends<br>
is that any flavor of this that ends up in the JDK eventually<br>
should really do this.  My idea is that we can<br>
wholeheartedly recommend this collection class<br>
for overall good behavior without any of the surprising<br>
performance traps of existing collection classes.<br>
<br>
But for the preliminary version, it makes sense to<br>
support only O(1) at one end, if it simplifies the<br>
implementation.  Random access will of course<br>
be worse than ArrayList, but by how much?<br>
We can do some benchmarking and look for<br>
micro-optimizations now.<br>
<br>
Kevin, what is you own personal feeling?<br>
Is the algorithm correct, and efficient enough?<br>
Do you think your new collection belongs in java.util?<br>
<font color="#888888"><br>
Martin<br>
</font><div><div></div><div><br>
On Sun, Apr 4, 2010 at 04:12, Kevin L. Stern <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>> wrote:<br>
> The data structure is available at the second link that I originally<br>
> provided (once again, it is<br>
> <a href="https://docs.google.com/Doc?docid=0Aabrz3MPBDdhZGdrbnEzejdfM2M3am5wM2Mz&hl=en" target="_blank">https://docs.google.com/Doc?docid=0Aabrz3MPBDdhZGdrbnEzejdfM2M3am5wM2Mz&hl=en</a>).<br>
> This does not have O(1) time insertion at the front as yet as it was unclear<br>
> to me whether or not it was agreed upon:<br>
> _________________<br>
> From: Osvaldo Doederlein <<a href="mailto:opinali@gmail.com" target="_blank">opinali@gmail.com</a>><br>
> Date: Mon, Mar 29, 2010 at 10:08 AM<br>
> Subject: Re: A List implementation backed by multiple small arrays rather<br>
> than the traditional single large array.<br>
> To: Martin Buchholz <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>><br>
> Cc: "Kevin L. Stern" <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>>,<br>
> <a href="mailto:core-libs-dev@openjdk.java.net" target="_blank">core-libs-dev@openjdk.java.net</a><br>
><br>
> Initially, it would be good enough to replace only java.util.ArrayList with<br>
> minimal overhead. ArrayList does not support efficient add-at-front or other<br>
> enhancements of ArrayDeque; but ArrayList is still a much more important and<br>
> popular collection, it's the primary "straight replacement for primitive<br>
> arrrays" and I guess it should continue with that role.<br>
> _________________<br>
><br>
> As a disclaimer, I'm still tinkering with this so I'll be updating the<br>
> document at the provided link as I find improvements.<br>
><br>
> Thoughts?<br>
><br>
> Thanks,<br>
><br>
> Kevin<br>
><br>
> On Thu, Apr 1, 2010 at 10:28 PM, Martin Buchholz <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>><br>
> wrote:<br>
>><br>
>> Hi Kevin,<br>
>><br>
>> You're probably the only one on this list who has<br>
>> seriously read the paper.  It is not surprising that<br>
>> taking a research paper into production would<br>
>> discover bugs - the research never had to undergo<br>
>> rigorous testing.  (I like the Java culture of<br>
>> combining spec + implementation + test suite)<br>
>><br>
>> I suggest you ask the authors directly about the bug.<br>
>> They would probably also be interested to hear<br>
>> about your implementation.<br>
>><br>
>> Are you aware of Integer.numberOfLeadingZeros?<br>
>><br>
>> <a href="http://download.java.net/jdk7/docs/api/java/lang/Integer.html#numberOfLeadingZeros%28int%29" target="_blank">http://download.java.net/jdk7/docs/api/java/lang/Integer.html#numberOfLeadingZeros(int)</a><br>


>><br>
>> Martin<br>
>><br>
>> On Wed, Mar 31, 2010 at 19:34, Kevin L. Stern <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>><br>
>> wrote:<br>
>> > I'm almost convinced now that the paper is incorrect.  The code below<br>
>> > gives<br>
>> > me the appropriate index into the index array and the offset into the<br>
>> > data<br>
>> > block.  That being said, remember when I mentioned that this will<br>
>> > include a<br>
>> > bit more work to access an element than a simple bit shift and a bit<br>
>> > mask?<br>
>> > Well this is more than a bit more - we'll be doing this each time an<br>
>> > index<br>
>> > is requested.  I'll spend some time trying to twiddle the bits to see if<br>
>> > I<br>
>> > can eliminate/combine some of the operations.<br>
>> ><br>
>> >         for (int r = 1; r < 33; r++) {<br>
>> >             int k = lg(r);<br>
>> >             int floorKO2 = k >> 1;<br>
>> >             int powFloorKO2 = (1 << floorKO2);<br>
>> >             int p = ((1 << floorKO2) - 1) << 1;<br>
>> >             int ceilKO2;<br>
>> >             if ((k & 1) == 1) {<br>
>> >                 ceilKO2 = floorKO2 + 1;<br>
>> >                 p += powFloorKO2;<br>
>> >             } else {<br>
>> >                 ceilKO2 = floorKO2;<br>
>> >             }<br>
>> >             int e = r & ((1 << ceilKO2) - 1);<br>
>> >             int b = (r >> ceilKO2) & (powFloorKO2 - 1);<br>
>> ><br>
>> >             System.out.println((r - 1) + " " + (p + b) + " " + e);<br>
>> >         }<br>
>> ><br>
>> > Kevin<br>
>> ><br>
>> > On Wed, Mar 31, 2010 at 7:08 PM, Kevin L. Stern<br>
>> > <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>><br>
>> > wrote:<br>
>> >><br>
>> >> I realize that 2 * (2^(k/2) - 1) only works for even numbered<br>
>> >> superblocks,<br>
>> >> the odd numbered superblocks need an additional term added (the number<br>
>> >> of<br>
>> >> data blocks in SB_[k-1]) to jive with my interpretation; anyhow, I also<br>
>> >> came<br>
>> >> across an alternative characterization of superblock in the paper which<br>
>> >> states that data blocks are grouped within a superblock when they are<br>
>> >> the<br>
>> >> same size - to me, though, that implies that my example structure below<br>
>> >> would be<br>
>> >><br>
>> >> SB_0: [1]<br>
>> >> SB_1: [2][2][2]<br>
>> >> SB_2: [4][4][4][4][4][4]<br>
>> >><br>
>> >> which seems to contradict my understanding of (1) below.  I must be<br>
>> >> reading this upside down.<br>
>> >><br>
>> >> On Wed, Mar 31, 2010 at 6:36 PM, Kevin L. Stern<br>
>> >> <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>><br>
>> >> wrote:<br>
>> >>><br>
>> >>> What am I missing here?  In "Resizable arrays in optimal time and<br>
>> >>> space"<br>
>> >>> the authors define their data structure with the following property:<br>
>> >>><br>
>> >>> (1)  "When superblock SB_k is fully allocated, it consists of<br>
>> >>> 2^(floor(k/2)) data blocks, each of size 2^(ceil(k/2))."<br>
>> >>><br>
>> >>> Since the superblock is zero-based indexed this implies the following<br>
>> >>> structure:<br>
>> >>><br>
>> >>> SB_0: [1]<br>
>> >>> SB_1: [2]<br>
>> >>> SB_2: [2][2]<br>
>> >>> SB_3: [4][4]<br>
>> >>> SB_4: [4][4][4][4]<br>
>> >>> [...]<br>
>> >>><br>
>> >>> Let's have a look at Algorithm 3, Locate(i), with i = 3:<br>
>> >>><br>
>> >>> r = 100 (the binary expansion of i + 1)<br>
>> >>> k = |r| - 1 = 2<br>
>> >>> p = 2^k - 1 = 3<br>
>> >>><br>
>> >>> What concerns me is their statement that p represents "the number of<br>
>> >>> data<br>
>> >>> blocks in superblocks prior to SB_k."  There are only two data blocks<br>
>> >>> in<br>
>> >>> superblocks prior to SB_2, not three.  Given (1) above, unless I'm<br>
>> >>> misinterpreting it, the number of data blocks in superblocks prior to<br>
>> >>> SB_k<br>
>> >>> should be:<br>
>> >>><br>
>> >>> 2 * Sum[i=0->k/2-1] 2^i = 2 * (2^(k/2) - 1)<br>
>> >>><br>
>> >>> This, of course, seems to work out much better in my example above,<br>
>> >>> giving the correct answer to my interpretation of their data<br>
>> >>> structure, but<br>
>> >>> I have a hard time believing that this is their mistake rather than my<br>
>> >>> misinterpretation.<br>
>> >>><br>
>> >>> Thoughts?<br>
>> >>><br>
>> >>> Kevin<br>
>> >>><br>
>> >>> On Tue, Mar 30, 2010 at 5:20 PM, Martin Buchholz <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>><br>
>> >>> wrote:<br>
>> >>>><br>
>> >>>> On Tue, Mar 30, 2010 at 04:25, Kevin L. Stern<br>
>> >>>> <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>><br>
>> >>>> wrote:<br>
>> >>>> > Hi Martin,<br>
>> >>>> ><br>
>> >>>> > Thanks much for your feedback.  The first approach that comes to<br>
>> >>>> > mind<br>
>> >>>> > to<br>
>> >>>> > implement O(1) time front as well as rear insertion is to create a<br>
>> >>>> > cyclic<br>
>> >>>> > list structure with a front/rear pointer - to insert at the front<br>
>> >>>> > requires<br>
>> >>>> > decrementing the front pointer (modulo the size) and to insert at<br>
>> >>>> > the<br>
>> >>>> > rear<br>
>> >>>> > requires incrementing the rear pointer (modulo the size).  We need<br>
>> >>>> > to<br>
>> >>>> > resize<br>
>> >>>> > when the two pointers bump into each other.  Could you explain more<br>
>> >>>> > about<br>
>> >>>> > your suggestion of introducing an arraylet that is shared by the<br>
>> >>>> > front<br>
>> >>>> > and<br>
>> >>>> > the rear?<br>
>> >>>><br>
>> >>>> It was a half-baked idea - I don't know if there's a way to turn it<br>
>> >>>> into<br>
>> >>>> something useful.  I was thinking of the ArrayDeque implementation,<br>
>> >>>> where all the elements live in a single array.<br>
>> >>>><br>
>> >>>> >  It's not clear to me how that would help and/or be a better<br>
>> >>>> > approach than the cyclic list.  Anyhow, the paper that you<br>
>> >>>> > reference,<br>
>> >>>> > "Resizable arrays in optimal time and space", gives a deque so if<br>
>> >>>> > we<br>
>> >>>> > take<br>
>> >>>> > that approach then the deque is specified.<br>
>> >>>><br>
>> >>>> Technically, ArrayList also supports the Deque operations -<br>
>> >>>> just not efficiently.<br>
>> >>><br>
>> >><br>
>> ><br>
>> ><br>
><br>
><br>
</div></div></blockquote></div><br>