cHash: Detection of Redundant Compilations via AST Hashing

Authors: 

Christian Dietrich and Valentin Rothberg, Leibniz Universität Hannover; Ludwig Füracker and Andreas Ziegler, Friedrich-Alexander Universität Erlangen-Nürnberg; Daniel Lohmann, Leibniz Universität Hannover

Awarded Best Paper!

Abstract: 

Software projects that use a compiled language are built hundreds of thousands of times during their lifespan. Hence, the compiler is invoked over and over again on an incrementally changing source base. As previous work has shown, up to 97 percent of these invocations are redundant and do not lead to an altered compilation result. In order to avoid such redundant builds, many developers use caching tools that are based on textual hashing of the source files. However, these tools fail in the presence of modifications that leave the compilation result unchanged. Especially for C projects, where module-interface definitions are imported textually with the C preprocessor, modifications to header files lead to many redundant compilations.

In this paper, we present the cHash approach and compiler extension to quickly detect modifications on the language level that will not lead to a changed compilation result. By calculating a hash over the abstract syntax tree, we achieve a high precision at comparatively low costs. While cHash is light-weight and build system agnostic, it can cancel 80 percent of all compiler invocations early and reduce the build-time of incremental builds by up to 51 percent. In comparison to the state-of-the-art CCache tool, cHash is at least 30 percent more precise in detecting redundant compilations.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {203169,
author = {Christian Dietrich and Valentin Rothberg and Ludwig F{\"u}racker and Andreas Ziegler and Daniel Lohmann},
title = {{cHash}: Detection of Redundant Compilations via {AST} Hashing},
booktitle = {2017 USENIX Annual Technical Conference (USENIX ATC 17)},
year = {2017},
isbn = {978-1-931971-38-6},
address = {Santa Clara, CA},
pages = {527--538},
url = {https://www.usenix.org/conference/atc17/technical-sessions/presentation/dietrich},
publisher = {USENIX Association},
month = jul
}

Presentation Audio