Spliterator.tryAdvance

[Remi Forax]

On 02/12/2013 01:52 PM, Doug Lea wrote:
> On 02/11/13 10:34, Remi Forax wrote:
>> There is another point,
>> the specification should be relatex to allow tryAdvance to not always 
>> call the
>> consumer taken as parameter.
>
> These are all the same issue in disguise (including the one
> you mentioned that I didn't get :-)

CHM.search is different from the proposed Spliterator.tryAdvance that 
returns a value because tryAdvance never consumes more than one element, 
just one in gfact. With that, you can use a well known value to say, 
I've done nothing and doesn't need to rely on "null" means nothing.

>
> The question is: Can you design Spliterators and/or
> related leaf-computation-level support such that none
> of the "basic" Stream ops require use of a lambda / inner class
> that needs a mutable variable?

yes !

>
> I took this path in ConcurrentHashMap
> (see 
> http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/ConcurrentHashMap.html), 
> resulting in 4 "basic" methods
> (plus 3 more for primitives). I think it is the right solution
> for CHM, but it cannot apply to Streams (CHM can rely on
> nullness, and imposes requirement that users pre-fuse multiple
> map and map-reduce ops, etc.)
>
> And if you explore what it would take to do this for the
> Stream API, it gets quickly out of hand -- at least
> a dozen or so operations that every Collection, Map, or
> other Stream/Spliterator source author would have to write.
> Which led to the present solution of only requiring
> forEach, trySplit, and tryAdvance.

forEach, tryAvance that rely on side effect is not that bad for leaf of 
a forkjoin because by design forkjoin put variables into fields. But for 
a serial stream, forcing values to be stored in fields instead of on 
stack or in register is really a bad idea from a perf point of view.

pre-fuse operations try to tackle another problem, the fact that calling 
the lambda are megamorphic.
This can be solved in the stream by having dedicated path or generating 
one code for the whole pipeline.

Here, we are talking about the spliterator interface, no other interface,
IMO, the spliterator interface should have 3 operations:
   void forEach(Consumer),
   Object tryAdvance(Object, Function<T,Object>) that take an element 
and try to call function on it and
   U reduce(U, Function<T,U>)
   (and reduceInt/reduceLong/reduceDouble).

   /**
    * Sentinel value used by tryAdvance to signal that there is no more 
element.
    */
   public static final Object END = new Object();

    /**
      * If no remaining element exists, tryAdvance returns {@code END}.
      * If a remaining element exists, tryAdvance will try to performs 
the given action on it,
      * if the remaining element is filtered out, then the value noValue 
taken as parameter is returned
      * else the action is called with the remaining element.
      *
      * @param noValue a value returned is the element is filtered out
      * @param action the action to perform.
      * @return {@code END} if no remaining elements existed
      * upon entry to this method, else the return value of the action.
      */
    Object tryAdvance(Object noValue, Function<? super T, ?> action);

so yes, there are more method to implement but you can use lambdas fof 
most of the basic operations instead of using inner classes. So I'm not 
sure it's more cumbersome.

>
> -Doug

Rémi

>
>>
>> If by example, I want to implements a Spliterator that filter the 
>> elements,
>> this implementation should be legal:
>>
>> class FilterSpliterator implements Spliterator {
>>    private final Spliterator spliterator;
>>    private final Predicate predicate;
>>
>>    public FilterSpliterator(Spliterator spliterator, Predicate 
>> predicate) {
>>       ....
>>    }
>>
>>    public void tryAdvance(Consumer consumer) {
>>       spliterator.tryAdvance(element -> {
>>          if (predicate.test(element)) {
>>            consumer.accept(element);
>>          }
>>       });
>>    }
>> }
>>
>> otherwise, you have to use a while loop around spliterator.tryAdvance 
>> but
>> because there is  no way to transmit the information that the element is
>> accepted or not
>> (see my previous mail), you can not use a lambda here and you have to 
>> rely on an
>> inner class.
>>
>> cheers,
>> Rémi
>>
>
>