Hacker News Reader

Iteration will be slower than Arraylist.

Just like LinkedList (which is even worse), there will be cache misses on jumps to new nodes.

Random access lookup will be (very slightly) slower as you determine which node to look inside.

This is hardly a new datastructure. Just one that's been thought of before and not standardized due to lack of compelling performance differentiation.

View on HN

Worrying about cache misses seems premature without value types in Java. The list elements are not physically embedded in the list, and accessing each one could easily result in a cache miss.

A second cache miss. That the language almost (1) forces the language implementation to be inefficient doesn't give those writing programs in the language to ignore further inefficiencies.

(1) A sufficiently smart compiler could, in some cases, convert a data structure that logically uses reference types into one that uses value types in the compiled code (I think that's highly hypothetical in this case, as it almost isn't worth spending time on for compiler writers, given that it will be possible very rarely)

Curious if there are numbers showing how much slower.

Reply on news.ycombinator.com