Running 100,000 Parallel Threads

An anonymous reader writes "This story explains how the latest Linux development kernel is now able to start and stop over 100,000 threads in parallel in only 2 seconds (about 14 minutes 58 seconds faster than with earlier Linux kernels)! Much of this impressive work is thanks to Ingo Molnar, author of the O(1) scheduler recently merged with the 2.5 Linux development kernel."

Re:Posix thread...

Your answer:

http://www.cs.wustl.edu/~schmidt/ACE.html

This is so far the best library I have used for pthread programming. Powerful, easy to use, and encapsulates message passing really well...

Hold this thread while I walk away

The linux song

100,000 Linux threads

this image springs to mind [discover.com]

Win ME Kicks that sorry statistic!!!!

It takes two seconds to start 100,000 threads???? Piff! With my ME computer, It doesn't matter how many parallel threads I am running... I can stop them all instantly by simply attempting to use my computer :P.

Re:Win ME Kicks that sorry statistic!!!!

Pff... I can start a million threads on my FreeBSD box and stop them all in an instant...

...by hitting the reset button.

I'm only a humble C programmer, but....

And this is great news, and, indeed, impressive. But my question is, what (if any) change is this going to make to my daily use of linux (for gcc, reading slashdot, and that's about it...) Am I going to notice any performance differences?

Re:I'm only a humble C programmer, but....

Just wait until Spyware For Linux(TM) comes out... With Bonzai Buddy For Linux(TM), Real Center For Linux(TM), XMMS Agent(TM), Linux Messenger(TM), Linux Update(TM), and FindFast for OpenOffice.org(TM). Then you will know why 100,000 parallel threads in two seconds is a good thing :P.

Re:I'm only a humble C programmer, but....

probably none. On the other hand the field I work in (high performance computing) this will be a great help. Currently we are running a 500,000 processor simulation on a four node cluster, startup and running both is a pain. Remeber, on of the great things about linux is some of the neat/usefull applications being ran on it (human genome, nuclear simulations, fluid simulations). Windows is a toy and geared toward "normal" users (read very few threads not processor intensive). Linux is more of a workhorse (many threads, computationally expensive, and high uptimes). While there are exceptions to this look at advances such as this in that light. And finally, just because you won't use it compiling a kernel doesn't mean it's not needed.

Re:I'm only a humble C programmer, but....

KDE actively discourages threads. Perhaps that will change now. Likewise servers, such as apache, will speed up.

I'm not so sure about that.

A threaded model doesn't necessarily offer advantages -- Apache's multiprocess model is really just as good on platforms without serious performance penalties on fork(), and Boa (which neither forks nor threads) is much, much faster than either Apache mode (though of course on SMP systems multiple instances must be run to use all the available CPUs).

Indeed, unless SMP is being taken advantage of, a well-written single-threaded application will always be faster than an equivalent multithreaded application. Such an application has less overhead and is able to jump between its "subprocesses" only when needed -- and without the latencies involved by letting the OS handle said scheduling. Back in the Real World, I still write threaded code -- but because writing unthreaded code (in the problem spaces where threads are useful) is harder, not because it's faster.

If you want to destroy my boxen. . .

Launch 100,000 threads while I walk away. . .

OK I'll shut up now.

Parallelism

This is very cool; but does it scale to multiple CPU systems? More and more, SMP, split-bus and multi-core architectures are going to be taking over. If this holds up in those environments, Linux may actually have a leg up on some of the dedicated task heavyweights.

Re:Not 100,000 threads in parallel, just 50.

Yeah right. And modded to "Informative"? Slashdot moderators are the _pits_.

Read ingo's reply to Linus. They _did_ start
one test serially and also _parallelly_ . In short he says that its possible.

vv

Re:Not 100,000 threads in parallel, just 50.

No, seriously. Process creation under Linux was time-similar to thread creation on other OSs. That's because Linux was as fast at creating *a process* as other OSs are at creating *a thread*. IIRC, threading was initially implemented in Linux from the process-creation methods, so it was similar in speed (the main advantage in Linux from threads was the shared memory space if your application wanted that sort of thing). That's why Apache 2.0 is bringing NT performance more in line with Linux 1.3 performance: NT's threading speed is a lot closer to Linux's forking speed. Again, I'd like to underscore I'm not an expert on this, and it's possible I'm mistaken about relative benchmarks (is NT w/Apache 2.0 a little faster than Linux w/Apache 1.3? Could be...) but I'm very confident of the basic underlying point, that Linux process creation is essentially comparable to other OSs' thread creation, perhaps even faster.

See, for example, http://www.linux.cu/pipermail/linux-prog/2001-Febr uary/000027.html [linux.cu], just one of the first Google links that popped up when I went looking for proof that I'm not on crack: "Linux newcomers often are unaware of the substantial differences between Linux and other operating systems. To implement concurrency, they use multithreading exclusively, mistakenly assuming as high an overhead associated with Linux multiprocessing as on other platforms." In fact, knowing how fast Linux's process creation is relative to other systems' thread creation makes this even more impressive in my mind. This isn't just a bug fix; much like with process creation before it, Linux is doing something fundamentally better than its counterparts.

Don't forget: Just because this is /. doesn't mean I'm just a Windows-hating troll. I try to make sure all my Windows-hating-troll-posts are at least backed up by facts. ;)

Re:Not 100,000 threads in parallel, just 50.

It's not process/thread _creation_ times that make the difference, it's the process/thread _context_switch_ times that really mount up, which is where Linux shines.

And yes, Linux's process context switches are on a par (possibly faster - can't be bothered to look up benchmarks) with NT's thread context switches.

