Spliterator for immutable linked list

Question

This is a 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 parallelizing:

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 parallelizing?

Answer 1

The spliterators which cannot report even the estimated size (which is default implementation for Iterable) are poorly split by parallel pipeline. You can fix this issue if you track the size of the List. In your case it's not very hard 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 would work better. Note that it's still poor man parallelization, because you cannot quickly jump to the middle of the list, but in many cases it will provide a reasonable speed-up.

Also note that it's better to explicitly specify the Spliterator.ORDERED characteristic. Otherwise the order may be ignored in parallel stream operations even if it's explicitly requested (for example, by forEachOrdered() terminal operation).

Answer 2

You might use some algorithm with interleaving - e.g., counting the elements and using remainder after integer division. That could split the elements for parallel iteration.

You could also iterate once before the iterator is even constructed, to split the list into intervals, but that would beat the purpose of stream - e.g. if you use it for anyMatch, it will slow you a lot.

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

Edit: Oh wait - you only implement Iterable. That is quite limiting, you have to come up with an algorithm that only has one pass. That means, the splitting itself won't be parallel at all, so you might as well enforce your parallelism elsewhere in the process.