7 ms·

Multi-core scaling: it’s not multi-threaded

65 points by lukes386 14y ago

speeder 14y ago
I wonder if we will ever figure a way to resume improving clock cycles instead of adding more parallelism. Parallelism has two major issues: First, not all applications need it, in many cases you want to do just a series of operations in a single starting number, and you don't need anything else, like if you are for example calculating a factorial, if you need only one factorial, it is useless to make it more parallel. Second, it is absurdly hard to code stuff for heavily parallelised hardware, most coders will make crap code that don't work, no matter how good we become in making helper libraries, it is totally another way of thinking. Yes, for some things, like servers, where you can throw a user into each core, it is nice... But for many other uses, even simple single-core parallelism, like SIMD, is not much useful.
- xentronium 14y ago
  > First, not all applications need it, in many cases you want to do just a series of operations in a single starting number, and you don't need anything else, like if you are for example calculating a factorial, if you need only one factorial, it is useless to make it more parallel. Sorry for nitpicking, but calculating factorial can certainly be parallelized. Easiest way to do this is multiply every n-th number on each core and then multiply n results together.
  - speeder 14y ago
    I doubt that you can have a much increase in performance as cores increase unless you are calculating numbers with huge amount of bits.
    - tbrownaw 14y ago
      Considering that factorial of 1e6 has about 18e6 bits (and factorial of 1e3 has 8.5e3 bits)? Yes, any factorial that doesn't have a huge amount of bits will be fast enough to calculate that there's not much point to parallelizing it.
    - PurplePanda 14y ago
      as the size of the input to the procedure increases you will indeed be calculating with numbers with a huge amount of bits
- stevenameyer 14y ago
  Well what we really need to continue to improve clock cycles is better cooling. Overclocking modern chips is really easy and all you really need to get a pretty solid increase in speed is a decent cpu cooler. Yes to get drastic increases you need to up voltage to the chip and there are concerns about the chip degrading faster at higher clock cycles, but for the most part a solid increase in speed can be achieved simply by telling it to go faster and making sure it doesn't overheat.
- sliverstorm 14y ago
  I wonder if we will ever figure a way to resume improving clock cycles instead of adding more parallelism. IPC has been steadily improving generation over generation, but it is a slow march. Chip frequency does not seem like it is going to go anywhere without some serious breakthroughs; processors are thermally limited, and while you can work on saving power there don't seem to be any 10x improvements in power coming that could let you crank up the clock. Scaling voltage down is great for reducing switching power, but it depends on smaller and smaller transistors, so leakage power has been steadily growing and eating into those gains. Chips are up against a lot of walls- power consumption, heat dissipation, and so on. Chip makers have and are working on pushing forwards, but short of a new kind of transistor there do not appear to be any improvements by orders of magnitude on the horizon for single-core performance. This is why parallelism is important. It is hard, and not every workload can be parallelised well, but there is simply no other known way to secure a 4x, 8x, 16x, etc boost in performance than 4x, 8x, 16x, etc parallelism. (Assuming your code isn't terrible, in which case fix your code!)
- tbrownaw 14y ago
  Sure parallel code is harder than sequential code, but it's not really all that much harder (maybe about 8 credit-hours at your local university?). The reason it's "too hard" is that most programs aren't slow enough to be worth the bother.
- TallGuyShort 14y ago
  If you're interested in faster clock cycles, check out the specs on this beast: http://www-03.ibm.com/systems/z/hardware/zenterprise/zec12.html http://www-03.ibm.com/systems/z/hardware/zenterprise/zec12.h...
  - masklinn 14y ago
    > If you're interested in faster clock cycles, check out the specs on this beast: http://www-03.ibm.com/systems/z/hardware/zenterprise/zec12.h.. http://www-03.ibm.com/systems/z/hardware/zenterprise/zec12.h.... You can overclock an old Core 2 higher than that, with a bit of luck and good gear. And it'll undoubtedly be cheaper than buying an IBM 'frame. FWIW overclocking records are currently above 8GHz on Vishera using N2 cooling. Granted N2 cooling can't actually be used, but that gives you the limits of the chips. You can reach 5.5GHz on water, and 6+ on cascade or single stage (which do work as standard cooling solutions)
