4 ms·

Cache, cache and cache. Three of the most important things Java gets wrong today. Mostly because Java doesn't have object arrays at all. Only primitive types ca

by vardump 12y ago

Cache, cache and cache. Three of the most important things Java gets wrong today. Mostly because Java doesn't have object arrays at all. Only primitive types can be array elements. So you get array of references to objects instead of array of objects. There are only 512 L1D cache lines in a CPU core. After just 512 references to memory areas covered by different cache lines, L1D entries will start to drop. Or earlier. In Java this happens very easily. Like when just iterating a single, not very large, data structure. Everything else (except maybe SIMD/GPU related items for compute purposes) are not anywhere near as important as fixing Java's current problems with CPU caches.

pjmlp 12y ago
Back when Java still wasn't known, we had Oberon(-2), Component Pascal and Modula-3. All system programming languages with GC, value types and AOT compilers (some implementations of Oberon did have JITs). Apparently 20 years detour was needed to go back to those features.
- seanmcdirmid 12y ago
  The CLR has had value types from the onset.
  - pjmlp 12y ago
    True, but only now is getting static compilation to native core. There were Bartok, mono -aot, Cosmo OS, but it seems if it isn't part of the reference platform, developers tend to ignore them. I have meet a few .NET devs unaware of NGEN.
    - seanmcdirmid 12y ago
      NGEN is a detail. If you don't care about it, it can remain an obscure detail :)
- mike_hearn 12y ago
  Apparently 20 years detour was needed to go back to those features. I think this is explainable by Java's history. When it was created, the design docs said Java was a simple, interpreted language with distributed objects and the target hardware was set top boxes. When Java unexpectedly took off, I suspect Sun weren't quite sure which ingredients were key to that success but fixated on "simple". They unlocked a huge market that was unserved at the time: companies that needed a much simpler C++. So that wasn't unreasonable. They then spent many years trying to handle customer requests for ever more runtime speed, whilst simultaneously not making Java as complex as C++. Hence the focus on super whizzy optimisations inside HotSpot ... many of which are just undoing performance hits introduced by the simplicity of the Java language. Value types increase the complexity of the language, no doubt about it. Heck, even having a difference between int and Integer increases complexity. When value types come out, I expect much rejoicing from people who need more runtime speed, and a whole lot of confused questions on Stack Overflow from people who aren't totally sure about the difference between a value type and a regular class. I also expect to come across codebases where classes were turned into value types more or less at random, or where the style code forbids value types entirely, etc. Java sort of has this problem already where weaker programmers who are using threads just slap synchronized keywords on every method until the crashes stop. Then HotSpot goes in and tries to figure out if the locks are actually needed or not and removes them at runtime. Don't get me wrong. I'm A++++ in favour of having value types on the JVM and in Java. But increasing complexity of the language is absolutely not cost free, especially not given Java's value proposition to big corporates.
spullara 12y ago
This is a focus for Java 10 — value types. John Rose is actually one of the guys working on it. He mentions this several times in the presentation as a key issue to solve in the JVM. https://www.google.com/search?client=safari&rls=en&q=value+types+john+rose&ie=UTF-8&oe=UTF-8 https://www.google.com/search?client=safari&rls=en&q=value+t...
kristianp 12y ago
This reminds me of something I'm curious about: why have L1 caches have been the same size for quite a few generations of Intel Core processors?
- vardump 12y ago
  Currently Intel's L1D (level 1 data) cache is 512 lines with 64 bytes each, 32 kB. Been that way for a pretty long time. L1D latency with a pointer is mostly 4 cycles. Not sure, but I think having 1024 entries would increase that to 5 cycles. Increasing cache line size from 64 bytes to 128 bytes would require more memory (DDRx SDRAM) bandwidth, because CPU needs to always fill a whole 64 byte - 128 byte with this change - cache line on a memory load. Even if you want just one byte. Wasted bandwidth for non-streaming workloads would be increased significantly. This change would force also L2 to have 128 byte cache lines, etc. LFBs and other buffers would of course also need to accommodate this. Skylake will be able to process 64 bytes (512 bits) with a single SIMD instruction, with AVX-512. Perhaps Intel will need to soon increase cache line size, if 1024 bits wide SIMD instructions are desired. SIMD gather instructions might be a hint that in the future memory loads will function in a different fashion. Maybe cache lines won't anymore be the smallest amount of data a CPU memory subsystem can deal with?
- wmf 12y ago
  Because that size is optimal, regardless of transistor size. Making the cache larger makes it slower (because of the speed of light AFAIK) and more power-hungry which reduces overall performance.
- jjoonathan 12y ago
  This reminds me of something I'm curious about: why aren't large SRAM arrays displaying DRAM? I know 6Ts are larger than 1T+1C, but even if SRAM were 6x as expensive (which ought to be a severe upper bound) that would put it at $50/GB which sounds like it could easily be worthwhile for certain workloads -- not unlike SSDs a few years ago. The latency advantage would be gigantic, especially if you could crowd the chips near the CPU. Is SRAM comparatively power hungry or something?
  - 12y ago
jermo 12y ago
ObjectLayout [1] should help with that but its not in standard Java. [1] http://objectlayout.org/ http://objectlayout.org/
im3w1l 12y ago
It'd go against OOP, but you could take all the member variables and put in separate arrays. E.g instead of an array of 3-vectors, you'd have an x-array, a y-array and a z-array.
- pkolaczk 12y ago
  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.
