In C++ programming, optimization goes beyond just tweaking code for performance gains. It fundamentally revolves around making smart design choices. Here’s why:
- Algorithm Selection: The choice of algorithm can drastically affect performance. Using an O(n log n) sort algorithm over an O(n^2) one is a prime example.
- Data Structures: Choosing the right data structure (e.g., using a hash table instead of a linked list for fast lookups) can lead to significant efficiency improvements.
- Memory Management: Efficient memory usage and minimizing allocations/deallocations can enhance performance. Techniques like memory pooling or using smart pointers properly can make a big difference.
- Concurrency and Parallelism: Designing systems that effectively use multiple threads or processes can improve performance. C++11 introduced standard support for threading, which aids in this.
- Avoiding Premature Optimization: Focusing on clean, maintainable code first and optimizing critical sections later is usually more effective.
Doxygen Case Study: Fighting Memory Thrashing Through Design Choices
When the processes running on your machine attempt to allocate more memory than your system has available, the kernel begins to swap memory pages to and from the disk. This is done in order to free up sufficient physical memory to meet the RAM allocation requirements of the requestor.
Excessive use of swapping is called thrashing and is undesirable because it lowers overall system performance, mainly because hard drives are far slower than RAM.
If your application needs to use a large amount of data, you will be exposed to thrashing and your application could slow dramatically. There are two solutions: either optimize your application to use memory more efficiently or add more physical RAM to the system.
Let’s discover which solution Doxygen uses to optimize its memory usage and avoid the thrashing problem.
Doxygen is the de facto standard tool for generating documentation from annotated C++ sources, but it also supports other popular programming languages such as C, Objective-C, C#, PHP, Java, Python, and many others. Thanks to Dimitri van Heesch for his great effort to develop and maintain the project.
Doxygen takes as input the source files, parses them to extract the needed data, and stores the result in class instances of kind DirDef, FileDef, NamespaceDef, ClassDef, and MemberDef. All inherit from the Definition class.
The instances of these classes will be used afterward to generate the documentation. The data that consumes the most memory is information about methods and variables, which are represented by the MemberDef class. The size of these instances can grow to more than 1 GB, depending on the number of methods and variables of the projects processed.
For some projects, storing all these instances in memory can affect system performance, and the generation of the documentation could take many hours.
How does Doxygen optimize memory?
Doxygen uses a disk-cache-based solution; using a disk cache is a popular way to optimize your memory usage. The idea is to store on disk data that would otherwise need to remain in memory; this cache will contain many slots, each one containing a specific piece of data, and some slots will be released if the cache size exceeds a certain value. The data released will be present on disk, and if we need them again they will be moved to memory.
In the case of Doxygen, the algorithm is very simple:
- Defines a cache with 65535 slots.
- When a MemberDef instance needs to be created, Doxygen checks if a cache slot is available; if so, the instance is created in memory; otherwise, it is stored in a data file on the disk, and an index file is updated to store where in the data file this data is stored.
- If Doxygen needs to access a MemberDef instance, it checks its presence in the cache. If it’s not present, Doxygen uses the index file to determine where the data is stored, seeks to this position in the data file, and loads it from the disk.
The performance of the cache depends on:
- The container: It could be a queue, an array, a list or maybe a custom container. The choice of one of these containers could impact your cache performance.
- The maximum size of the cache.
- The algorithm used to evict entries from the cache. When the cache reaches its maximum, you have to decide which entries to release; for example, you could:
- Release the first slots loaded.
- Release the latest slots loaded.
- Release the least-used slots.
1- The Container
Doxygen defines the ObjCache class, which is a linked list of CacheNode instances; this class is responsible for adding and removing instances from the cache.
Here’s how Doxygen declares its cache:
Doxygen::symbolCache =new ObjCache(16+cacheSize);// 16 -> room for 65536 elements, 2- Cache size
Doxygen gets the maximum cache size from the configuration file:
int cacheSize =Config_getInt("SYMBOL_CACHE_SIZE");It’s a good idea to let this parameter be configurable, so you can increase the cache if you have a machine with a large amount of physical memory to increase the cache performance. However, for the newer Doxygen releases, this parameter is removed from the configuration file, and a default value is used.
3- The algorithm for evicting entries from the cache
Here’s the code snippet from the Doxygen source code responsible for releasing the cache when it reaches its maximum:
As specified in the makeResident method code, which is very well commented, the least recently used item is removed if the cache is full.
This method is invoked for almost all MemberDef methods; it’s called each time you have to access the MemberDef state to check if this member is loaded or not, load it if it is not, and remove the least recently used member from the cache.
The impact of using the cache
Using a cache can improve application performance, but does it provide a significant optimization, or is it merely a micro-optimization that is not worth the added complexity?
Before using Clang as the C/C++ parser for our product, we used Doxygen as the parser in our first version. We did many tests on cache size; when we disabled the cache and parsed some C++ projects with this modified version, the parsing time increased a lot, sometimes from 5 min to 25 min. For large projects, it can take hours and significantly affect system performance.
Conclusion
Effective C++ optimization is deeply rooted in making informed design choices. By selecting the right algorithms, data structures, and memory management techniques, and by leveraging concurrency where appropriate, developers can achieve significant performance improvements. This strategic approach to design is what truly drives optimization in C++.