Tag Archives: iterator

Parallel Streams and Spliterators

Today we are going to look at one of the aspects where using streams is a real win – when we need to thread work. As well as parallel streams, we will also look at Spliterators which acts as the machinery which pushes elements into the pipeline.

Streams use a technique known as internal iteration. It’s internal because the Iterator (or in our case Spliterator) which supplies work through our stream is hidden from us. To use a stream all we need do [once we have a source] is add the stages of the pipeline and supply the functions that these stages require. We don’t need to know how the data is being passed along the pipeline, just that it is. The benefit is that the workings are hidden from us and we can focus more on the work that must be done rather than how it can be done.

The opposite, external iteration is where we are given a loop variable or iterator and we look up the value, and pass it through the code ourselves. This obviously gives us a benefit in that have full control and low overhead. The downside is we have to do all the work looking up the values and passing them through the loop body. This will also mean more test code, and testing loop bodies properly can be tricky. With normal for-loops we also have to be careful of one-off errors.

The question we need to ask ourselves when considering the iteration method: Do we really need absolute control for the task? Streams do some things really well but come with a small performance penalty. Perhaps a non-stream (or even non-Java) solution is more appropriate for high performance work. On the other hand, sorting and filtering files to display in say a ‘recently accessed’ menu item doesn’t require high performance. In that case we’d probably settle for an easy and quick way to do it rather than the best performing one. Even if we go with a performant solution some benchmarking will be necessary as surprises often await. Thus we’re trading convenience off against performance, development time and risk of bugs.

Streams are easy to parallelise as we’ll see. We just change the type of the stream to a parallel stream using the parallel() operator. To do this with internal iteration is hard because it’s set up that we get one item per iteration. The best we can do in that environment is pass work off to threads. To do things efficiently we’d probably have to ditch looping through all the values in the outer loop and look at dividing the work up another way. We’ll see a way of doing this.

With that in mind we’ll look at a prime number generator. First this is not the most efficient prime number generator. For a demonstration it was useful to have an application that was well known, easy to understand, easy to perform with streams and would take a fair bit of computation time to complete.

Let’s look at the internal iteration version first:

EDIT: It’s been pointed out that the simple test (i % j == 0) is better than (i / j * j == i)

public class ForLoopPrimes
{
  public static Set<Integer> findPrimes(int maxPrimeTry)
  {
    Set<Integer> s = new HashSet<>();

    // The candidates to try (1 is not a prime number by definition!)
    outer:
    for (int i = 2; i <= maxPrimeTry; i++)
    {
      // Only need to try up to sqrt(i) - see notes
      int maxJ = (int) Math.sqrt(i);

      // Our divisor candidates
      for (int j = 2; j <= maxJ; j++)
      {
        // If we can divide exactly by j, i is not prime
        if (i / j * j == i)
        {
          continue outer;
        }
      }

      // If we got here, it's prime
      s.add(i);
    }

    return s;
  }

  public static void main(String args[])
  {
     int maxPrimeTry = 9999999;

     long startTime = System.currentTimeMillis();

     Set<Integer> s = findPrimes(maxPrimeTry);

     long timeTaken = System.currentTimeMillis() - startTime;

     s.stream().sorted().forEach(System.out::println);

     System.out.println("Time taken: " + timeTaken);
  }
}

Note: Since we only need to find one divisor, and multiplication is commutative, we only need to exhaust all potential pairs of factors and test one of them [the smaller]. The smaller can’t be any bigger than the square root of the candidate prime and must be at least 2.

This is an example of a brute force algorithm. We’re trying every combination rather than using any stealth or optimisation. We’d also in this case expect the internal iteration version to run fast since there is not a lot of work per iteration.

So why do we have to demonstrate this?

Suppose we want to take advantage of hardware in modern processors and thread this up. How might we do it? Up to Java 7 and certainly before Java 5 this would have been a real pain. We’ve got to divide up the workload, maintain a pool of threads and signal them that there is work available and then collect the work back from them when done. We probably also want to shut the worker threads down at the end if we have any more work to do. While it’s not rocket science, it can be hard to get right quickly and subtle bugs can be hard to spot.