K.

Re:Not 100,000 threads in parallel, just 50.

The latency issues that cause mp3 skipping under heavy load in Linux have nothing at all to do with context switching, and everything to do with /scheduling/ latency: how long it takes for a process that has work to do to actually get control of the cpu. Context switching has /nothing/ to do with that.

The low latency patches go through the kernel breaking up areas where spinlocks are held for long periods of time. That's what causes massive scheduling latency in the kernel.

Context switching under Linux /is/ extremely fast - it's actually been measured (a lot), and it's something the kernel developers pay a lot of attention to and optimise very carefully. They literally count cpu cycles in these code paths. Context switching time is a serious performance limiter in many areas, so getting it right is important, and it's something that Linux does /very/ well.

Go do some real research before you accuse someone who's right of karma whoring bullshit.

himi

Re:Not 100,000 threads in parallel, just 50.

Apache 2.0 doesn't actually do thread creation very frequently. The thread creation cost occurs mostly at startup. So the limiting factors for threaded Apache performance on Linux are mainly:

• The speed with which the kernel can schedule and context-switch among threads
  For some recent data on this, see http://marc.theaimsgroup.com/?l=apache-httpd-dev&m =103228014211983 [theaimsgroup.com]. The O(1) scheduler patch for 2.4 seems to help here.
• Memory usage per thread
• Concurrency limitations of the Apache code itself
  This has been improving gradually with successive 2.0 releases, as the remaining global locks are removed or optimized.
• General robustness of the thread implementation
  The current (2.4) Linux threading implementation doesn't work well with debuggers.

At first glance, it looks like the NPTL could be a win for threaded Apache on Linux, as offers some solutions first the first and last of these issues.

Re:Not 100,000 threads in parallel, just 50.

Read Ingo's posts too:

actually, that was Ulrich's other test, which tests the serial starting of 100,000 threads. the test i did started up 100,000 concurrent threads which shot up the load-average to a couple of thousands. [the default timeslice the parent has is enough to start more than 50,000 parallel threads a pop or so.]

And another one:

Anton tested 1 million concurrent threads on one of his bigger PowerPC boxes, which started up in around 30 seconds. I think he saw a load average of around 200 thousand. [ie. the runqueue was probably a few hundred thousand entries long at times.]

Re:Help with DoS?

How the hell did this get +2?
a) most server software, apache 2 aside, doesn't use threads;
b) most DoS attacks are based on bandwidth saturation rather than local resource starvation. As a result, it doesn't help.

BS. This guy asks an innocent question, certainly not worth 2 antagonistic responses. Besides, Apache is a very important application, plus I know other server software that uses thread.

The DoS attacks that are based on bandwidth saturation are typically called DDoS attacks instead. I would say that most DoS attacks are in fact based on crashing the server, which is clearly not based on bandwidth saturation. Plus, there are important attacks that rely on resource saturation, such as the TCP SYN attack. Stopping DoS is not a one step process; you have to deal with it at every stage of the game.

-a

Sounds cool, but all I could think of...

"Hello, my name is Ingo Molnar. You killed -9 my process: prepare to die."

Sorry, had to :P

