5 ms·

does anybody have any idea what's going on here? If I had to guess I'd say that the code is doing too much synchronization between threads that, in the end, on

by pilif 16y ago

does anybody have any idea what's going on here? If I had to guess I'd say that the code is doing too much synchronization between threads that, in the end, only one thread really gets to run at a time anyways at which point moving the process from CPU to CPU is the only thing going on besides running that one thread on the server, hence it's way faster if it doesn't have to do any moving around. IMHO this is an indication of a bug in the code and not generic advice. Or does somebody see another issue that might cause this?

spudlyo 16y ago
If it was a mutex contention issue, moving it to a single core wouldn't change anything -- there would be still be contention. I'm guessing it has something to do with CPU cache hits.
- bnoordhuis 16y ago
  No, that's not right. There is only one code path executing so there can never be another thread contending for the same lock. A lock begins as a spinlock (busy wait loop) for a few thousand iterations before degrading to a full-blown lock that puts the thread to sleep. Because there is no other thread vying for the lock, the spinlock succeeds immediately and the thread keeps on running.
  - spudlyo 16y ago
    There is only one code path executing so there can never be another thread contending for the same lock. Are you sure there is only one code path executing? Don't all the threads get allocated time slices of the single CPU? I believe it's true that there is only one concurrent code path, but a thread can still acquire a lock and then come off the CPU.
    - bnoordhuis 16y ago
      Yes, you are right - and my previous comment somewhat skims over the details. Sorry for that. :) The difference in a single-core scenario is that the threads can't all become starved because a thread on another CPU holds the lock - the VM will simply cycle to the next thread and continue. In interpreted mode you don't even suffer a context switch. One edge case is where a thread acquires a lock and is then itself put to sleep because of blocking I/O or trying to obtain another lock. But that is simply a bad practice.
- JoeAltmaier 16y ago
  Inter-core mutex is MUCH slower than single-core. Because of the "memory boundary" problem. See, any lock depends upon a single memory location that is atomically test and set. When more than one cpu is involved, then the memory has to be plumbed down thru caches until its in memory common to all involved cpus - which is probably main memory when more than 2 cores are involved. On a single CPU its the L2 cache.
bnoordhuis 16y ago
I think you are on to something. His example code uses AtomicLong, a class that needs to synchronize on itself if the architecture has no native method to update 64 bits integers. Too bad Paul doesn't mention if he is running a 32 bits or 64 bits VM.
lincolnq 16y ago
Sort of agree, although my intuition tells me not that there's an excessively-coarse-locking problem, but that there's most likely a contention problem. The essence of a contention problem, for those who don't know, is that some shared structure (maybe a counter, or the head of a queue, or something) is polled and updated for every message that needs to be processed. Since processors don't (usually) share their caches, updating a value in shared memory causes that cache line on the other processors to be invalidated, so the next time the other processor needs to poll that value it has to retrieve it from memory, which takes a lot of extra time compared to getting it off the L1. This problem often arises with shared work queues and counters. For work queues you can solve it by giving each processor its own work queue and having it steal work from other processors when it finishes its own queue. A textbook by Herlihy and Shavit, The Art of Multiprocessor Programming, discusses this stuff in detail.
- deleted 16y ago
  [deleted]
