import java.util.concurrent.atomic.AtomicLong; public final class FalseSharing implements Runnable { public final static int NUM_THREADS = 4; // change public final static long ITERATIONS = 500L * 1000L * 1000L; private final int arrayIndex; private static PaddedAtomicLong[] longs = new PaddedAtomicLong[NUM_THREADS]; static { for (int i = 0; i < longs.length; i++) { longs[i] = new PaddedAtomicLong(); } } public FalseSharing(final int arrayIndex) { this.arrayIndex = arrayIndex; } public static void main(final String[] args) throws Exception { final long start = System.nanoTime(); runTest(); System.out.println("duration = " + (System.nanoTime() - start)); } private static void runTest() throws InterruptedException { Thread[] threads = new Thread[NUM_THREADS]; for (int i = 0; i < threads.length; i++) { threads[i] = new Thread(new FalseSharing(i)); } for (Thread t : threads) { t.start(); } for (Thread t : threads) { t.join(); } } public void run() { long i = ITERATIONS + 1; while (0 != --i) { longs[arrayIndex].set(i); } } public static long sumPaddingToPreventOptimisation(final int index) { PaddedAtomicLong v = longs[index]; return v.p1 + v.p2 + v.p3 + v.p4 + v.p5 + v.p6; } public static class PaddedAtomicLong extends AtomicLong { public volatile long p1, p2, p3, p4, p5, p6 = 7L; } }
With this code I get similar performance results to those stated in the previous False Sharing article. The padding in PaddedAtomicLong above can be commented out to see the false sharing effect.
I think we should all lobby the powers that be inside Oracle to have intrinsics added to the language so we can have cache line aligned and padded atomic classes. This and some other low-level changes would help make Java a real concurrent programming language. We keep hearing them say multi-core is coming. I say it is here and Java needs to catch up.
In your prev article you created an array of VolatileLong and here an array of AtomicLongArray.
ReplyDeleteWhat is the guarantee that the AtomicLongArray or VolatileLong instances will be allocated next to each other?
Well, yes if you create them in a loop, then it is very likely that they will be co-located. But there is no guarantee that these 4 instances will be next to each other on the heap.
If they do get spread across on the old gen heap where there is no compaction, re-location (until a major GC) padding might not even be necessary if they are spread out. Correct?
It would be nice if you made it clear to your readers that we really have no control over where the JVM places instances on the heap.
Ashwin,
ReplyDeleteYou are totally right in that we have no guarantee how Java objects will be placed on the heap. This is the source of the problem with false sharing. If you have counters or pointers that are used across threads it is vitally important to ensure they are in different cache lines or the application will not scale up with cores. The point of the padding is to protect the counters/pointers to ensure they ever get placed in the same cache line.
Does this make sense?
Martin...
Yup. Makes sense. Couldn't you have created a large AtomicLongArray and then let each thread update position 8, 16, 24, 32 and so on?
ReplyDeleteInstead of 4 AtomicLongArrays and then updating position 0 in each of those 4 arrays?
Thanks for taking the time to write such things.
If I knew up front that would be a possibility. Often when designing large systems we don't know such things, or we have created a library used by another application.
ReplyDeleteIt is hard to create a small enough example with sufficient context. The above example illustrates how bad things can been when it happens. If you pad such structures then you need not worry about where they get located in memory. Only the highly contended concurrent structures need such padding.
After a good discussion with Jeff Hain we have discovered the JVM cannot be trusted when it comes to re-ordering code. What happens before the volatile seems to be safe but what happens after is not reliable. We have a better solution by replacing the VolatileLong with the following and using the normal methods of AtomicLong.
ReplyDeletestatic class PaddedAtomicLong extends AtomicLong
{
public volatile long p1, p2, p3, p4, p5, p6, p7 = 7L;
}
Oh how I wish the Java powers the be would get serious about this stuff and add some intrinsics that are cache line aligned and padded. This have been the biggest source or performance bugs in the Disruptor.
I've updated this blog based on all the feedback.
ReplyDeleteMartin,
ReplyDeleteAgree that it would be great if there was a way to declare a field such it is guaranteed to occupy it's own cache line, and let the JVM deal with placing the right padding in the object layout. What you do here with artificial padding is the next best thing, but as you know, what actually happens to object layout becomes JVM-implementation specific.
Being paranoid, I'd add some more stuff to your padding technique to make it harder to get rid of the padding fields through optimization. A hypothetically smart enough JVM would still be able to prove away the need to actually implement the atomic long field p1...p7 in your code above: The PaddedAtomicLong class is only visible from the final (and therefor non-extendable) FalseSharing class. The compiler can therefore "know" that it is looking at all the code that will ever see the padding fields, and can prove that no behavior actually depends on p1...p7. The JVM could then implement the above without taking any space for the padding fields...
You can probably defeat this by making the PaddedAtomicLong class visible outside of FalseSharing, either directly or by adding accessor method on FalseSharing that would depend on all the p1...p7 values and could theoretically be called by someone outside.
Updated example based on Gil's feedback.
ReplyDeleteJust use an array (or direct bytebuffer but you pay a full page for it) and place the element in the middle. Java cant reorder that. This is what I do if I want dedicated cache lines.
ReplyDeleteStanimir,
ReplyDeleteI've often used an array of 15 longs for example and put the value at index 7 to achieve the same result. However this does not work if the value requires volatile semantics. For that you need to use AtomicLongArray or similar. Based on my measurements the indirection and bounds checking costs for this can be significant in an algorithm.
I know a bunch of folk are proposing an @Contended annotation for Java to mark fields so they can be cache line aligned and padded. I hope it comes soon. :-)
Hi Martin,
DeleteI saw that the current version of Sequence in Disruptor now uses unsafe.compareAndSwapLong(..) to update the 7th index.
Why is the length of the long array 15 and not another size? Is it because an array of 15 longs exactly fills the Level 2 cache?
Cheers
John
By using index 7 (8th element) ensures that there will be 56 bytes of padding either side of the value. 56 bytes plus the 8 for the value ensures nothing else can share the same 64-byte cache line regardless of starting location in memory for the array.
DeleteHi Martin,
DeleteI was trying your benchmark code with the Java 8 @Contended annotation. The performance was similar to the one without padding.... Did you manage to try it ?
Martin,
ReplyDeleteyes I meant AtomicLongArray. if you do not wish to pay for the indirection, Unsafe is (always) an option. No bounds checking w/ unsafe either.
Are there any simple hardware manuals of multiple cores that show key components like caches ? This is for illustration to understand how caches and cores interact to create false sharing.
ReplyDeleteMohan,
ReplyDeleteSee section 3.4 of the following document:
http://img.delivery.net/cm50content/intel/ProductLibrary/100412_Parallel_Programming_02.pdf
FWIW - I have a centos5.8 VM running on hyperv w/ oracle java 1.6.0_22, and this version of the false sharing test with the padded atomic is about 4 times faster than VolatileLong. A typical run for me with padded atomic long:
ReplyDeleteduration = 7019998000
Your blog is a wonderful reading. Thanks. I have 2 questions regarding memory padding:
ReplyDelete1. long type take 8byte. obj takes 2 words = 16 byte. but with impl as
public final static class VolatileLong // 16byte
{
public volatile long value = 0L; // 8 byte
public long p1, p2, p3, p4, p5, p6; // 6*8 = 48byte
}
seems total = 16 + 8 + 48 = 72 bytes > 64 byte cache line.
2. How do you find this problem? are you looking at assembly code to understand cache line is constantly sync-ed?
I do not want the mark word to be in the cache line which can be modified by taking out locks or the garbage collector ageing the object.
DeleteEven in 64-bit mode compressed pointers are enabled by default, this includes the class pointer in the object header.
https://wikis.oracle.com/display/HotSpotInternals/CompressedOops
If found the problem years ago when investigating the reasons why one can get variations in performance runs.
ok, so you find the problem during perf test run. How do you narrow down the issue? Are you digging the assembly?
DeleteAssembly does not show the problem. You need to look for a lot of unexplained L2 caches misses as a hint that something is going on.
DeleteSee also @Contended proposal: http://mail.openjdk.java.net/pipermail/hotspot-dev/2012-November/007309.html
ReplyDeleteGreat blog, thumbs up!
I've not tried @Contended as it has not made it into a mainstream JVM yet.
DeleteHi Martin,
ReplyDeleteWonderful blog.
Can you explain how do you come up with how many long member variable to use in PaddedAtomicLong?
Eg.
public static class PaddedAtomicLong extends AtomicLong
{
public volatile long p1, p2, p3, p4, p5, p6 = 7L; // 8 * 6 = 48bytes
}
}
How do we ensure this will fit exactly inside the cache line (which is 64 bits I presume)? Does this means that PaddedAtomicLong object itself will take up 16bytes (8 bytes for object but what about the remaining 8 bytes) ?
Thanks Martin.
Add another 8 bytes for the value itself and a minimum of 8 bytes for the object header.
DeleteHi Martin,
ReplyDeletehow will be store an object of type VolatileLong in this case:
public final static class VolatileLong // 16byte
{
public volatile long value = 0L; // 8 byte
public long p1, p2, p3, p4, p5, p6; // 6*8 = 48byte
}
seems total = 16 + 8 + 48 = 72 bytes > 64 byte cache line. As far as I know header will have 2 words since is about 64bites system. an object of type VolatileLong will be store on 2 cache lines ? If was the case when two different objects of type VolatileLong can be stored one after another in memory, in the example bellow, second object of type VolatileLong will be stored from byte 9 of second cache line, since first object ends at byte 8 on second cache line or it's added another 7 bytes as padding and start from byte 16 ?
It does not matter if too much padding it used. It is important that we use enough. To discover object layout try the following tool:
Deletehttp://openjdk.java.net/projects/code-tools/jol/
I've seen object headers range from 4 - 12 bytes depending on JVM.
Fantastic article! Martin, small question: does Intel for example have a tool that would measure the cache hits and misses that you could recommend?
ReplyDeleteYes Intel has VTune. There are some other free tools that I discuss in this blog.
Deletehttp://mechanical-sympathy.blogspot.co.uk/2012/08/memory-access-patterns-are-important.html
Hi Martin ,
ReplyDeleteNice article . Two questions "
1. In general normal systems that don't need to have very high performance criteria (most apps I have worked in enterprise works well without any of these things that does have acceptable performance) , does the above complexity for cache line miss justified ?
2 . Having each programmer adding this typing of padding by programmer can be erroneous and make it look complex.
These are the sorts of issues which concern programmers working on high-performance applications or those providing libraries to support concurrent/parallel code. These are not the issues which should concern the typical programmer.
DeleteI modified your previous version of the code to annotate the value with @Contended and the results are as bad as the false sharing. Did you see better performance with @Contended?
ReplyDeletepublic final static class VolatileLong {
public @Contended volatile long v;}
Try -XX:-RestrictContended as a JVM flag.
DeleteYes, the flag made it performant. Interesting that oracle would want to restrict it by default.
DeleteHi Martin,
ReplyDeleteBeen reading about false sharing, cache coherence protocols, etc. and am doing some microbenchmarking in Java to see how false sharing effects performance. Basically, I have an array of longs of size num_threads * longs_per_cacheline (8 * 8 in my case). Then each thread i increments its respective long in the array (a[0], a[8], a[16], ...). This should prevent false sharing since there is only one counter per cacheline. However, when I change the offset so that the counters reside next to each other in the array (a[0], a[1], a[2], ...), I see little to no performance degradation. Running perf should reveal an increase in cache misses in the non-padded version due to an increase in cache coherence traffic but I see no indication of that. What is going on??
public class SharedCounter2 {
private static final int NUM_THREADS = Runtime.getRuntime().availableProcessors();
private static final int OFFSET = 8;
private static long[] counters = new long[NUM_THREADS * OFFSET];
private static Thread[] threads = new Thread[NUM_THREADS];
public static void main(String[] args) {
TimerUtil.time(() -> {
for (int i = 0; i < NUM_THREADS; i++) {
final int j = i;
threads[i] = new Thread(() -> {
for (int k = 0; k < 2100000000; k++) {
counters[j * OFFSET]++;
}
});
}
for (int i = 0; i < NUM_THREADS; i++) {
threads[i].start();
}
long sum = 0;
for (int i = 0; i < NUM_THREADS; i++) {
try {
threads[i].join();
sum += counters[i * OFFSET];
counters[i * OFFSET] = 0;
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println("Sum: " + sum);
}, 10);
}
}
P.S. A similar version of the above code using a shared AtomicLong such that all threads simply call getAndIncrement() performs horribly as expected.
Try changing your code to be an AtomicLongArray then try the various options on that.
DeleteYes, changing it to an AtomicLongArray does cause the performance to degrade when there is false sharing.
DeleteI suspect that since AtomicLongArray is doing volatile accesses, the memory barriers are flushing the store buffer, thus causing invalidations if the counters reside in the same cacheline. On the other hand, the code above does not perform volatile accesses (they're not shared, except for when the main thread accumulates the sum), the store buffers aren't being flushed as often?
It is all about blocking progress. Store buffers, write combining buffers, out of order execution, etc. Memory ordered writes highlight the issues. Fundamentally can you make progress without the L1 cacheline being in exclusive state when using the ordered write operations is worth digging into.
DeleteIs there possibility to write java agent that will pad objects if annotated. This way client code will be clean.
ReplyDeleteThoughts
Do contended variables work well with Unsafe.putLong/Unsafe.putOrderedLong? I've written a very simple class it doesnt seem to working as I expect it to:
ReplyDeletepublic class ContendedAtomicCounter {
private static final Unsafe UNSAFE = UnsafeAccess.UNSAFE;
private static final long VALUE_OFFSET;
@Contended
private volatile long value;
static {
try {
VALUE_OFFSET = UNSAFE.objectFieldOffset(Field.class.getDeclaredField("value"));
} catch (NoSuchFieldException e) {
throw new RuntimeException(e);
}
}
public ContendedAtomicCounter(long value) {
set(value);
}
public void set(final long value) {
UNSAFE.putLong(this, VALUE_OFFSET, value);
}
public void setVolatile(long value) {
UNSAFE.putLongVolatile(this, VALUE_OFFSET, value);
}
public long get() {
return value;
}
public boolean compareAndSet(long expected, long updated) {
return UNSAFE.compareAndSwapLong(this, VALUE_OFFSET, expected, updated);
}
public long incrementAndGet() {
return getAndIncrement() + 1L;
}
public long getAndIncrement() {
return UNSAFE.getAndAddLong(this, VALUE_OFFSET, 1L);
}
}
Hi Martin
ReplyDeleteIm confused of my results which I have run on my 64bit jvm, jdk8 and Intel Core i7-4790 3.60ghz
JOL output says that object header stores 12 bytes, and also alignment / padding gap stores 4 bytes:
OFFSET SIZE TYPE DESCRIPTION VALUE
0 12 (object header) N / A
12 4 (alignment / padding gap)
16 8 long AtomicLong.value N / A
24 8 long PaddedAtomicLong.p1 N / A
32 8 long PaddedAtomicLong.p2 N / A
40 8 long PaddedAtomicLong.p3 N / A
48 8 long PaddedAtomicLong.p4 N / A
56 8 long PaddedAtomicLong.p5 N / A
Instance size: 64 bytes
Space losses: 4 bytes internal + 0 bytes external = 4 bytes total
So regarding that, I'm correct with using only 5 paddings in my PaddedAtomicLong.
Surprisingly, tests duration results vary from time to time ...
Sometimes duration is about 5 ~ seconds, and sometimes it runs for 18 ~ seconds.
I've even tried to put some warmup phases before exact test, but that didnt help either.
Why is that happening? Any Ideas?