harkyns_castle 12y ago
Some of the talks [1] on the LMAX Disruptor [2] were interesting with regard to how it interacted with the various caches and how important it could be. 1. https://www.youtube.com/watch?v=DCdGlxBbKU4 https://www.youtube.com/watch?v=DCdGlxBbKU4 2. https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/

by vardump 12y ago

pjmlp 12y ago

Back when Java still wasn't known, we had Oberon(-2), Component Pascal and Modula-3. All system programming languages with GC, value types and AOT compilers (some implementations of Oberon did have JITs). Apparently 20 years detour was needed to go back to those features.

seanmcdirmid 12y ago
The CLR has had value types from the onset.
- pjmlp 12y ago
  True, but only now is getting static compilation to native core. There were Bartok, mono -aot, Cosmo OS, but it seems if it isn't part of the reference platform, developers tend to ignore them. I have meet a few .NET devs unaware of NGEN.
  - seanmcdirmid 12y ago
    NGEN is a detail. If you don't care about it, it can remain an obscure detail :)
mike_hearn 12y ago
Apparently 20 years detour was needed to go back to those features. I think this is explainable by Java's history. When it was created, the design docs said Java was a simple, interpreted language with distributed objects and the target hardware was set top boxes. When Java unexpectedly took off, I suspect Sun weren't quite sure which ingredients were key to that success but fixated on "simple". They unlocked a huge market that was unserved at the time: companies that needed a much simpler C++. So that wasn't unreasonable. They then spent many years trying to handle customer requests for ever more runtime speed, whilst simultaneously not making Java as complex as C++. Hence the focus on super whizzy optimisations inside HotSpot ... many of which are just undoing performance hits introduced by the simplicity of the Java language. Value types increase the complexity of the language, no doubt about it. Heck, even having a difference between int and Integer increases complexity. When value types come out, I expect much rejoicing from people who need more runtime speed, and a whole lot of confused questions on Stack Overflow from people who aren't totally sure about the difference between a value type and a regular class. I also expect to come across codebases where classes were turned into value types more or less at random, or where the style code forbids value types entirely, etc. Java sort of has this problem already where weaker programmers who are using threads just slap synchronized keywords on every method until the crashes stop. Then HotSpot goes in and tries to figure out if the locks are actually needed or not and removes them at runtime. Don't get me wrong. I'm A++++ in favour of having value types on the JVM and in Java. But increasing complexity of the language is absolutely not cost free, especially not given Java's value proposition to big corporates.

spullara 12y ago

This is a focus for Java 10 — value types. John Rose is actually one of the guys working on it. He mentions this several times in the presentation as a key issue to solve in the JVM. https://www.google.com/search?client=safari&rls=en&q=value+types+john+rose&ie=UTF-8&oe=UTF-8 https://www.google.com/search?client=safari&rls=en&q=value+t...

kristianp 12y ago

This reminds me of something I'm curious about: why have L1 caches have been the same size for quite a few generations of Intel Core processors?

vardump 12y ago
Currently Intel's L1D (level 1 data) cache is 512 lines with 64 bytes each, 32 kB. Been that way for a pretty long time. L1D latency with a pointer is mostly 4 cycles. Not sure, but I think having 1024 entries would increase that to 5 cycles. Increasing cache line size from 64 bytes to 128 bytes would require more memory (DDRx SDRAM) bandwidth, because CPU needs to always fill a whole 64 byte - 128 byte with this change - cache line on a memory load. Even if you want just one byte. Wasted bandwidth for non-streaming workloads would be increased significantly. This change would force also L2 to have 128 byte cache lines, etc. LFBs and other buffers would of course also need to accommodate this. Skylake will be able to process 64 bytes (512 bits) with a single SIMD instruction, with AVX-512. Perhaps Intel will need to soon increase cache line size, if 1024 bits wide SIMD instructions are desired. SIMD gather instructions might be a hint that in the future memory loads will function in a different fashion. Maybe cache lines won't anymore be the smallest amount of data a CPU memory subsystem can deal with?
wmf 12y ago
Because that size is optimal, regardless of transistor size. Making the cache larger makes it slower (because of the speed of light AFAIK) and more power-hungry which reduces overall performance.
jjoonathan 12y ago
This reminds me of something I'm curious about: why aren't large SRAM arrays displaying DRAM? I know 6Ts are larger than 1T+1C, but even if SRAM were 6x as expensive (which ought to be a severe upper bound) that would put it at $50/GB which sounds like it could easily be worthwhile for certain workloads -- not unlike SSDs a few years ago. The latency advantage would be gigantic, especially if you could crowd the chips near the CPU. Is SRAM comparatively power hungry or something?
- 12y ago

jermo 12y ago

ObjectLayout [1] should help with that but its not in standard Java. [1] http://objectlayout.org/ http://objectlayout.org/

im3w1l 12y ago

It'd go against OOP, but you could take all the member variables and put in separate arrays. E.g instead of an array of 3-vectors, you'd have an x-array, a y-array and a z-array.

pkolaczk 12y ago
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.

harkyns_castle 12y ago

Some of the talks [1] on the LMAX Disruptor [2] were interesting with regard to how it interacted with the various caches and how important it could be. 1. https://www.youtube.com/watch?v=DCdGlxBbKU4 https://www.youtube.com/watch?v=DCdGlxBbKU4 2. https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/