- Symmetry 14y ago
  For increasing frequency the problem is we used to be able to just bump the clock speeds when the circuits shrank, but we've gotten small enough that the transistors start to leak now, so we have to drive them with less voltage to prevent the chip from overheating, meaning the clock has to come back down </huge-oversimplification>. There are some possible ways forward. If we're sticking with transistors we might be able to switch to a material with better electrical properties, but that needs lots of research before it'll be higher performance than silicon. There are also funky non-transistor based ideas for doing computation, like using DNA or nano-scale clockwork or ballistic electrons. I have no idea how feasible that stuff is. In the shorter term, computer engineers are finding ways to turn those extra transistors into better single threaded performance by better prefetching, branch prediction, and re-ordering your instructions so that more than one are executed at a time even though you never thought about parallelism when writing it. That's why a modern computer core is much faster than an old Pentium 4, even though the clock speeds might be the same. The problem with that is that using more transistors tends to provider at most a O(sqrt(n)) speedup, whereas adding more cores potentially provides an O(n) speedup.
jws 14y ago
…from 33-MHz to 3-GHz, a thousand-fold increase… There had to be a better way to write that. I suppose more work per clock cycle and increased number of cores contributes the other x10 of raw performance. But then the author goes on to say they are stuck, which isn't true of performance, only clock rate. In any event, putting an "up is down" in your sentence should generally be avoided. Edit: The >>>proscribed<<< method for resolving this is a “lock”, where… Sigh. The article covers a lot of ground lightly. It talks about the new Haswell transactional memory instructions, the way Linux shards network counters, and a way to make Linux not use a core so you can schedule a process on it that will never be preempted.
- shawkinaw 14y ago
  I think he just screwed up the math.
6ren 14y ago
Hypothesis: we will never solve multi-core for general purpose computing (there's also http://en.wikipedia.org/wiki/Amdahl%27s_law http://en.wikipedia.org/wiki/Amdahl%27s_law). But we can do multi-core for the embarrassing parallelizable - such as graphics (top GPUs have over 1000 cores), so instead of solving this problem, our focus will shift to those tasks for which multi-core does work - because it's only these that keep improving at Moore's Law-like rates. Arguably, this is already happening.
- joe_the_user 14y ago
  I am not sure what would theoretically prevent each web page and each application from running on a separate core (or two). Considering the number of people who love multiple tabs, I can't see how that wouldn't seem like a win for even thirty or more cores.
  - tbrownaw 14y ago
    I thought some browsers already do this? But it still won't make use of more than a very small number of cores, one (or a couple) for the tab you're interacting with, and a small part of another one for all the other tabs that are sitting there idle.
    - mistercow 14y ago
      Chrome does split pages across different processes, and this, as far as I know, makes use of multiple cores. For (I assume) memory overhead reasons, it doesn't put each tab in a separate process by default, although there is (or used to be) a flag to switch to that behavior.
  - mistercow 14y ago
    The problem is that most web pages and programs don't actually do very much when they're in the background, and many (most?) of the software that does grind away for long periods of time without user interaction (compilers, ray tracers, video encoding etc.) are already able to make good use of many cores. But users who fit that profile are a niche market. What the vast majority of users need in terms of speed is acute performance. A dedicated core for every webpage is not very useful because users don't load up a bunch of tabs at the same time and then flip between them many times per second, interacting with each one. Instead CPU usage tends to happen in short bursts directly following user interaction, so even if every tab has its own core, you won't usually see very much contention for CPU between different tabs. The same goes for most native programs. Users just don't multitask fast enough to make separate cores relevant for most programs.
nkurz 14y ago
He suggests an interesting approach. 1) Tell the kernel it only has a limited set of cores to work with. The way to fix Snort’s jitter issues is to change the Linux boot parameters. For example, set “maxcpus=2”. This will cause Linux to use only the first two CPUs of the system. Sure, it knows other CPU cores exist, it just will never by default schedule a thread to run on them. 2) Manually schedule your high priority process onto a reserved core. Then what you do in your code is call the “pthread_setaffinity_np()” function call to put your thread on one of the inactive CPUs (there is Snort configuration option to do this per process). As long as you manually put only one thread per CPU, it will NEVER be interrupted by the Linux kernel. 3) Turn off interrupts to keep things as real time as possible. You can still get hardware interrupts, though. Interrupt handlers are really short, so probably won’t exceed your jitter budget, but if they do, you can tweak that as well. Go into “/proc/irq/smp_affinity” and turn of the interrupts in your Snort processing threads. 4) Profit? At this point, I’m a little hazy at what precisely happens. What I think will happen is that your thread won’t be interrupted, not even for a clock cycle. Can anyone remove the haziness? I'm more interested in this for benchmarking than performance, and wonder how it compares to other ways of increasing priority like "chrt". Is booting with a low "maxcpus" necessary, or can the same be done at runtime?
- jamesaguilar 14y ago
  I think he has some iffy premises. I'm not certain, but I guess pthread mutexes probably use userspace mutexes under the covers. If they don't you could select a library that does. Grabbing uncontended mutexes should be basically free. It is definitely not a good idea to write all your own abstractions, as he suggests, unless you have a really great understanding of the issues involved. You'd probably still get it wrong sometimes even with that. Affinity is definitely valuable, but I don't think you should need to disable interrupts for most applications. I'm not even sure if it is generally possible, since interrupts are sometimes used to swap pages or notify the kernel that a page isn't mapped or that a blocked resource is now available. The reason affinity is valuable is not because of kernel interactions. It's because of NUMA and cpu cache swapping. Affinity can prevent thread migration, which is expensive mainly because data also has to be migrated or else accessed in a less efficient manner. Likewise, make sure that if you dispatch an asynchronous call, the handler runs on the same core you sent the call from. Finally, it's a common fallacy in these kinds of posts to act as if threads can't be used to do shared-little or shared-nothing-style multi-programming. They often aren't, but there's nothing that prevents it.
