Showing posts with label Streams. Show all posts
Showing posts with label Streams. Show all posts

Nov 19, 2018

Hibernate Acceleration by Snapshots

A Google search for “Hibernate and performance” will yield innumerable articles describing how to fix performance issues. This post is not yet another performance improver. Instead we will demonstrate how to remove bottlenecks in your Hibernate project by using JPA support in Spring boot in tandem with in-JVM-memory snapshots which provide speedups of orders of magnitude. Let us use the Sakila sample database for the purpose of this post. The database contains, among other things, Films and Actors and relations between them.

A Straightforward Hibernate and Spring Application

A non-complicated way of interacting with a relational database is to use the Spring JPA plugin to allow Spring to handle dependency injection and setup of the project. This allows for a pure java implementation without any XML code to set up the ORM. For example, a properly annotated plain Film class is all that is needed to map the database table of films into the Java object domain.

@Entity
public class Film {
   @Id
   @Column(name="film_id")
   private int id;
   private String title;
   private String description;
   private int releaseYear;

   // ... more fields, getter and setters et c
}

The perhaps most straightforward way of retrieving such entities is by means of a Repository


@Repository
public interface FilmRepository extends CrudRepository {
}
which allows us to write an application with minimal boilerplate that operates on Films with code such as the following.

@SpringBootApplication
public class HibernateSpeedmentApplication implements CommandLineRunner {

   public static void main(String[] args) {
       SpringApplication.run(HibernateSpeedmentApplication.class, args);
   }

  @Autowired
  FilmRepository filmRepository;

  // ... code using the filmRepository
}

Here Spring helps us inject the filmRepository which can then be used as follows where we stream over all films and sum the film lengths.


public Long getTotalLengthHibernate() {
   return StreamSupport.stream(filmRepository.findAll().spliterator(), false)
       .mapToLong(com.example.hibernatespeedment.data.Film::getLength)
       .sum();
}

Clearly, this is an inefficient way of summing all the film lengths, since it entails fetching all film entities to the JVM and then summing a single property. Since we just retrieve a single value and are not interested in updating any data we would be better off with a Data Transfer Object that only contains the film length. That would require us to write some code that SELECTs the length column server side in the database. When we realize that we want some of the logic of this operation to be moved to the database, it makes a lot of sense to compute the whole sum in the database instead of transferring the film lengths. We then arrive at the following piece of code.


public Long getTotalLengthHibernateQuery() {
   EntityManager em = entityManagerFactory.createEntityManager();
   Query query = em.createQuery("SELECT SUM(length) FROM Film");
   return (Long) query.getSingleResult();
}

Now the application logic contains an explicit work split between JVM and database including a query language construct that is more or less opaque to the compiler.

Remove a Bottleneck with Speedment

While the stream construct with which we started out in the section above was very inefficient, it has appeal in the way that it abstracts away the details of the database operations. The ORM Speedment has a Streams based API allowing stream operations to be efficient. The Speedment based application code is very similar to the Hibernate example with the exception that the Repository is replaced by a Manager and this manager provides streams of entities. Thus, the corresponding Speedment application code would be as follows.

@Autowired
FilmManager filmManager;

public Long getTotalLengthSpeedment() {
   return filmManager.stream()
       .mapToLong(Film.LENGTH.asLong())
       .sum();
}

There are several advantages of deciding on the SQL details at runtime rather than in the application code, including type safety and lower maintenance cost for a more concise business logic code base. The perhaps most prominent advantage of the clean abstraction from database operations, however, is that it allows the runtime to provide acceleration. As a matter of setup configuration and with no modification of any application logic, an optional plugin to the Speedment runtime allows partial snapshots of the database to be prefetched to an in-memory data store, providing several orders of magnitude application speedup without rewriting any part of the application logic.

For this particular example, the Query based Hibernate solution was approximately 5 times faster than the naive approach of streaming over the full set of entities. The Speedment powered solution returned a result 50 times faster than the Query based Hibernate solution. If you try it out, your mileage may vary depending on setup, but clearly the in-memory snapshot will invariably be orders of magnitude faster than round tripping the database with an explicit query which in turn will be significantly faster than fetching the full table to the JVM which happens in the naive implementation.

