A List implementation backed by multiple small arrays rather than the traditional single large array.
Kevin L. Stern
kevin.l.stern at gmail.com
Thu Apr 15 11:12:45 UTC 2010
Hi Benedict,
Unless I am misreading your post, this now has a very similar feel to the
first data structure that I posted to the list. Martin Buchholz then
pointed out that we can incorporate the ideas from
[Brodnik99resizablearrays] and reap additional benefits.
Regards,
Kevin
On Thu, Apr 15, 2010 at 4:07 AM, Benedict Elliott Smith <lists at laerad.com>wrote:
> Hi Kevin,
>
> Yes, as I was going to bed last night I realised I had not fully addressed
> the problem that was originally being visited; only reduced the constant
> factor for addition to the end of the list. A trivial modification fixes
> that, however; same scheme but up to some maximum arraylet size (of a power
> of 2), after which the array is increased in size linearly. Performance
> doesn't seem to have been affected appreciably, although not been exhaustive
> in the benchmarking:
>
> 10 items inserts versus ArrayList: Chunked=1.15, ExpArray=1.16
> 10 items inserts Chunked / ExpArray = 0.99
> 10 items get versus ArrayList: Chunked=1.15, ExpArray=1.16
> 10 items get Chunked / ExpArray = 0.99
> 100 items inserts versus ArrayList: Chunked=1.24, ExpArray=1.01
> 100 items inserts Chunked / ExpArray = 1.23
> 100 items get versus ArrayList: Chunked=1.24, ExpArray=1.01
> 100 items get Chunked / ExpArray = 1.23
> 1000 items inserts versus ArrayList: Chunked=1.22, ExpArray=1.03
> 1000 items inserts Chunked / ExpArray = 1.19
> 1000 items get versus ArrayList: Chunked=1.22, ExpArray=1.03
> 1000 items get Chunked / ExpArray = 1.19
> 10000 items inserts versus ArrayList: Chunked=1.22, ExpArray=1.03
> 10000 items inserts Chunked / ExpArray = 1.18
> 10000 items get versus ArrayList: Chunked=1.22, ExpArray=1.03
> 10000 items get Chunked / ExpArray = 1.18
> 100000 items inserts versus ArrayList: Chunked=0.82, ExpArray=0.75
> 100000 items inserts Chunked / ExpArray = 1.09
> 100000 items get versus ArrayList: Chunked=0.82, ExpArray=0.75
> 100000 items get Chunked / ExpArray = 1.09
>
> The nice thing about this is that the maximum amount of wasted memory is
> user configurable. Even with a low setting as above (65K) performance seems
> pretty consistent.
>
> Code for calculating index and array offset are pretty straight forward;
> haven't given much thought to optimisations just yet:
>
> private final int indexFor(int a, int i) {
> return 1 + i - (a > maxArrayIndex ? (1 + a - maxArrayIndex) <<
> maxArraySizeShift : 1 << a) ;
> }
> private final int arrayFor(int i) {
> return i >= (maxArraySize << 1) ? (i + 1 >>> maxArraySizeShift) +
> maxArrayIndex - 1 : 31 - Integer.numberOfLeadingZeros(i + 1) ;
> }
>
> Regarding the double list idea - yes, I agree, I certainly didn't think
> that one through fully!
>
>
>
> On 15 April 2010 02:44, Kevin L. Stern <kevin.l.stern at gmail.com> wrote:
>
>> Hi Benedict,
>>
>> Like you, I am relatively new to this mailing list; I am also trying to
>> tread lightly so as not to step on any toes. That being said, I think that
>> I can offer a response to your inquiry.
>>
>> Regarding: "The idea is to simply double the new array size each time a
>> new array needs to be allocated"
>>
>> It seems this would not address the desire of offering an alternative to
>> the allocation of a large backing array for ArrayList (your largest backing
>> array could still reach a size of 1/2 * Integer.MAX_VALUE) and would not
>> address the desire of wasting the (asymptotically) minimum amount of memory
>> in the worst case while maintaining O(1) amortized time bounds. The data
>> structure described in [Brodnik99resizablearrays] has a maximum backing
>> array size of sqrt(n) and caps wasted memory at sqrt(n). What advantage
>> over ArrayList do you see in your data structure?
>>
>> Regarding: "Also, with regard to a Deque implementation, it seems that
>> the simplest solution would be to simply have two lists, with one accepting
>> inserts for near the beginning and being ordered in reverse whilst the other
>> accepted inserts for near to the end."
>>
>> What happens with your structure when you add n elements and then remove
>> element 0 n times? I think that once you work out all the kinks you'll end
>> up with the two stacks approach, which is mentioned in
>> [Brodnik99resizablearrays] and which I mentioned in an earlier email, or
>> you'll end up with the circular list approach, which is not friendly to O(1)
>> amortized time bounds in a data structure that resizes more often than O(n)
>> due to the 'unshift' to the front = 0 position. I think the best approach
>> is the one mentioned in [Brodnik99resizablearrays], which is the approach
>> that I am currently working on. Incidentally, this approach also provides
>> for a much improved index unpacking procedure using only bit shifts and bit
>> masks, although it is at the expense of (O(1)) additional work during
>> resize.
>>
>> Regards,
>>
>> Kevin
>>
>>
>>
>> On Wed, Apr 14, 2010 at 4:42 PM, Benedict Elliott Smith <lists at laerad.com
>> > wrote:
>>
>>> Hi,
>>>
>>> I hope you don't consider it rude to involve myself in this conversation
>>> towards the end - I joined the mailing list only recently.
>>>
>>> I'm not sure if this offers a huge amount to the discussion, but I have
>>> tinkered with a "chunked" array list which seems to offer better time
>>> performance in general at the cost of greater (worst case) memory
>>> utilisation. It is easier to understand IMHO as well, although this is not
>>> necessarily a great benefit here. It turns out the idea is very similar to
>>> the one implemented already by Kevin, though; but perhaps simpler. The idea
>>> is to simply double the new array size each time a new array needs to be
>>> allocated, or in effect allocate an array that is the size of all existing
>>> arrays put together. With this scheme the calculation for array and offset
>>> are really very straight forward ( floor(log(i)) and 1 + i -
>>> 2^floor(log(i))) ). Memory utilisation is the same as for ArrayList, but
>>> obviously inserts at the end are much quicker.
>>>
>>> I have prototyped the data structure this evening and benchmarked
>>> additions at the end of the list, for which the performance is pretty
>>> impressive.
>>>
>>> Some random statistics for addition only on the client JVM (I have
>>> quickly dubbed my implementation ExpArrayList)
>>> All statistics were run in two rounds with ~1000 runs per round per
>>> statistic per list, and the second round results were used.
>>>
>>> 10 items versus ArrayList: Chunked=1.14, ExpArray=1.02
>>> 10 items Chunked / ExpArray = 1.12
>>> 100 items versus ArrayList: Chunked=1.20, ExpArray=0.82
>>> 100 items Chunked / ExpArray = 1.45
>>> 1000 items versus ArrayList: Chunked=1.03, ExpArray=0.51
>>> 1000 items Chunked / ExpArray = 2.02
>>> 10000 items versus ArrayList: Chunked=0.88, ExpArray=0.49
>>> 10000 items Chunked / ExpArray = 1.79
>>> 100000 items versus ArrayList: Chunked=0.32, ExpArray=0.20
>>> 100000 items Chunked / ExpArray = 1.64
>>>
>>> and server JVM:
>>> 10 items versus ArrayList: Chunked=1.00, ExpArray=1.16
>>> 10 items Chunked / ExpArray = 0.86
>>> 100 items versus ArrayList: Chunked=1.29, ExpArray=0.96
>>> 100 items Chunked / ExpArray = 1.34
>>> 1000 items versus ArrayList: Chunked=1.16, ExpArray=0.92
>>> 1000 items Chunked / ExpArray = 1.27
>>> 10000 items versus ArrayList: Chunked=0.93, ExpArray=0.84
>>> 10000 items Chunked / ExpArray = 1.12
>>> 100000 items versus ArrayList: Chunked=0.71, ExpArray=0.65
>>> 100000 items Chunked / ExpArray = 1.10
>>>
>>> Interestingly insertion at the beginning of the list appears to be
>>> quicker with ExpArrayList, at least on the server JVM, whereas I would have
>>> expected them to be fairly close.
>>> Amazingly ExpArrayList is faster even than ArrayList for insertion at the
>>> beginning of large lists, which I haven't yet tried to understand. Insertion
>>> in the middle is similar.
>>>
>>> 10 items versus ArrayList: Chunked=9.82, ExpArray=3.80
>>> 10 items Chunked / ExpArray = 2.59
>>> 100 items versus ArrayList: Chunked=7.30, ExpArray=3.41
>>> 100 items Chunked / ExpArray = 2.14
>>> 1000 items versus ArrayList: Chunked=2.83, ExpArray=1.09
>>> 1000 items Chunked / ExpArray = 2.59
>>> 10000 items versus ArrayList: Chunked=1.56, ExpArray=0.72
>>> 10000 items Chunked / ExpArray = 2.16
>>>
>>> Finally, there are promising results for get() from the ExpArrayList as
>>> well (server JVM), again somehow beating ArrayList for larger lists:
>>> 10 items get versus ArrayList: Chunked=1.27, ExpArray=1.16
>>> 10 items get Chunked / ExpArray = 1.10
>>> 100 items get versus ArrayList: Chunked=1.45, ExpArray=1.17
>>> 100 items get Chunked / ExpArray = 1.25
>>> 1000 items get versus ArrayList: Chunked=1.42, ExpArray=1.07
>>> 1000 items get Chunked / ExpArray = 1.33
>>> 10000 items get versus ArrayList: Chunked=1.26, ExpArray=1.02
>>> 10000 items get Chunked / ExpArray = 1.24
>>> 100000 items get versus ArrayList: Chunked=1.05, ExpArray=0.86
>>> 100000 items get Chunked / ExpArray = 1.22
>>>
>>>
>>> I'm willing to explore this further but I'm not sure how desirable that
>>> is, given that Kevin's data structure appears to perform pretty well already
>>> wrt to CPU time, and better wrt to memory utilisation, and in effect this
>>> mostly changes only the function to determine which array to use, not the
>>> body of the implementation. Let me know if you would like a copy of the
>>> source code and I will find somewhere to upload it.
>>>
>>> Also, with regard to a Deque implementation, it seems that the simplest
>>> solution would be to simply have two lists, with one accepting inserts for
>>> near the beginning and being ordered in reverse whilst the other accepted
>>> inserts for near to the end. The only trick would be having the list at the
>>> beginning support iteration in reverse order cheaply, but this could easily
>>> be achieved by creating an extension of List with a reverseIterator()
>>> method.
>>>
>>>
>>> Anyway, not sure if this helped at all but fancied joining in...
>>>
>>>
>>>
>>>
>>> On 14 April 2010 12:25, Joe Kearney <joe.j.kearney at googlemail.com>wrote:
>>>
>>>> Hi Kevin,
>>>>
>>>> It implements List, as well as Deque. It is indeed based on ArrayDeque,
>>>> with the added operations to implement list. It does so reasonably
>>>> efficiently, moving the fewest elements possible on each operation, that is
>>>> zero for the queue operations, at most n/2 for the rest and all of them for
>>>> a backing array resize.
>>>>
>>>> The idea is to get a replacement for arraylist that performs like
>>>> arraydeque on remove(0). As a side effect, we should be able to get better
>>>> performance on other operations by requiring fewer elements to be moved.
>>>>
>>>> Thanks,
>>>> Joe
>>>>
>>>> 2010/4/14 Kevin L. Stern <kevin.l.stern at gmail.com>
>>>>
>>>> Hi Joe,
>>>>>
>>>>> I was referring to the ChunkedArrayList when I stated that add does not
>>>>> amortize to constant time when the data structure employs the circular list
>>>>> trick to achieve deque behavior; ChunkedArrayList potentially resizes every
>>>>> n^(1/2) operations.
>>>>>
>>>>> Regarding your CircularArrayList, does it differ from Java's
>>>>> ArrayDeque? I took only a cursory look at it, so please understand if I
>>>>> have missed your reason for creating CircularArrayList altogether.
>>>>>
>>>>> Regards,
>>>>>
>>>>> Kevin
>>>>>
>>>>>
>>>>> On Tue, Apr 13, 2010 at 6:52 AM, Joe Kearney <
>>>>> joe.j.kearney at googlemail.com> wrote:
>>>>>
>>>>>> Hi Kevin, Martin,
>>>>>>
>>>>>> To add another discussion point, I've been writing a
>>>>>> draft/proof-of-concept of retrofitting the List interface onto ArrayDeque.
>>>>>> This works over the raw array, it doesn't use the fancier structures being
>>>>>> discussed elsewhere on this list that deal with splitting huge arrays into
>>>>>> arraylets, or that provide for O(1) insert in the middle.
>>>>>>
>>>>>>
>>>>>> http://code.google.com/p/libjoe/source/browse/trunk/src/joe/collect/CircularArrayList.java
>>>>>>
>>>>>> I'd be interested if you have any comments in the context of this
>>>>>> discussion. The code is not entirely ready yet, a couple of tests fail
>>>>>> (6/789) because of a corner case I haven't nailed yet, but the idea is there
>>>>>> at least. I'd like to add array shrinking later, when the size dips below
>>>>>> capacity*0.4 perhaps, to avoid flickering up and down around...
>>>>>>
>>>>>> Tests show performance to be close to ArrayList for the O(1)
>>>>>> operations. Timings for indexed reads and writes showed
>>>>>> no discernible difference between implementations last time I ran the
>>>>>> tests. I don't understand at the moment why the iterator add at index
>>>>>> size/3, size/2 perform 30% slower than ArrayList on smaller lists, nor the
>>>>>> dodgy numbers for ArrayList.insert(5), I'll look at this soon. Those
>>>>>> operations that become O(1) in a circular implementation (that are
>>>>>> implemented and tested here) are faster than in ArrayList. Insert/remove in
>>>>>> the middle are somewhat faster than ArrayList because we only have to copy
>>>>>> at most half of the elements, except when resizing the array.
>>>>>>
>>>>>> Kevin, I don't fully understand your point about not amortizing to
>>>>>> O(1). Certainly that's true for insert not at head or tail. Otherwise this
>>>>>> implementation only moves array elements to the front on an array resize
>>>>>> operation which happens every O(ln n) operations at most, if we do lots of
>>>>>> adds, maybe a little more if we add array shrinking too. This is the same
>>>>>> as ArrayList. Are you just referring to the add-in-the-middle case?
>>>>>>
>>>>>> Some performance results below, code for these is in the repository
>>>>>> above too. This was the second run, after a warmup.
>>>>>>
>>>>>> Thanks,
>>>>>> Joe
>>>>>>
>>>>>> ------------------------------------------------ CircularArrayList
>>>>>> ------------------------------------------------
>>>>>> size add get set iterAdd/3 iterAdd/2
>>>>>> insert(5) removeRnd removeMid remove(0)
>>>>>> 10 20 67 70 125 102
>>>>>> 90 240 191 138
>>>>>> 100 19 67 70 166 138
>>>>>> 94 230 194 118
>>>>>> 1000 28 64 67 681 538
>>>>>> 91 324 382 119
>>>>>> 10000 30 65 67 5884 4425
>>>>>> 94 1296 2330 124
>>>>>> ---------------------------------------------------- ArrayList
>>>>>> ----------------------------------------------------
>>>>>> size add get set iterAdd/3 iterAdd/2
>>>>>> insert(5) removeRnd removeMid remove(0)
>>>>>> 10 23 68 70 100 69
>>>>>> 32913 162 130 105
>>>>>> 100 20 67 70 129 104
>>>>>> 21944 169 134 135
>>>>>> 1000 29 63 67 651 506
>>>>>> 9602 364 333 526
>>>>>> 10000 30 63 66 5878 4414
>>>>>> 9947 2312 2280 4437
>>>>>>
>>>>>> 2010/4/13 Kevin L. Stern <kevin.l.stern at gmail.com>
>>>>>>
>>>>>> Hi Martin,
>>>>>>>
>>>>>>> I had intended to address your request for absolute O(1) operations
>>>>>>> in the previous email. The approach to achieving this suggested in
>>>>>>> [Brodnik99resizablearrays] is tantamount to making ArrayList operations
>>>>>>> absolute O(1) by keeping around an array of size (3/2)*n and filling it with
>>>>>>> a constant number of entries from the main array each time add is called.
>>>>>>> Although this distributes the work done during a resize across the n
>>>>>>> operations required to enter a resize-required state, it is at the expense
>>>>>>> of additional memory usage and slower add operations. My thought is that
>>>>>>> this would be a fine approach for a real-time application that requires hard
>>>>>>> guarantees on performance but would be a liability in so many Java
>>>>>>> applications that do not require these hard guarantees. I look forward to
>>>>>>> hearing your thoughts on the matter, though.
>>>>>>>
>>>>>>> Kevin
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Apr 13, 2010 at 6:18 AM, Kevin L. Stern <
>>>>>>> kevin.l.stern at gmail.com> wrote:
>>>>>>>
>>>>>>>> Hi Martin,
>>>>>>>>
>>>>>>>> It's interesting to note that the old circular list trick will not
>>>>>>>> suffice to turn this data structure into a deque since we might be copying
>>>>>>>> all n elements back to the front = 0 position every n^(1/2) operations (add
>>>>>>>> wouldn't amortize to O(1)). We could use the old two stacks trick (push
>>>>>>>> elements onto one stack, flip (the bottom) half (of) the elements to the
>>>>>>>> 'other' stack when the 'other' stack becomes empty), mentioned in
>>>>>>>> [Brodnik99resizablearrays], but I find this to be a bit CS 101. In
>>>>>>>> [Brodnik99resizablearrays] the authors suggest a method for making all
>>>>>>>> blocks roughly the same size, allowing us to expand/shrink capacity at the
>>>>>>>> beginning or the end; this is the approach that I will take to create a
>>>>>>>> deque.
>>>>>>>>
>>>>>>>> The FAQ for the Sun Contributor Agreement Q3 (
>>>>>>>> http://www.sun.com/software/opensource/contributor_agreement.jsp#sa_3)
>>>>>>>> indicates that one should check with the project to determine where the SCA
>>>>>>>> should be sent. Do you know where I would find this information?
>>>>>>>>
>>>>>>>> Kevin
>>>>>>>>
>>>>>>>> @MISC{Brodnik99resizablearrays,
>>>>>>>> author = {Andrej Brodnik and Svante Carlsson and Erik D. Demaine
>>>>>>>> and J. Ian Munro and Robert Sedgewick},
>>>>>>>> title = {Resizable Arrays in Optimal Time and Space},
>>>>>>>> year = {1999}
>>>>>>>>
>>>>>>>> }
>>>>>>>>
>>>>>>>> On Sun, Apr 11, 2010 at 4:17 PM, Martin Buchholz <
>>>>>>>> martinrb at google.com> wrote:
>>>>>>>>
>>>>>>>>> Hi Kevin,
>>>>>>>>>
>>>>>>>>> Thanks for your continuing work on this.
>>>>>>>>>
>>>>>>>>> I like the test results, and agree with your analysis.
>>>>>>>>> I'm especially happy that you're beating
>>>>>>>>> ArrayList at some operations.
>>>>>>>>>
>>>>>>>>> I'd like to see O(1) addition at the beginning,
>>>>>>>>> implement both List and Deque (I regret
>>>>>>>>> our not having done this with ArrayDeque).
>>>>>>>>>
>>>>>>>>> An additional property that would be nice to
>>>>>>>>> have (but don't try too hard)
>>>>>>>>> is to provide some kind of real-time
>>>>>>>>> guarantees on the cost of an individual operation,
>>>>>>>>> not just amortized time. E.g. ArrayList.add
>>>>>>>>> is worst-case O(n), making it unsuitable for use
>>>>>>>>> in some real-time applications.
>>>>>>>>>
>>>>>>>>> I will help get your changes into the obvious
>>>>>>>>> software distributions. I assume you're happy
>>>>>>>>> with having this class included in any of
>>>>>>>>> Doug Lea's jsr166, guava-libraries, or the JDK itself.
>>>>>>>>> You should sign a Sun contributor agreement,
>>>>>>>>> or whatever the Oracle equivalent is,
>>>>>>>>> if you have not done so yet.
>>>>>>>>>
>>>>>>>>> Doug Lea likes public domain,
>>>>>>>>> guava-libraries likes the Apache license.
>>>>>>>>>
>>>>>>>>> We should get various people a chance to give
>>>>>>>>> a thumbs up on the design of this class -
>>>>>>>>> Doug Lea, Josh Bloch.
>>>>>>>>>
>>>>>>>>> Martin
>>>>>>>>>
>>>>>>>>> On Sun, Apr 11, 2010 at 09:32, Kevin L. Stern <
>>>>>>>>> kevin.l.stern at gmail.com> wrote:
>>>>>>>>> > Hello Martin,
>>>>>>>>> >
>>>>>>>>> > 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).
>>>>>>>>> >
>>>>>>>>> > 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.
>>>>>>>>> >
>>>>>>>>> > Kevin
>>>>>>>>> >
>>>>>>>>> > 1000000 elements:
>>>>>>>>> > Client JVM:
>>>>>>>>> > Add to ChunkedArrayList over ArrayList: 1.30
>>>>>>>>> > Indexed access ChunkedArrayList over ArrayList: 1.80
>>>>>>>>> > Iterator ChunkedArrayList over ArrayList: 0.52
>>>>>>>>> >
>>>>>>>>> > Server JVM:
>>>>>>>>> > Add to ChunkedArrayList over ArrayList: 0.81
>>>>>>>>> > Indexed access ChunkedArrayList over ArrayList: 2.87
>>>>>>>>> > Iterator ChunkedArrayList over ArrayList: 1.31
>>>>>>>>> >
>>>>>>>>> > 100000 elements:
>>>>>>>>> > Client JVM:
>>>>>>>>> > Add to ChunkedArrayList over ArrayList: 0.96
>>>>>>>>> > Indexed access ChunkedArrayList over ArrayList: 1.86
>>>>>>>>> > Iterator ChunkedArrayList over ArrayList: 0.48
>>>>>>>>> >
>>>>>>>>> > Server JVM:
>>>>>>>>> > Add to ChunkedArrayList over ArrayList: 0.96
>>>>>>>>> > Indexed access ChunkedArrayList over ArrayList: 1.89
>>>>>>>>> > Iterator ChunkedArrayList over ArrayList: 2.68
>>>>>>>>> >
>>>>>>>>> > 10000 elements:
>>>>>>>>> > Client JVM:
>>>>>>>>> > Add to ChunkedArrayList over ArrayList: 1.04
>>>>>>>>> > Indexed access ChunkedArrayList over ArrayList: 2.33
>>>>>>>>> > Iterator ChunkedArrayList over ArrayList: 0.53
>>>>>>>>> >
>>>>>>>>> > Server JVM:
>>>>>>>>> > Add to ChunkedArrayList over ArrayList: 0.97
>>>>>>>>> > Indexed access ChunkedArrayList over ArrayList: 2.45
>>>>>>>>> > Iterator ChunkedArrayList over ArrayList: 2.52
>>>>>>>>> >
>>>>>>>>> > 1000 elements:
>>>>>>>>> > Client JVM:
>>>>>>>>> > Add to ChunkedArrayList over ArrayList: 0.99
>>>>>>>>> > Indexed access ChunkedArrayList over ArrayList: 2.27
>>>>>>>>> > Iterator ChunkedArrayList over ArrayList: 0.54
>>>>>>>>> >
>>>>>>>>> > Server JVM:
>>>>>>>>> > Add to ChunkedArrayList over ArrayList: 0.84
>>>>>>>>> > Indexed access ChunkedArrayList over ArrayList: 1.23
>>>>>>>>> > Iterator ChunkedArrayList over ArrayList: 1.11
>>>>>>>>> >
>>>>>>>>> >
>>>>>>>>> > On Fri, Apr 9, 2010 at 7:42 PM, Martin Buchholz <
>>>>>>>>> martinrb at google.com> wrote:
>>>>>>>>> >>
>>>>>>>>> >> My feeling on whether to support O(1) at both ends
>>>>>>>>> >> is that any flavor of this that ends up in the JDK eventually
>>>>>>>>> >> should really do this. My idea is that we can
>>>>>>>>> >> wholeheartedly recommend this collection class
>>>>>>>>> >> for overall good behavior without any of the surprising
>>>>>>>>> >> performance traps of existing collection classes.
>>>>>>>>> >>
>>>>>>>>> >> But for the preliminary version, it makes sense to
>>>>>>>>> >> support only O(1) at one end, if it simplifies the
>>>>>>>>> >> implementation. Random access will of course
>>>>>>>>> >> be worse than ArrayList, but by how much?
>>>>>>>>> >> We can do some benchmarking and look for
>>>>>>>>> >> micro-optimizations now.
>>>>>>>>> >>
>>>>>>>>> >> Kevin, what is you own personal feeling?
>>>>>>>>> >> Is the algorithm correct, and efficient enough?
>>>>>>>>> >> Do you think your new collection belongs in java.util?
>>>>>>>>> >>
>>>>>>>>> >> Martin
>>>>>>>>> >>
>>>>>>>>> >> On Sun, Apr 4, 2010 at 04:12, Kevin L. Stern <
>>>>>>>>> kevin.l.stern at gmail.com>
>>>>>>>>> >> wrote:
>>>>>>>>> >> > The data structure is available at the second link that I
>>>>>>>>> originally
>>>>>>>>> >> > provided (once again, it is
>>>>>>>>> >> >
>>>>>>>>> >> >
>>>>>>>>> https://docs.google.com/Doc?docid=0Aabrz3MPBDdhZGdrbnEzejdfM2M3am5wM2Mz&hl=en
>>>>>>>>> ).
>>>>>>>>> >> > This does not have O(1) time insertion at the front as yet as
>>>>>>>>> it was
>>>>>>>>> >> > unclear
>>>>>>>>> >> > to me whether or not it was agreed upon:
>>>>>>>>> >> > _________________
>>>>>>>>> >> > From: Osvaldo Doederlein <opinali at gmail.com>
>>>>>>>>> >> > Date: Mon, Mar 29, 2010 at 10:08 AM
>>>>>>>>> >> > Subject: Re: A List implementation backed by multiple small
>>>>>>>>> arrays
>>>>>>>>> >> > rather
>>>>>>>>> >> > than the traditional single large array.
>>>>>>>>> >> > To: Martin Buchholz <martinrb at google.com>
>>>>>>>>> >> > Cc: "Kevin L. Stern" <kevin.l.stern at gmail.com>,
>>>>>>>>> >> > core-libs-dev at openjdk.java.net
>>>>>>>>> >> >
>>>>>>>>> >> > Initially, it would be good enough to replace only
>>>>>>>>> java.util.ArrayList
>>>>>>>>> >> > with
>>>>>>>>> >> > minimal overhead. ArrayList does not support efficient
>>>>>>>>> add-at-front or
>>>>>>>>> >> > other
>>>>>>>>> >> > enhancements of ArrayDeque; but ArrayList is still a much more
>>>>>>>>> important
>>>>>>>>> >> > and
>>>>>>>>> >> > popular collection, it's the primary "straight replacement for
>>>>>>>>> primitive
>>>>>>>>> >> > arrrays" and I guess it should continue with that role.
>>>>>>>>> >> > _________________
>>>>>>>>> >> >
>>>>>>>>> >> > As a disclaimer, I'm still tinkering with this so I'll be
>>>>>>>>> updating the
>>>>>>>>> >> > document at the provided link as I find improvements.
>>>>>>>>> >> >
>>>>>>>>> >> > Thoughts?
>>>>>>>>> >> >
>>>>>>>>> >> > Thanks,
>>>>>>>>> >> >
>>>>>>>>> >> > Kevin
>>>>>>>>> >> >
>>>>>>>>> >> > On Thu, Apr 1, 2010 at 10:28 PM, Martin Buchholz <
>>>>>>>>> martinrb at google.com>
>>>>>>>>> >> > wrote:
>>>>>>>>> >> >>
>>>>>>>>> >> >> Hi Kevin,
>>>>>>>>> >> >>
>>>>>>>>> >> >> You're probably the only one on this list who has
>>>>>>>>> >> >> seriously read the paper. It is not surprising that
>>>>>>>>> >> >> taking a research paper into production would
>>>>>>>>> >> >> discover bugs - the research never had to undergo
>>>>>>>>> >> >> rigorous testing. (I like the Java culture of
>>>>>>>>> >> >> combining spec + implementation + test suite)
>>>>>>>>> >> >>
>>>>>>>>> >> >> I suggest you ask the authors directly about the bug.
>>>>>>>>> >> >> They would probably also be interested to hear
>>>>>>>>> >> >> about your implementation.
>>>>>>>>> >> >>
>>>>>>>>> >> >> Are you aware of Integer.numberOfLeadingZeros?
>>>>>>>>> >> >>
>>>>>>>>> >> >>
>>>>>>>>> >> >>
>>>>>>>>> http://download.java.net/jdk7/docs/api/java/lang/Integer.html#numberOfLeadingZeros(int)<http://download.java.net/jdk7/docs/api/java/lang/Integer.html#numberOfLeadingZeros%28int%29>
>>>>>>>>> >> >>
>>>>>>>>> >> >> Martin
>>>>>>>>> >> >>
>>>>>>>>> >> >> On Wed, Mar 31, 2010 at 19:34, Kevin L. Stern <
>>>>>>>>> kevin.l.stern at gmail.com>
>>>>>>>>> >> >> wrote:
>>>>>>>>> >> >> > I'm almost convinced now that the paper is incorrect. The
>>>>>>>>> code below
>>>>>>>>> >> >> > gives
>>>>>>>>> >> >> > me the appropriate index into the index array and the
>>>>>>>>> offset into the
>>>>>>>>> >> >> > data
>>>>>>>>> >> >> > block. That being said, remember when I mentioned that
>>>>>>>>> this will
>>>>>>>>> >> >> > include a
>>>>>>>>> >> >> > bit more work to access an element than a simple bit shift
>>>>>>>>> and a bit
>>>>>>>>> >> >> > mask?
>>>>>>>>> >> >> > Well this is more than a bit more - we'll be doing this
>>>>>>>>> each time an
>>>>>>>>> >> >> > index
>>>>>>>>> >> >> > is requested. I'll spend some time trying to twiddle the
>>>>>>>>> bits to see
>>>>>>>>> >> >> > if
>>>>>>>>> >> >> > I
>>>>>>>>> >> >> > can eliminate/combine some of the operations.
>>>>>>>>> >> >> >
>>>>>>>>> >> >> > for (int r = 1; r < 33; r++) {
>>>>>>>>> >> >> > int k = lg(r);
>>>>>>>>> >> >> > int floorKO2 = k >> 1;
>>>>>>>>> >> >> > int powFloorKO2 = (1 << floorKO2);
>>>>>>>>> >> >> > int p = ((1 << floorKO2) - 1) << 1;
>>>>>>>>> >> >> > int ceilKO2;
>>>>>>>>> >> >> > if ((k & 1) == 1) {
>>>>>>>>> >> >> > ceilKO2 = floorKO2 + 1;
>>>>>>>>> >> >> > p += powFloorKO2;
>>>>>>>>> >> >> > } else {
>>>>>>>>> >> >> > ceilKO2 = floorKO2;
>>>>>>>>> >> >> > }
>>>>>>>>> >> >> > int e = r & ((1 << ceilKO2) - 1);
>>>>>>>>> >> >> > int b = (r >> ceilKO2) & (powFloorKO2 - 1);
>>>>>>>>> >> >> >
>>>>>>>>> >> >> > System.out.println((r - 1) + " " + (p + b) + "
>>>>>>>>> " + e);
>>>>>>>>> >> >> > }
>>>>>>>>> >> >> >
>>>>>>>>> >> >> > Kevin
>>>>>>>>> >> >> >
>>>>>>>>> >> >> > On Wed, Mar 31, 2010 at 7:08 PM, Kevin L. Stern
>>>>>>>>> >> >> > <kevin.l.stern at gmail.com>
>>>>>>>>> >> >> > wrote:
>>>>>>>>> >> >> >>
>>>>>>>>> >> >> >> I realize that 2 * (2^(k/2) - 1) only works for even
>>>>>>>>> numbered
>>>>>>>>> >> >> >> superblocks,
>>>>>>>>> >> >> >> the odd numbered superblocks need an additional term added
>>>>>>>>> (the
>>>>>>>>> >> >> >> number
>>>>>>>>> >> >> >> of
>>>>>>>>> >> >> >> data blocks in SB_[k-1]) to jive with my interpretation;
>>>>>>>>> anyhow, I
>>>>>>>>> >> >> >> also
>>>>>>>>> >> >> >> came
>>>>>>>>> >> >> >> across an alternative characterization of superblock in
>>>>>>>>> the paper
>>>>>>>>> >> >> >> which
>>>>>>>>> >> >> >> states that data blocks are grouped within a superblock
>>>>>>>>> when they
>>>>>>>>> >> >> >> are
>>>>>>>>> >> >> >> the
>>>>>>>>> >> >> >> same size - to me, though, that implies that my example
>>>>>>>>> structure
>>>>>>>>> >> >> >> below
>>>>>>>>> >> >> >> would be
>>>>>>>>> >> >> >>
>>>>>>>>> >> >> >> SB_0: [1]
>>>>>>>>> >> >> >> SB_1: [2][2][2]
>>>>>>>>> >> >> >> SB_2: [4][4][4][4][4][4]
>>>>>>>>> >> >> >>
>>>>>>>>> >> >> >> which seems to contradict my understanding of (1) below.
>>>>>>>>> I must be
>>>>>>>>> >> >> >> reading this upside down.
>>>>>>>>> >> >> >>
>>>>>>>>> >> >> >> On Wed, Mar 31, 2010 at 6:36 PM, Kevin L. Stern
>>>>>>>>> >> >> >> <kevin.l.stern at gmail.com>
>>>>>>>>> >> >> >> wrote:
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> What am I missing here? In "Resizable arrays in optimal
>>>>>>>>> time and
>>>>>>>>> >> >> >>> space"
>>>>>>>>> >> >> >>> the authors define their data structure with the
>>>>>>>>> following
>>>>>>>>> >> >> >>> property:
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> (1) "When superblock SB_k is fully allocated, it
>>>>>>>>> consists of
>>>>>>>>> >> >> >>> 2^(floor(k/2)) data blocks, each of size 2^(ceil(k/2))."
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> Since the superblock is zero-based indexed this implies
>>>>>>>>> the
>>>>>>>>> >> >> >>> following
>>>>>>>>> >> >> >>> structure:
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> SB_0: [1]
>>>>>>>>> >> >> >>> SB_1: [2]
>>>>>>>>> >> >> >>> SB_2: [2][2]
>>>>>>>>> >> >> >>> SB_3: [4][4]
>>>>>>>>> >> >> >>> SB_4: [4][4][4][4]
>>>>>>>>> >> >> >>> [...]
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> Let's have a look at Algorithm 3, Locate(i), with i = 3:
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> r = 100 (the binary expansion of i + 1)
>>>>>>>>> >> >> >>> k = |r| - 1 = 2
>>>>>>>>> >> >> >>> p = 2^k - 1 = 3
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> What concerns me is their statement that p represents
>>>>>>>>> "the number
>>>>>>>>> >> >> >>> of
>>>>>>>>> >> >> >>> data
>>>>>>>>> >> >> >>> blocks in superblocks prior to SB_k." There are only two
>>>>>>>>> data
>>>>>>>>> >> >> >>> blocks
>>>>>>>>> >> >> >>> in
>>>>>>>>> >> >> >>> superblocks prior to SB_2, not three. Given (1) above,
>>>>>>>>> unless I'm
>>>>>>>>> >> >> >>> misinterpreting it, the number of data blocks in
>>>>>>>>> superblocks prior
>>>>>>>>> >> >> >>> to
>>>>>>>>> >> >> >>> SB_k
>>>>>>>>> >> >> >>> should be:
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> 2 * Sum[i=0->k/2-1] 2^i = 2 * (2^(k/2) - 1)
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> This, of course, seems to work out much better in my
>>>>>>>>> example above,
>>>>>>>>> >> >> >>> giving the correct answer to my interpretation of their
>>>>>>>>> data
>>>>>>>>> >> >> >>> structure, but
>>>>>>>>> >> >> >>> I have a hard time believing that this is their mistake
>>>>>>>>> rather than
>>>>>>>>> >> >> >>> my
>>>>>>>>> >> >> >>> misinterpretation.
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> Thoughts?
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> Kevin
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>> On Tue, Mar 30, 2010 at 5:20 PM, Martin Buchholz
>>>>>>>>> >> >> >>> <martinrb at google.com>
>>>>>>>>> >> >> >>> wrote:
>>>>>>>>> >> >> >>>>
>>>>>>>>> >> >> >>>> On Tue, Mar 30, 2010 at 04:25, Kevin L. Stern
>>>>>>>>> >> >> >>>> <kevin.l.stern at gmail.com>
>>>>>>>>> >> >> >>>> wrote:
>>>>>>>>> >> >> >>>> > Hi Martin,
>>>>>>>>> >> >> >>>> >
>>>>>>>>> >> >> >>>> > Thanks much for your feedback. The first approach
>>>>>>>>> that comes to
>>>>>>>>> >> >> >>>> > mind
>>>>>>>>> >> >> >>>> > to
>>>>>>>>> >> >> >>>> > implement O(1) time front as well as rear insertion is
>>>>>>>>> to create
>>>>>>>>> >> >> >>>> > a
>>>>>>>>> >> >> >>>> > cyclic
>>>>>>>>> >> >> >>>> > list structure with a front/rear pointer - to insert
>>>>>>>>> at the
>>>>>>>>> >> >> >>>> > front
>>>>>>>>> >> >> >>>> > requires
>>>>>>>>> >> >> >>>> > decrementing the front pointer (modulo the size) and
>>>>>>>>> to insert
>>>>>>>>> >> >> >>>> > at
>>>>>>>>> >> >> >>>> > the
>>>>>>>>> >> >> >>>> > rear
>>>>>>>>> >> >> >>>> > requires incrementing the rear pointer (modulo the
>>>>>>>>> size). We
>>>>>>>>> >> >> >>>> > need
>>>>>>>>> >> >> >>>> > to
>>>>>>>>> >> >> >>>> > resize
>>>>>>>>> >> >> >>>> > when the two pointers bump into each other. Could you
>>>>>>>>> explain
>>>>>>>>> >> >> >>>> > more
>>>>>>>>> >> >> >>>> > about
>>>>>>>>> >> >> >>>> > your suggestion of introducing an arraylet that is
>>>>>>>>> shared by the
>>>>>>>>> >> >> >>>> > front
>>>>>>>>> >> >> >>>> > and
>>>>>>>>> >> >> >>>> > the rear?
>>>>>>>>> >> >> >>>>
>>>>>>>>> >> >> >>>> It was a half-baked idea - I don't know if there's a way
>>>>>>>>> to turn
>>>>>>>>> >> >> >>>> it
>>>>>>>>> >> >> >>>> into
>>>>>>>>> >> >> >>>> something useful. I was thinking of the ArrayDeque
>>>>>>>>> >> >> >>>> implementation,
>>>>>>>>> >> >> >>>> where all the elements live in a single array.
>>>>>>>>> >> >> >>>>
>>>>>>>>> >> >> >>>> > It's not clear to me how that would help and/or be a
>>>>>>>>> better
>>>>>>>>> >> >> >>>> > approach than the cyclic list. Anyhow, the paper that
>>>>>>>>> you
>>>>>>>>> >> >> >>>> > reference,
>>>>>>>>> >> >> >>>> > "Resizable arrays in optimal time and space", gives a
>>>>>>>>> deque so
>>>>>>>>> >> >> >>>> > if
>>>>>>>>> >> >> >>>> > we
>>>>>>>>> >> >> >>>> > take
>>>>>>>>> >> >> >>>> > that approach then the deque is specified.
>>>>>>>>> >> >> >>>>
>>>>>>>>> >> >> >>>> Technically, ArrayList also supports the Deque
>>>>>>>>> operations -
>>>>>>>>> >> >> >>>> just not efficiently.
>>>>>>>>> >> >> >>>
>>>>>>>>> >> >> >>
>>>>>>>>> >> >> >
>>>>>>>>> >> >> >
>>>>>>>>> >> >
>>>>>>>>> >> >
>>>>>>>>> >
>>>>>>>>> >
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100415/e89225df/attachment.html>
More information about the core-libs-dev
mailing list