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.