Coexistence - Using the Right Tool for the Job

While in-memory acceleration does deliver unparallelled speed it is no panacea. For some tables, a speedup of several orders of magnitude may not yield any noticeable effect on the overall application. For other tables, querying an in-memory snapshot of data may not be acceptable due to transactional dependencies. For example, operating on a snapshot may be perfect for the whole dataset in a business intelligence system, a dashboard of KPIs or a tool for exploring historical trade data. On the other hand, the resulting balance after a bank account deposit needs to be immediately visible to the online bank and thus serving the bank account from a snapshot would be a terrible idea.

In many real-world scenarios one would need a solution where some data is served from a snapshot while data from other tables are always fetched from the database. In such a common hybrid case, the code that directly fetches data from the database may use the same Speedment API as the snapshot querying code but for projects already using Hibernate it works perfectly well to combine Speedment and Hibernate.

Since both Hibernate and Speedment rely on JDBC under the hood, they will ultimately use the same driver and may therefore work in tandem in an application. Having a Hibernate powered application, a decision to move to Speedment for bottlenecks can therefore be local to the part of the application that will benefit the most. The rest of the Hibernate application will coexist with the code that leverages Speedment.

It is easy to try this out for yourself. The Sakila database is Open Source and can be downloaded here. Speedment is available as a free version, use the Initializer to download.




Note: For the Spring autowire of the Speedment FilmManager to work, we also need a configuration class which may look as follows.

@Configuration
public class Setup {
    @Bean
    public SakilaApplication createApplication() {
        SakilaApplication app = new SakilaApplicationBuilder()
            .withBundle(DataStoreBundle.class)
            .withUsername("sakila")
            .withPassword("sakila")
            .build();
        app.getOrThrow(DataStoreComponent.class).load();
        return app;
    }

    @Bean
    public FilmManager createFilmMananger(SakilaApplication app) {
        return app.getOrThrow(FilmManager.class);
    }
}

Nov 25, 2016

Speedment 3.0 - Higher Order Functions

Generally accessible in Java 8, higher order functions open up a whole new level of abstractions allowing us to reason about code and algorithms in a new way. When our code can operate on functions as input and output we are given the power to easily express algorithms that modify behavior just like we have always done for data.

The power to create algorithms that modify behavior makes it possible to reason about functionality. Such a higher order algorithm can therefore extend or optimize the characteristic of a function, before the function receives any input.

Speedment is an Open Source ORM with an API founded in Java 8 streams. This post describes some new features of the API of recently released Speedment version 3.0 which add more features to support higher order functions. A reader already familiar with higher order functions and declarative programming may benefit from skipping ahead to the last section.

Functions Operating on Functions

To many developers, there is a fundamental difference between functions and data. A common view of a traditional program is a clear separation of the two; the program is a static structure of procedures and functions determined at compile time which operates on data, part of which typically is supplied at runtime.

For example, it is natural to have a program that prints a sorted list of names that are given as input. When compiled, the sorting function is static but can dynamically be used on any data that happens to be a list of names. If our program was to be generalized to take the actual sorting algorithm as input, we have created a higher order function since our program accepts a function as input.

Seen in such a way, functional aspects of Java are not new. Supplying a function as parameter is commonplace in Java, perhaps most notably as event driven callbacks for asynchronous interfaces. The callback idiom is a very simple type of operation on functions since the function itself is never altered - it is just kept as a reference until the time comes to call it.


Runnable callback = new Runnable() {
  @Override
  public void run() {
    System.out.println("ping");
  }
};

// Some other time, in a context far, far away...
callback.run();

The concept of higher order functions entails not only that functions can be referred to and invoked within the framework of the language itself, but also that functions are treated as other data on which other functions can operate.

The Bliss of Meta Functions

A better example of the power of functional programming in Java 8 would showcase modification of an existing behavior. Even though not obvious from syntax, the Java 8 concept of streams does exactly that. Consider the following code.

IntStream.iterate(0, i -> i + 1)
  .map(n -> n*2)
  .filter(n -> n % 10 != 0)
  .limit(10)
  .forEachOrdered(System.out::println);

