C++ Programming/Optimization
From Wikibooks, the open-content textbooks collection
Contents |
[edit] Optimizations
Optimization can be regarded as a directed effort to increase the performance of something, an important concept in engineering, in the particular in this case we will cover Software engineering. We will deal with specific computational tasks and best practices to reduce resources utilizations, not only of system resources but also of programmers and users, all based in optimal solutions evolved from the empirical validating of hypothesis and logical steps.
All optimization steps taken should have as a goal the reduction of requirements and the promotion of the program objectives, in doubt all claims can only be substantiated by doing a profiling the given problem and the applied solution.
Optimization is often a topic of discussion among programmers and not all conclusion may be consensual, since they are very closely related to the goals, the programmer experience and dependent of specific setups. The level of optimization will depend directly from actions and decisions the programmer makes. Those can be simple things, from simple coding practices to the selection of the tools one choses to use to create the program. Even selecting the compiler will have some impact.
[edit] Code
One of the safest ways of optimization is to reduce complexity, ease organization and structure and at the same time evading code bloat. This requires the capacity to plan without losing track of future needs, in fact it is a compromise the programmer makes between a multitude of factors.
Code optimization techniques, fall into the categories of:
- High Level Optimization
- Algorithmic Optimization (Mathematical Analysis)
- Simplification
- Low Level Optimization
- Loop Unrolling
- Strength Reduction
- Duff's Device
- Clean Loops
[edit] KISS
The "keep it simple, stupid" (KISS) principle, calls for giving simplicity a high priority in development. It is very similar to a maxim from Albert Einstein's that states, "everything should be made as simple as possible, but no simpler.", the difficulty for many adopters have is to determine what level of simplicity should be maintained. In any case, analysis of basic and simpler system is always easier, removing complexity will also open the door for code reutilization and a more generic approach to tasks and problems.
[edit] The right data in the right container
One should store the appropriate data structure in the appropriate container, prefer storing pointers to objects rather than the objects themselves, use "smart" pointers (see the Boost library) and don't attempt to store auto_ptr<> in STL containers, it is not allowed by the Standard, but some implementations are known to incorrectly allow it.
Avoid removing and inserting elements in the middle of a container, doing it at the end of the container has less overhead. Use STL containers when the number of objects is unknown; use static array or buffer when it is known. This requires the understanding of not only each container, but its O(x) guarantees.
Take as an example the STL containers on the issue of using (myContainer.empty()) versus (myContainer.size() == 0), it is important to understand that depending on the container type or its implementation, the size member function might have to count the number of objects before comparing it to zero. This is very common with list type containers.
While the STL attempts to provides optimal solutions to general cases, if performance doesn't match your requirements think about writing your own optimal solution for your case, maybe a custom container (probably based on vector) that doesn't call individual object destructors and uses custom allocators that avoid the delete time overhead.
Using pre-allocation of memory can provide some speed gains and be as simple remember to use the STL vector<T>::reserve() if permitted. Optimize the use system's memory and the target hardware. In todays systems, with virtual memory, threads and multiple-cores (each with its own cache) where I/O operations on the main memory and the amount of time spent moving it around, can slow things down. This can become a performance bottleneck. Instead opt for array-based data structures (cache-coherent data structures), like the STL vector, because data is stored contiguously in memory, over pointer-linked data structures as in linked lists. This will avoid "death by swapping", as the program needs to access highly fragmented data, and will even help the memory pre-fetch that most modern processors do today.
Whenever possible avoid returning containers by value, pass containers by reference.
[edit] Code reutilization
Optimization is also reflected on the effectiveness of a code. If you can use an already existing code base/framework that a considerable number of programmers have access to, you can expect it to be less buggy and optimized to solve your particular need.
Some of these code repositories are available to programmers as libraries. Be careful to consider dependencies and check how implementation is done: if used without considerations this can also lead to code bloat and increased memory footprint, as well as decrease the portability of the code. We will take a close look at them in the Libraries Section of the book.
To increase code reutilization you will probably fragment the code in smaller sections, files or code, remember to equate that more files and overall complexity also increases compile time.
[edit] ASM
If portability is not a problem and you are proficient with assembler you can use it to optimize computational bottlenecks, even looking at the output of a disassembler will often help looking for ways to improve it. Using ASM in your code brings to the table some other problems (maintainability for instance) so use it at a last resort in you optimization process, and if you use it be sure to document what you have done well.
The x86 Disassembly Wikibook provides some optimization examples using x86 ASM code.
[edit] Reduction of compile time
Some projects may take a long time to compile. To reduce the time it takes to finish compiling the first step is to check if you have the any Hardware deficiencies. You may be low in resources like memory or just have a slow CPU, even having your HD with a high level of fragmentation can increase compile time.
On the other side, problems may not be due to hardware limitations but in the tools you use, check if you are using the right tools for the job at hand, see if you have the latest version, or if do, if that is what is causing trouble, some incompatibilities may result from updates. In compilers new is always better, but you should check first what has changed and if it serves your purposes.
Experience tells that most likely if you are suffering from slow compile times, the program you are trying to compile was probably poorly designed, check the structure of object dependencies, the includes and take some the time to structure your own code to minimize re-compilation after changes if the compile time justifies it.
Use pre-compiled headers and external header guards this will reduce the work done by the compiler.
[edit] Compiler optimizations
Compiler optimization is the process of tuning the output of a compiler in an attempt to improve the operations the programmer has requested, so to minimize or maximize some attribute of an compiled program while ensuring the result is identical.
The most common optimizations available to the programmer fall into three categories:
- Speed; improving the runtime performance of the generated object code. This is the most common optimization
- Space; reducing the size of the generated object code
- Safety; reducing the possibility of data structures becoming corrupted (for example, ensuring that an illegal array element is not written to)
Unfortunately, many "speed" optimizations make the code larger, and many "space" optimizations make the code slower -- this is known as the space-time tradeoff.
[edit] Run time
As we have seen before runtime is the duration of a program execution, from beginning to termination. This is were all resources needed to run the compiled code are allocated and hopefully released, this is the final objective of any program to be executed, as such it should be the target for ultimate optimizations.
[edit] Memory footprint
In the past computer memory has been expensive and technologically limited in size, and scarce resource for programmers. Large amounts of ingenuity was spent in implement complex programs and process huge amounts of data using as little as possible of this resource. Today, modern systems contain enough memory for most usages but capacity demands and expectations have increased as well; as such, techniques to minimize memory usage may still be essential.
- Remember to use
swap()onstd::vector(or deque).
When attempting to reduce reduce (or zero) the size of a vector or deque using the swap(), on a standard container of that type, will guarantee that the memory is released and no overhead buffer for growth is used. It will also avoid the fallacy of using erase() or reserve() that will not reduce the memory footprint.
[edit] Lazy initialization
It is always needed to maintain the balance between the performance of the system and the resource consumption. Lazy instantiation is one memory conservation mechanism, by which the object initialization is deferred until it is required.
Look at the following example:
#include <iostream> class Wheel { int speed; public: int getSpeed(){ return speed; } void setSpeed(int speed){ this->speed = speed; } }; class Car{ private: Wheel wheel; public: int getCarSpeed(){ return wheel.getSpeed(); } char *getName(){ return "My Car is a Super fast car"; } }; int main(){ Car myCar; std::cout << myCar.getName(); }
Instantiation of class Car by default instantiates the class Wheel. The purpose of the whole class is to just print the name of the car. Since the instance wheel doesn't serve any purpose, initializing it is a complete resource waste.
It is better to defer the instantiation of the un-required class until it is needed. Modify the above class Car as follows:
class Car{ private: Wheel *wheel; public: Car() { wheel=NULL; // a better place would be in the class constructor initialization list } ~Car() { if (wheel) { delete wheel; } } int getCarSpeed(){ if(wheel == NULL){ wheel = new Wheel(); } return wheel->getSpeed(); } char *getName(){ return "My Car is a Super fast car"; } };
Now the Wheel will be instantiated only when the member function getCarSpeed() is called.
