TL;DR
This paper investigates the effectiveness of two Information Retrieval (IR) techniques, BM25 and its variant BM25F, for automatically locating relevant source code segments for specific software features. The study demonstrates that BM25 and BM25F consistently outperform traditional IR models like VSM, UM, and LDA across four open-source projects, offering a more efficient way for developers to find code related to features or bug fixes.
What Problem Does This Paper Address?
Software development and maintenance involve frequent tasks like adding new features, improving existing ones, and fixing bugs. A crucial part of these tasks is "feature location," which means identifying the specific source code entities (like functions or classes) that implement a particular functionality. Manually searching through thousands of code artifacts is time-consuming and error-prone for developers. While automatic and semi-automatic methods using Information Retrieval (IR) techniques have been proposed to aid this process, the optimal IR approach for feature location, especially as a component of more complex hybrid systems, remains an open question. This paper aims to empirically evaluate and compare established IR models with BM25 and BM25F for this specific task.
Methods
The core of this research lies in applying and comparing different Information Retrieval (IR) models for feature location. The general framework involves:
- Document Preprocessing and Representation: Source code is treated as a collection of documents (e.g., methods, classes, or files). Text from identifiers and comments is extracted, then processed by removing stop words, splitting multi-word identifiers (like "OpenFile" into "open" and "file"), and stemming terms to their root form. Documents are then represented as vectors, typically using a "bag-of-words" model.
- Query Processing: Feature descriptions (often bug reports) are similarly preprocessed.
- IR Technique Application: Various IR models are used to calculate the similarity between the query (feature description) and the source code documents.
- Ranking: Documents are ranked based on their similarity scores, with higher ranks indicating higher relevance to the feature.
The specific IR techniques evaluated are:
- Vector Space Model (VSM): Uses TF-IDF (Term Frequency-Inverse Document Frequency) to weigh terms.
- Unigram Model (UM): A language model that uses a single multinomial distribution over terms for each document, with Jelinek-Mercer smoothing to handle unseen terms.
- Latent Dirichlet Allocation (LDA): A topic model that represents documents as a distribution of topics, and topics as a distribution of terms.
- BM25: A popular ranking function that considers term frequency and document length, with parameters to control their weights.
- BM25F: A variant of BM25 that extends the model by classifying document terms into different "fields" (e.g., title, body) and assigning different scaling parameters to each field, allowing for more nuanced weighting. In this study, BM25F was adapted to use two fields: "main" (general text) and "invocation" (method names).
The paper also addresses the issue of long feature descriptions by using a normalized query term frequency scheme for BM25 and BM25F.
Datasets
The study evaluated the techniques on four open-source software projects:
- ArgoUML
- JabRef
- jEdit
- muCommander
The features used for queries were derived from bug reports, patch notes, and enhancement descriptions. The "gold standard" for evaluation was a set of modified methods relevant to each feature, which were adapted to the class level for consistency. These datasets are available online as part of benchmarks.
Key Insights and Ideas
- BM25/BM25F Superiority: The most significant finding is that BM25 and BM25F consistently outperform VSM, UM, and LDA when all terms from feature descriptions are used as queries without manual selection or reformulation. This suggests that these models are more robust to the inherent noise and length of typical feature descriptions.
- Parameter Tuning is Crucial (and Challenging): The performance of BM25 and BM25F is highly dependent on parameter tuning. While the paper explores various parameter combinations, it highlights that finding optimal parameters can be challenging, especially without prior knowledge of the system's relevant entities.
- Field Division in BM25F: The adaptation of BM25F with two fields ("main" and "invocation") shows promise, though the optimal weighting between these fields varied across projects, indicating that a one-size-fits-all approach might not be ideal.
- Simplicity Can Be Effective: The study reinforces previous findings that simpler IR models (like VSM and UM) can perform well, sometimes even better than more complex models like LDA, especially when queries are carefully selected. However, BM25 and BM25F manage to achieve better results even with less curated queries.
- Document Length Normalization: The "worst" configurations for BM25 and BM25F often involved full document length normalization (b=1), suggesting that for feature location, overly aggressive length normalization might not be beneficial.
Key Results
The study evaluated performance using the Mean Reciprocal Rank (MRR) metric. The key results are:
- BM25 and BM25F consistently achieved higher MRR scores across all four projects compared to VSM, UM, and LDA when using their best configurations.
- For example, in the jEdit project, the best MRR for BM25 and BM25F was around 0.63, while for VSM, UM, and LDA, it was around 0.47, 0.54, and 0.38 respectively.
- The best configurations for BM25 and BM25F often had similar MRR values for each project.
- The parameter
k_q(query term frequency scaling) in BM25 and BM25F often benefited from higher values, indicating that terms appearing frequently in the query are important. - For BM25F, the field-dependent parameter
b_1(for the "main" field) being lower (e.g., 0.5) was often associated with better performance, while higher values were in worst configurations.
Limitations and Future Work
- Parameter Tuning Effort: The authors acknowledge that extensive parameter tuning was required, which is not practical in real-world scenarios without prior knowledge. They suggest that empirical parameter recommendations for BM25/BM25F in feature location are needed.
- Limited Fields in BM25F: BM25F was tested with only two fields. Exploring more granular field divisions (e.g., separate fields for comments, identifiers, method names) could further improve performance.
- Evaluation Metric: MRR only considers the rank of the first relevant entity. Future work could explore other metrics like Top-N Rank or Mean Average Precision (MAP) to provide a more comprehensive evaluation.
- Hybrid Approaches: The paper suggests that BM25 family methods could be integrated into existing hybrid feature location techniques to potentially enhance their performance.
- Computational Cost: The paper notes that a large number of parameter values were not explored due to computational constraints.
Summary updated