A reader used to for example unix pipes would perhaps interpret this algorithm as a source of data creating an unbounded sequence of integers on line 1, doubling each number on line 2, removing the numbers evenly divisible by 10 on line 3 and then on line 4 throwing away all numbers except for the first 10 before printing them when reaching line 5. Actually quite far from what will happen when the code is executed, this is in a sense a very useful intuition.

Interpreting this example as a stream of data being manipulated from top to bottom by each operation yields a correct understanding of the resulting output while creating minimal cognitive encumbrance on the reader. It makes it possible for a reader and even the designer of the code to correctly understand the meaning of the code in terms of output without really thinking about how the expression actually will be evaluated.

What actually does happen in lines 1 through 4 is that a function is created and modified. No integers are created, let alone filtered or mapped, until we reach line 5. That last line is a terminating operation of the stream entailing that it operates on all aspects of the stream, including both the source of data and the operations to finally return the result. Having access to the information about the entire operation and the source, the terminator of the stream can deliver the result without performing unnecessary operations on items what will be discarded by the limit operation.

This lazy evaluation is possible since the program describes the requested operations rather than actually executing them. What at first may seem like a simple sequence of function invocations on a sequence of integers is actually a creation of a function that is passed to another function.

By using higher order functions we decouple the declarative description of the function from the imperative interpretation. The program simply describes what is computed while leveraging previous work invested in the design of the used stream components which determine how the computation will take place.

Functions operating on other functions allows blissful ignorance of (and therefore also decoupling from) execution details.

Parallelism as a Simple Add-on

Decoupling of algorithm from executional details is also the reason why parallelism can be so elegantly implemented for Java 8 streams. The following code will utilize available processor cores to parallelize the work of the stream.

IntStream.iterate(0, i -> i + 1)
  .parallel()
  .map(n -> n*2)
  .filter(n -> n % 10 != 0)
  .limit(10)
  .forEachOrdered(System.out::println);

This small alteration of the stream will yield fundamentally different execution characteristics. In this case, the parallel version is likely to be more wasteful than the original version. The typical implementation of a parallel stream, the Spliterator, will partition the stream of integers in chunks processed concurrently. Since several threads are helping out multiplying integers by two and filtering out numbers that are multiples of ten, the limit operation which requires synchronization between the parallel workers will be fed with more numbers than it will allow to pass through. The first non-parallel example would pull items from the source when needed, stopping just when the limit is reached.

Speedment Taking Higher Order Functions to the Extreme

Similarly to the declarative example above where the composer of the stream describes what to calculate rather than how to do it, the typical user of a relational database is used to query the database by means of the declarative language SQL. Compared to the number of software engineers that have ever designed software that uses data from a relational database, very few are actually concerned with the details of how the database engine cleverly executes the query.

An ORM provides a mapping between the data model of a relational database and the object centric view of an object oriented language such as Java. The Java 8 stream ORM Speedment provides such a mapping with a fully declarative Java 8 stream API.

As seen above, the conceptual building blocks for declarative programming of applications leveraging relational database data are available even without Speedment;

  1. the database is queried using the declarative SQL and
  2. the Java 8 streams features provide a similarly declarative approach to design of the operations on the data once retrieved to the JVM.

However, without Speedment the two declarative languages have to be mixed in an application. In a previous post on this blog we have seen that the designer has to suboptimize two separate programs; the declarative description of the data to retrieve from the database and then in a separate language the operations to perform on that data in the JVM.

The language barrier between the database engine and the JVM forces the designer to design, optimize and then maintain the structure of the data as transferred from the database since it constitutes output from the first part of the solution and input to the next. Taking the declarative approach from its starting point in two declarative building blocks all the way to its logical conclusion of a unified declarative construct, Speedment abstracts away the SQL query and allows the user of the framework to create a design based solely on streams.

Consider the fully declarative Speedment way of counting the users belonging to a particular department in the following code snippet.


long count = users.stream()
  .filter(User.DEPARTMENT.equal(1))
  .count();