Java 7 makes this a lot easier with the ForkJoin framework. It’s still tricky and easy to get wrong. We’ll use a RecursiveAction to break up the outer loop into pieces of work using a divide-and-conqueror strategy. Note that parallel streams do this as well.

public class ForkJoinPrimes
{
  private static int workSize;
  private static Queue<Results> resultsQueue;

  // Use this to collect work
  private static class Results
  {
    public final int minPrimeTry;
    public final int maxPrimeTry;
    public final Set resultSet;

    public Results(int minPrimeTry, int maxPrimeTry, Set resultSet)
    {
      this.minPrimeTry = minPrimeTry;
      this.maxPrimeTry = maxPrimeTry;
      this.resultSet = resultSet;
    }
  }

  private static class FindPrimes extends RecursiveAction
  {
    private final int start;
    private final int end;

    public FindPrimes(int start, int end)
    {
      this.start = start;
      this.end = end;
    }

    private Set<Integer> findPrimes(int minPrimeTry,
                                    int maxPrimeTry)
    {
      Set<Integer> s = new HashSet<>();

      // The candidates to try
      // (1 is not a prime number by definition!)
      outer:
      for (int i = minPrimeTry; i <= maxPrimeTry; i++)
      {
        // Only need to try up to sqrt(i) - see notes
        int maxJ = (int) Math.sqrt(i);

        // Our divisor candidates
        for (int j = 2; j <= maxJ; j++)
        {
          // If we can divide exactly by j, i is not prime
          if (i / j * j == i)
          {
            continue outer;
          }
        }

        // If we got here, it's prime
        s.add(i);
      }

      return s;
    }

    protected void compute()
    {
      // Small enough for us?
      if (end - start < workSize)
      {
        resultsQueue.offer(new Results(start, end,
                                 findPrimes(start, end)));
      }
      else
      {
        // Divide into two pieces
        int mid = (start + end) / 2;

        invokeAll(new FindPrimes(start, mid),
                            new FindPrimes(mid + 1, end));
      }
    }
  }

  public static void main(String args[])
  {
    int maxPrimeTry = 9999999;
    int maxWorkDivisor = 8;

    workSize = (maxPrimeTry + 1) / maxWorkDivisor;

    ForkJoinPool pool = new ForkJoinPool();

    resultsQueue = new ConcurrentLinkedQueue<>();

    long startTime = System.currentTimeMillis();

    pool.invoke(new FindPrimes(2, maxPrimeTry));

    long timeTaken = System.currentTimeMillis() - startTime;

    System.out.println("Number of tasks executed: " +
                       resultsQueue.size());

    while (resultsQueue.size() > 0)
    {
      Results results = resultsQueue.poll();

      Set<Integer> s = results.resultSet;

      s.stream().sorted().forEach(System.out::println);
    }

    System.out.println("Time taken: " + timeTaken);
  }
}

This is quite recognisable since we have reused the sequential code to carry out the work in a subtask. We create two RecursiveActons to break the workload into two pieces. We keep breaking down until the workload is below a certain size when we carry out the action. We finally collect our results on a concurrent queue. Note there is a fair bit of code.

Let’s look at a sequential Java 8 streams solution:

public class SequentialStreamPrimes
{
  public static Set<Integer> findPrimes(int maxPrimeTry)
  {
    return IntStream.rangeClosed(2, maxPrimeTry)
                    .map(i -> IntStream.rangeClosed(2,
                                          (int) (Math.sqrt(i)))
                    .filter(j -> i / j * j == i).map(j -> 0)
                    .findAny().orElse(i))
                    .filter(i -> i != 0)
                    .mapToObj(i -> Integer.valueOf(i))
                    .collect(Collectors.toSet());
  }

  public static void main(String args[])
  {
    int maxPrimeTry = 9999999;

    long startTime = System.currentTimeMillis();

    Set<Integer> s = findPrimes(maxPrimeTry);

    long timeTaken = System.currentTimeMillis() - startTime;

    s.stream().sorted().forEach(System.out::println);

    System.out.println("Time taken: " + timeTaken);
  }
}

