August 03, 2007
How Much Scalability Do You Have or Need?O(1): Sequential Code
O(1) means that the program typically has one CPU-intensive piece of work available to be actively executed at any given time. It may occasionally perform multiple concurrent operations, such as occasional background work in addition to the main foreground work, but the extra work is not ongoing and/or doesn't keep more than a single core busy.
This category includes not only all sequential code, but also every concurrent application with throughput that is as good as sequential because its threads execute serially, such as by being convoyed on a global lock or message queue. The free throughput lunch is over for both these kinds of O(1) code, but the fully serial option tends to have the additional liability of poorer responsiveness, while a concurrent application tends to be better structured to do background work asynchronously[1, 2].
For example, consider Microsoft Word: As I type this paragraph, WINWORD.EXE has between 8 and 11 active threads, but all CPU cores remain virtually idle. Each time Word regularly performs a background Save, one core's utilization increases to more than 50 percent for about two seconds before the system returns to idle. This version of Word is O(1) when used in this mode; I'm not likely to see improvement when running it on a system with a greater number of hardware cores, even though the application uses several threads internally.
In all O(1) cases, if we want better throughput for CPU-bound operations, essentially, our only option is to try to optimize our code in traditional ways because adding more cores won't help.
Previous Page |
1 How Much Scalability?
|
2 O(1): Sequential Code
|
3 O(K): Explicitly Threaded Code
|
4 Comparing O(1) and O(K)
|
5 O(N): Scalable Throughput And the Free Lunch
Next Page
|
 |
|
|||||||||||||||||||||||||||||
|
|
|
