Optimizing Memory Usage: Insights from Doxygen

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 to free enough physical memory to satisfy the requester’s memory allocation needs.

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 process large amounts of data, it may be exposed to thrashing and could slow down dramatically. There are two possible solutions: optimize the application to use memory more efficiently, or add more physical RAM to the system.

Let’s see which solution Doxygen uses to optimize memory usage and avoid thrashing.

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. Many thanks to Dimitri van Heesch for his tremendous work in developing and maintaining the project.

Doxygen takes source files as input, parses them to extract the required data, and stores the results in instances of the DirDef, FileDef, NamespaceDef, ClassDef, and MemberDef classes. All of them inherit from the Definition class.

The instances of these classes will then be used to generate the documentation. The data that consumes the most memory is the information about methods and variables, which is represented by the MemberDef class. The size of these instances could grow to exceed 1 GB, depending on the number of methods and variables in the projects being processed.

For some projects, storing all these instances in memory can affect system performance, and generating the documentation may take many hours.

How does Doxygen optimize memory?

Doxygen uses a cache-based solution. Using a cache is a common way to optimize memory usage. The idea is to store in a cache the data that needs to be in memory. This cache contains many slots, each holding a specific piece of data. Some slots are released when the cache exceeds a certain size. The released data is moved to disk and loaded back into memory when needed again.

In the case of Doxygen, the algorithm is very simple:

• Define a cache with 65,535 slots.
• When a MemberDef instance needs to be created, Doxygen checks whether a cache slot is available. If it is, the instance is created in memory; otherwise, it is stored in a data file on disk, and an index file is updated to record where in the data file this data is stored.
• When Doxygen needs to access a MemberDef instance, it checks whether the instance is present in the cache. If it is not present, Doxygen uses the index file to determine where the data is stored, seeks to that position in the data file, and loads it from 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 container can impact your cache performance.
• The maximum cache size.
• The algorithm used to remove entries from the cache. When the cache reaches its maximum size, you have to decide which entries to release. For example, you could:
  • Release the first slots loaded.
  • Release the last slots loaded.
  • Release the least-used slots.

1. The Container

Doxygen defines the ObjCache class, which is a linked list of CacheNode objects. 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");

Making this parameter configurable is useful because, on a machine with a large amount of physical memory, you can increase the cache size to improve performance. However, in newer Doxygen releases, this parameter has been removed from the configuration file, and a default value is used.

3. The algorithm for releasing entries from the cache

Here's the code snippet from the Doxygen source code responsible for releasing cache entries when the cache reaches its maximum:

As specified in the 

method code, which is very well commented, the least recently used item is removed if the cache is full.

This method is invoked by almost all 

 methods. It is called whenever the 

state needs to be accessed. It checks whether the member is loaded, loads it if necessary, and removes the least recently used member from the cache.

The advantage of using the cache

Using a cache can improve application performance, but does it provide a significant benefit, 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 for our first version. We ran many tests on cache size: when we disabled the cache and parsed some C++ projects with this modified version, the parsing time increased dramatically, sometimes from 5 minutes to 25 minutes. For large projects, the process can take hours and significantly affect system performance.

Conclusion

Using a cache can significantly improve application performance when working with large amounts of data. Exploring how open-source projects implement their caches can be very useful when designing a cache for your own applications.