EDIT: A better and quicker version was posted on DZone by Tom De Greyt. Out of courtesy I’ve asked for permission to repost his solution rather than just add it here, but it would also serve as a good exercise for the reader to try to find it. Hint: it involves a noneMatch. If you want to see it, it’s in the comments on the link but it would be beneficial to try to spend a few minutes to find it first.

We can see the streams solution matches up with the external iteration version quite well except for a few tricks needed:

  • Since we only need one factor we use findAny(). This acts like the break statement.
  • findAny() returns an Optional so we need to unwrap it to get our value. If we have no value (i.e. we found a prime) we will store the prime (the outer value, i) by putting it in the orElse clause.
  • If the inner IntStream finds a factor, we can map to 0 which we can filter out before storing.

So let’s make it threaded. We only need to change the findPrimes method slightly:

  public static Set<Integer> findPrimes(int maxPrimeTry)
  {
    return IntStream.rangeClosed(2, maxPrimeTry)
                    .parallel()
                    .map(i -> IntStream.rangeClosed(2,
                                          (int) (Math.sqrt(i)))
                    .filter(j -> i / j * j == i).map(j -> 0)
                    .findAny().orElse(i))
                    .filter(i -> i != 0)
                    .mapToObj(i -> Integer.valueOf(i))
                    .collect(Collectors.toSet());
  }

This time we don’t have to mess around with the algorithm. Simply by adding an intermediate stage parallel() to the stream we make it divide up the work. Parallel(), like filter and map, is an intermediate operation. Intermediate operations can also change the behaviour of a stream as well as affect the passing values. Other intermediate stages we’re not seen yet are:

  • sequential() – make the stream sequential
  • distinct() – only distinct values pass
  • sorted() – a sorted stream is returned, optionally we can pass a Comparator
  • unordered() – return an unordered stream

If we fire up jconsole while we’re running and look at the Threads tab, we can compare the sequential and parallel version. In the parallel version we can see several ForkJoin threads doing the work.

I did some timings and got the following results [note this is not completely accurate since other tasks might have been running in the background on my machine – values are to the nearest half-second].

  • External, sequential (for-loop): 8.5 seconds
  • External, parallel (ForkJoin): 2.5 second
  • Internal, sequential (sequential stream): 21 seconds
  • Internal, parallel (parallel stream): 6 seconds

This is probably as expected. The amount of work per iteration in the inner loop is low, so any stream actions will have relatively high overhead as seen in the sequential stream version. The parallel stream comes in slightly faster than the for-loop, but the ForkJoin version outperforms it by a factor of more than 2. Note how simpler the streams version was [once we get the hang of streams of course] compared to the amount of code in the ForkJoin version.

Let’s have a look at the work-horse of this work distribution, the Spliterator. A Spliterator is an interface like an Iterator, but instead of just providing the next value, it can also divide work up into smaller pieces which are executed by ForkJoinTasks.

When we create a Spliterator we provide details of the size of the workload and characteristics that the values have. Some types of Spliterators such as RangeIntSpliterator [which IntRange supplies] use the characteristics() method to return characteristics, rather than having them supplied via a constructor like AbstractSpliterator does.

We obviously need the size of the workload so we can divide up the work up and know when to stop dividing. The characteristics we can supply are defined in the Spliterator interface as follows:

SIZED – we can supply a specific number of values that will be sent prior to processing (versus an InfiniteSupplyingSpliterator)
SUBSIZED – implies that any Spliterators that trySplit() creates will be SIZED and SUBSIZED. Not all SIZED Spliterators will split into SUBSIZED spliterators. The API gives an example of a binary tree where we might know how many elements are in the tree, but not in the sub-trees
ORDERED – we supply the values in sequence, for example from a list
SORTED – the order follows a sort order (rather than sequence); ORDERED must also be set
DISTINCT – each value is different from every other, for example if we supply from a set
NONNULL – values coming from the source will not be null
IMMUTABLE – it’s impossible to change the source (such as add or remove values) – if this is not set and neither is CONCURRENT we’re advised to check the documentation for what happens on modification (such as a ConcurrentModificationException)
CONCURRENT – the source may be concurrently modified safely and we’re advised to check the documentation on the policy