The source of the stream is a manager instance called users. As described in length above, viewing a stream as a sequence of objects flowing from the source and modified on each following line will give the correct understanding of the result of the operation while not necessarily any insight to the actual execution of the program. The same applies here. Retrieving all the users from the database in line 1, then in line 2 filtering out the users belonging to department number 1 and finally counting the remaining users would yield the desired result of the operation.

This understanding of the algorithm has a strong appeal in its abstract simplicity and allows the Speedment framework to decide on all the details of the execution. Not only does Speedment optimize the operations on the data in the JVM, but since also the relational database operations are covered by the abstraction the SQL query will be created by Speedment taking the full pipeline of operations into account.

By means of a sequence of reductional operations on the pipeline Speedment will collapse the operations to a single SQL statement that relieves the JVM from any operations on user instances. The executed query will actually be as follows.


SELECT COUNT(*) FROM user WHERE (department = 1)

As showed above in the example of the parallel streams, in a declarative setting where the framework makes decisions on execution strategy it is easy to reuse a declarative program in a new setting with completely different executional properties. In its enterprise version, the Speedment framework may also chose to execute queries using data from an in-JVM memory data store, improving database latency by orders of magnitude without changing a single line of the declarative program describing the business logic.

Speedment 3.0 Structural Support for Higher Order Functions

Recently released Speedment 3.0 adds improved API support for higher order functions. While the runtime framework SQL optimization of those constructs is not yet finished, it allows design of more complex and elegant declarative programs that are prepared to be executing more efficiently in later versions of Speedment. The following code can be used to set the “category” property to 3 for all users born in a particular range of dates.

users.stream()
  .filter(User.BORN.between(1985, 1995)) // Filters out Users born 1985 up to and including 1994
  .map(User.CATEGORY.setTo(3))           // Applies a function that sets their category to 3
  .forEach(users.updater());             // Applies the updater function to the selected users
The updater construct is new in Speedment 3.0 and lends itself to executional optimization in the Speetment framework since if the preceding pipeline has suitable properties the whole update operation pipeline may be collapsed to a single SQL UPDATE statement. While version 3.0 of the framework does not perform all the possible optimizations to collapse the pipeline to a single SQL statement, the program will yield a correct result by a sequence of UPDATE operations. Another example of the extended support for higher order functions in Speedment 3.0 are the categorizers. Functions designed to work with the standard Java stream operations, the categorizers allow constructs such as the following which creates a mapping from users to their homepages assuming a homepage has a foreign key pointing to its owner.

Map<User, List<HomePage>> join = homepages.stream()
  .collect(
    groupingBy(users.finderBy(HomePage.OWNER), toList())
  );
As we have seen in two examples above, the beauty of the declarative programming paradigm is that executional properties are abstracted away. When the Speedment framework in a later version implements all the needed optimizations, existing Speedment leveraging applications will start emitting smarter SQL queries to the relational database as soon as they use the newer framework version. A dream come true from an application maintenance perspective, the declarative program describes a solution and therefore remains the same since the problem it solves is the same.

Sep 29, 2016

Java 8: Streams in Hibernate and Beyond

In version 5.2 Hibernate has moved to Java 8 as base line. Keeping up with the new functional paradigm of Java 8 with lambdas and streams, Hibernate 5.2 also supports handling a query result set as a stream. Admittedly a small addition to the API, streams add significant value by allowing the Hibernate user to leverage streams parallelism and functional programming without creating any custom adaptors.

This post will elaborate on the added superficially small but fundamentally important streams feature of Hibernate 5.2 and then discuss how the Java 8 stream ORM Speedment takes the functional paradigm further by removing the language barrier and thus enabling a clean declarative design.

The following text will assume general knowledge of relational databases and the concept of ORM in particular. Without a basic knowledge of Java 8 streams and lambdas the presentation will probably seem overly abstract since basic features will be mentioned without further elaboration.

Imperative Processing of a Query Result

To contrast different approaches to handling the data from a relational database via Hibernate, we consider an example that despite its simplicity illustrates the big picture - an HQL query produces a set of Java objects that are further processed in the JVM. We start out fully imperative and gradually move towards a declarative design.

The table we use is a table of Hares, where a Hare has a name and an id.


CREATE TABLE `hare` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(45) NOT NULL,
  PRIMARY KEY (`id`)
);