- gipyro 16y ago
  This is pretty much correct. Another solution to this is to have an array[#CPU] of counters/structures and you only update the counter/structure for that specific CPU.
  - kmod 16y ago
    Not quite -- you need to make sure that the counters are on separate cache lines, otherwise you'll still get the same issue.
- ntoshev 16y ago
  This hypothesis makes a lot of sense. One should be able to test it on a Nehalem architecture: benchmark the program running on two cores, once choosing them to be different physical cores versus the same physical core. Your theory predicts the latter option to be much faster, and faster than the single core mode, because the two virtual cores will share the same caches.
gizmo 16y ago
A bug in the code? That makes little sense. The thing is this is a microoptimization, so the effect of taking a slightly different code path explodes and becomes significant. We could be measuring anything here. Maybe we're measuring the internal locking mechanics of Java. Maybe we're measuring the TCP stack internals. Maybe it's just about the CPU cache. Maybe it's about context switching in his specific linux kernel. It could be any number of things you're measuring here. Anything! His idea of running apache tomcat and apache bench shows that he didn't really think it through, because OF COURSE a 6 microsecond difference is not going to show up because processing HTTP headers takes miliseconds! Orders of magnitude difference here!
illumin8 16y ago
Here is what is going on: He's using Intel Core i7. This architecture is very similar to AMD Hypertransport in that each CPU is directly attached to a bank of memory, and has an on-die memory controller. This has obvious performance benefits because smart operating system kernels can take advantage of this and locate a processes memory on the bank connected directly to the CPU the process is running on. There is a slight disadvantage though when running highly multithreaded applications: If a thread running on CPU A wants to access memory on CPU B, it takes an extra hop to get there. This increases memory latency. What is happening is that he has a highly multithreaded application where threads are accessing memory attached to a different CPU. When he restricts the process to a single core, all memory is directly attached to the CPU and there are no extra hops, decreasing memory latency and increasing performance dramatically. This trick only works on processes that can effectively run on only one CPU and within the memory limit of that CPU's attached RAM.
- deleted 16y ago
  [deleted]
- deleted 16y ago
  [deleted]
- illumin8 16y ago
  I may have to revise my theory because it seems like he is running a single CPU system (quad core, hyperthreaded to look like 8 cores). Without a multiple physical CPU system the extra memory hop wouldn't exist. This could also be an issue caused by hyperthreading itself. The extra 4 cores are not real physical cores on the die. They are just an extra thread that runs on each of the existing cores. What could be happening is that there is some thread locking going on where one thread is waiting for a message or event from a thread that is executing on the virtual second core, which in turn isn't executing right at the moment because it's not a real core. An interesting test would be to have him turn off Hyperthreading in the BIOS and see if that improves performance without limiting to only 1 core. Alternatively, he could restrict the process to run on CPUs 0, 2, 4, and 6, which should run it on only the "real" cores. I always disliked Intel's hyperthreading. Don't try to fool me into thinking I have more cores than I really do. I know it speeds up some apps, but it hurts others.
azim 16y ago
I've done a lot of work on similar topics, building real-time messaging systems in C++. The author's findings are not unique and are very common to any producer-consumer messaging system. Essentially the issue is that you want your L2 to stay hot. If a single core is enough to satisfy your processing requirements, adding more threads and more cores isn't going to speed you up. Instead the parallelism will actually put more pressure on the scheduler, causing your threads to bounce around to cores with a cold L2 cache. If your cache is cold, your pipeline stalls out, and your performance is dead.
- runT1ME 16y ago
  ding ding ding. >Essentially the issue is that you want your L2 to stay hot Exactly the reason a 'parallel' app can slow down as you get more cores. More contention means more ACTUAL locking which mean more cache flushes, from my understanding.
acqq 16y ago
I'm very sure he has the code he haven't really made to properly scale with more cores or processors. The fact that he doesn't write much about the code in the article suggests me that he doesn't really know how to make scalable processing -- for anything nontrivial it's not easy at all, and I'd personally be able to make it more optimal in C than in Java, simply because there's more that I don't directly control in Java.
- nl 16y ago
  The fact that he doesn't write much about the code in the article suggests me that he doesn't really know how to make scalable processing If you read his blog, you may revist that opinion. He wrote the custom email server that powers mailinator which processes over 2 million emails an hour. Take a look at http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html http://mailinator.blogspot.com/2009/06/beautiful-race-condit... or http://mailinator.blogspot.com/2009/06/on-java-visibility.html http://mailinator.blogspot.com/2009/06/on-java-visibility.ht... for example. And I bet you couldn't make it more optimal in C.
  - acqq 16y ago
    I still claim he doesn't understand scalability for multi processor platforms. I don't claim he didn't made fast processing by writing his custom code, but he writes, his code is fastest on a single core, and as far as I see, he doesn't know why. So I conclude he knows to code but only non-parallel.

by pilif 16y ago

spudlyo 16y ago

If it was a mutex contention issue, moving it to a single core wouldn't change anything -- there would be still be contention. I'm guessing it has something to do with CPU cache hits.

bnoordhuis 16y ago
No, that's not right. There is only one code path executing so there can never be another thread contending for the same lock. A lock begins as a spinlock (busy wait loop) for a few thousand iterations before degrading to a full-blown lock that puts the thread to sleep. Because there is no other thread vying for the lock, the spinlock succeeds immediately and the thread keeps on running.
- spudlyo 16y ago
  There is only one code path executing so there can never be another thread contending for the same lock. Are you sure there is only one code path executing? Don't all the threads get allocated time slices of the single CPU? I believe it's true that there is only one concurrent code path, but a thread can still acquire a lock and then come off the CPU.
  - bnoordhuis 16y ago
    Yes, you are right - and my previous comment somewhat skims over the details. Sorry for that. :) The difference in a single-core scenario is that the threads can't all become starved because a thread on another CPU holds the lock - the VM will simply cycle to the next thread and continue. In interpreted mode you don't even suffer a context switch. One edge case is where a thread acquires a lock and is then itself put to sleep because of blocking I/O or trying to obtain another lock. But that is simply a bad practice.
JoeAltmaier 16y ago
Inter-core mutex is MUCH slower than single-core. Because of the "memory boundary" problem. See, any lock depends upon a single memory location that is atomically test and set. When more than one cpu is involved, then the memory has to be plumbed down thru caches until its in memory common to all involved cpus - which is probably main memory when more than 2 cores are involved. On a single CPU its the L2 cache.

bnoordhuis 16y ago

I think you are on to something. His example code uses AtomicLong, a class that needs to synchronize on itself if the architecture has no native method to update 64 bits integers. Too bad Paul doesn't mention if he is running a 32 bits or 64 bits VM.

lincolnq 16y ago

Sort of agree, although my intuition tells me not that there's an excessively-coarse-locking problem, but that there's most likely a contention problem. The essence of a contention problem, for those who don't know, is that some shared structure (maybe a counter, or the head of a queue, or something) is polled and updated for every message that needs to be processed. Since processors don't (usually) share their caches, updating a value in shared memory causes that cache line on the other processors to be invalidated, so the next time the other processor needs to poll that value it has to retrieve it from memory, which takes a lot of extra time compared to getting it off the L1. This problem often arises with shared work queues and counters. For work queues you can solve it by giving each processor its own work queue and having it steal work from other processors when it finishes its own queue. A textbook by Herlihy and Shavit, The Art of Multiprocessor Programming, discusses this stuff in detail.

