DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
Building Scalable Real-Time Apps with AstraDB and Vaadin
Register Now

Trending

  • 4 Expert Tips for High Availability and Disaster Recovery of Your Cloud Deployment
  • Database Integration Tests With Spring Boot and Testcontainers
  • Building the World's Most Resilient To-Do List Application With Node.js, K8s, and Distributed SQL
  • What Is Envoy Proxy?

Trending

  • 4 Expert Tips for High Availability and Disaster Recovery of Your Cloud Deployment
  • Database Integration Tests With Spring Boot and Testcontainers
  • Building the World's Most Resilient To-Do List Application With Node.js, K8s, and Distributed SQL
  • What Is Envoy Proxy?
  1. DZone
  2. Data Engineering
  3. Data
  4. Benchmarking Java Lists Performance

Benchmarking Java Lists Performance

LinkedList is slightly slower than ArrayList with adding items to the end of the list. It is also slower when retrieving items with an index (random access).

Jay Sridhar user avatar by
Jay Sridhar
CORE ·
Mar. 07, 17 · Opinion
Like (10)
Save
Tweet
Share
19.80K Views

Join the DZone community and get the full member experience.

Join For Free

Let's examine the performance characteristics of the list implementations ArrayList and LinkedList. We perform the testing for a variety of list sizes from 100 items to 1M items. We use the JMH test harness to conduct the test on a single core machine. The results are presented below.

ArrayList Add Performance

This test measures the performance of creating the list and populating the list for a specified number of items. The test code is shown below — nothing fancy. A specified number of integers is created using the Random class and collecting them into a particular type of List. For this test, we have included ArrayList, LinkedList, and Vector.

@State(Scope.Thread)
static public class MyState {
 @Param("100")
 public int NSIZE;
}

@Benchmark
public void test_createArrayList(MyState state) {
 Random random = new Random();
 List < Integer > list = random
  .ints(state.NSIZE)
  .collect(ArrayList::new, List::add, List::addAll);
}

@Benchmark
public void test_createLinkedList(MyState state) {
 Random random = new Random();
 List < Integer > list = random
  .ints(state.NSIZE)
  .collect(LinkedList::new, List::add, List::addAll);
}

@Benchmark
public void test_createVector(MyState state) {
 Random random = new Random();
 List < Integer > list = random
  .ints(state.NSIZE)
  .collect(Vector::new, List::add, List::addAll);
}

The performance of the operation is shown below. As mentioned before, we tested from 100 through 1M items as shown on the X-axis. The Y-axis is the throughput in ops per second and is shown in log scale since there is a steep drop-off as the size increases.

There are a couple of conclusions we can draw from this graph. As always, results are specific for this run of the code. (In other words, your mileage may vary.)

  1. LinkedList adding is slower as the number of items increases.
  2. There's no perceptible difference between ArrayList and Vector.

arraylist linkedlist benchmark performance in create and add.

ArrayList Loop Performance

Let's now check the performance of the ArrayList in a loop. Since iterating over a List is one of the most important operations in programs in general, this aspect is quite important.

We have tested the following ways of iterating a list. The code loops over a List and fetches each item; thus, it represents reasonably real-world code.

Enhanced For-Each

This is a simple for-each loop. To prevent the JVM for optimizing the code out of existence, we maintain a loop variable, increment it each loop, and return it.

@Benchmark
public int test_forEach(MyState state) {
    int n = 0 ;
    for (int num : state.list) {
    n++;
    }
    return n;
}

A Regular Indexed for Loop

This loop iterates over all elements in order and fetches each element.

@Benchmark
public int test_forLoop(MyState state) {
    int n = 0;
    for (int i = 0 ; i < state.list.size() ; i++) {
    int value = state.list.get(i);
    n++;
    }
    return n;
}

Loop With Iterator

This loop uses the normal Collection.iterator method to retrieve an iterator and fetches the item from it.

@Benchmark
public int test_iterator(MyState state) {
    int n = 0;
    for (Iterator<Integer> it=state.list.iterator(); it.hasNext(); ) {
    int num = it.next();
    n++;
    }
    return n;
}

Process Items in a Stream

This loop uses the new Java 8 streams facility with a lambda.

@Benchmark
public int test_stream(MyState state) {
    return state.list.stream().reduce(0, (x, y) -> x+y);
}

Here are the results. As before, the X-axis is the size of the ArrayList and the Y-axis is the throughput in ops/s with a higher number indicating faster performance. Also, note that the Y-axis is log scale.

Nothing unusual here. The performance of the loop drops over the size of the list. A surprise here is that the performance of the ArrayList stream is less by about 20% than the other methods. Again, your mileage may vary.

arraylist benchmark performance in loop get

LinkedList Loop Performance

These are the same tests as above on a LinkedList, ranging in size from 100 items to 10,000 items.

A few observations are in order here. The for-loop is way slower than the other methods, which is to be expected since the LinkedList is not a RandomAccess List. ArrayList has an O(1) performance for retrieval while LinkedList has an O(N) performance. It is reflected here.

Also, the streams processing pipeline is slower by about 20% than the for-each and iterator methods.

linkedlist benchmark loop get

Summary

In this article, we examined some performance characteristics of the ArrayList and LinkedList including creation, adding, and retrieval in a loop. The LinkedList is slightly slower with adding items to the end of the list. It is also slower when retrieving items with an index (random access).



If you enjoyed this article and want to learn more about Java Collections, check out this collection of tutorials and articles on all things Java Collections.

Data structure Java (programming language)

Published at DZone with permission of Jay Sridhar, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Trending

  • 4 Expert Tips for High Availability and Disaster Recovery of Your Cloud Deployment
  • Database Integration Tests With Spring Boot and Testcontainers
  • Building the World's Most Resilient To-Do List Application With Node.js, K8s, and Distributed SQL
  • What Is Envoy Proxy?

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com

Let's be friends: