Decomposing God Header File via Multi-View Graph Clustering

Yue Wang, Wenhui Chang, Yanzhen Zou, Tongwei Deng, Bing Xie

TL;DR

This paper introduces a novel multi-view graph clustering approach to decompose "God Header Files" – large, complex header files that hinder code maintenance and slow down compilation. Their method achieves higher accuracy and better architectural quality than existing techniques, significantly reducing recompilation times by up to 60%.

What Problem Does This Paper Address?

In large C/C++ projects, "God Header Files" are a significant pain point. These are header files that grow to encompass a vast number of declarations, macros, and data structures. When such a file is modified, it triggers recompilation of a huge portion of the codebase, leading to unbearable build times and making code maintenance a chore. Existing "God Class" refactoring methods aren't suitable because they don't account for the crucial build dependencies across the entire system, nor do they adequately handle the potential for cyclic dependencies that can arise when breaking down header files. This paper aims to solve this by proposing a method to intelligently decompose these monolithic header files into smaller, more manageable units.

Methods

The core of the proposed solution is a multi-view graph clustering approach. Here's a breakdown:

  1. Code Element Graph Construction: They first parse the God Header File to extract code elements (macros, types, functions) and represent their relationships as a graph. Three types of relationships are considered:
  2. Dependency: One element uses another.
  3. Semantic: Textual similarity of identifiers.
  4. Co-usage: How often elements appear together across source files, reflecting build dependencies.
  5. Dependency-Based Graph Coarsening: To preserve strong structural relationships, they merge code elements that have high dependency weights, creating a "coarsened" graph. This ensures tightly coupled elements stay together.
  6. Multi-View Graph Clustering: They then apply a novel algorithm called DuaLGR to cluster the coarsened graph. This algorithm leverages both semantic and co-usage views (representing different aspects of code relationships) and adaptively weights them to create a consensus graph for clustering. This is key to handling the diverse nature of code relationships.
  7. Cyclic Dependency Fixing: A crucial step is to ensure the resulting sub-header files have acyclic dependencies. They employ a heuristic algorithm, extending a two-node cycle fixing method, to iteratively resolve any cycles by strategically moving code elements between proposed sub-header files, optimizing for minimal disruption and maximum gain.

Datasets

The authors created two datasets for evaluation:

  • Synthetic God Header Files: Artificially generated by merging smaller header files from open-source projects (PolarDB, fontforge, FreeRDP). This dataset is used to evaluate the accuracy of their decomposition against a known ground truth.
  • Real-world God Header Files: A collection of 649 God Header Files identified from 203 open-source C projects on GitHub. These files were selected based on having a large number of code elements and a significant file impact, and they come with rich commit histories.

They also built a publicly available benchmark dataset for God Header File decomposition [14].

Key Insights and Ideas

  • Build Dependencies Matter: Unlike God Class refactoring, decomposing header files must consider how changes propagate through the build system (co-usage relationships). This is a critical insight that existing methods miss.
  • Multi-View Clustering is Key: Different code relationships (dependency, semantic, co-usage) offer complementary information. A multi-view approach, especially one that can adaptively weight these views (like DuaLGR), is more robust than simply combining them with fixed weights.
  • Acyclic Dependencies are Non-Negotiable: Cyclic dependencies in header files can lead to compilation errors. A dedicated step to fix these cycles is essential for practical decomposition.
  • God Header Files are Widespread: Their preliminary study found that at least 37.5% of analyzed C projects contain God Header Files, highlighting the prevalence and importance of this problem.

Key Results

  • Accuracy: Their approach achieved 11.5% higher accuracy (measured by MoJoFM) on synthetic datasets compared to state-of-the-art God Class refactoring methods. It also demonstrated more consistent performance across different projects.
  • Architectural Quality: For real-world God Header Files, their decomposition resulted in higher modularity (average improvement of 9.1%) and acyclic dependencies, leading to a simpler and clearer architecture.
  • Recompilation Time Reduction: The decomposition significantly reduced recompilation times for historical commits, ranging from 15% to 60%. For one file (extern.h), this translated to saving approximately 60 hours of recompilation over its evolution.

Limitations and Future Work

  • Automatic Naming: The current approach doesn't automatically generate descriptive names for the decomposed sub-header files, which would aid comprehension.
  • Optimal Subfile Count: While they allow users to specify the number of subfiles, they plan to investigate how to automatically suggest an optimal number.
  • Integrating Acyclic Constraint: The current method fixes cycles after clustering. Future work aims to integrate this constraint directly into the clustering process.
  • Generalization: While evaluated on diverse datasets, the results might vary for different types of files or algorithms.
  • Expert Involvement: For highly complex God Header Files, expert intervention might still be necessary for optimal redesign.

Summary updated

Abstract

God Header Files, just like God Classes, pose significant challenges for code comprehension and maintenance. Additionally, they increase the time required for code recompilation. However, existing refactoring methods for God Classes are inappropriate to deal with God Header Files because the code elements in header files are mostly short declaration types, and build dependencies of the entire system should be considered with the aim of improving compilation efficiency. Meanwhile, ensuring acyclic dependencies among the decomposed sub-header files is also crucial in the God Header File decomposition. This paper proposes a multi-view graph clustering based approach for decomposing God Header Files. It first constructs and coarsens the code element graph, then a novel multi-view graph clustering algorithm is applied to identify the clusters and a heuristic algorithm is introduced to address the cyclic dependencies in the clustering results. To evaluate our approach, we built both a synthetic dataset and a real-world God Header Files dataset. The results show that 1) Our approach could achieve 11.5% higher accuracy than existing God Class refactoring methods; 2) Our decomposition results attain better architecture on real-world God Header Files, evidenced by higher modularity and acyclic dependencies; 3) We can reduce 15% to 60% recompilation time for historical commits that require recompiling.
BibTeX
@misc{wang2024decomposing,
  author = {Yue Wang and Wenhui Chang and Yanzhen Zou and Tongwei Deng and Bing Xie},
  title = {{Decomposing God Header File via Multi-View Graph Clustering}},
  year = {2024},
  eprint = {2406.16487},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.16487},
}
Figure