Making Formulog Fast: An Argument for Unconventional Datalog Evaluation (Extended Version)
Preprint
Abstract
By combining Datalog, SMT solving, and functional programming, the language Formulog provides an appealing mix of features for implementing SMT-based static analyses (e.g., refinement type checking, symbolic execution) in a natural, declarative way. At the same time, the performance of its custom Datalog solver can be an impediment to using Formulog beyond prototyping -- a common problem for Datalog variants that aspire to solve large problem instances. In this work we speed up Formulog evaluation, with surprising results: while 2.2x speedups are obtained by using the conventional techniques for high-performance Datalog (e.g., compilation, specialized data structures), the big wins come by abandoning the central assumption in modern performant Datalog engines, semi-naive Datalog evaluation. In its place, we develop eager evaluation, a concurrent Datalog evaluation algorithm that explores the logical inference space via a depth-first traversal order. In practice, eager evaluation leads to an advantageous distribution of Formulog's SMT workload to external SMT solvers and improved SMT solving times: our eager evaluation extensions to the Formulog interpreter and Souffl\'e's code generator achieve mean 5.2x and 7.6x speedups, respectively, over the optimized code generated by off-the-shelf Souffl\'e on SMT-heavy Formulog benchmarks. Using compilation and eager evaluation, Formulog implementations of refinement type checking, bottom-up pointer analysis, and symbolic execution achieve speedups on 20 out of 23 benchmarks over previously published, hand-tuned analyses written in F#, Java, and C++, providing strong evidence that Formulog can be the basis of a realistic platform for SMT-based static analysis. Moreover, our experience adds nuance to the conventional wisdom that semi-naive evaluation is the one-size-fits-all best Datalog evaluation algorithm for static analysis workloads.Keywords
All Related Versions
This publication has 48 references indexed in Scilit:
- Specializing parallel data structures for DatalogConcurrency and Computation: Practice and Experience, 2020
- Soufflé: On Synthesis of Program Analyzers2016
- Bottom-Up Context-Sensitive Pointer Analysis for JavaLecture Notes in Computer Science, 2015
- Dedalus: Datalog in Time and Space2011
- Z3: An Efficient SMT Solver2008
- Specifying and Reasoning About Dynamic Access-Control Policies2006
- A Tool for Checking ANSI-C Programs2004
- Datalog with Constraints: A Foundation for Trust Management Languages2002
- Naive Evaluation of Recursively Defined Relations1986
- Negation as Failure1978