abraininavat 14y ago
Maybe I'm missing something, but I'm not getting the point. It seems to me there's no fundamental difference between multiprocess with shared-memory regions for anything that needs to be shared and multithreaded with mostly thread-local storage plus some shared data. The kernel is going to multiplex your single-threaded processes among the available cores just the same as it will multiplex your multiple threads among the available cores. Multi-threaded techniques, like mutexes, don’t scale on multi-core. Conversely, as Snort demonstrates, you can split a problem across multiple processes instead of threads, and still have multi-core code. Synchronization is synchronization. There are inter-process synchronization primitives, including mutexes. And you can use lock-free synchronization in a single-process multi-threaded scenario.
kyrra 14y ago
Tangentially related, Snort was doing research to move to a multi-threaded architecture, but decided against it due to cache synchronization problems [1]. Though, their thoughts about splitting up processing was quite different than what the OP blog post suggests. It looks like Snort gave up on one way of doing multi-threading, but they could still go the way suggested in the OPs post. [1] http://securitysauce.blogspot.com/2009/04/snort-30-beta-3-released.html http://securitysauce.blogspot.com/2009/04/snort-30-beta-3-re...
- robertgraham 14y ago
  Yea, some engineers created a ground-up rewrite of Snort called "Suricata" that was multi-threaded, and therefore faster than Snort, which is only single-threaded. Suricata then failed to show any benchmark where they exceeded Snort's speed, and they fail to mention that Snort works fine on multi-core. It's one of those things "everyone knows multi-threaded is better than single-threaded", but everyone's wrong.
