Balancing precision and performance in structured merge

摘要

Software-merging techniques face the challenge of finding a balance between precision and performance. In practice, developers use unstructured-merge (i.e., line-based) tools, which are fast but imprecise. In academia, many approaches incorporate information on the structure of the artifacts being merged. While this increases precision in conflict detection and resolution, it can induce severe performance penalties. Striving for a proper balance between precision and performance, we propose a structured-merge approach with auto-tuning. In a nutshell, we tune the merge process on-line by switching between unstructured and structured merge, depending on the presence of conflicts. We implemented a corresponding merge tool for Java, called JDime. Our experiments with 50 real-world Java projects, involving 434 merge scenarios with over 51 million lines of code, demonstrate that our approach indeed hits a sweet spot: While largely maintaining a precision that is superior to that of unstructured merge, structured merge with auto-tuning is up to 92 times faster than purely structured merge, 10 times on average.