Re:Sounds cool, but all I could think of...

I think it's more commmonly this:

"Hello, my name is Ingo Molnar. You kill -9 my parent process. Prepare to vi."

NOOO!!!!!

At school (before I graduated so long ago) we would "fork bomb" the compute servers [ while(1) do { fork(); } ] in an attempt to extend deadlines or simply be assholes :)

Re:NOOO!!!!!

I am replying pre-emptively to dissuade the AC's who would otherwise reply to you and point out that your post should not have been modded funny because this innovation would not prevent fork() bombing because it involves spawning threads and not processes.

I am further replying pre-emptively to dissuade the AC's who would otherwise reply to me and point out my egregious abuse of run-on sentences.

I am further replying pre-emptively to dissuade the AC's who would otherwise reply to me and point out my egregious abuse of +1 bonus.

I am further replying pre-emptively to dissuade the AC's who would mod this post down as off-topic because they do not get the parallel allusion to fork-bombing.

Re:NOOO!!!!!

Dude, you seriously need to look into writing patents.

Windows

Just out of curiousity, how does the benchmark in windows compare?

Re:Windows comparison

Very thread uses a minimum of *1 PAGE* of reserve memory for its statck, which is 64K. However, you have to go out of your way to use less than 1 megabyte of reserve memory. Since only 2GB of reserve memory (addressable memory) is available to user applications, this would fit your 2000 thread figure like a glove.

C//

whoa!

I have no idea what the hell you're talking about but it certainly sounds impressive. :)

Great

Now we finally have the power to run 99,999 pop up ads when we visit that pr0n site

Re:Possible use

"use only as many threads as CPUs"
>>>>>>>>
Then please stay away from my GUI apps. I hate those UNIX grognards that come from that school of thought, then try to code GUI applications with only one thread and end up with apps that can't update the GUI while doing I/O. On my 300 MHz PII, that particular trait made Galeon unusable. It had one rendering thread for all the tabs, so when I was loading a complex page like /. in another tab, whatever tab I was actually reading would freeze up.

nice, but...

It's nice that the Linux kernel can handle that many threads. But user level threads generally are even more lightweight, and high performance implementations like those on Solaris provide both user level and kernel level threads and map the former onto the latter. Is Linux going to get something similar? Is Sun perhaps donating their implementation? Or are these new kernel threads so lightweight and quick that they are competitive with Solaris on their own, without the mess and complication of adding user level threads?

Re:nice, but...

According to a mail from Ingo Molnar halfway down the linked article, M:N threading doesn't really solve the real problem - it's good at switching back and forth between running threads, but the real reason for having very large amounts of threads (be they kernel or user space threads) to begin with, is to do IO, and for that, there is no real advantage of user space threads.

More info on the 1:1 vs M:N issue can be read in the white paper [redhat.com]

How will this affect Mozilla, OpenOffice...

How will this change affect Mozilla, the Sun JVM and OpenOffice, for instance.

While it probably is generally true that it will take some time for most applications to start using the new threading model some larger applications could support it fairly soon.

Can we expect these applications to be adapted to the new threading model some time soon, and how will it affect performance?

big deal

100.000 threads? What nonsense; everybody knows that no computer would ever use more than 640.

100000?!

640 should be enough for anybody!

LEXX

Linus didn't think much of O1 scheduler

I remember that Linus made a remark that he tought that the O1 scheduler wouldn't impact Linux much at all, and that its development would not be a biggie for Linux, downplaying the importance of what it can achieve. Go Ingo for keeping at it!

Re:Alternative headline

Gigantic performance problem in Linux code fixed after several years of "many eyes" scanning over it.

Uh, why did that get moderated as a troll? Oh, right, Linux is absolutely perfect, and anyone who says otherwise must be a troll.

Come on, Linux's scheduler has long been known to have performance problems once you have a lot of processes/threads... for example, read this paper [linuxalpha.org] [text version [216.239.39.100]] (appropriately subtitled "How I Learned to Love the Alpha and Hate the Scheduler"):

0.8.1 Create a fixed priority scheduler.
Currently, the Linux scheduler is very different than the traditional Unix schedulers. Although the Linux scheduler is very efficient when only several processes are running, it is not scalable. In order to match the performance of *BSD and other Unices, another scheduling algorithm must be used.

Moderators, don't be Slashbots, moderating according to the groupthink. Educate yourselves, and you'll be better moderators, and better people.