2 ms·

Has anyone run similar tests on the JVM after warmup? Theoretically the JVM should be pushing memory around to negate as much of the cache penalty as possible,

Has anyone run similar tests on the JVM after warmup? Theoretically the JVM should be pushing memory around to negate as much of the cache penalty as possible, and I've definitely noticed this in some algorithms (this is how people come up with code where Java outperforms almost identical code in pure C, and I've seen 3:1 speed differences in favor of the JVM), but I'd be curious to see the graphs. Maybe I'll do it later today if I get a few minutes...

ajross 17y ago
That seems very unlikely. Effects like the ones in the article (which is great, btw) can't be "fixed" simply by moving the data. In the first example, there's simply no way for any runtime environment to "know" at creation time that you would be walking the array in 16 byte strides. And if it tried to reorder the data dynamically, it would obviously have to touch all that memory, thus invalidating whatever caching could be done anyway. Where JVMs beat naive C, it's almost always in the locking and synchronization code. See the Sun paper on Biased Locking for an example of the kind of tricks you can do by (for example) "guessing" that newly locked objects are only ever going to be referenced by one thread. But memory is memory. The JVMs view of it lacks a raw pointer, but is otherwise pretty much the same as C's.
- sketerpot 17y ago
  On that note, I'm a fan of the speculative lock elision in the Azul Systems machines. When the JVM sees a synchronized section, it can create a snapshot of the current register and memory state and execute the critical section speculatively, checking for memory access conflicts with other threads, and roll back the changes if there's a conflict. Actual locks are a fall-back option. It's a special case of hardware transactional memory. (Specifically, bounded best-effort HTM; it can only track a limited number of memory changes, and aborts if you push it too far.) It can give small but non-trivial scaling improvements on multithreaded code. For example, suppose you have several threads that want to change a hash table. They could lock the whole hash table first -- or they could go ahead without locking, and abort if there was an actual memory conflict. Essentially it lowers the granularity of locking, automatically.

ajross 17y ago

That seems very unlikely. Effects like the ones in the article (which is great, btw) can't be "fixed" simply by moving the data. In the first example, there's simply no way for any runtime environment to "know" at creation time that you would be walking the array in 16 byte strides. And if it tried to reorder the data dynamically, it would obviously have to touch all that memory, thus invalidating whatever caching could be done anyway. Where JVMs beat naive C, it's almost always in the locking and synchronization code. See the Sun paper on Biased Locking for an example of the kind of tricks you can do by (for example) "guessing" that newly locked objects are only ever going to be referenced by one thread. But memory is memory. The JVMs view of it lacks a raw pointer, but is otherwise pretty much the same as C's.

sketerpot 17y ago
On that note, I'm a fan of the speculative lock elision in the Azul Systems machines. When the JVM sees a synchronized section, it can create a snapshot of the current register and memory state and execute the critical section speculatively, checking for memory access conflicts with other threads, and roll back the changes if there's a conflict. Actual locks are a fall-back option. It's a special case of hardware transactional memory. (Specifically, bounded best-effort HTM; it can only track a limited number of memory changes, and aborts if you push it too far.) It can give small but non-trivial scaling improvements on multithreaded code. For example, suppose you have several threads that want to change a hash table. They could lock the whole hash table first -- or they could go ahead without locking, and abort if there was an actual memory conflict. Essentially it lowers the granularity of locking, automatically.