These characteristics are used by the splitting machinery, for example in the ForEachOps class (which is used to carry out tasks in a pipeline terminated with a forEach). Normally we can just use a pre-built Spliterator [and often don’t even need to worry about that because it’s supplied by the stream() method]. Remember the streams framework allows us to get work done without having to know all the details of how its being done. It’s only in the rare cases of a special problem or needing maximum performance do we have to worry.

Splitting is done by the trySplit() operation. This returns a new Spliterator. For the requirements of this function the API documentation should be referred to.

When we consume the contents of [part of] the stream in bulk using the Spliterator, the forEachRemaining(action) operation is called. This takes source data and calls the next action via the action’s accept call. For example if the next operation is filter, the accept call on filter is called. This calls the test method of the contained predicate, and if that is true, the accept method of the next stage is called. At some point a terminal stage will be called [the accept method calls no other stage] and the final value will be consumed, reduced or collected. When we call a stream() method, this pipeline is created and calling intermediate stages chains them to the end of the pipeline. Calling the final consuming stage makes the final link and sets everything off.

Alternatively when we need to generate each element from a non-bulk source, the tryAdvance() function is used. This is passed an action which accept is called on as before. However, we return true if we want to continue and false if we don’t. InfiniteSupplyingSpliterator for example always returns true, but we can use an AbstractSpliterator if we want to control this. Remember the AbstractIntSpliterator from our SixGame in the finite generators article? One of our tryAdvance functions was this:

@Override
public boolean tryAdvance(Consumer action)
{
  if (action == null)
    throw new NullPointerException();
  if (done)
    return false;

  action.accept(rollDie());

  return true;
}

In this case if we roll the die we always continue. This would allow the done logic to be set from elsewhere if we didn’t want to roll a die again. It might have been slightly better to have returned !done instead of true to terminate generation immediately as soon as the six was thrown. However in this case going through another cycle was hardly a chore.

That’s it for the streams overview. In the next article we’ll look a bit more at lambda expressions.

Finite sequence generators in Java 8

… and introducing default methods.

Last time we looked at generators, and more specifically those generating an infinite sequence. We saw that there were several ways to achieve this:

  • The older Java 7 way with an iterator like class
  • Using Stream’s iterate method
  • Using Stream’s generate method

We also saw that when using a Stream we had to use the limit method on our infinite sequence otherwise it would keep generating and the program couldn’t continue. The problem with using limit was that once we’d got the values, we couldn’t use the stream again to get more. To solve this problem, we used an IntSupplier and created several streams with it to process batches of values.

What if the sequence we wanted to process was finite. We want to avoid buffering up values in advance. We also want to consume the sequence without knowing up front how many values it will return because of reasons such as:

  • We can’t work it out or it’s difficult to
  • There is a random element
  • We want to decouple the generating function from stream doing the consuming

We saw a simple finite sequence with our Hello World! example in the first article. In this case we were not generating the sequence with a function, we were instead processing a pre-initialised list. We also saw we could use an iterator when we discussed infinite sequences, but went on to discuss other ways. We’ll see that in this case, we are virtually forced into the Iterator solution.

Let’s take a simple sequence which we can’t know the length of. We’ll simulate a game where the idea is to keeping throwing a die until we get a six. First we’ll start with a non-functional implementation:

public class SixGame
{
	public static class DieThrowIterator implements Iterator<Integer>
	{
		private int dieThrow = 0;
		private Random rand = new Random(System.nanoTime());

		@Override
		public boolean hasNext()
		{
			return dieThrow != 6;
		}

		@Override
		public Integer next()
		{
			dieThrow = Math.abs(rand.nextInt()) % 6 + 1;
			return dieThrow;
		}
	}

	public static void main(String args[])
	{
		DieThrowIterator dieThrowIterator = new DieThrowIterator();

		while (dieThrowIterator.hasNext())
		{
			System.out.println("You threw a " + dieThrowIterator
                                  .next());
		}
	}
}

(Note our random number generation is not very robust, but for a simple demonstration it will do).

Let’s try to use a Stream. We can’t use Stream’s iterate function because it doesn’t allow a stop condition. Also an IntSupplier with generate is not an option unless we want to use limit(1) and create a stream for each die throw, when we might as well not use a stream at all.

