Evaluating Stable Tree Differencing in HyperDiff
E.R. Hoste (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Q.T. Le Dilavrec – Mentor (TU Delft - Software Engineering)
Carolin Brandt – Mentor (TU Delft - Software Engineering)
Jesper Cockx – Graduation committee member (TU Delft - Programming Languages)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Structural code differencing algorithms are used in software engineering tasks such as version control, code review, and change classification. While the Gumtree algorithm is a popular choice due to its performance and accuracy, it is inherently unstable: the output of a diff may change depending on the direction in which it is computed. A stable variant of Gumtree has been proposed to enforce directional symmetry in mappings. In this paper, we empirically evaluate the performance overhead of Gumtree Stable compared to the original Greedy variant. We also assess the impact of lazy evaluation, enabled by the HyperDiff framework, as a general optimization technique applicable to both variants. Our experiments on real-world code changes show that while stability introduces slight overhead in most cases, some cases see relatively large performance gains, averaging out to a runtime improvement when run on larger datasets. Additionally, lazy evaluation significantly reduces runtime for both Stable and Greedy variants. These findings clarify the trade-offs involved in adopting stable differencing and demonstrate how HyperDiff can be used to optimize structural diff computations independently of algorithmic stability.