miga 14y ago
I recall similar results on nearly all applications since my late MSc study: Mutexes are bad, pipes and sockets give better scaling. Thread sync primitives just sometimes scale up to 8-12 cores, but indeed multiprocess applications usually get much faster. In the age of GCed VMs one needs to also consider sync cost of GC.
javert 14y ago
So, this post has a number of errors, and is fundamentally wrong. (a) pthread_mutex_t and friends use futexes, which only call into the kernel when there actually is contention. (b) it would be better to use chrt (change to real-time priority) than the maxcpus trick, because the former accomplishes the same thing, but allows the core to still be used if the high-priority thread suspends (e.g. to do disk or network I/o). (c) Contrary to his claim about Snort, there is no reason to prefer a multiprocess design over a multithreaded design for a particular application. There is no savings in overhead or synchronization or anything like that by going with processes. In fact, using processes and then using memory mapping to share when you could use threads, is just making things harder for yourself for no reason. (d) What I’m trying to show you here is that “multi-core” doesn’t automatically mean “multi-threaded”. Well, in computer science terminology, a thread is a schedulable entity, and a process is a schedulable entity with memory protection. So, he's wrong. Lots of developers talk about threads and processes as orthogonal things, though, so I can see why he made that claim. (e) The overall theme of my talk was to impress upon the audience that in order to create scalable application, you need to move your code out of the operating system kernel. You need to code everything yourself instead of letting the kernel do the heavy lifting for you. That is horrible advice that is just going to lead to lots of bugs and wasted effort. It's premature optimization. Even most people using the Linux realtime preemption patch (PREEMPT_RT) do not have such strict requirements that they need to take this advice. (f) Your basic design should be one thread per core and lock-free synchronization that never causes a thread to stop and wait. Might apply to certain very specific real-time (as in, embedded systems or HFT) scenarios, but in general, no, you're just wasting the core when that one thread doesn't need to use it. Prefer real-time priorities if you really need it. (g) Specifically, I’ve tried to drill into you the idea that what people call “multi-threaded” coding is not the same as “multi-core”. Multi-threaded techniques, like mutexes, don’t scale on multi-core. Again, you can only use multiple cores in parallel if there are multiple threads. And multi-threaded techniques do scale. You definitely may want to use lock-free synchronization instead of mutexes in some specialized scenarios, though. EDIT: OK, here is one other thing I forgot in the list above. (h) There are multiple types of locks, like spinlocks, mutexes, critical sections, semaphores, and so on. Even among these classes there are many variations. Technically, mutexes and semaphores both are ways of protecting critical sections, and a spinlock is a way of implementing a lock (including, possibly, a mutex or semaphore lock). Again, this is to some degree the difference between developers with a shared lingo and computer scientists. But if you go by that kind of lingo, you're missing part of the picture.
javert 14y ago
There are two fundamental ways of doing this: pipelining and worker-threads. In the pipeline model, each thread does a different task, then hands off the task to the next thread in the pipeline. Why not just implement the pipeline entirely in one thread, and then replicate them (just like worker threads)? What will happen is that the first worker thread will be executing stage 2, while the second worker thread is executing stage 1. The OS will automatically schedule them on different cores. Am I missing something?
- robertgraham 14y ago
  When there is high-contention for a resource, it's better that one thread do it and access it contention-free, rather than make multiple threads content for it. Even so-called "lock-free" synchronization has locks, they are just very short (30 clock cycles). Therefore, you still want to avoid contention if you can figure out a way to do it. I didn't really go into enough detail in my example, but pulling packets off the network is a good example. You can have one thread do it, and therefore need no contention. Then you can setup multiple single-producer/single-consumer ring-buffers to forward those packets to worker threads to complete the processing of the packet. Thus, you essentially get rid of all the atomic/lock-free contention you would otherwise have.
  - javert 14y ago
    * When there is high-contention for a resource, it's better that one thread do it and access it contention-free, rather than make multiple threads content for it.* Right, and that's what I'm suggesting. So, if you have a pipelined architecture, keep the pipeline inside worker threads, instead of across them, except when you need to distribute work to the workers (i.e., the first stage, where you do something like take packets from the network). I think we agree on all that. I was just curious if there was ever a reason to do it the other way, i.e., having a separate thread for each stage of the entire pipeline. It seemed like you were suggesting that was useful in some cases, but perhaps I'm reading into things too much.
- wmf 14y ago
  If a certain stage has global state a pipeline architecture may result in lower contention because that state is only accessed by one core and thus doesn't have to be locked. Lock-free producer-consumer communication between stages can be efficient. (AFAIK LineRate just took pipelining to the bank.) If your app has no global state a run-to-completion aka worker architecture is more efficient.
stefantalpalaru 14y ago
"Multi-threaded software goes up to about four cores, but past that point, it fails to get any benefit from additional cores." Is there any basis for this affirmation or just the fact that his system has only 4 cores?
- montecarl 14y ago
  This article speaks in broad generalities that seemed to be based on the authors particular interests. There is no reason why multi-threaded software can't scale near linearly for the right problems.
  - pnathan 14y ago
    > There is no reason why multi-threaded software can't scale near linearly for the right problems. For the other problems, you're limited by Amdahl.
  - robertgraham 14y ago
    My point was to talk about the wrong problems. Networking is actually a "right" problem, and should be nearly embarrassingly parallel since two cores and process two unrelated packets at the same time. But, if you look at network stacks on open-source projects, you see a lot of fail. That's the point of my post, as a reference to point to why that spinlock in your networking code is a bad idea, and why it's probably better to replace it with an atomic operation or a lock-free alternative.
- robertgraham 14y ago
  My desktop is 6 hyperthreaded cores (12 "cores" total). It's a general principle of why mobile phone CPUs aren't putting a lot more cores in their devices, and why they didn't go the Atom route of hyperhreading: code on cellphones fail to take advantage of the additional cores.
- deleted 14y ago
  [deleted]
nonamegiven 14y ago
"Multi-tasking was the problem of making a single core run multiple tasks. The core would switch quickly from one task to the next to make it appear they were all running at the same time, even though during any particular microsecond only one task was running at a time. We now call this “multi-threading”, where “threads” are lighter weight tasks." I must have missed something. Multi-tasking is multiple processes, which mostly have nothing to do with each other, switched in and out of the processor(s) by the OS, which do not share in-process memory or context. The programmer does nothing to make this happen, and normally has little to no say in it. Multi-threading is a single process, where the threads carefully share context and memory, and they're all working roughly on the same thing; the programmer makes this happen explicitly, and usually fucks it up. https://en.wikipedia.org/wiki/Multitasking https://en.wikipedia.org/wiki/Multitasking https://en.wikipedia.org/wiki/Multitasking#Multithreading https://en.wikipedia.org/wiki/Multitasking#Multithreading

