RSS
Optimization
| Language: | C++ |
| Category: | System |
| Date: | 2008-07-21 |
| Author: | Hackers programming |
A programmer's life is a continual struggle with slow-downs and lack of time. Every day he or she spends several hours on optimization. Each programmer tries to optimize everything that happens to be close at hand. Are you sure you do this properly? Maybe you can do something better.
I'm aware of the fact that people are lazy. As for me, I got accustomed that my computer does everything for me, and I don't remember what a ball-point pen looks like. I had to write an application on a sheet of paper not long ago. It turned out that I forgot how to write a letter by hand, so I looked at the computer keyboard. Honestly! This is a technical progress that allows me to do everything with my computer.
To write a two-line message, a person turns on his or her computer and starts MS Word or another text processor, thus wasting time. Why doesn't he or she write the message by hand? Because it wouldn't be imposing!
Programmers are especially shameless. Many of them don't care about the source code they write because nobody is going to see it. However, they are wrong. From this point of view, open-source applications have a great advantage because they are much cleaner and faster. Programmers are often too lazy to optimize the size and speed of the code they write. When I see such programs I want to swear. Unfortunately, this wouldn't make these programs better.
Hackers are even more lazy. A few years ago, the image of a programmer or hacker was a shaggy-haired, unwashed cigarette smoker. Now it is a "digital" beer-drinker whose job is done completely by computers. I wonder whether doctors tell such people they have beer instead of blood in their blood vessels. I have nothing against beer, and I like beer. However, one should have sense of measure.
This is a degradation provoked by MS. We grab a mouse and start clicking here and there, forgetting the keyboard and hotkeys. I'm convinced this should be stopped. Recently, I sometimes become so lazy that I put away the keyboard, start the on-screen keyboard and use only the mouse. It only remains to cover my body with fur and put me into a cage with monkeys.
Don't spend money on upgrading your computer! Upgrade yourself first. Optimize your work, and your computer will work faster.
This part of the book originally was intended as a description of how to optimize program code. However, I subsequently included one my article from my Internet site into this book. Everything should be optimized. I'll talk about the theory of optimization whose laws are universal. You can use the same laws to optimize both your daily schedule to do everything on time and the operating system on your computer to make it work faster. However, the main discussion will relate to optimization of program code. Here you'll find a little more information than in the article on my site.
As always, I'll try to give as many practical examples as possible so that you can see that I'm not pulling the wool over your eyes and use my recommendations in practice.
I'll begin with the laws that are applicable not only to programming, but also to real life. At the end, I'll tell you things that can be useful when optimizing your code.
Law 1
Everything can be optimized. Even if you think a work is done fast enough, it can be done faster.
This is really the case. This law is especially true for programming. There is no ideal code. Even a simple operation such as 2+2 can be optimized. To obtain the best result, you should act consistently and in the order described below.
Remember that each task can be fulfilled at least in two ways (or more), and you should choose the best one that will provide the desired performance and universality.
Law 2
The first thing you should do is to search for the weakest and slowest links. What is the point in optimizing the best links first? If you try to optimize them, you are likely to encounter unexpected conflicts. In addition, the gain will be scantly.
I remember a case of my life. Around 1996, I came up with a crazy idea of writing my own Doom-like computer game. I wasn't going to make profit of it; this was just a challenge for my brain. After four month of hard work I obtained a sort of an engine. I created one bare level, at which a gamer could move. Being very proud of myself, I started moving along corridors.
There were no monsters, doors, or scenes, but the program was very slow. I imagined what would happen if I add monsters, attributes, and AI, and all my pride left me. Who needs an engine that is extremely slow without scenes at a resolution 320x200 (then it was cool!)? You're right, nobody does.
My virtual world certainly needed some optimization. During a month, I struggled with my code and "polished" every statement of my engine. The result was the following: The world was drawn 10% faster, but it was still slow. Suddenly I understood what the weakest link was: displaying on the screen. My engine computed graphics fast enough, but displaying the image was really a slow-down. There wasn't the AGP bus at those times, and I used a simple S3 PCI video card with 1 Mb of memory.
After a few hours of sorcery I got maximum of my PCI and myself. I compiled the engine and entered my virtual world. I hit the "forward" key and immediately found myself at the opposite wall. There were no slow-downs, the speed was breakneck, and displaying was instant.
As you see, my mistake was that I wrongly determined the weakest link in my engine at first. I spent a month on optimization of the mathematical portion of the code, but the result was just 10% of performance gain. However, when I actually found the weakest link, I could increase performance by a few times.
This is why I tell you that you should start optimizing with the weakest links. If you speed up their work, it is likely that you won't need to speed up other parts of your code. You can spend many days or even months optimizing stronger links and gain 10% (which can be insufficient). On the other hand, you can spend a few hours optimizing the weakest link and increase performance by 10 times!
The Weak Links of the Computer
I cannot understand people who update a processor and leave an old S3 video card, a 5400 rpm Winchester, and 32 Mb of memory. Look inside the case of your computer and examine its contents. If you find that you have only 65 Mb of memory, say loudly: "Dear DIMM, you're the weakest link, and you must leave my computer!" After that buy 128 Mb of memory, or 256 Mb, or, better still 512 Mb and enjoy acceleration of Visual C++, PhotoShop, and other "heavy" applications.
In such a case, increasing the processor clock rate by a hundred of megahertz would provide a smaller increase in performance. When you use "heavy" applications and are short of memory, the processor spends too much time on writing data to and reading it from the swap file. On the other hand, if there is enough memory in your computer, the processor performs only computation and doesn't waste time on swapping data.
The same is true for a video adapter. If your video card is weak, the processor will compute scenes faster than they are displayed. This will result in delays and small performance gain. In contrast, a good video card can display data fast and save the processor from some computation.
Law 3
During the next step you should dissect all operations and locate those repeated many times. Apply optimization to such operations first.
I'll illustrate this law with a programming example. Suppose you have some code. (Below is just a logic, not an actual program.)
1. A:=A*2 2. B:=1 3. X:=X+B 4. B:=B+1 5. If B<100 go to step 3
Every programmer will tell that the weakest link is the first line because it uses multiplication. This is true. Multiplication is a time-consuming operation, and you'll save a pair of clock ticks if you replace it with addition (A:=A+A) or, better still, with a shift. However, you won't gain more, and this will be unnoticeable.
Now look at the code again. Do you see anything? I do. This code uses a loop: "While B<100 do X:=X+B". It implies 100 jumps from step 5 to step 3. These are quite a few. Can we optimize anything? It's easy. The loop includes lines 3 and 4. What if we duplicate them inside the loop?
2. B:=1 3. X:=X+B 4. B:=B+1 5. X:=X+B 6. B:=B+1 7. If B<100 go to step 3
Here a large loop is converted to a smaller one. The second and third operations are repeated twice. As a result, lines 3 and 4 are executed twice during one iteration, and only then a jump to line 3 is performed. This loop is repeated only 50 times (because two operations are done within one iteration). This means we saved 50 jumps. Not bad. We saved several hundreds of clock ticks.
What if we write lines 2 and 3 ten times inside the loop? These lines will be executed ten times during one iteration, and the loop will require only ten iterations to perform 100 operations. This saves 90 jumps.
A disadvantage of this approach is that the code became larger. However, its speed increased significantly. This approach is good, but you shouldn't abuse it. On the one hand, the speed increases, but on the other hand the size increases. Large size is a disadvantage of any program. Therefore, you should look for the golden mean.
In every business, one of the most important thing is a reasonable sufficiency. The more you increase the size for the speed's sake, the less is the resulting optimization.
There are a lot of examples in real life. Any cyclic operation can be optimized. Do you want an example? Here it is. Suppose your Internet provider has a few access telephones. You dial each of them trying to find which is not busy. A novice user would say that the provider should optimize their modem pools so that a user can dial only one number. However, an experienced user knows that not every user has a good connection to each telephone exchange. This is why providers have pools on different exchanges so that you can choose a pool with the best connection. Install a dialer (a lot of them are available on the Internet), and it will automatically dial the telephone numbers one after one.
Another example: You have a one-hour plastic card of an Internet provider. It is pointless to enter its telephone number into the dialer because it is quite likely that you will never connect to this provider again. If you change settings of your dialer and then reset them back, you'll spend more time than it is required to call the provider with the standard Windows tools. Conclusion: Carefully choose tools for implementing your tasks.
Law 4
(This law is an extension of the previous.)
Optimization of operations that are performed once is the waste of time. Think twice before you optimize infrequent operations.
About half a year ago, I read a story on the Internet (http://www.exler.ru/novels/wife.htm, in Russian) called "The Notes of a Programmer's Wife". A cool realistic story. When I was reading, I felt like it had been written by my wife. God bless my Little Red Riding Hood, she isn't that mean. The plot of the story is the following.
A pretty girl is getting married with a programmer, and they have to mail invitation cards. Rather than typing them with a typewriter, the programmer declares himself an expert and writes a special program. He spends a day on writing and another on debugging.
His main mistake was a wrong optimization of his work. It would be easier to type a template in any text processor and then change the names of people invited to this sorrowful (according to my own experience) event. Even if a person doesn't have a text processor, it is really pointless to write a program. The expenses are high, and the program will be used only once. In fact, using a typewriter would be a better solution.
Earlier, I criticized lazy people. However, laziness spurs you to optimize your actions. He is not an expert who worked hard all day without a result, but he who completed his job quickly and effectively. These things shouldn't be confused.
Law 5
You should know your computer's internals and its working principles. The better you know the way how your computer executes your code, the better optimization you can achieve.
This law refers only to programming. It is difficult to give a complete set of ready solutions, but I'll try to describe a few techniques.
- Try to avoid floating-point computation. Any operation on integers is many times faster.
- Multiplication is a very slow operation; division is even slower. If you need to multiply a number by 3, it will be easier for the processor to add this number three times than to multiply it once. However, cutting-edge processors multiply quite fast, and the difference isn't very noticeable.
How can you optimize division? You should know mathematics. A processor has shift operations. You should know that the processor "thinks" in the binary number system, and the numbers are stored in the computer in binary representation. For example, the number 198 looks like 11000110 for the processor. Now let's look at the shift operations.
Right shift. If you shift the number 11000110 one position to the right, the last digit will disappear, and only 1100011 will remain. Now enter this number into your calculator and convert it to the decimal number system. You'll obtain 99. As you see, this is a half of 198. Conclusion: When you shift a number one position to the right, you divide it by two.
Left shift. Let's take the same number 11000110. if you shift it one position to the left, the rightmost position will become vacant, and a zero will fill it. The result will be 110001100. Convert this number to the decimal number system, and you'll obtain 396. What is it? It is 198 multiplied by two.
Conclusion: When you shift a number one position to the right, you divide it by two; when you shift it to the left, you multiply it by two. Therefore, use shifts whenever you can because they are executed many times faster than multiplication or division, and even addition or subtraction.
- When creating a procedure, don't burden it with many parameters, before the procedure is called, its parameters are pushed on the stack (this is a special memory area), and they are popped off the stack when the procedure starts. The more the parameters, the higher the overheads on accessing the stack.
I'd like to mention that you also should be very careful with the parameters themselves. Mind you don't pass variables that can contain large amounts of data! It is best to pass the procedure the memory address where the data is stored and use this address inside the procedure. Imagine you need to pass a procedure a text whose size is equal to that of an issue of The New York Times. Before calling the procedure, the program will try to push this on the stack. If stack overflow doesn't occur, you'll wait long enough.
- In the most crucial fragments of code (such as output to the screen), you can use the assembly language. Even Delphi or C++ inline assemblers are much faster than the standard language functions. If the execution speed is very important in a fragment of code, you can separate the assembly code into an individual module, compile it with the TASM or MASM compiler, and link to your program.
The assembly language is quick and compact, but it is very difficult to write a large project in it. I recommend you not to abuse it and use it only where speed is crucial.
Law 6
For complex computation, you can prepare tables with data computed beforehand and then use these tables in the real-time mode.
When the first version of Doom appeared, the gamer community was astonished with the quality of graphics and the speed of work. This actually was a masterpiece of programming because computers couldn't render 3d graphics in real time at those times. Nobody even thought about 3d accelerators, and video cards only displayed data and didn't perform any additional computation.
How did Doom authors manage to create that 3d world? The secret was simple like everything in our world. The game didn't compute scenes. All complicated mathematical computation was done beforehand, and the results were recorded in a database that was loaded at the program start. Of course, it was impossible to populate the database with all conceivable data, so it stored only the main results. When a value missing from the pre-computed table was required, the nearest approximate value was taken. Thus, Doom obtained an excellent performance and a good quality of 3d images.
When Quake was released, the gamer community again was astonished with the quality of light and shadows in the virtual world of Quake. Computation of light is an extremely complicated task, to say nothing of shadows. How could the authors achieve such a quality of scenes and high performance? The answer is the same: by using tables with pre-computed values.
Some time later the game industry was astonished even more. When Quake 3, in which lighting was computed in real time, was released, its world turned out to be a bit unnatural. Even Half-Life that was released later on the engine of old Quake, looked much more natural and usual. This was because the computers weren't powerful enough to perform real-time computation, and rounding errors deteriorated the game environment.
Nevertheless, Quake has always been a legend because the world is splendid there. If light and shadows were completely missing from its graphics, the game would remain wonderful. It is marvelous, and it is a real masterpiece of real hackers.
Law 7
There are no unnecessary checks.
Very often optimization results in unstable code because some programmers try to increase performance by removing checks they consider unnecessary. Remember: There are no unnecessary checks! If you think a non-standard situation is unlikely, this doesn't mean your user won't encounter it. The user is very likely to hit a wrong key or enter wrong data.
Make sure you check the user's entry. Do this as soon as the data is entered and don't wait until you need it.
Don't make checks inside a loop. Extra if statements inside loops affect performance very much, therefore, make checks before of after a loop.
Loops are a weak link of each program, and you should begin optimization with loops. Don't put checks inside loops. There shouldn't be extra operations inside a loop because they will be repeated many times.
Law 8
Don't be over-diligent when optimizing. Too-high expenditures on increasing performance can bring your effort to nothing . Set yourself realistic goals and tasks. If you failed to optimize your code to a desired level, it is pointless to keep on trying and taking pains. Quite likely, you will be able to find another solution to the problem.
It is often impossible to reach the ideal because optimization of speed and optimization of quality are opposite goals. This is especially noticeable when it comes to programming graphics. To speed up rendering a scene (for example, in a computer game), you can perform quick, but approximate computation. As a result, the computer works quickly, but the quality of the image isn't high. To increase quality, much time is required, and you often have to choose between the opposites.
Developers of graphic editors sacrifice speed because real-time computing isn't required there. However, developers of computer games have to sacrifice quality. Otherwise, it would be impossible to play, and nobody will buy such a game.