4 ms·

Still if you need all three together, that's potential 3-cache misses instead of 1.

vardump 12y ago
And if there are too many fields, this technique can confuse CPU hardware prefetcher not to see the sequential access pattern making prefetching less useful (or even completely useless). This will increase memory latency and make CPU stall longer while waiting for memory. If you're unlucky, physical memory read pointer distance in bytes is modulo of 64 * <number of memory channels>, all 3 reads might hit the same physical memory module, but in a different DRAM page. All accesses would buffer on just one memory controller and one memory module, significantly reducing available bandwidth. At physical memory level read pointer distance between different arrays could also cause cache aliasing and consequently extra cache invalidations. See http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf http://www.intel.com/content/dam/www/public/us/en/documents/... for details. Find "aliasing" from it in your favorite PDF viewer. If you are just sequentially and continuously streaming from one array, none of this should normally happen. You can of course still get conflicts leading to CPU stalls when writing data, but that's a different matter. Considering the above, you might want to store your vector x, y, z in a same array, interleaving the values: x = array[objIndex * 3 + 0]; y = array[objIndex * 3 + 1]; z = array[objIndex * 3 + 2]; Not pretty! In real code, you might want to use 4 as multiplier. Then a JVM with vectorization support might have (or might not) better opportunities to load whole vector together with a single SIMD (SSE/AVX) instruction.
- TheLoneWolfling 12y ago
  And now we're back to value structs.
  - vardump 12y ago
    High performance cache friendly value struct emulating Java code can be unbelievably ugly. Just one object with elementary type array members.
    - TheLoneWolfling 12y ago
      And here is where I wish Java actually had a struct type. Alas, like so many other things about the Java language (No operator/assignment overloading, no unsigned integer types, etc, etc), it seems to have been a deliberate, although potentially under-thought, design decision.
      - pron 12y ago
        But Java and the JVM are getting value types, which are immutable structs.
        TheLoneWolfling 12y ago
        What about for mutable structs?
        pron 12y ago
        Mutable struct are a very bad idea.
        TheLoneWolfling 12y ago
        Elaborate? What makes it a bad idea? Having to rewrite an entire struct to change one value within it seems... counterproductive, considering that the purpose of having structs is largely speed-based. I can see it being useful to be able to flag a struct as immutable for certain cases, but for there not being a mutable version?
        pron 12y ago
        The main point of value types is that they're passed by value. As such, they have no concept of identity. The value 2 stored in variable x is the same as the value 2 stored in variable y. So, too, the value 2+3i, represented as the value type Complex { double r, i; }, is the same no matter where it is stored. Introducing mutation changes that. Values can now be destroyed. This is the conceptual reason. The practical reason is that structs help you with speed when their size is no more than the size of the machine's cache line, i.e. up to 64 bytes. Beyond that, you incur an extra cache miss when accessing them (even below, if they're not aligned, but the smaller they are the smaller the chance), so you might as well use a pointer, and your copying costs are no longer negligible, so a pointer might be a better idea anyway. So conceptually mutable "values" are a bad idea, and there's no reason to have them because beyond the cache line size they might cost you in performance more than they buy you, and below it mutation doesn't help as copying costs are very low. The only benefit mutable structs might have is when you want to lay out a large number of objects, which you'll be accessing sequentially, consecutively in RAM. This way, the CPU's prefetcher will help you stream them into the cache. But the way HotSpot's allocator works, you're almost certain to get the same behavior with objects anyway, and if whatever tiny performance difference this might buy is that important to you, you might be better off using C, anyway. The goal of the JVM is to get you the best performance for the least amount of work; not to let you work hard to squeeze out a few more performance improvement percentages. It sometimes certainly allows for that, but not at the cost of such a fundamental change, which is bound to do more harm than good.

And if there are too many fields, this technique can confuse CPU hardware prefetcher not to see the sequential access pattern making prefetching less useful (or even completely useless). This will increase memory latency and make CPU stall longer while waiting for memory. If you're unlucky, physical memory read pointer distance in bytes is modulo of 64 * <number of memory channels>, all 3 reads might hit the same physical memory module, but in a different DRAM page. All accesses would buffer on just one memory controller and one memory module, significantly reducing available bandwidth. At physical memory level read pointer distance between different arrays could also cause cache aliasing and consequently extra cache invalidations. See http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf http://www.intel.com/content/dam/www/public/us/en/documents/... for details. Find "aliasing" from it in your favorite PDF viewer. If you are just sequentially and continuously streaming from one array, none of this should normally happen. You can of course still get conflicts leading to CPU stalls when writing data, but that's a different matter. Considering the above, you might want to store your vector x, y, z in a same array, interleaving the values: x = array[objIndex * 3 + 0]; y = array[objIndex * 3 + 1]; z = array[objIndex * 3 + 2]; Not pretty! In real code, you might want to use 4 as multiplier. Then a JVM with vectorization support might have (or might not) better opportunities to load whole vector together with a single SIMD (SSE/AVX) instruction.

TheLoneWolfling 12y ago
And now we're back to value structs.
- vardump 12y ago
  High performance cache friendly value struct emulating Java code can be unbelievably ugly. Just one object with elementary type array members.
  - TheLoneWolfling 12y ago
    And here is where I wish Java actually had a struct type. Alas, like so many other things about the Java language (No operator/assignment overloading, no unsigned integer types, etc, etc), it seems to have been a deliberate, although potentially under-thought, design decision.
    - pron 12y ago
      But Java and the JVM are getting value types, which are immutable structs.
      - TheLoneWolfling 12y ago
        What about for mutable structs?
        pron 12y ago
        Mutable struct are a very bad idea.
        TheLoneWolfling 12y ago
        Elaborate? What makes it a bad idea? Having to rewrite an entire struct to change one value within it seems... counterproductive, considering that the purpose of having structs is largely speed-based. I can see it being useful to be able to flag a struct as immutable for certain cases, but for there not being a mutable version?
        pron 12y ago
        The main point of value types is that they're passed by value. As such, they have no concept of identity. The value 2 stored in variable x is the same as the value 2 stored in variable y. So, too, the value 2+3i, represented as the value type Complex { double r, i; }, is the same no matter where it is stored. Introducing mutation changes that. Values can now be destroyed. This is the conceptual reason. The practical reason is that structs help you with speed when their size is no more than the size of the machine's cache line, i.e. up to 64 bytes. Beyond that, you incur an extra cache miss when accessing them (even below, if they're not aligned, but the smaller they are the smaller the chance), so you might as well use a pointer, and your copying costs are no longer negligible, so a pointer might be a better idea anyway. So conceptually mutable "values" are a bad idea, and there's no reason to have them because beyond the cache line size they might cost you in performance more than they buy you, and below it mutation doesn't help as copying costs are very low. The only benefit mutable structs might have is when you want to lay out a large number of objects, which you'll be accessing sequentially, consecutively in RAM. This way, the CPU's prefetcher will help you stream them into the cache. But the way HotSpot's allocator works, you're almost certain to get the same behavior with objects anyway, and if whatever tiny performance difference this might buy is that important to you, you might be better off using C, anyway. The goal of the JVM is to get you the best performance for the least amount of work; not to let you work hard to squeeze out a few more performance improvement percentages. It sometimes certainly allows for that, but not at the cost of such a fundamental change, which is bound to do more harm than good.