Ultra-Large-Scale Repository Analysis via Graph Compression

Ultra-Large-Scale Repository Analysis via Graph Compression Stefano Zacchiroli [email protected] @zacchiro joint work with Paolo Boldi, Antoine Pietri, and Sebastiano Vigna Université de Paris & Inria, France 19 February 2020 SANER 2020: 27th Intl. Conf. on Software Analysis, Evolution and Reengineering London, ON, Canada Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 1 / 16 Motivations Free/Open Source Software (FOSS)+social coding (GitHub, GitLab, ...) = massive amount of data for empirical software engineering (ESE) software evolution and clone detection have vastly benefited from it An ESE growth crisis? GitHub alone: ~100 M repositories exponential growth rate, doubling every ~2 years (Rousseau et al., 2009) possibly the tip of the iceberg w.r.t. the rise of distributed forges and non-public collaborative development (cf. inner source) Current mitigation approaches scale-out analysis: not always applicable, expensive sampling: (e.g., top-starred repos) prone to selection bias and external validity issues Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 2 / 16 Motivations Free/Open Source Software (FOSS)+social coding (GitHub, GitLab, ...) = massive amount of data for empirical software engineering (ESE) software evolution and clone detection have vastly benefited from it An ESE growth crisis? GitHub alone: ~100 M repositories exponential growth rate, doubling every ~2 years (Rousseau et al., 2009) possibly the tip of the iceberg w.r.t. the rise of distributed forges and non-public collaborative development (cf. inner source) Current mitigation approaches scale-out analysis: not always applicable, expensive sampling: (e.g., top-starred repos) prone to selection bias and external validity issues Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 2 / 16 Motivations Free/Open Source Software (FOSS)+social coding (GitHub, GitLab, ...) = massive amount of data for empirical software engineering (ESE) software evolution and clone detection have vastly benefited from it An ESE growth crisis? GitHub alone: ~100 M repositories exponential growth rate, doubling every ~2 years (Rousseau et al., 2009) possibly the tip of the iceberg w.r.t. the rise of distributed forges and non-public collaborative development (cf. inner source) Current mitigation approaches scale-out analysis: not always applicable, expensive sampling: (e.g., top-starred repos) prone to selection bias and external validity issues Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 2 / 16 Research question Is it possible to efficiently perform software development history analyses at ultra large scale, on a single, relatively cheap machine? development history: all information captured by state-of-the-art Version Control Systems (VCS) cheap machine: commodity hardware, desktopor server-gread, few kUSD of investment ultra large scale: in the ballpark of (the known extent of) all publicly available software source code Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 3 / 16 Research question Is it possible to efficiently perform software development history analyses at ultra large scale, on a single, relatively cheap machine? development history: all information captured by state-of-the-art Version Control Systems (VCS) cheap machine: commodity hardware, desktopor server-gread, few kUSD of investment ultra large scale: in the ballpark of (the known extent of) all publicly available software source code Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 3 / 16 Research question Is it possible to efficiently perform software development history analyses at ultra large scale, on a single, relatively cheap machine? development history: all information captured by state-of-the-art Version Control Systems (VCS) cheap machine: commodity hardware, desktopor server-gread, few kUSD of investment ultra large scale: in the ballpark of (the known extent of) all publicly available software source code Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 3 / 16 Research question Is it possible to efficiently perform software development history analyses at ultra large scale, on a single, relatively cheap machine? development history: all information captured by state-of-the-art Version Control Systems (VCS) cheap machine: commodity hardware, desktopor server-gread, few kUSD of investment ultra large scale: in the ballpark of (the known extent of) all publicly available software source code Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 3 / 16 Corpus — Software Heritage our proxy for publicly available software: THE GREAT LIBRARY OF SOURCE CO D E both source code and its development history as captured by VCS coverage: all public repositories from GitHub and GitLab.com historical forges: Google Code, Gitorious package manager repositories: NPM, PyPI, Debian 90 M repositories, 5.5 B unique files, 1.1 B unique files (data dump: 2018-09-25) available as offline dataset Antoine Pietri, Diomidis Spinellis, Stefano Zacchiroli The Software Heritage Graph Dataset: Public software development under one roof MSR 2019: 16th Intl. Conf. on Mining Software Repositories. IEEE Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 4 / 16 Compression efficiency Forward graph total size 91 GiB bits per edge 4.91 Backward graph total size 83 GiB bits per edge 4.49 Operation cost The structure of a full bidirectional archive graph fits in less than 200 GiB of RAM, for a hardware cost of ~300 USD. Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 11 / 16 A domain-agnostic benchmark — full corpus traversal Benchmark — Full BFS visit Forward graph wall time 1h48m throughput 1.81 M nodes/s (553 ns/node) Backward graph wall time 3h17m throughput 988 M nodes/s (1.01 µs/node) Benchmark — Edge lookup random sample: 1 B nodes (8.3% of entire graph) Forward graph visited edges 13.6 B throughput 12.0 M edges/s (83 ns/edge) Backward graph visited edges 13.6 B throughput 9.45 M edges/s (106 ns/edge) Note how edge lookup time is close to DRAM random access time (50-60 ns). Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 12 / 16 Domain-specific benchmarks — source code artifact multiplication Simple clone detection style experiments realized exploiting the compressed corpus: 1file→commit multiplication: how much identical source code files re-occur in different comments 2commit→origin multiplication: how much identical commits re-occur in different repositories Implementation for each node—content for (1), commit for (2)—visit the backward graph and count all reachable nodes of the desired type—commit for (1), origin for (2) naive approach, O(|V|x|E|) complexity Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 13 / 16 File→commit multiplication — results Multiplication factor Visit size random sample of 953 M contents (17% of the full corpus) processing time: ~2.5 days (single machine with 20 x 2.4 GHz cores) in spite of the naive O(|V|x|E|) approach, generally considered intractable at this scale Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 14 / 16 Limitations Incrementality compression is inherently not incremental not an issue for most research use cases, because we analyze immutable data dumps common workaround (e.g., for the Web and social networks) is to keep an uncompressed in-memory overlay for graph updates, and periodically recompress In-memory v. on-disk the compressed in-memory graph structure has no attributes usual data design is to exploit the 0..N-1 integer ranges to memory map node attributes to secondary storage we have done this with a node type map; it weights 4 GB (3 bit per node) works well for queries that do graph traversal first and "join" node attributes last; ping-pong between the two is expensive edge attributes are more problematic Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 15 / 16 Limitations Incrementality compression is inherently not incremental not an issue for most research use cases, because we analyze immutable data dumps common workaround (e.g., for the Web and social networks) is to keep an uncompressed in-memory overlay for graph updates, and periodically recompress In-memory v. on-disk the compressed in-memory graph structure has no attributes usual data design is to exploit the 0..N-1 integer ranges to memory map node attributes to secondary storage we have done this with a node type map; it weights 4 GB (3 bit per node) works well for queries that do graph traversal first and "join" node attributes last; ping-pong between the two is expensive edge attributes are more problematic Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 15 / 16 Wrapping up Graph compression is a viable technique to analyze the history of all public source code, as captured by modern version control systems (VCS), on a budget. It is a novel tool for VCS analyses that might allow to expand the scope of our experiments, reducing selection biases and improving external validity. More work is needed to provide compression incrementality and allow to efficiently query VCS properties during traversal. See full paper for more details Paolo Boldi, Antoine Pietri, Sebastiano Vigna, Stefano Zacchiroli Ultra-Large-Scale Repository Analysis via Graph Compression SANER 2020, 27th Intl. Conf. on Software Analysis, Evolution and Reengineering. IEEE preprint: http://bit.ly/swh-graph-saner20 Contacts Stefano Zacchiroli / [email protected] / @zacchiro / talk to me at SANER 2020! Stefano Zacchiroli Large scale VCS analysis via graph compression 19 Feb 2020, SANER 16 / 16