If we look under the hood at the implementation of IntStream’s generate function we see that it creates an InfiniteSupplyingSpliterator. This has a problem for us – the tryAdvance function always returns true meaning we can never stop.

We could implement our own Spliterator where our tryAdvance checks for a stop condition. We can’t simply extend InfiniteSupplyingSpliterator and override the tryAdvance method since it’s an inner class of a default access class. So the only way is a cut and paste job rather than inheritance. I’m very nervous about copying large parts of code which might change in future versions; this is saying to me it’s not what was intended. We should look for other ways first.

Let’s look to see how List does its streaming. List’s streaming comes from inheriting Iterable. To create an Iterable we only need to implement its iterator() function – for the example let’s do so as an inner-class:

	public static class DieThrowIterable implements Iterable<Integer>
	{
		@Override
		public Iterator<Integer> iterator()
		{
			return new DieThrowIterator();
		}
	}

We can then stream:

	public static void main(String args[])
	{
		Stream<Integer> stream = StreamSupport.stream(
				new DieThrowIterable().spliterator(), false);

		stream.map(i -> "You threw a " + i).forEach(System.out::println);
	}

Wait a moment… Iterable is an interface, yet it has a spliterator() method implemented. How can that be?

If we look at the interface, there is indeed a spliterator() method creating a new spliterator for us. If we also look closely, we see the default keyword. This was added in Java 8 (cunningly default is already a reserved word for switch statements so it won’t break old code). When we write interfaces we can provide default methods already implemented. Now some people might have reservations about this as it’s turning an interface in to effectively an abstract class. There are some good reasons and advantages this gives us:

  • It avoids having to create abstract classes to implement interfaces to supply default methods. Thus there is less boiler-plate to write, and also prevents the consumer of the API implementing the interface when we expected the abstract class to be used instead.

  • It helps with multiple inheritance issues (inherting from two or more classes which C++ supports, but not Java). In Java, the problems with multiple inheritance were avoided by allowing only single inheritance from classes, but we can implement as many interfaces as desired. Problem is we had to implement large portions of those interfaces in each class that used them – a real pain.

  • Our API vendors can also now add new methods to interfaces without breaking old code. This is one reason we see a default method here. A new interface would make the JDK even larger and make things more complicated.

  • Lambda expressions bind to interfaces with one single method left to implement. If there were more we couldn’t do this binding. We’ll look at this in a future article.

Note: If we implement more than one interface with an identical default method, and we do not override it by implementing in the class or a parent class, this is an error. Whether eventually it’ll be possible to use Scala-like mix-in traits is an interesting question.

So using Iterable is one way to do finite sequence generators, although the documentation accompanying the default spliterator() method suggests it should be overridden for better performance. In a later article we’ll come back and look at spliterators in some more detail.

In the next article we’ll look another couple of ways to implement finite sequence generators, one good, and one we should avoid.

Generators with Java 8

Today we’ll look at creating generators. In simple terms, a generator is a function which returns the next value in a sequence. Unlike an iterator, it generates the next value when needed, rather than returning the next item of a pre-generated collection. Some languages such as Python support generators natively via keywords such as yield. When a generator’s next value is requested in Python, the generator function continues to run until the next yield statement, where a value is returned. The generator function is able to continue where it left off which can be quite confusing for the uninitiated. So how to do something similar in Java?

We saw in the last article that we can use an IntStream to generate a simple set of numbers, but we had to generate them all up front. That’s fine if we know how many we’re going to need. What if we don’t, and we want to be able to get the next whenever we like? This is where a generator comes in.

Let’s choose a simple infinite sequence, the square numbers. In a standard Java implementation we’d end up with something like the following:

public class Squares
{
        private int i = 1;

        public int next()
        {
                int thisOne = i++;
                return thisOne * thisOne;
        }

        public static void main(String args[])
        {
                Squares squareGenerator = new Squares();

                System.out.println(squareGenerator.next());
                System.out.println(squareGenerator.next());
                System.out.println(squareGenerator.next());
        }
}

This prints the first three square numbers. Note we could have gone further and implemented this as an iterator.