To avoid discussing the query language per se, we use an example of a simplistic HQL query that creates a result set containing all the contents of a table of the database. The naïve approach to finding the item we are looking for would be to iterate over the data of the table as follows.


List<Hare> hares = session.createQuery("SELECT h FROM Hare h", Hare.class).getResultList();
for (Hare hare : hares) {
  if (hare.getId() == 1) {
    System.out.println(hare.getName());
  }
}

Note how the design of the query result handling is fully imperative. The implementation clearly states a step-by-step instruction of how to iterate over the elements and what to do with each element. By the end of the day, when it is time to run the program, all programs are in a sense imperative since the processor will need a very explicit sequence of instrucitons to execute. The imperative approach to programming may therefore seem the most intuitive.

Declaring the Goal, Receiving the Path

In contrast to the imperative design, the declarative approach focuses on what to be done, rather than on how to do it. This does not just tend to create more concise and elegant programs, but introduces a fundamental advantage as it allows the computer to figure out the transition from what to how. Sometimes without even thinking about it, many programmers are used to this approach in the realm of relational databases since the query language SQL is one of the most popular instances of declarative programming. Relieved of the details of exactly how the database engine will retrieve the data the designer can focus on what data to get, and then of course what to do with it after it is retrieved.

Java 8 streams and lambdas allow for a declarative approach to handling collections of data. Instead of listing a sequence of instructions to be carried out, the user of a stream first creates a pipeline of abstract operations to be carried out and when presented with a terminated pipeline, the stream implementation will figure out the imperative details.

Even before Hibernate 5.2, our running example could be ported to the Java 8 domain of streams by just adding a simple method call in the chain of operations since the List itself has a stream method.


List<Hare> hares = session.createQuery("SELECT h FROM Hare h", Hare.class).getResultList();
hares.stream()
  .filter(h -> h.getId() == 1)
  .forEach(h -> System.out.println(h.getName()));

While this example may seem similar to the imperative iteration in the previous design, the fundamental difference is that this program will first create a representation of the operations to be carried out and then lazy evaluate it. Thus, nothing actually happens to the items of the List until the full pipeline is created. We express what we want in terms of a functional composition of basic operations but do not lock down any decisions about how to execute the resulting function.

Since a major feature of functional programming is the compositional design, a more typical streams approach would be to chain stepwise operations on the data. To extract the name of the item, we may map the getter on the stream as follows.


List<Hare> hares = session.createQuery("SELECT h FROM Hare h", Hare.class).getResultList();
hares.stream()
  .filter(h -> h.getId() == 1)
  .map(Hare::getName)
  .forEach(System.out::println);
This pattern is suboptimal in many aspects. The obvious problem mentioned above of not using the database to filter the data in the first place is just one of them. Another problem is that this pattern forces the entire table to be loaded in JVM memory before the iteration can start. Notice how a List of Hare is populated in the first line of each code snippet. In order to start filtering that stream, we first instantiate the entire source of the stream. This means that in terms of memory footprint, the JVM memory will have to accommodate all Hares in the database - completely defeating the purpose of analyzing a set of data piece by piece in a stream.

Streaming a Result Set

As shown in the section above, naïve streams of query results in Hibernate before version 5.2 came with a steep price. Even though the underlying JDBC database driver handles the results of a query as a result set over which the user may iterate piece by piece, streams were not supported by the query result instance, forcing the functionally inclined developer to implement a stream source from the result set or go via an intermediate collection to get a stream without custom stream implementation.

With Hibernate 5.2, the query result can produce a stream, allowing the following minimal change in code which has the important advantage of not loading the entire table into an intermediate representation from which to source the stream.


session.createQuery("SELECT h FROM Hare h", Hare.class).stream()
  .filter(h -> h.getId() == 1)
  .map(Hare::getName)
  .forEach(System.out::println);
With this improvement, Java 8 streams are efficiently supported out-of-the-box by Hibernate without creating a custom stream source from the result set.

Selection by the Source

As mentioned above, the code snippets so far illustrate the general case of an HQL query generating a result which the JVM will use for some further processing. The details of the example reveal an almost offensive lack of interest in what the database can do for the user locally in terms of filtering data and that shortcoming will be adressed in the following.

