While threads can speed up execution of code, are they actually needed? Can every piece of code be done using a single thread or is there something that exists that can only be accomplished by using multiple threads?
First of all, threads cannot speed up execution of code. They do not make the computer run faster. All they can do is increase the efficiency of the computer by using time that would otherwise be wasted. In certain types of processing this optimization can increase efficiency and decrease running time.
The simple answer is yes. You can write any code to be run on a single thread. Proof: A single processor system may only run instructions linearly. Having multiple lines of execution is done by the operating system processing interrupts, saving the state of the current thread, and starting another one.
The complex answer is ... more complex! The reason that multithreaded programs may often be more efficient than linear ones is because of a hardware "problem". The CPU can execute calculations more quickly than memory and hard storage IO. So, an "add" instruction, for example, executes far more quickly than a "fetch". Caches and dedicated program instruction fetching (not sure of the exact term here) can combat this to some extent, but the speed issue remains.
Threading is a way of combating this mismatch by using the CPU for CPU bound instructions while IO instructions are completing. A typical thread execution plan probably would be: Fetch data, process data, write data. Assume that fetching and writing take 3 cycles and processing takes one, for illustrative purposes. You can see that while the computer is reading or writing, it's doing nothing for 2 cycles each? Clearly it's being lazy, and we need to crack our optimization whip!
We can rewrite the process using threading to use this wasted time:
And so on. Obviously this is a somewhat contrived example, but you can see how this technique can utilize the time that would otherwise be spent waiting for IO.
Note that threading as shown above can only increase efficiency on heavily IO bound processes. If a program is mainly calculating things, there's not going to be a lot of "holes" we could do more work in. Also, there is an overhead of several instructions when switching between threads. If you run too many threads, the CPU will spend most of it's time switching and not much actually working on the problem.
That all is well and good for a single core processor, but most modern processors have two or more cores. Threads still serve the same purpose - to maximize CPU use, but this time we have the ability to run two separate instructions at the same time. This can decrease running time by a factor of however many cores are available, because the computer is actually multitasking, not context switching.
With multiple cores, threads provide a method of splitting work between the two cores. The above still applies for each individual core though; A program that runs a max efficiency with two threads on one core will most likely run at peak efficiency with about four threads on two cores. (Efficiency is measured here by minimum NOP instruction executions.)
The problems with running threads on multiple cores (as opposed to a single core) are generally taken care of by hardware. The CPU will be sure that it locks the appropriate memory locations before reading/writing to it. (I've read that it uses a special flag bit in memory for this, but this could be accomplished in several ways.) As a programmer with higher level languages, you don't have to worry about anything more on two cores as you would have to with one.
TL;DR: Threads can split work up to allow the computer to process several tasks asynchronously. This allows the computer to run at maximum efficiency by utilizing all the processing time available, rather than locking when a process is waiting for a resource.
|show 8 more comments|
Simple proof sketch:
Note, however, that there is a big assumption hidden in there: namely that the language used within the single thread is Turing-complete.
So, the more interesting question would be: "Can adding just multi-threading to a non-Turing-complete language make it Turing-complete?" And I believe, the answer is "Yes".
Let's take Total Functional Languages. [For those who are not familiar: just like Functional Programming is Programming with Functions, Total Functional Programming is Programming with Total Functions.]
Total Functional Languages are obviously not Turing-complete: you cannot write an infinite loop in a TFPL (in fact, that's pretty much the definition of "total"), but you can in a Turing Machine, ergo there exists at least one program that cannot be written in a TFPL but can in a UTM, therefore TFPLs are less computationally powerful than UTMs.
However, as soon as you add threading to a TFPL, you get infinite loops: just do each iteration of the loop in a new thread. Every individual thread always returns a result, therefore it is Total, but every thread also spawns a new thread that executes the next iteration, ad infinitum.
I think that this language would be Turing-complete.
At the very least, it answers the originial question:
If you have a language that cannot do infinite loops, then multi-threading allows you to do infinite loops.
Note, of course, that spawning a thread is a side-effect and thus our extended language is not only no longer Total, it isn't even Functional anymore.
In theory, everything a multithreaded program does can be done with a single-threaded program as well, just slower.
In practice, the speed difference may be so big there is no way one can use a single-threaded program for the task. E.g. if you have a batch data processing job running every night, and it takes more than 24 hours to finish on a single thread, you have no other option than to make it multithreaded. (In practice, the threshold is probably even less: often such update tasks must finish by early morning, before users start to use the system again. Also, other tasks may depend on them, which must also finish during the same night. So the available runtime may be as low as a few hours / minutes.)
Doing computing work on multiple threads is a form of distributed processing; you are distributing the work over multiple threads. Another example of distributed processing (using multiple computers instead of multiple threads) is the SETI screensaver: crunching that much measurement data on a single processor would take an awful long time and the researchers would prefer seeing the results before retirement ;-) However, they don't have the budget to rent a supercomputer for so long, so they distribute the job over millions of household PCs, to make it cheap.
While there are some performance advantages that can be had by using threads in that you can distribute work across multiple cores, they often come at a great price.
One of the downsides to using threads not mentioned yet here is the loss of resource compartmentalization that you get with single threaded process spaces. For example, say you run into the case of a segfault. It is, in some cases, possible to recover from this in a multi-process application in that you simply let the faulting child die and respawn a new one. This is the case in Apache's prefork backend. When one httpd instance goes belly up, the worse case is that the particular HTTP request may be dropped for that process but Apache spawns a new child and often the request if just resent and serviced. The end result is that Apache as a whole is not taken down with the faulty thread.
Another consideration in this scenario is memory leaks. There are some cases where you can gracefully handle a thread crashing (on UNIX, recovering from some specific signals -- even segfault/fpviolation -- is possible), but even in that case, you may have leaked all the memory allocated by that thread (malloc, new, etc.). So while you process may live on, it leaks more and more memory over time with each fault/recovery. Again, there are to some degree ways to minimize this like Apache's use of memory pools. But this still does not guard against memory that might have been allocated by third party libs that the thread may have been using.
And, as some people have pointed out, understanding synchronization primitives are perhaps the hardest thing to really get right. This problem by itself -- just getting the general logic right for all your code -- can be a huge headache. Mysterious deadlocks are prone to happen at the strangest times, and sometimes not even until your program has been running in production, which makes debugging all the more difficult. Add to this the fact that synchronization primitives often vary widely with platform (Windows vs. POSIX), and debugging can often be more difficult, as well as the possibility for race conditions at any time (startup/initialization, runtime, and shutdown), programming with threads really has little mercy for beginners. And even for experts, there still is little mercy just because knowledge of threading itself does not minimize complexity in general. Each line of threaded code sometimes seems to exponentially compound the overall complexity of the program as well increase the probability for a hidden deadlock or strange race condition to surface at any time. It can also be very difficult to write test cases to ferret these things out.
This is why some projects like Apache and PostgreSQL are for the most part process-based. PostgreSQL runs every backend thread in a separate process. Of course this still does not alleviate the problem of synchronization and race conditions, but it does add in quite a bit of protection and in some ways simplifies things.
Multiple processes each running a single thread of execution can be much better than multiple threads running in a single process. And with the advent of much of the new peer-to-peer code like AMQP (RabbitMQ, Qpid, etc.) and ZeroMQ, it's much easier to split threads across different process spaces and even machines and networks, greatly simplifying things. But still, it's not a silver bullet. There is still complexity to deal with. You just move some of your variables from process space into the network.
The bottom line is that the decision to enter into the domain of threads is not a light one. Once you tread into that territory, almost instantly everything becomes more complex and whole new breeds of problems enter your life. It can be fun and cool, but it's like nuclear power -- when things go wrong, they can go badly and fast. I remember taking a class in criticality training many years ago and they showed pictures of some scientists at Los Alamos who played with plutonium in the labs back in the WWII. Many took little or no precautions against the event of an exposure, and in the blink of an eye -- in a single bright, painless flash, it would all be over for them. Days later they were dead. Richard Feynman later referred to this as "tickling the dragon's tail." That's kind of what playing with threads can be like (at least for me anyway). It seems rather innocuous at first, and by the time your bitten, your scratching your head at how quickly things went sour. But at least threads won't kill you.
First of, a single threaded application will never take advantage of a multi-core CPU or hyper-threading. But even on a single core, single threaded CPU doing multi-threading has advantages.
Consider the alternative and whether that makes you happy. Suppose you have multiple tasks that need to run simultaneously. For instance you have to keep communicating with two different systems. How do you do this without multi-threading? You would probably create your own scheduler and let it call the different tasks that need to be performed. This means that you need to split up your tasks into parts. You probably need to meet some real-time constraints you must make sure that your parts do not take up too much time. Otherwise timer will expire in other tasks. This makes splitting a task up more difficult. The more tasks you need to manage yourself, the more splitting up you need to do and the more complex your scheduler will become to meet all the constraints.
When you have multiple threads life can become easier. A pre-emptive scheduler can stop a thread at any time, keep its state, and re(start) another. It will restart when your thread gets its turn. Advantages: the complexity of writing a scheduler has already been done for you and you don't have to split up your tasks. Also, the scheduler is capable of managing processes/threads that you yourself are not even aware of. And also, when a thread doesn't need to do anything (it is waiting for some event) it will take up no CPU cycles. This not so easy to accomplish when you are creating your down single-threaded scheduler. (putting something to sleep is not so difficult, but how does it wake up?)
The downside of multi-threaded development is that you need to understand about concurrency issues, locking strategies and so on. Developing error-free multi-threaded code can be quite hard. And debugging can be even harder.
Yes. You can't run code on multiple CPUs or CPU cores with a single thread.
Without multiple CPUs/cores, threads can still simplify code that conceptually runs in parallel, such as client handling on a server -- but you could do the same thing without threads.
Threads are not only about speed but about concurrency.
If you have not a batch application as @Peter suggested but instead a GUI toolkit like WPF how you could interact with users and business logic with just one thread?
Also, suppose you're building a Web Server. How you would serve more than one user concurrently with just one thread (supposing no other processes)?
There are many scenarios where just one thread simple isn't enough. That's why recent advancements such as Intel MIC processor with more than 50+ cores and hundreds of threads are taking place.
Yes, parallel and concurrent programming is hard. But necessary.
Multi-Threading can let the GUI interface still be responsive during long processing operations. Without multi-threading, the user would be stuck watching a locked form while a long process is running.
apps dealing with blocking IO that also need to remain responsive to other inputs (the GUI or other connections) cannot be made singlethreaded
the addition of checking methods in the IO lib to see how much can be read without blocking can help this but not many libraries make any full guarantees about this
|show 1 more comment|
A lot of good answers but I'm not sure any phrase it quite as I would--Perhaps this offers a different way to look at it:
Threads are just a programming simplification like Objects or Actors or for loops (Yes, anything you implement with loops you can implement with if/goto).
Without threads you simply implement a state engine. I've had to do this many times (The first time I did it I'd never heard of it--just made a big switch statement controlled by a "State" variable). State machines are still quite common but can be annoying. With threads a huge chunk of the boilerplate goes away.
They also happen to make it easer for a language to break it's runtime execution into multi-CPU friendly chunks (So do Actors, I believe).
Java provides "Green" threads on systems where the OS doesn't provide ANY threading support. In this case it's easier to see that they are clearly nothing more than a programming abstraction.
Multi-threaded code can deadlock the program logic and access stale data in ways that single threads cannot.
Threads can take an obscure bug from something an average programmer can be expected to debug and move it into the realm where stories are told of the luck needed to catch the same bug with it's pants down when an alert programmer happened to be looking at just the right moment.
OSes uses time slicing concept where each thread gets it's time to run and then gets preempted. Approach like that can replace threading as it stands now, but writing your own schedulers in every application would be overkill. Moreover, you'd have to work with I/O devices and so on. And would require some support from hardware side, so that you could fire interrupts to get your scheduler to run. Basically you would be writing a new OS every time.
In general threading can improve performance in cases where threads wait for I/O, or are sleeping. It also allows you to make interfaces that are responsive, and allow stopping processes, while you perform long tasks. And also, threading improves things on true multicore CPUs.
You will see the multithreadin requirements when you run into execution flow that needs to run concurrently, as well as gui-responsiveness while a long running task chugs away.
First, threads can do two or more things at the same time (if you have more than one core). While you can also do this with multiple processes, some tasks just don't distribute over multiple processes very well.
Also, some tasks have spaces in them that you can't easily avoid. For example, it's hard to read data from a file on disk and also have your process do something else at the same time. If your task necessarily requires lots of reading data from the disk, your process will spend a lot of time waiting for the disk no matter what you do.
Second, threads can allow you to avoid having to optimize large amounts of your code that's not performance-critical. If you only have a single thread, every piece of code is performance critical. If it blocks, you are sunk -- no tasks that would be done by that process can make forward progress. With threads, a block will only affect that thread and other threads can come along and work on tasks that need to be done by that process.
A good example is infrequently-executed error handling code. Say a task encounters a very infrequent error and the code to handle that error needs to page into memory. If the disk is busy, and the process has only a single thread, no forward progress can be made until the code to handle that error can be loaded into memory. This can cause bursty response.
Another example is if you might very rarely have to do a database lookup. If you wait for the database to reply, your code will hit a huge delay. But you don't want to go to the trouble of making all this code asynchronous because it's so rare that you need to do these lookups. With a thread to do this work, you get the best of both worlds. A thread to do this work makes it non performance critical as it should be.