65 points by lukes386 14y ago

I wonder if we will ever figure a way to resume improving clock cycles instead of adding more parallelism. Parallelism has two major issues: First, not all applications need it, in many cases you want to do just a series of operations in a single starting number, and you don't need anything else, like if you are for example calculating a factorial, if you need only one factorial, it is useless to make it more parallel. Second, it is absurdly hard to code stuff for heavily parallelised hardware, most coders will make crap code that don't work, no matter how good we become in making helper libraries, it is totally another way of thinking. Yes, for some things, like servers, where you can throw a user into each core, it is nice... But for many other uses, even simple single-core parallelism, like SIMD, is not much useful.

xentronium 14y ago
> First, not all applications need it, in many cases you want to do just a series of operations in a single starting number, and you don't need anything else, like if you are for example calculating a factorial, if you need only one factorial, it is useless to make it more parallel. Sorry for nitpicking, but calculating factorial can certainly be parallelized. Easiest way to do this is multiply every n-th number on each core and then multiply n results together.
- speeder 14y ago
  I doubt that you can have a much increase in performance as cores increase unless you are calculating numbers with huge amount of bits.
  - tbrownaw 14y ago
    Considering that factorial of 1e6 has about 18e6 bits (and factorial of 1e3 has 8.5e3 bits)? Yes, any factorial that doesn't have a huge amount of bits will be fast enough to calculate that there's not much point to parallelizing it.
  - PurplePanda 14y ago
    as the size of the input to the procedure increases you will indeed be calculating with numbers with a huge amount of bits
stevenameyer 14y ago
Well what we really need to continue to improve clock cycles is better cooling. Overclocking modern chips is really easy and all you really need to get a pretty solid increase in speed is a decent cpu cooler. Yes to get drastic increases you need to up voltage to the chip and there are concerns about the chip degrading faster at higher clock cycles, but for the most part a solid increase in speed can be achieved simply by telling it to go faster and making sure it doesn't overheat.
sliverstorm 14y ago
I wonder if we will ever figure a way to resume improving clock cycles instead of adding more parallelism. IPC has been steadily improving generation over generation, but it is a slow march. Chip frequency does not seem like it is going to go anywhere without some serious breakthroughs; processors are thermally limited, and while you can work on saving power there don't seem to be any 10x improvements in power coming that could let you crank up the clock. Scaling voltage down is great for reducing switching power, but it depends on smaller and smaller transistors, so leakage power has been steadily growing and eating into those gains. Chips are up against a lot of walls- power consumption, heat dissipation, and so on. Chip makers have and are working on pushing forwards, but short of a new kind of transistor there do not appear to be any improvements by orders of magnitude on the horizon for single-core performance. This is why parallelism is important. It is hard, and not every workload can be parallelised well, but there is simply no other known way to secure a 4x, 8x, 16x, etc boost in performance than 4x, 8x, 16x, etc parallelism. (Assuming your code isn't terrible, in which case fix your code!)
tbrownaw 14y ago
Sure parallel code is harder than sequential code, but it's not really all that much harder (maybe about 8 credit-hours at your local university?). The reason it's "too hard" is that most programs aren't slow enough to be worth the bother.
TallGuyShort 14y ago
If you're interested in faster clock cycles, check out the specs on this beast: http://www-03.ibm.com/systems/z/hardware/zenterprise/zec12.html http://www-03.ibm.com/systems/z/hardware/zenterprise/zec12.h...
- masklinn 14y ago
  > If you're interested in faster clock cycles, check out the specs on this beast: http://www-03.ibm.com/systems/z/hardware/zenterprise/zec12.h.. http://www-03.ibm.com/systems/z/hardware/zenterprise/zec12.h.... You can overclock an old Core 2 higher than that, with a bit of luck and good gear. And it'll undoubtedly be cheaper than buying an IBM 'frame. FWIW overclocking records are currently above 8GHz on Vishera using N2 cooling. Granted N2 cooling can't actually be used, but that gives you the limits of the chips. You can reach 5.5GHz on water, and 6+ on cascade or single stage (which do work as standard cooling solutions)
