CHM trySplit of a map with odd size

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

CHM trySplit of a map with odd size

Ben Manes
I checked Doug's CVS repository and I didn't see a fix for this off-by-one issue.

When writing parameterized tests for a custom Spliterator view, the tests failed for maps of size 1. ConcurrentHashMap trySplit will return a new Spliterator with an estimated size of zero and set the source spliterator to zero as well. The contract states that trySplit should return null in that case and leave the source spliterator unchanged. When the map is an odd size larger than 1, the two spliterators have an even estimated count. For size 3 this means that the estimate is 2. This resulted in tests with a population size of 25 to fail. These issues occur for keySet, values, and entrySet views.

To verify my expectations, I then tested with ConcurrentSkipListMap. A split always returns null and the resulting source spliterator has an estimated count of Integer.MAX_VALUE. This happens for any non-empty map. Perhaps this should have been Long.MAX_VALUE as according to the JavaDoc that indicates an infinite, unknown, or too computationally expensive size.

The JavaDoc says the estimate may be arbitrarily inaccurate. It would be nice if either the implementations were more accurate or included a comment hinting to their behavior.

@Test
public void keySpliterator_trySplit() {
  Map<Integer, Integer> map = new ConcurrentHashMap<>();
  map.put(1, 1);

  Spliterator<Integer> spliterator = map.keySet().spliterator();
  Spliterator<Integer> other = spliterator.trySplit();
  // 1. Split should return null, but is present
  // assertThat(other, is(nullValue()));

  // 2. Size should be 1, but is 0
  // int size = (int) (spliterator.estimateSize() + other.estimateSize());
  // assertThat(size, is(map.size()));
}

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CHM trySplit of a map with odd size

Doug Lea
On 02/22/2016 04:33 AM, Ben Manes wrote:

> When writing parameterized tests
> a custom Spliterator view, the tests failed for maps of size 1.
> ConcurrentHashMap trySplit will return a new Spliterator with an estimated size
> of zero and set the source spliterator to zero as well.

I believe that plain HashMap and some other classes can do this as well.
They return regions that should (statistically) hold elements but might not.
Similarly for some IO-based spliterators.

> The contract states that
> trySplit should return null in that case

It says that it must eventually return null.

>
> The JavaDoc says the estimate may be arbitrarily inaccurate. It would be nice if
> either the implementations were more accurate or included a comment hinting to
> their behavior.

That's what the SIZED characteristic is for. Non-exact spliterators
don't set SIZED.

I agree that these rules make writing unit tests more complicated, but
the underlying idea is not to force implementations to do things that
are slow or impossible for some sources or sata structures.

-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CHM trySplit of a map with odd size

Paul Sandoz

> On 22 Feb 2016, at 16:04, Doug Lea <[hidden email]> wrote:
>
> On 02/22/2016 04:33 AM, Ben Manes wrote:
>
>> When writing parameterized tests
>> a custom Spliterator view, the tests failed for maps of size 1.
>> ConcurrentHashMap trySplit will return a new Spliterator with an estimated size
>> of zero and set the source spliterator to zero as well.
>
> I believe that plain HashMap and some other classes can do this as well.
HashMap does, you are faster than me in replying :-)


> They return regions that should (statistically) hold elements but might not.

e.g. in the case of certain maps, the entry table is split in two and we don’t know which half of the table the single entry resides.

Paul.

> Similarly for some IO-based spliterators.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (858 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: CHM trySplit of a map with odd size

Ben Manes
Thanks. I realized that my unit test expectations were unreasonable and undesirable. This wasn't meant as a bug report but rather sharing my experience as an easy mistake to make. The request was that it might be beneficial to add a short bit of JavaDoc stating some of the behavior to the implementations. An additional nice to have would be a slightly stronger estimated size, if not prohibitively expensive, that matched my naive expectations in a single threaded context.


On Monday, February 22, 2016 7:44 AM, Paul Sandoz <[hidden email]> wrote:



> On 22 Feb 2016, at 16:04, Doug Lea <[hidden email]> wrote:
>
> On 02/22/2016 04:33 AM, Ben Manes wrote:
>
>> When writing parameterized tests
>> a custom Spliterator view, the tests failed for maps of size 1.
>> ConcurrentHashMap trySplit will return a new Spliterator with an estimated size
>> of zero and set the source spliterator to zero as well.
>
> I believe that plain HashMap and some other classes can do this as well.

HashMap does, you are faster than me in replying :-)


> They return regions that should (statistically) hold elements but might not.

e.g. in the case of certain maps, the entry table is split in two and we don’t know which half of the table the single entry resides.

Paul.


> Similarly for some IO-based spliterators.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (1K) Download Attachment