The optimization desperately needed for this code is of course to adjust the query to allow the database to create a result set closer to the desired result of the operation. Focusing on just filtering the rows of the database and leaving the extraction of the columns to the JVM, the now familiar code snippet can be updated to the following.


session.createQuery("SELECT h FROM Hare h WHERE id = 1", Hare.class).stream()
  .map(Hare::getName)
  .forEach(System.out::println);

Note that this short piece of a program contains two declarative parts that require separate design with different kinds of considerations. Since the program is divided between what happens before and after the stream is created, any optimization will have to consider what happens on both sides of that barrier.

While this indeed is considerably more elegant than the first example (which admittedly for pedagogical reasons was designed to showcase potential for improvement rather than representing a real solution to a problem), the barrier poses a fundamental problem in terms of declarative design. It can rightfully be claimed that the program still is an imperative program composed by two declarative sub routines - first execute the query and then execute the Java part of the program. We may chose to refer to this as the language barrier, since the interface between the two declarative languages creates a barrier over which functional abstraction will not take place.

Enter Speedment - Going Fully Declarative

As discussed above, the advantages of Java 8 streams extend far beyond a more elegant syntax. The appeal of the functional approach to data processing also stems from among other things,
  • the seamless generalization to parallelism (expressing a design as a pipeline of operations is a great starting point for building a set of parallel pipes),
  • design by composition (reuse and modularization of code is encouraged by a paradigm of composing solutions as a composition of smaller operations),
  • higher order functions (behavior expressed as lambdas can be used as language entities such as parameters to methods) and
  • declarative programming (the application designer focuses on what is needed, the framework or stream primitives design determines the details about how, allowing lazy evaluation and shortcuts).

We have shown how the new Hibernate API of version 5.2 adds basic support for streams, which allows for a declarative approach to describing the operations applied to the dataset retrieved from the database. While this is a fundamental insight and improvement, the Hibernate design with a foundation in an explicit query language limits the reach of the declarative features of the resulting programs due to the language barrier constituted by the interface between two languages.

The logical next step along the path from iterative to declarative design would be to break the language barrier and that is what the Java stream ORM Speedment does.

In the Speedment framework, the resulting SQL query is the responsibility of the framework. Thus, a program leveraging Speedment does not use any explicit query language. Instead, all the data operations are expressed as a pipeline of operations on a stream of data and the framework will create the SQL query. Returning to our example, a Speedment based design could be expressed as follows.


hares.stream()
  .filter(h -> h.getId() == 1)
  .map(Hare::getName)
  .forEach(System.out::println);

The hares manager is the source of the stream of Hares. No SQL will be run or even created until the pipeline of operations is terminated. In the general case, the Speedment framework cannot optimize a SQL query followed by lambda filters since the lambda may contain any functionality. Therefore, the executed SQL query for this example will be a query for all data in the Hares table since the behavior of the first filter cannot be analysed by the framework. To allow the framework to optimize the pipeline, there is a need for a data structure representing the operations in terms of basic known building blocks instead of general lambda operations. This is supported by the framework and is expressed in a program as follows.


hares.stream()
  .filter(Hare.ID.equal(1))
  .map(Hare.NAME.getter())
  .forEach(System.out::println);

The pipeline of operations is now a clean data structure declaratively describing the operations without any runnable code, in contrast to a filter with a lambda. Thus, the SQL query that will be run is no longer a selection of all items of the table, but instead a query of the type "SELECT * FROM hares WHERE ID=1". Thus, by removing the language barrier, a fully declarative design is achieved. The program states "Find me the names of the hares of the database with ID 1" and it is up to the Speedment framework and the database engine to cooperate in figuring out how to turn that program into a set of instructions to execute.

This discussion uses an very simplistic example to illustrate a general point. Please see the Speedment API Quick Start for more elaborate examples of what the framework can do.

Edit: This text is also published at DZone: Streams in Hibernate and Beyond.

Jul 25, 2016

The Way of the Lambda - Elegant and Efficient