Symmetry 14y ago
For increasing frequency the problem is we used to be able to just bump the clock speeds when the circuits shrank, but we've gotten small enough that the transistors start to leak now, so we have to drive them with less voltage to prevent the chip from overheating, meaning the clock has to come back down </huge-oversimplification>. There are some possible ways forward. If we're sticking with transistors we might be able to switch to a material with better electrical properties, but that needs lots of research before it'll be higher performance than silicon. There are also funky non-transistor based ideas for doing computation, like using DNA or nano-scale clockwork or ballistic electrons. I have no idea how feasible that stuff is. In the shorter term, computer engineers are finding ways to turn those extra transistors into better single threaded performance by better prefetching, branch prediction, and re-ordering your instructions so that more than one are executed at a time even though you never thought about parallelism when writing it. That's why a modern computer core is much faster than an old Pentium 4, even though the clock speeds might be the same. The problem with that is that using more transistors tends to provider at most a O(sqrt(n)) speedup, whereas adding more cores potentially provides an O(n) speedup.

jws 14y ago

…from 33-MHz to 3-GHz, a thousand-fold increase… There had to be a better way to write that. I suppose more work per clock cycle and increased number of cores contributes the other x10 of raw performance. But then the author goes on to say they are stuck, which isn't true of performance, only clock rate. In any event, putting an "up is down" in your sentence should generally be avoided. Edit: The >>>proscribed<<< method for resolving this is a “lock”, where… Sigh. The article covers a lot of ground lightly. It talks about the new Haswell transactional memory instructions, the way Linux shards network counters, and a way to make Linux not use a core so you can schedule a process on it that will never be preempted.

shawkinaw 14y ago
I think he just screwed up the math.

6ren 14y ago

Hypothesis: we will never solve multi-core for general purpose computing (there's also http://en.wikipedia.org/wiki/Amdahl%27s_law http://en.wikipedia.org/wiki/Amdahl%27s_law). But we can do multi-core for the embarrassing parallelizable - such as graphics (top GPUs have over 1000 cores), so instead of solving this problem, our focus will shift to those tasks for which multi-core does work - because it's only these that keep improving at Moore's Law-like rates. Arguably, this is already happening.

joe_the_user 14y ago
I am not sure what would theoretically prevent each web page and each application from running on a separate core (or two). Considering the number of people who love multiple tabs, I can't see how that wouldn't seem like a win for even thirty or more cores.
- tbrownaw 14y ago
  I thought some browsers already do this? But it still won't make use of more than a very small number of cores, one (or a couple) for the tab you're interacting with, and a small part of another one for all the other tabs that are sitting there idle.
  - mistercow 14y ago
    Chrome does split pages across different processes, and this, as far as I know, makes use of multiple cores. For (I assume) memory overhead reasons, it doesn't put each tab in a separate process by default, although there is (or used to be) a flag to switch to that behavior.
- mistercow 14y ago
  The problem is that most web pages and programs don't actually do very much when they're in the background, and many (most?) of the software that does grind away for long periods of time without user interaction (compilers, ray tracers, video encoding etc.) are already able to make good use of many cores. But users who fit that profile are a niche market. What the vast majority of users need in terms of speed is acute performance. A dedicated core for every webpage is not very useful because users don't load up a bunch of tabs at the same time and then flip between them many times per second, interacting with each one. Instead CPU usage tends to happen in short bursts directly following user interaction, so even if every tab has its own core, you won't usually see very much contention for CPU between different tabs. The same goes for most native programs. Users just don't multitask fast enough to make separate cores relevant for most programs.

nkurz 14y ago

He suggests an interesting approach. 1) Tell the kernel it only has a limited set of cores to work with. The way to fix Snort’s jitter issues is to change the Linux boot parameters. For example, set “maxcpus=2”. This will cause Linux to use only the first two CPUs of the system. Sure, it knows other CPU cores exist, it just will never by default schedule a thread to run on them. 2) Manually schedule your high priority process onto a reserved core. Then what you do in your code is call the “pthread_setaffinity_np()” function call to put your thread on one of the inactive CPUs (there is Snort configuration option to do this per process). As long as you manually put only one thread per CPU, it will NEVER be interrupted by the Linux kernel. 3) Turn off interrupts to keep things as real time as possible. You can still get hardware interrupts, though. Interrupt handlers are really short, so probably won’t exceed your jitter budget, but if they do, you can tweak that as well. Go into “/proc/irq/smp_affinity” and turn of the interrupts in your Snort processing threads. 4) Profit? At this point, I’m a little hazy at what precisely happens. What I think will happen is that your thread won’t be interrupted, not even for a clock cycle. Can anyone remove the haziness? I'm more interested in this for benchmarking than performance, and wonder how it compares to other ways of increasing priority like "chrt". Is booting with a low "maxcpus" necessary, or can the same be done at runtime?