What we have here is an example of lazy evaluation in a non-functional style. Wikipedia defines lazy evaluation as: ‘In programming language theory, lazy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed’. Lazy evaluation is useful because we don’t need to worry about infinite sequences, performing computationally expensive operations up-front, and about storage.

Let’s expand on the example to allow getting a batch of results. This is easy – create a nextN function which calls next() a number of times and returns the results in say a List:

public class Squares2
{
        private int i = 1;

        public int next()
        {
                int thisOne = i++;
                return thisOne * thisOne;
        }

        public List<Integer> nextN(int n)
        {
                List<Integer> l = new ArrayList<>();

                for (int i = 0; i < n; i++)
                {
                        l.add(next());
                }

                return l;
        }

        public static void main(String args[])
        {
                Squares2 squareGenerator = new Squares2();

                squareGenerator.nextN(10).forEach(System.out::println);
        }
}

A few points:

  • Notice in the nextN function there is the empty diamond in the new ArrayList statement. This was added in Java 7 to save having to state the type both on the left and the right hand side; the compiler now works it out.
  • List is an Iterable, and Iterable now has a forEach() method which was added in Java 8. We could use stream() as before to create a stream, but if all we want to do is pass the contents to a function forEach() does nicely.

Now, to save having to write nextN for every sequence we make, we could create a new type which extends Iterator providing the nextN function.

The only problem we face here is that we have to save the batch in a list before we can operate on it. Java 8 provides another way. Let’s go back and start again with the following code:

public class Squares3
{
        public static void main(String args[])
        {
                IntStream.rangeClosed(1, 10).map(i -> i * i)
                         .forEach(System.out::println);
        }
}

This uses IntStream to get the indexes of the sequence in a stream and calls map to convert them into their squares. The problem is that to get more squares than the tenth we need to duplicate the pipeline and start it off from the right place. Let’s look at another way without using a range:


        public static void main(String args[])
        {
                IntStream myStream = IntStream.iterate(1, i -> i + 1);

                myStream.limit(10).map(i -> i * i)
                                  .forEach(System.out::println);
        }

This also generates the first 10 square numbers. This time it uses the iterate function. This takes two parameters, the first is our initial value, and the second is a function defining how to get to the next value from the previous. It’s a good place to use a lambda function. We can even dispense of the map function since we can undo squaring easily in iterate to get what the last index was:

        public static void main(String args[])
        {
                IntStream myStream = IntStream.iterate(1,
                        i -> ((int) Math.pow(Math.sqrt(i) + 1, 2)));

                myStream.limit(10).forEach(System.out::println);
        }

This solves one of the problems of having to buffer beforehand. However, we need to use the limit operator on the stream to limit it to 10 items, otherwise it would keep on going. Unfortunately this is a problem, since once we’ve got the 10 the stream is ‘operated on’ and we can’t use it again to generate more. If we try, we get an IllegalStateException. We’d have to create another stream to get more.

So how do we get around the problem of the stream being used up? Instead of using IntStream’s iterate function, we can use generate instead. IntStream’s generate function takes an instance of an IntSupplier. IntSupplier has a getAsInt() function which returns the next int in the sequence which is very much like our next() function. Here is an example that prints the first 20 square numbers in two batches:

public class SquaresGenerator
{
        private static class SqSupplier implements IntSupplier
        {
                int i = 0;

                @Override
                public int getAsInt()
                {
                        i++;
                        return i * i;
                }
        }

        public static void main(String args[])
        {
                SqSupplier sqSupplier = new SqSupplier();
                IntStream myStream = IntStream.generate(sqSupplier);
                IntStream myStream2 = IntStream.generate(sqSupplier);

                myStream.limit(10).forEach(System.out::println);
                myStream2.limit(10).forEach(System.out::println);
        }
}

Again we’re using limit to stop the stream continuing indefinitely. However unlike last time, although the stream is used up, the generator still survives and can be used again. No buffering needed either, just keeping hold of the supplier. The only downside vs the old Java way is that we have to use Streams to get sequence members, although this comes with other benefits such as parallelism which we’ll see in a later article.

Overall, there are several ways to generate a sequence and which we chose may depend on our needs. Using an IntSupplier is a good way to integrate with the rest of the Java 8 functional programming support.