Potential issue with CHM.toArray

[Peter Levart]

On 08/28/2013 12:10 PM, Paul Sandoz wrote:
> Hi,
>
> Intermittent failures were reported with the CHM toArray test in the JDK.
>
> I updated the tests to increase the number of runs and the number of workers and i can reliably reproduce on my laptop, see below.
>
> The test presumes the size should always increase but fails when it observes a new new size less than the previously observed size.
>
> Is that a valid assumption?

I guess it should be a valid assumption. If a thread observes some 
entries in the Map at a particular time and the same thread observes 
less entries at a later time it means that some entries have 
disappeared. That observation is surprising if the only modifications to 
the Map are concurrent insertions of new entries...

> especially when resizing is in progress and bins are transferred from the old to the new table e.g. if one sets the initial capacity of the CHM in the test to say 8 * 1024 (double the number of entries)  there is no issue.
>
> The toArray implementation essentially uses the iterator, with some use of size estimates to create arrays with hopefully minimal re-sizing. So there is nothing particular about toArray regarding traversal.

The same can be observed by just counting the elements returned from 
Iterators of various Collection views...

It's interesting to print out the two consecutive arrays when this 
happens. Here's one such occurrence:

prevArray: [0, 1024, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 
34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47]
nextArray: [0, 1024, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]

I modified the CHM.Traverser class (a base for all Iterators) to collect 
all tables that it traverses via ForwardingNode.nextTable links during 
iteration. Here's one such occurrence printing also the state of 
Traverser after the iteration:

prevIterator(iterations=62): tab lengths/hashCodes=[ 32/119d7047 
64/776ec8df 32/119d7047 64/776ec8df], index=32, baseIndex=32, 
baseLimit=32, baseSize=32
nextIterator(iterations=36): tab lengths/hashCodes=[ 32/119d7047 
64/776ec8df 32/119d7047], index=48, baseIndex=16, baseLimit=32, baseSize=32


It seems that the iteration can traverse through the same tables 
multiple times (back and forth) by following ForwardingNode.nextTable 
links. Aren't nextTable links supposed to be only in "forward" 
direction, leading to from smaller to larger tables?


Regards, Peter

>
> Paul.