Re:GlueList – Fast New Java List Implementation
by geophile on Friday August 12, 2016 @01:03PM
(#12277135)
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.
Re:GlueList – Fast New Java List Implementation
by Someone on Friday August 12, 2016 @01:38PM
(#12277378)
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)
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.