Avoid Cache misses in Java

Question

Currently im switching my state of mind to develop applications more cache friendly.
In C++ im using stack allocation where i can,also i'm holding data with this same purpose in one array(Data Driven Programming) etc...
But im also Java developer and there comes a question:
I heard that Java is "cache miss generator".
Everything there is in heap,and is scattered in whole RAM after allocation or garbage collector work.I think the same problem is with C#.
Will it have sense to write Java in Data Driven way?
Is there any way to optimize Java code,or we are stuck with Java automatic optimization and cache misses?

Answer 1

In C++ im using stack allocation where i can,also i'm holding data with this same purpose in one array(Data Driven Programming) etc...

In Java it will automatically place short live obejcts on the stack using Escape Analysis. I wouldn't worry about this unless you see in a profiler that this is an issue. Even then it could be that the profiler is preventing the escape analysis from working and it is not a problem in a real program.

I heard that Java is "cache miss generator".

Java had far more referencing than C++ or C# code which has been written to use structs or objects which are embedded inside objects. How much difference this makes depends on how sensitive your application is to micro-tuning.

Everything there is in heap,and is scattered in whole RAM after allocation or garbage collector work.I think the same problem is with C#.

Java (and C#) is not a random memory arranger either. In theory the objects could be anywhere, but in practice they are not usually. Consider if you have;

class A { }

class B {
    A a = new A();
}

If you create a B, the A could be anywhere, but generally it is not. When Java allocates memory in the Eden space it is usually continuous in memory. This is the simplest and most efficient way to allocate memory. This means that 99.9% of the time, A will be immediately after B, possibly on the same cache line. In fact "false sharing" is a real problem in Java for some use cases. i.e. when you would like to two objects which are not on the same cache line.

What happens on a GC?

In the OpenJDK/Oracle JVM, objects are copied in reverse order of discovery. i.e. A would appear immediately before B in most cases.

Will it have sense to write Java in Data Driven way?

This case be the case, and in < 1% of cases this can make a big difference. However, for most of your code, if not most of your applications, you will have much, much bigger problems to worry about.

Is there any way to optimize Java code,or we are stuck with Java automatic optimization and cache misses?

You can use Unsafe to control memory structures of your choice. We (Chronicle Software) have libraries which allow you do just that, but even though we would love you to use our services, in 99% cases, there is no good reason to worry about this sort of micro-tuning. Only in extreme cases would it make any real difference.

I dont want modify garbage collector.But i know it copies everything around so it messes a bit structure.I want avoid this as much as i can.

This is what the GC does. It packs together related objects, not just for efficiency but because copying objects in the manner they are found is the simplest implementation. Arranging data randomly is something you would have to do deliberately if you wanted that and it would be more work. e.g. if you want to avoid "false sharing" it is non-trivial.

Answer 2

You can improve cache performance in Java too, but it is involved. Arrays of primitive types are contiguous blocks of memory, so as long as you can rewrite your code in terms of those you are golden. As Stepanov said, you can write FORTRAN in any language. I have seen this actually being done in the past, but it is not nice...

C# on the other hand is a friendlier language to this respect. struct types have contiguous members, so you can build higher level cache friendly abstractions in C#, additionally List<T> for a value-type T is allocated in a single contiguous block of memory.