I have been considering adding threaded procedures to my application to speed up execution, but the problem is that I honestly have no idea how to use threads, or what is considered "thread safe". For example, how does a game engine utilize threads in its rendering processes, or in what contexts would threads only be considered nothing but a hindrance? Can someone point the way to some resources to help me learn more or explain here?
A:
There's a nice book, Java Concurrency in Practice, http://www.javaconcurrencyinpractice.com/ .
Ondra Žižka
2010-01-23 01:10:34
Although this is an awesome book, it assumes prior knowledge of the basic mechanisms of concurrency in Java, which the asker is probably not ready for.
Grundlefleck
2010-01-23 01:12:58
That's right, I forgot it doesn't include an intro.
Ondra Žižka
2010-01-23 04:07:42
+2
A:
Threads don't speed up applications. Algorithms speed up applications. Threads can be used in algorithms, if appropriate.
Richard Pennington
2010-01-23 01:13:10
Threads *can* speed up your application, under certain conditions. Such as when serial, blocking tasks can be split up into parallel tasks. The effect is increased on multi-core systems, which is becoming the norm. Consider a task which must make a TCP/IP request and wait for a response. If this task blocks on one thread, 10 of them will take 10x the time. If parallelised, this can be reduced to just over 1x the amount of time.
Grundlefleck
2010-01-23 01:18:14
Yeah, I have studied in an algorithms class and am always studying algorithms, but I wanted to broaden my horizons a bit more with multi-core processors becoming the norm.
Orm
2010-01-23 01:32:06
For the negative voter: I'm a firm believer that you only introduce threads into an algorithm when it makes sense. No sooner.
Richard Pennington
2010-01-23 02:47:40
+23
A:
This is a very broad topic. But here are the things I would want to know if I knew nothing about threads:
They are units of execution within a single process that happen "in parallel" - what this means is that the current unit of execution in the processor switches rapidly. This can be achieved via different means. Switching is called "context switching", and there is some overhead associated with this.
They can share memory! This is where problems can occur. I talk about this more in depth in a later bullet point.
The benefit of parallelizing your application is that logic that uses different parts of the machine can happen simultaneously. That is, if part of your process is I/O-bound and part of it is CPU-bound, the I/O intensive operation doesn't have to wait until the CPU-intensive operation is done. Some languages also allow you to run threads at the same time if you have a multicore processor (and thus parallelize CPU-intensive operations as well), though this is not always the case.
Thread-safe means that there are no race conditions, which is the term used for problems that occur when the execution of your process depends on timing (something you don't want to rely on). For example, if you have threads
AandBboth incrementing a shared counterC, you could see the case whereAreads the value ofC, thenBreads the value ofC, thenAoverwritesCwithC+1, thenBoverwritesCwithC+1. Notice thatConly actually increments once!A couple of common ways avoid race conditions include synchronization, which excludes mutual access to shared state, or just not having any shared state at all. But this is just the tip of the iceberg - thread-safety is quite a broad topic.
I hope that helps! Understand that this was a very quick introduction to something that requires a good bit of learning. I would recommend finding a resource about multithreading in your preferred language, whatever that happens to be, and giving it a thorough read.
danben
2010-01-23 01:13:58
That actually gives me an idea about how to thread my rendering. Split the container with the stored game objects in half then have two threads simultaneously render either the first or second half. Or split the container into quarters or eights. If I am wrong in this, stop me now.
Orm
2010-01-23 01:34:49
@Orm: I am not familiar with games development, but I guess that the bottleneck is the actual rendering to the screen? So if you have several threads going through the game objects to create the off-screen buffers for the image, and the renderer can quickly swap in the pre-computed buffers, then that should speed it up. You then have to be careful about how these threads then split up which objects to render, your splitting up idea sounds reasonable.
Grundlefleck
2010-01-23 01:41:23
Yeah. The thing is that the efficiency is restricted to O(n). So the split could occur in the main application thread before any rendering takes place, like(Singletons are already initialized in the Engine's initialization, so an instance is guaranteed to exist before anything.)Renderer::Instance()->PreRenderProcess();Renderer::Instance()->Render();
Orm
2010-01-23 01:45:43
@Orm: I also am not very familiar with graphics rendering, but a good thing to remember is that (outside of a multicore environment) the speedup from parallelizing tasks only occurs when you run different types of tasks in parallel, where type is dependent on the part of the machine it uses (see my third bullet point). As an example, parallelizing something like merge sort would give no benefit because it's all done in the CPU, whereas GUI applications have to be threaded because you don't want the I/O thread that lets the user interact with the app to have to wait for CPU-intensive tasks.
danben
2010-01-23 01:49:23
Alright, so threading things like reading user input and setting it apart from graphics processing is something I should definitely look into is what you're saying?
Orm
2010-01-23 01:55:32
All I'm saying is that you should make sure the part of your application that you want to parallelize will actually benefit from being parallelized. When in doubt, you can always benchmark and compare.
danben
2010-01-23 02:05:27
Also, if you are in fact working in a multicore environment then your graphics rendering will likely be able to benefit from that, as lots of games are now being written to take advantage of multiple processors.
danben
2010-01-23 02:06:48
@Orm: there's a general rule of parallel programming behind what danben is saying. It's called Ahmdal's Law, and it boils down to "The speed increase of an application is limited by the fraction that's sequential". So if you have to render 100 objects *in sequence*, and that takes up 40% of your rendering loop, it is impossible to speed up the loop by more than 60%, no matter how many threads you use.
Grundlefleck
2010-01-23 14:15:10
+1
A:
Well someone will probably answer this better, but threads are for the purpose of having background processing that won't freeze the user interface. You don't want to stop accepting keyboard input or mouse input, and tell the user, "just a moment, I want to finish this computation, it will only be a few more seconds." (And yet its amazing how many times commercial programs do this.
As far as thread safe, it means a function that does not have some internal saved state. If it did you couldn't have multiple threads using it simutaneously.
As far as thread programming you just have to start doing it, and then you'll start encountering various issues unique to thread programming, for example simultaneuous access to data, in which case you have to decide to use some syncronization method such as critical sections or mutexes or something else, each one having slightly different nuances in their behavior.
As far as the differences between processes and threads (which you didn't ask) processes are an OS level entity, whereas threads are associated with a program. In certain instances your program may want to create a process rather than a thread.
Mark
2010-01-23 01:14:18
Though anything stateless is thread-safe, thread-safe does NOT mean stateless
danben
2010-01-23 01:17:29
Sorry, I'm in a picky mood... "... threads are for the purpose of having background processing that won't freeze the user interface." - that reads as if that is the exclusive purpose of threading, which is definitely not true, though it is one of the uses.
Grundlefleck
2010-01-23 01:20:10
+1
A:
Threads are simply a way of executing multiple things simultaneously (assuming that the platform on which they are being run is capable of parallel execution). Thread safety is simply (well, nothing with threads is truly simple) making sure that the threads don't affect each other in harmful ways.
In general, you are unlikely to see systems use multiple threads for rendering graphics on the screen due to the multiple performance implications and complexity issues that may arise from that. Other tasks related to state management (or AI) can potentially be moved to separate threads however.
jsight
2010-01-23 01:16:39
+1
A:
First rule of threading: don't thread. Second rule of threading: if you have to violate rule one...don't. Third rule: OK, fine you have to use threads, so before proceeding get your head into the pitfalls, understand locking and the common thread problems such as deadlock and livelocking.
Understand that threading does not speed up anything, it is only useful to background long-running processes allowing the user can do something else with the application. If you have to allow the user to interact with the application while the app does something else in the background, like poll a socket or wait for ansynchronous input from elsewhere in the application, then you may indeed require threading.
The thread sections in both Effective Java and Clean Code are good introductions to threads and their pitfalls.
Dave Sims
2010-01-23 01:24:08
Multithreading *does* provide a speedup when you have a parallelizable, CPU-bound task and there are multiple processors (or cores) available. Divide the work into *n* threads and get the job done in roughly 1/n time, where *n* is less than or equal to the number of processors.
Wyzard
2010-01-23 06:16:36
This is true, and more applicable these days with more multi-core processors than ever. Point taken. But utilizing threads simply for optimization even in multi-processor environments is a dicey proposition, advisable only if your architecture is *necessarily* asynchronous, for instance when writing a server of some kind that will spin off multiple workers, etc.
Dave Sims
2010-01-23 14:05:01
The point I was trying to make (and probably botched) about "don't thread" is that threading introduces a host of risks and unpredictability to your codebase that it is advisable to avoid if you possibly can. Threading for its own sake just to "speed up" an application is not a good idea, particularly in OO environments where locks, mutexes and the like can create an increasingly complex and unpredictable environment. Thar be dragons.
Dave Sims
2010-01-23 14:11:27
Well, as my initial design of my rendering engine turned out to be fundamentally flawed anyway, so threads my not be necessary after this revision.
Orm
2010-01-25 01:37:02
+2
A:
There are four things you should know about threads.
Threads are like processes, but they share memory.
Threads often have hardware, OS, and language support, which might make them better than processes.
There are lots of fussy little things that threads need to support (like locks and semaphores) so they don't get the memory they share into an inconsistent state. This makes them a little difficult to use.
Locking isn't automatic (in the languages I know), so you have to be very careful with the memory they (implicitly) share.
wisty
2010-01-23 01:31:30
+1
A:
Since the question is tagged with 'Java', I assume you are familiar with Java, in which case this is a great introductory tutorial http://java.sun.com/docs/books/tutorial/essential/concurrency/
fsm
2010-01-23 01:37:51
+1
A:
Orm, great question to ask. I think all serious programmers should learn about threads, cause eventually you will at least consider using them and you really want to be prepared when it happens. Concurrency bugs can be incredibly subtle and the best way to avoid them is to know what idioms are safe(-ish).
I highly recommend you take the time to read the book Concurrent Programming in Java: Design Principles and Patterns by Doug Lea: http://gee.cs.oswego.edu/dl/cpj/
Lea takes the time not only to teach you the concepts, but also to show you the correct and incorrect ways to use the concurrent programming primitives (in Java but also helpful for any other environment that uses shared-memory locking/signaling style concurrency). Most of all he teaches respect for the difficulty of concurrent programming.
I should add that this style of concurrent programming is the most common but not the only approach. There's also message passing, which is safer but forces you to structure your algorithm differently.
+1
A:
Since the original post is very broad, and also tagged with C++, I think the following pointers are relevant:
Anthony Williams, maintainer of the Boost Thread Library, has been working on a book called "C++ Concurrency in Action", a description of which you can find here. The first (introductory) chapter is available for free in pdf form here.
Also, Herb Sutter (known, among other things, for his "Exceptional C++" series) has been writing a book to be called "Effective Concurrency", many articles of which are available in draft form here.
Alexandros Gezerlis
2010-01-23 06:29:37