A behavior mismatch in AbstractCollection.toArray(T[] )

[David Holmes]

Hi Sean,

On 13/12/2011 5:21 PM, Sean Chou wrote:
> When I was reading the code of AbstractCollection.toArray(T[] ), I
> found its behavior maybe different from the spec in multithread
> environment. The spec says "If the collection fits in the specified
> array, it is returned therein. Otherwise, a new array is allocated
> with the runtime type of the specified array and the size of this
> collection."  However, in multithread environment, it is not easy to
> tell if the collection fits in the specified array, because the
> items may be removed when toArray is copying.

Right. The problem is that AbstractCollection doesn't address 
thread-safety or any other concurrency issues so doesn't account for the 
collection growing or shrinking while the toArray snapshot is being 
taken. Really the collection implementations that are designed to 
support multiple threads should override toArray to make it clear how it 
should behave. As it stands, in my opinion, it is more a "quality of 
implementation" issue as to whether AbstractCollection expends effort 
after creating the array to see if the array is actually full or not; or 
whether after creating an array it turns out it could have fit in the 
original.

For a concurrent collection  I would write the spec for toArray 
something like:

"The current size of the collection is examined and if the collection 
fits in the specified array it will be the target array, else a new 
array is allocated based on that current size and it becomes the target 
array. If the collection grows such that the target array no longer fits 
then extra elements will not be copied into the target array. If the 
collection shrinks then the target array will contain null elements."

Or for the last part "then the target array will be copied to a new 
array that exactly fits the number of elements returned".

David Holmes
------------

>
>      Here is a testcase:
> //////////////////////////////////////////////////////////////////////////
>
> import java.util.Map;
> import java.util.concurrent.ConcurrentHashMap;
>
> public class CollectionToArrayTest {
>
>      static volatile Map<String, String>  map = new
> TConcurrentHashMap<String, String>();
>      static volatile boolean gosleep = true;
>
>      static class TConcurrentHashMap<K, V>  extends ConcurrentHashMap<K, V>  {
>          public int size() {
>              int oldresult = super.size();
>              System.out.println("map size before concurrent remove is "
>                      + oldresult);
>              while (gosleep) {
>                  try {
>                      // Make sure the map is modified during toArray is
> called,
>                      // between getsize and being iterated.
>                      Thread.sleep(1000);
>                      // System.out.println("size called, size is " +
> oldresult +
>                      // " take a sleep to make sure the element is deleted
> before size is returned.");
>                  } catch (Exception e) {
>                  }
>              }
>              return oldresult;
>          }
>      }
>
>      static class ToArrayThread implements Runnable {
>          public void run() {
>              for (int i = 0; i<  5; i++) {
>                  String str = Integer.toString(i);
>                  map.put(str, str);
>              }
>              String[] buffer = new String[4];
>              String[] strings = map.values().toArray(buffer);
>              // System.out.println("length is " + strings.length);
>              if (strings.length<= buffer.length) {
>                  System.out.println("given array size is "
>                                  + buffer.length
>                                  + " \nreturned array size is "
>                                  + strings.length
>                                  + ", \nbuffer should be used according to
> spec. Is buffer used : "
>                                  + (strings == buffer));
>              }
>          }
>      }
>
>      static class RemoveThread implements Runnable {
>          public void run() {
>              String str = Integer.toString(0);
>              map.remove(str);
>              gosleep = false;
>          }
>      }
>
>      public static void main(String args[]) {
>          CollectionToArrayTest app = new CollectionToArrayTest();
>          app.test_concurrentRemove();
>      }
>
>      public void test_concurrentRemove() {
>
> System.out.println("//////////////////////////////////////////////\n" +
>                  "The spec says if the given array is large\n "  +
>                          "enough to hold all elements, the given array\n" +
>                          "should be returned by toArray. This \n" +
>                          "testcase checks this case. \n" +
>                          "//////////////////////////////////////////////");
>
>          Thread[] threads = new Thread[2];
>          threads[0] = new Thread(new ToArrayThread());
>          threads[1] = new Thread(new RemoveThread());
>
>          threads[0].start();
>
>          try {
>              // Take a sleep to make sure toArray is already called.
>              Thread.sleep(1200);
>          } catch (Exception e) {
>          }
>
>          threads[1].start();
>      }
> }
>
> //////////////////////////////////////////////////////////////////////////
>
> TConcurrentHashMap is used to make sure the collection is modified
> during toArray is invoked. So the returned array fits in the specified
> array, but a new array is used because toArray checks the size
> before copying.
>
> Is this a bug ?
>
>