Which code does perform better to find a specific element in a list

Question

There are multiple ways to find a element in a list. For example I have a list with some elements that have a unique ID. For a given ID I want to return the specific element from the list.

List example (just schema, not correct syntax):

//Element(String id, int value)
List<Element> list = new ArrayList();
int elemCount = 1000000;
for(int i = 0; i<elemCount; i++)
    list.add(new Element("id"+i, i));
Collections.shuffle(list);
Element e = getElement("id" + ThreadLocalRandom.current().nextInt(0, elemCount));

Given the following two methods, which does perform generally better based on the java internal implementation and why?

First method:

public Element getElement(String id) {
   return list.stream()
      .filter(e -> e.getId().equals(id))
      .findAny()
      .orElse(null);
}

Second method:

public Element getElement(String id) {
   for(Element e : list)
      if(e.getId().equals(id))
         return e;
   return null;
}

• "Element" as object is chosen just for example.
• Not relevant: Structure and size of the Element, PC performance etc.
• Java Version: 1.8.0_111

Answer 1

Since i couldn't get a answer based on the java internal implementation, i did a benchmark for my self.

I want to share with you the results i came up with. I did run a benchmark for every list from size 1 to 1000. Every benchmark for every list size did run 10000 times with the average calculated to get out errors.

Disclaimer: I'm not a benchmark expert and i just did a simple implementation. The results are not 100% accurate and the conclusions i made can be wrong. If you can do it better, than feel free improve my benchmark oder make one your self and post the results in a new answer.

You can find the benchmark files here: https://github.com/Spenhouet/BenchmarkFindElement

1. Using a parallelStream for this simple task has more overhead and is slower than just a normal stream.
2. If the list is sorted and the wanted item is the last of the list, .findFirst() ist faster than .findAny().
3. If the list is sorted and the wanted item is the last of the list, by using .findAny() the "for" method is faster.
4. If the list is shuffled and the wanted item id is random than .findFirst() and .findAny() makes no difference.
5. If the list is shuffled and the wanted item id is random than there is only a little difference between the "stream" and the "for" method. The "stream" method is a little bit better

Tested with Java Version: 1.8.0_111

For example the performance graph for finding a random id in the the shuffled lists with 505 to 575 items. The blue line is the "for" method and the red line the "stream" method.

For example the performance graph for finding a random id in the the shuffled lists with 1 to 100000 items (only 10 times average). The blue line is the "for" method and the red line the "stream" method.

If you want to take a look at some graphs / generate them your selfe, then just download the repository from the github link above, import the project and run it with the VM options -Xms1024m -Xmx4068m.

With 1 to 40000 list elements and 100 runs each for average and the VM options: -Xms1024m -Xmx4068m -XX:+PrintCompilation -verbose:gc -Xbatch -XX:CICompilerCount=2