deleted 16y ago
[deleted]
gipyro 16y ago
This is pretty much correct. Another solution to this is to have an array[#CPU] of counters/structures and you only update the counter/structure for that specific CPU.
- kmod 16y ago
  Not quite -- you need to make sure that the counters are on separate cache lines, otherwise you'll still get the same issue.
ntoshev 16y ago
This hypothesis makes a lot of sense. One should be able to test it on a Nehalem architecture: benchmark the program running on two cores, once choosing them to be different physical cores versus the same physical core. Your theory predicts the latter option to be much faster, and faster than the single core mode, because the two virtual cores will share the same caches.

gizmo 16y ago

A bug in the code? That makes little sense. The thing is this is a microoptimization, so the effect of taking a slightly different code path explodes and becomes significant. We could be measuring anything here. Maybe we're measuring the internal locking mechanics of Java. Maybe we're measuring the TCP stack internals. Maybe it's just about the CPU cache. Maybe it's about context switching in his specific linux kernel. It could be any number of things you're measuring here. Anything! His idea of running apache tomcat and apache bench shows that he didn't really think it through, because OF COURSE a 6 microsecond difference is not going to show up because processing HTTP headers takes miliseconds! Orders of magnitude difference here!

illumin8 16y ago

Here is what is going on: He's using Intel Core i7. This architecture is very similar to AMD Hypertransport in that each CPU is directly attached to a bank of memory, and has an on-die memory controller. This has obvious performance benefits because smart operating system kernels can take advantage of this and locate a processes memory on the bank connected directly to the CPU the process is running on. There is a slight disadvantage though when running highly multithreaded applications: If a thread running on CPU A wants to access memory on CPU B, it takes an extra hop to get there. This increases memory latency. What is happening is that he has a highly multithreaded application where threads are accessing memory attached to a different CPU. When he restricts the process to a single core, all memory is directly attached to the CPU and there are no extra hops, decreasing memory latency and increasing performance dramatically. This trick only works on processes that can effectively run on only one CPU and within the memory limit of that CPU's attached RAM.

deleted 16y ago
[deleted]
deleted 16y ago
[deleted]
illumin8 16y ago
I may have to revise my theory because it seems like he is running a single CPU system (quad core, hyperthreaded to look like 8 cores). Without a multiple physical CPU system the extra memory hop wouldn't exist. This could also be an issue caused by hyperthreading itself. The extra 4 cores are not real physical cores on the die. They are just an extra thread that runs on each of the existing cores. What could be happening is that there is some thread locking going on where one thread is waiting for a message or event from a thread that is executing on the virtual second core, which in turn isn't executing right at the moment because it's not a real core. An interesting test would be to have him turn off Hyperthreading in the BIOS and see if that improves performance without limiting to only 1 core. Alternatively, he could restrict the process to run on CPUs 0, 2, 4, and 6, which should run it on only the "real" cores. I always disliked Intel's hyperthreading. Don't try to fool me into thinking I have more cores than I really do. I know it speeds up some apps, but it hurts others.

azim 16y ago

I've done a lot of work on similar topics, building real-time messaging systems in C++. The author's findings are not unique and are very common to any producer-consumer messaging system. Essentially the issue is that you want your L2 to stay hot. If a single core is enough to satisfy your processing requirements, adding more threads and more cores isn't going to speed you up. Instead the parallelism will actually put more pressure on the scheduler, causing your threads to bounce around to cores with a cold L2 cache. If your cache is cold, your pipeline stalls out, and your performance is dead.

runT1ME 16y ago
ding ding ding. >Essentially the issue is that you want your L2 to stay hot Exactly the reason a 'parallel' app can slow down as you get more cores. More contention means more ACTUAL locking which mean more cache flushes, from my understanding.

acqq 16y ago

I'm very sure he has the code he haven't really made to properly scale with more cores or processors. The fact that he doesn't write much about the code in the article suggests me that he doesn't really know how to make scalable processing -- for anything nontrivial it's not easy at all, and I'd personally be able to make it more optimal in C than in Java, simply because there's more that I don't directly control in Java.

nl 16y ago
The fact that he doesn't write much about the code in the article suggests me that he doesn't really know how to make scalable processing If you read his blog, you may revist that opinion. He wrote the custom email server that powers mailinator which processes over 2 million emails an hour. Take a look at http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html http://mailinator.blogspot.com/2009/06/beautiful-race-condit... or http://mailinator.blogspot.com/2009/06/on-java-visibility.html http://mailinator.blogspot.com/2009/06/on-java-visibility.ht... for example. And I bet you couldn't make it more optimal in C.
- acqq 16y ago
  I still claim he doesn't understand scalability for multi processor platforms. I don't claim he didn't made fast processing by writing his custom code, but he writes, his code is fastest on a single core, and as far as I see, he doesn't know why. So I conclude he knows to code but only non-parallel.