jamesaguilar 14y ago
I think he has some iffy premises. I'm not certain, but I guess pthread mutexes probably use userspace mutexes under the covers. If they don't you could select a library that does. Grabbing uncontended mutexes should be basically free. It is definitely not a good idea to write all your own abstractions, as he suggests, unless you have a really great understanding of the issues involved. You'd probably still get it wrong sometimes even with that. Affinity is definitely valuable, but I don't think you should need to disable interrupts for most applications. I'm not even sure if it is generally possible, since interrupts are sometimes used to swap pages or notify the kernel that a page isn't mapped or that a blocked resource is now available. The reason affinity is valuable is not because of kernel interactions. It's because of NUMA and cpu cache swapping. Affinity can prevent thread migration, which is expensive mainly because data also has to be migrated or else accessed in a less efficient manner. Likewise, make sure that if you dispatch an asynchronous call, the handler runs on the same core you sent the call from. Finally, it's a common fallacy in these kinds of posts to act as if threads can't be used to do shared-little or shared-nothing-style multi-programming. They often aren't, but there's nothing that prevents it.

abraininavat 14y ago

Maybe I'm missing something, but I'm not getting the point. It seems to me there's no fundamental difference between multiprocess with shared-memory regions for anything that needs to be shared and multithreaded with mostly thread-local storage plus some shared data. The kernel is going to multiplex your single-threaded processes among the available cores just the same as it will multiplex your multiple threads among the available cores. Multi-threaded techniques, like mutexes, don’t scale on multi-core. Conversely, as Snort demonstrates, you can split a problem across multiple processes instead of threads, and still have multi-core code. Synchronization is synchronization. There are inter-process synchronization primitives, including mutexes. And you can use lock-free synchronization in a single-process multi-threaded scenario.

kyrra 14y ago

Tangentially related, Snort was doing research to move to a multi-threaded architecture, but decided against it due to cache synchronization problems [1]. Though, their thoughts about splitting up processing was quite different than what the OP blog post suggests. It looks like Snort gave up on one way of doing multi-threading, but they could still go the way suggested in the OPs post. [1] http://securitysauce.blogspot.com/2009/04/snort-30-beta-3-released.html http://securitysauce.blogspot.com/2009/04/snort-30-beta-3-re...

robertgraham 14y ago
Yea, some engineers created a ground-up rewrite of Snort called "Suricata" that was multi-threaded, and therefore faster than Snort, which is only single-threaded. Suricata then failed to show any benchmark where they exceeded Snort's speed, and they fail to mention that Snort works fine on multi-core. It's one of those things "everyone knows multi-threaded is better than single-threaded", but everyone's wrong.

miga 14y ago

I recall similar results on nearly all applications since my late MSc study: Mutexes are bad, pipes and sockets give better scaling. Thread sync primitives just sometimes scale up to 8-12 cores, but indeed multiprocess applications usually get much faster. In the age of GCed VMs one needs to also consider sync cost of GC.

javert 14y ago

So, this post has a number of errors, and is fundamentally wrong. (a) pthread_mutex_t and friends use futexes, which only call into the kernel when there actually is contention. (b) it would be better to use chrt (change to real-time priority) than the maxcpus trick, because the former accomplishes the same thing, but allows the core to still be used if the high-priority thread suspends (e.g. to do disk or network I/o). (c) Contrary to his claim about Snort, there is no reason to prefer a multiprocess design over a multithreaded design for a particular application. There is no savings in overhead or synchronization or anything like that by going with processes. In fact, using processes and then using memory mapping to share when you could use threads, is just making things harder for yourself for no reason. (d) What I’m trying to show you here is that “multi-core” doesn’t automatically mean “multi-threaded”. Well, in computer science terminology, a thread is a schedulable entity, and a process is a schedulable entity with memory protection. So, he's wrong. Lots of developers talk about threads and processes as orthogonal things, though, so I can see why he made that claim. (e) The overall theme of my talk was to impress upon the audience that in order to create scalable application, you need to move your code out of the operating system kernel. You need to code everything yourself instead of letting the kernel do the heavy lifting for you. That is horrible advice that is just going to lead to lots of bugs and wasted effort. It's premature optimization. Even most people using the Linux realtime preemption patch (PREEMPT_RT) do not have such strict requirements that they need to take this advice. (f) Your basic design should be one thread per core and lock-free synchronization that never causes a thread to stop and wait. Might apply to certain very specific real-time (as in, embedded systems or HFT) scenarios, but in general, no, you're just wasting the core when that one thread doesn't need to use it. Prefer real-time priorities if you really need it. (g) Specifically, I’ve tried to drill into you the idea that what people call “multi-threaded” coding is not the same as “multi-core”. Multi-threaded techniques, like mutexes, don’t scale on multi-core. Again, you can only use multiple cores in parallel if there are multiple threads. And multi-threaded techniques do scale. You definitely may want to use lock-free synchronization instead of mutexes in some specialized scenarios, though. EDIT: OK, here is one other thing I forgot in the list above. (h) There are multiple types of locks, like spinlocks, mutexes, critical sections, semaphores, and so on. Even among these classes there are many variations. Technically, mutexes and semaphores both are ways of protecting critical sections, and a spinlock is a way of implementing a lock (including, possibly, a mutex or semaphore lock). Again, this is to some degree the difference between developers with a shared lingo and computer scientists. But if you go by that kind of lingo, you're missing part of the picture.

