Java object arrays - use of hardware memory cache

Question

Iterating over consecutive elements of an array is generally considered to be more efficient than iterating over consecutive linked list elements because of caching.

This is undoubtedly true as long as elements have elementary data types. But if the elements are objects, my understanding is that only the references to the objects will be stored in the contiguous memory area of the array (which is likely to be cached) while the actual object data will be stored anywhere in main memory and cannot be cached effectively.

As you normally not only iterate over the container but also need to access object data in each iteration, doesn't this more or less kill the performance benefit of the array over the list?

Edit: The comment about different scenarios varying greatly is probably correct. So let's consider a specific one: You search for a specific object in the container. In order to find it you need to compare a given string to another string that is a class variable of the object.

"my understanding is that only the references to the objects will be stored in the contiguous memory area of the array" Correct. The answer to the remainder of the question is "It depends." Different scenarios vary greatly, there's no general answer to this question. — T.J. Crowder
– T.J. Crowder, Commented Jun 30, 2016 at 8:48
Maybe. Interesting question though; but it would rather surprise me if you get more helpful answers than downvotes and close requests. — GhostCat
– GhostCat, Commented Jun 30, 2016 at 8:48
IMO array still provides faster access due to less number of operations required to reach to next node as compared to LinkedList. — Gaurava Agarwal
– Gaurava Agarwal, Commented Jun 30, 2016 at 9:00

Joop Eggen · Accepted Answer · 2016-06-30 09:10:43Z

1

No, for objects ("pointers") there is an indirection in both. A linked list needs for every node to step to the next one. So it still has an overhead.

But yes, in a relative way the gain concerns only a part, very roughly the half of the pure walk through, counting indirection steps.

And ofcourse every indirection makes access more chaotic, slower.

BTW there is the ArrayList too being similar fast as arrays.

edited Jun 30, 2016 at 9:10

answered Jun 30, 2016 at 9:00

Joop Eggen

110k8 gold badges89 silver badges142 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Frank Puffer Over a year ago

In this context, I would expect ArrayList to behave like an array.

Joop Eggen Over a year ago

Yes, I wanted to mention it in order not to chase people to arrays, when a List is more appropriate.

Collectives™ on Stack Overflow

Java object arrays - use of hardware memory cache

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related