In Java 8, you can do
items.removeIf(i -> predicate(i));
where you used to do
for (Iterator it = items.iterator(); it.hasNext();) {  
    if (predicate(it.next())) {
        it.remove();    
    }
}
which is not only considerably more elegant but also a more efficient solution in some cases. I have the graphs to prove it!

Background

Recently having spent a few years away from Java development, it is great to be back and find that Java 8 indeed has delivered on what was promised in 2013. With lambdas and streams it is possible to tackle problems in a functional manner and write code that is both readable and efficient. This over due modernization of the language is by far the most important change in Java 8, but there are also other improvements that deserve mentioning. This post elaborates on the topic of Collection.removeIf() which allows for conditional removal of elements of a collection.

The Way of the Iterator

Removing elements of a collection while iterating over it is somewhat like cutting off the branch on which you are sitting, but by using Iterators that can be done without a runtime ConcurrentModificationException. Consider the following typical simplistic example, where the elements of the collection items for which predicate() holds true are removed.
for (Iterator it = items.iterator(); it.hasNext();) {
    if (predicate(it.next())) {
        it.remove();    
    }
}
If the collection in question is a linked list of size n and m elements are removed, the full iteration with removals is O(n + m) = O(n) since iteration steps and removal from the list are constant time operations and m is limited by n. If, however, the data structure of the collection is one where removal is relatively expensive compared to iteration, the complexity becomes less favorable. For an ArrayList a single removal step is O(n) since all items at higher indices have to be moved. There are still n iteration steps to be made so the full sequence of removals becomes O(m*n) which is O(n^2) assuming worst case with the number of removals being a constant fraction of the array size.

In more pragmatic terms, what happens in the ArrayList case is that for each element that is removed, all elements of higher indices are moved to fill the gap in the backing array. This is clearly suboptimal since that operation is repeated for each removal. Thus, to reach its final destination an element will visit all locations between the starting position and the destination. In case many elements are removed, this may be a considerable amount of work in vain.

The Java 8 way of the lambda

In Java 8, the code snippet from above can be expressed as follows.
items.removeIf(i -> predicate(i));
Clearly more concise, this expression is also more efficient on an ArrayList compared to the Iterator approach. Where the Iterator requires completion of each removal operation before continuing to the next one, removeIf operates on a predicate and can therefore iterate over all items once to determine which elements are to be removed and then shift the remaining elements to the correct new indices all in a second pass. Therefore, removeIf is O(n) since it performs two linear passes through the collection.
Each retained element in the resulting collection is moved just once, while for the Iterator approach it would be moved one step at a time towards its destination. See this gist for the relevant JDK code.

The Difference Visualized

We compare execution times for the two approaches as a function of the array size for a rather extreme case where 999 out of 1000 items are removed from an ArrayList. For each data point 40 runs are made, the 5 fastest and slowest outliers are removed and the sum of the remaining 30 form the execution time value. For details please refer to this gist.

We expect the execution time to be considerably shorter for the Java 8 way of the lambda and as a matter of fact that is what we find. We also note that within the resolution of the graph, the lines are quite noise free due to the many repeats and filtering of outlier results.



For array sizes of 150,000 elements, the removeIf() approach is more than 3000 times faster. Even more importantly, the factor between the two increases as the size of the array increases which is expected since the way of the lambda has a superior asymptotical time complexity.

To better compare the time complexity of the two, we scale up the green line to match the green one. By multiplying the execution times of the faster algorithm by ~1500, the graphs can be compared in terms of shape. As expected, we find linear behavior for the Java 8 removeIf() design, while the old ways show a quadratic time complexity due to the inefficient removal of elements.


When scaling up the measurements we get to see some noise in the green line. The sensitivity to random fluctuations in execution time is greater since the execution times are several orders of magnitude shorter compared to the blue. Both lines are fitted to polynomials of power two and as can be clearly seen, the light green line is very similar to a straight line while the blue line clearly aims for the sky in a super linear fashion.

Edit: There is a reddit thread about this blog post. Good points are being made there, for example the fact that the removeIf implementation is atomic (in the database sense) as it first evaluates the predicate for all items before making any alterations to the list. Thus, if the predicate throws an exception for any of the items in the list, the list will remain unchanged.

Also published at DZone: The Way of the Lambda and removeIf().