javert 14y ago

There are two fundamental ways of doing this: pipelining and worker-threads. In the pipeline model, each thread does a different task, then hands off the task to the next thread in the pipeline. Why not just implement the pipeline entirely in one thread, and then replicate them (just like worker threads)? What will happen is that the first worker thread will be executing stage 2, while the second worker thread is executing stage 1. The OS will automatically schedule them on different cores. Am I missing something?

robertgraham 14y ago
When there is high-contention for a resource, it's better that one thread do it and access it contention-free, rather than make multiple threads content for it. Even so-called "lock-free" synchronization has locks, they are just very short (30 clock cycles). Therefore, you still want to avoid contention if you can figure out a way to do it. I didn't really go into enough detail in my example, but pulling packets off the network is a good example. You can have one thread do it, and therefore need no contention. Then you can setup multiple single-producer/single-consumer ring-buffers to forward those packets to worker threads to complete the processing of the packet. Thus, you essentially get rid of all the atomic/lock-free contention you would otherwise have.
- javert 14y ago
  * When there is high-contention for a resource, it's better that one thread do it and access it contention-free, rather than make multiple threads content for it.* Right, and that's what I'm suggesting. So, if you have a pipelined architecture, keep the pipeline inside worker threads, instead of across them, except when you need to distribute work to the workers (i.e., the first stage, where you do something like take packets from the network). I think we agree on all that. I was just curious if there was ever a reason to do it the other way, i.e., having a separate thread for each stage of the entire pipeline. It seemed like you were suggesting that was useful in some cases, but perhaps I'm reading into things too much.
wmf 14y ago
If a certain stage has global state a pipeline architecture may result in lower contention because that state is only accessed by one core and thus doesn't have to be locked. Lock-free producer-consumer communication between stages can be efficient. (AFAIK LineRate just took pipelining to the bank.) If your app has no global state a run-to-completion aka worker architecture is more efficient.

stefantalpalaru 14y ago

"Multi-threaded software goes up to about four cores, but past that point, it fails to get any benefit from additional cores." Is there any basis for this affirmation or just the fact that his system has only 4 cores?

montecarl 14y ago
This article speaks in broad generalities that seemed to be based on the authors particular interests. There is no reason why multi-threaded software can't scale near linearly for the right problems.
- pnathan 14y ago
  > There is no reason why multi-threaded software can't scale near linearly for the right problems. For the other problems, you're limited by Amdahl.
- robertgraham 14y ago
  My point was to talk about the wrong problems. Networking is actually a "right" problem, and should be nearly embarrassingly parallel since two cores and process two unrelated packets at the same time. But, if you look at network stacks on open-source projects, you see a lot of fail. That's the point of my post, as a reference to point to why that spinlock in your networking code is a bad idea, and why it's probably better to replace it with an atomic operation or a lock-free alternative.
robertgraham 14y ago
My desktop is 6 hyperthreaded cores (12 "cores" total). It's a general principle of why mobile phone CPUs aren't putting a lot more cores in their devices, and why they didn't go the Atom route of hyperhreading: code on cellphones fail to take advantage of the additional cores.
deleted 14y ago
[deleted]

nonamegiven 14y ago

"Multi-tasking was the problem of making a single core run multiple tasks. The core would switch quickly from one task to the next to make it appear they were all running at the same time, even though during any particular microsecond only one task was running at a time. We now call this “multi-threading”, where “threads” are lighter weight tasks." I must have missed something. Multi-tasking is multiple processes, which mostly have nothing to do with each other, switched in and out of the processor(s) by the OS, which do not share in-process memory or context. The programmer does nothing to make this happen, and normally has little to no say in it. Multi-threading is a single process, where the threads carefully share context and memory, and they're all working roughly on the same thing; the programmer makes this happen explicitly, and usually fucks it up. https://en.wikipedia.org/wiki/Multitasking https://en.wikipedia.org/wiki/Multitasking https://en.wikipedia.org/wiki/Multitasking#Multithreading https://en.wikipedia.org/wiki/Multitasking#Multithreading