r/javahelp • u/AudioManiac • Mar 18 '20
Is there a performance cost when using Arrays.asList().contains() within a loop?
I'm reviewing some code a junior guy on my team and he has written the following logic:
for(final Object data : list)
{
if(Arrays.asList(properties.getExtendedSlots()).contains(data.getId()))
{
...more logic
}
else
{
.....
}
}At first look I thought it made more sense to create a list variable before the loop and call contains on that, instead of using Arrays.asList() each iteration. Like so:
List<Object> extendedSlotsList = Arrays.asList(properties.getExtendedSlots());
for(final Object data : list)
{
if(extendedSlotsList.contains(data.getId()))
{
...more logice
}
}But I'm not actually sure if there actually is a performance trade-off to simply doing it the first way. In my head it seems costly, as it must be creating a new list every iteration before calling contains(), which seems unnecessary when you can just create it once. But perhaps I'm wrong?
5
u/aram535 Mar 18 '20
depends on the size of the array, the optimizer should be able to cache the entries. HOWEVEr, it's really bad coding and will bite you down the road at some point.
If you are at least on Java 8 try using streams, it'll be nicer, easier to read, no potential bottlenecks and it'll be more future proof than your existing code.
3
u/lookForProject Mar 18 '20
What do you mean with the optimizer ?
Also, size of the array doesn't matter forArrays.asList4
u/aram535 Mar 18 '20
The "compiler" has an optimizer built into it.
I'm not talking about a method.... if you run through a 100,000 size array through a for loop that loops it 1,000 times .... well then you're doing a scan of the entire array for 1,000,000,000 times.
A simple hash of the key you're looking for would let you do it much quicken and only once.
0
u/lookForProject Mar 18 '20
The Javac does very little optimization, and I don't know how the JIT compiler might optimize this. Is a JIT-compiler (I assume every platform has another JIT-compiler) smart enough to understand that ExtendedSlots isn't changed between iterations?
Also, why on earth am I on -1 points? Was my question unreasonable?
1
u/aram535 Mar 18 '20
I stopped asking why people upvote/downvote ... it's a pointless exercise.
To get back your original question ... you're arguing the uses and functions of JIT but don't know if an Arrays.asList is the most proper way of doing loops??!?
JIT has nothing to do with the compiler optimizer. This is just the first link from google, but I would suggest reading upon it.
https://www.javaworld.com/article/2078635/jvm-performance-optimization-part-2-compilers.html
1
u/lookForProject Mar 18 '20
Will click your link later, but from my understanding:
javac doesn't do much optimization, some, but not much. Javac compiles your code to bytecode, something the JVM can read. The JVM interprets it into machine code. Unless I'm wrong, when you're talking about compiling in the JVM, you're talking about the JIT compiler.1
1
u/MoreCowbellMofo Mar 18 '20
You can test it if you get time stamps for running the process and calculate the difference. I'd imagine, yes, you are correct in thinking creating the list once for all objects in the list is the more optimal choice.
Better still, convert properties.extendedSlots() to a Set... if possible, remember sets have no duplicate items.
Converting extendedSlots() to:
Set extendedSlots = new HashSet();
still has the same time complexity for creating it, however your contains() method will scale far better as contains executes in O(1), rather than O(n).
0
Mar 18 '20
I always think don’t do it multiple times if I can do it once.
So even if the code relatively light. Create the list once and reuse it.
Depending non the size of the list, will depend if using a HashSet or sorting will help or not.
Currently you’ve got a O(N*M) algorithm there.
1
u/AudioManiac Mar 18 '20
The second list is tiny, only 2 elements are should never grow much larger, at least in this iteration of our code. But I like the performance points people are making regarding using HashSet. If I was to use that, would the complexity then just be O(n)? Since hashset contains is O(1)
2
Mar 18 '20
HashSet is more complicated; as long as the hash function is good and the set isn’t loaded to much; then you get O(1)
But if you’ve only got 2 elements; it isn’t worth it.
Remember that O(1) is for guiding scaling.
This will probably be classified as a premature optimisation; but you can just time both and see what works for you.
Nothing wrong with smaller simpler code even with a worse O rating if the domain knowledge means it’s ok.
0
u/FIREINMYVEINS_ Mar 19 '20
i don't want to sound like an ass but this piece of code shows that there is something wrong with the design.
your example is like having a static list of cities for properties.getExtendedSlots() and then you have a bunch of Persons in that list variable who have a property "city they live in".
your problem now resumes to "do something for every person that lives in that list of cities".
the code you presented there doesn't look like it states clearly what is doing so maybe consider delegating that check responsibility elsewhere.
about the code itself, clearly you should not use list to store those extended slots (maybe consider storing them at init time differently by converting that array to a Map for example).
and as a piece of advice : please use standard formatter for your code (like the google formatter, i think for intellij you have a plugin)
1
u/AudioManiac Mar 19 '20
I appreciate the advice, but I don't think, nor should you be able to, determine what the rest of the code or business logic is like based on 5 lines of code I've picked out from it.
properties is just a spring bean that reads from a properties file. It just contains a field that is a list of configurable ids that we want displayed differently on table on our frontend. We're clearly able to determine that from the rest of the code.
clearly you should not use list to store those extended slots
You don't give a valid reason why. A map would make no sense to use here.
please use standard formatter
I use my work project's formatter and code style, not Googles.
I appreciate your thought process none the less though!
1
u/FIREINMYVEINS_ Mar 19 '20
The reason for not using list is because you want to use it for lookup. Lists are not suited for lookup since you need to go through all the elements everytime.
As for the formatter, the java code conventions is something every piece of java code should adhere to.
https://www.oracle.com/technetwork/java/codeconventions-150003.pdf
1
u/AudioManiac Mar 19 '20
The reason for not using list is because you want to use it for lookup. Lists are not suited for lookup since you need to go through all the elements everytime.
Fair point, as other people have suggested to use a hashset instead, but seeing how this list only every contains 2 items, using a list isn't a massive problem.
the java code conventions is something every piece of java code should adhere to
This is nothing I have control over, we have our project standards which as far as I know follow these conventions or most of them
1
u/FIREINMYVEINS_ Mar 19 '20
if it is going to contain only two elements, maybe it's better to keep it in a dedicated object so you can "lookup" with a || (or operator)
-1
u/Robyt3 Mar 18 '20 edited Mar 18 '20
The source-code for Arrays.asList simply creates a new ArrayList, so depending on the size of list, it can be very inefficient to create this list again and again.
However even better would be to first put all elements in the array in a HashSet, which has O(1) contains performance.
If you don't want to store all values in an additional Set, using Stream.of(array).anyMatch(Predicate.isEqual(element)) would also be a better option than Arrays.asList(array).contains(element).
2
u/ObscureCulturalMeme Mar 18 '20
The source-code for
Arrays.asListsimply creates a newArrayListLook more closely. It creates an instance of a local private class, which is confusingly named
ArrayList, but that's not the same as the class that users code with directly.The inner class merely wraps the incoming array; nothing is copied. (And the docs for as List mention that fact.)
2
u/Robyt3 Mar 18 '20
I see, that's slightly confusing naming.
1
u/ObscureCulturalMeme Mar 18 '20
It's very confusing, and I've no idea why they did it that way. You're not the first person in the Java community to have been tripped up by that naming. (You're not even the first person in this conversation to have been tripped up.)
1
u/lookForProject Mar 18 '20
Why would the size of the
Arraymatter?Stream.ofdoes have a much larger overhead thenArrays.asList.1
0
u/lookForProject Mar 18 '20 edited Mar 18 '20
You're not wrong. The first one calls new ArrayList<>() every iteration. But, creating a new ArrayList isn't costly. The only thing the constructor does, is assigning the Array you get from properties.getExtendedSlots() to an instance variable. None of the parents do much in their constructor either. So the overhead is just that: you create a Object and assign a the Array to an instance variable.
But most of the time, it isn't about speed, it's about readability. And making something more logically valid, increases the readability. Your version is more readable, as creating a new List from the same Array,again and again and again, doesn't make much sense.
I have no idea what the size is of your extendedSlotsList, but if efficiency is an issue: contains for ArrayList just iterates every element in the Array until it finds the correct element. That's O(n). A TreeSet is O(log(n)). Hashset is O(1), If you implemented your hashcode right and if you have no collision.
Edit: added the info about HashSet, because O(1) can be misleading.
Edit 2: I reread your code again. I noticed data.getId(). It's reasonable to assume that your id is a Number. /u/morhp and /u/MoreCowbellMofo are correct that a hashSet is your best option here.
24
u/morhp Professional Developer Mar 18 '20
Arrays.asList()is relatively fast. It obviously creates a newListobject, but that just wraps the array, no data is copied, so not a huge deal. The second variant will be faster, but it probably won't matter that much.The slow thing is the
contains()call, because on aListthat has to look at each element individually.It would probably be better to create a
HashSetof the available ids before the loop and use the contains()-method of theHashSet(which is much faster and it doesn't get slower the more ids are in the set).