|
|
|
|
|
|
by stiff
4536 days ago
|
|
|
Thanks for the great resources. I still wonder to what extent is it at all possible to do cache-friendly data structures on the JVM. Besides the somewhat abstract data structure considerations of the kind posted, there is still the issue of whether in the end references are stored in the collections memory or the values themselves. On the surface level it looks like Java collections generally use references for everything, except perhaps for arrays and (maybe) ArrayLists of primitive types. See for example: http://java.dzone.com/articles/slab-guaranteed-heap-alignmen... |
|
|
Nevertheless, cache-friendly data structures are still very much possible on the JVM. Consider something like a B-Tree node, with an array of references to the children and an array of keys. The node object and the arrays will be stored together in memory, so the only cache-missing pointer following you'd do is when you jump from one node to another, just as would happen in C/C++. So the memory placement is certainly not as flexible as in C/C++, but you can certainly be pretty cache friendly. In fact, this is a very active topic, as a lot of people are starting to use Java in low latency applications. For example, look at the discussions here: https://groups.google.com/forum/#!forum/mechanical-sympathy
There is work being done to support value types in Java, that are immutable, cannot be referenced (hence only compared by value), and stored inline in arrays (well, the latter is an implementation issue and up to the particular JVM to decide). This may be included in Java 9.