Separator for immutable linked list

Question

This is the classic implementation of an immutable linked list:

public abstract class List<A> implements Iterable<A> { private static final List NIL = new Nil(); public abstract A head(); public abstract List<A> tail(); public List<A> cons(A a) { return new Cons<>(a, this); } public static <A> List<A> nil() { return NIL; } @Override public Iterator<A> iterator() { return new Iterator<A>() { private List<A> list = List.this; @Override public boolean hasNext() { return list != NIL; } @Override public A next() { A n = list.head(); list = list.tail(); return n; } }; } public Stream<A> stream() { return StreamSupport.stream(spliterator(), false); } public Stream<A> parallelStream() { return StreamSupport.stream(spliterator(), true); } } class Nil extends List { @Override public Object head() { throw new NoSuchElementException(); } @Override public List tail() { throw new NoSuchElementException(); } } class Cons<A> extends List<A> { private final A head; private final List<A> tail; Cons(A head, List<A> tail) { this.head = head; this.tail = tail; } @Override public A head() { return head; } @Override public List<A> tail() { return tail; } } 

The default implementation of spliterator() does not support efficient parallelization:

 List<Integer> list = List.<Integer> nil().cons(3).cons(2).cons(1); list.parallelStream().forEach(i -> { System.out.println(i); try { Thread.sleep(1000); } catch (Exception e) { e.printStackTrace(); } }); 

This will print 1, 2, 3 sequentially.

How to implement spliterator() to support efficient parallelization?

Answer 1

Separators that cannot even give an approximate size (which is the default implementation for Iterable ) are loosely separated by a parallel pipeline. You can fix this problem if you track the size of the List . In your case, it’s not very difficult to track the exact size:

 public abstract class List<A> implements Iterable<A> { ... public abstract long size(); @Override public Spliterator<A> spliterator() { return Spliterators.spliterator(iterator(), size(), Spliterator.ORDERED); } } class Nil extends List { ... public long size() { return 0; } } class Cons<A> extends List<A> { ... private final long size; Cons(A head, List<A> tail) { this.head = head; this.tail = tail; this.size = tail.size()+1; } ... @Override public long size() { return size; } } 

After that, parallelization will work better. Please note that this is still a poor parallelization of people, because you cannot quickly jump to the middle of the list, but in many cases this will provide reasonable acceleration.

Also note that it is better to explicitly specify the Spliterator.ORDERED attribute. Otherwise, the order may be ignored in parallel streaming operations, even if it is explicitly requested (for example, with the forEachOrdered() operation).

Answer 2

You can use some alternating algorithm - for example, counting elements and using the remainder after integer division. This can lead to the separation of elements for parallel iteration.

You can also iterate before the iterator is constructed to split the list into intervals, but this will exceed the purpose of the stream. if you use it for anyMatch , it will slow you down a lot.

There is not a very efficient way to split a linked list (in less than linear time) unless you create your own implementation of a linked list that has additional information.

Edit: Oh wait - you only implement Iterable . This is quite limiting; you have to come up with an algorithm that has only one pass. This means that splitting itself will not be parallel, so you could also apply your parallelism elsewhere in the process.