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 Video Library
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
View Events Video Library
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
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

Integrating PostgreSQL Databases with ANF: Join this workshop to learn how to create a PostgreSQL server using Instaclustr’s managed service

Mobile Database Essentials: Assess data needs, storage requirements, and more when leveraging databases for cloud and edge applications.

Monitoring and Observability for LLMs: Datadog and Google Cloud discuss how to achieve optimal AI model performance.

Automated Testing: The latest on architecture, TDD, and the benefits of AI and low-code tools.

Related

  • Demystifying Project Loom: A Guide to Lightweight Threads in Java
  • Auditing Spring Boot Using JPA, Hibernate, and Spring Data JPA
  • How To Validate Archives and Identify Invalid Documents in Java
  • Unraveling Lombok's Code Design Pitfalls: Exploring Encapsulation Issues

Trending

  • Java Parallel GC Tuning
  • Deploy a Session Recording Solution Using Ansible and Audit Your Bastion Host
  • 5 Web3 Trends to Follow in 2023
  • API Design
  1. DZone
  2. Coding
  3. Java
  4. Performance of Java Collections

Performance of Java Collections

Alan Hohn user avatar by
Alan Hohn
·
Oct. 03, 13 · Interview
Like (0)
Save
Tweet
Share
8.84K Views

Join the DZone community and get the full member experience.

Join For Free

what is the real-world effect of choosing the wrong kind of collection?

i’m in the midst of teaching an introduction to java class. like most courses of this type, when i introduce the standard jvm collections i intend to provide guidance on which type of collection to use when.

i wanted to show the real-world effects of making the correct or incorrect decision, so i put together an example. i used the excellent caliper library to create a class that benchmarks pulling data from existing collections. caliper is nice for this kind of thing because it does the measurement for you, and automatically handles some things like garbage collection coming in and messing up your test. it also publishes the results to a webapp , with a useful table that i’ll be able to use in my slides. caliper is undergoing a change to its api at the moment, so i used the old api since that’s the version that’s available in maven. both apis look a lot like junit; the old api looks like junit 3 and the new api looks like junit 4.

the benchmark code is part of my small but growing github repository associated with my introduction to java class. the benchmark methods look like this:

    public string timearraylistiteration(int reps) {
        string name = null;
        for (int i = 0; i < reps; i++) {
            for (person p: personarraylist) {
                name = p.getlastname();
            }
        }
        return name;
    }

the time at the front of the method name works like junit 3’s test — it marks the method as something that caliper should benchmark. caliper handles choosing a sensible value for reps in order to provide consistent and meaningful output. the method returns a “meaningful” value so that the compiler won’t be able to optimize it away.

of course, there are a lot of benchmarks out there already, but most of them focus on comparing the performance of different collections libraries, or of similar collection types that should have the same big-o performance. what i was after is showing the dramatic difference of using the wrong collection type entirely (e.g. a list instead of a map).

is this realistic? it is in my experience. i’ve found and fixed many cases where a list collection was being used even when most users of the collection were doing searches for a specific element. it seems that “data store” classes are susceptible to this kind of thing, especially when they start out with simple append and iteration operations and then progress to include more complex functions.

from my simple test, the qualitative ordering of performance is what everyone would expect. it’s painful to iterate over a map’s values. it’s very painful to search a list. what might be at least a little surprising is the size of the difference.

benchmark results

iteration over a hash map took 3 times as long as over an array list, and 1.5x a linked list. searching over an array list took 13 times as long as pulling an item out of a hash map when there was an index handy to help.

note that because i choose to search for a random element, there’s a lot of variance in the searches that have to iterate over the collection. so the displayed number is the average performance under uniform access assumptions.

one other interesting point is the relative performance of array lists versus linked lists when fetching a specific element with a known location. most people suggest linked lists as the number of elements grows large, and that’s good advice where there will be inserts and deletes that are not at the end. but if the primary use case will be adding things, fetching them, and iterating over them, a large array list may still be noticeably better.

my intent with this code was to scare my students into using the right collection, so i didn’t spend time on other things i think would be interesting, like measuring how expensive it is to maintain an extra index on a hash map in order to avoid a search. these numbers seem to indicate that it would be worthwhile to spend 10 times the cost of a single search on index updates. since updating hash map indices is o(1) , that suggests it’s almost always worth it. it would be interesting to try to verify that.

Java (programming language)

Published at DZone with permission of Alan Hohn, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Demystifying Project Loom: A Guide to Lightweight Threads in Java
  • Auditing Spring Boot Using JPA, Hibernate, and Spring Data JPA
  • How To Validate Archives and Identify Invalid Documents in Java
  • Unraveling Lombok's Code Design Pitfalls: Exploring Encapsulation Issues

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

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends: