egglog: The Next-Generation Equality Saturation Engine
This is the repo for the core of the egglog engine, which combines the power of equality saturation and Datalog.
For getting started, try out the egglog tutorial!
You can also run egglog in your web browser or check out the documentation.
For a "battery-included" experience, we recommend egglog-experimental. It provides more features through additional egglog plugins.
If you want to cite egglog, please use this citation.
The following instructions are for using/developing the core directly.
Prerequisites & compilation
Install Cargo.
git clone [email protected]:egraphs-good/egglog.git
cargo install --path=egglog
Usage
The core can be used in REPL mode with:
cargo run --release
The standard mode processes an input file:
cargo run --release [-f fact-directory] [--to-dot] [--to-svg] [-j --threads <THREADS>] <files.egg>
- The
--to-dot command will save a graphviz dot file at the end of the program, replacing the .egg extension with .dot.
- The
--to-svg, which requires Graphviz to be installed, will save a graphviz svg file at the end of the program, replacing the .egg extension with .svg.
- Set
RUST_LOG=INFO to see more logging messages, as we use env-logger defaulting to warn.
- The
-j option specifies the number of threads to use for parallel execution. The default value is 1, which runs everything in a single thread. Passing 0 will use the maximum inferred parallelism available on the current system.
One can also use egglog as a Rust library by adding the following to your Cargo.toml:
[dependencies]
egglog = "3.0.0"
See also the Python binding for using egglog in Python.
Egglog can also be compiled to WebAssembly, see ./wasm-example for more information.
Development
To view documentation in a browser, run cargo doc --open.
Run cargo test to run the core egglog tests.
Git size budget
PRs run a Git size budget check to catch accidentally committed generated data
or other large files. The check measures compressed Git objects reachable from
the PR merge commit but not from the base commit, so it also catches files that
were added in an earlier PR commit and deleted before the final diff.
To run the same check locally, compare the base ref with the ref you want to
measure:
python3 scripts/git-size-budget.py upstream/main HEAD
To try different thresholds locally, set SOFT_LIMIT_BYTES and
HARD_LIMIT_BYTES.
Community extensions
The community has maintained egglog extensions for IDEs. However, they are outdated at the time of writing.
Parallelism
egglog has support to run programs in parallel
via the -j flag. This support is relatively new and most users just run
egglog single-threaded; the codspeed benchmarks only evaluate single-threaded
performance. However, please take care not to pessimize parallel performance
where possible (e.g. by adding coarse-grained locks).
Each EGraph has its own scoped thread pool. The CLI uses one thread by default;
pass -j 0 to use the available parallelism or -j N to select a fixed number
of threads. Library users can configure an e-graph with EGraph::new,
with_num_threads, or set_num_threads.
Benchmarks
All PRs use codspeed to evaluate the performance of a
change against a suite of micro-benchmarks. You should see a "performance
report" from codspeed a few minutes after posting a PR for review. Generally
speaking, PRs should only improve performance or leave it unchanged, though
exceptions are possible when warranted.
To debug performance issues, we recommend looking at the codspeed profiles, or
running your own using
samply,
flamegraph-rs,
cargo-instruments (on MacOS) or
perf (on Linux). All codspeed benchmarks correspond to named .egg files,
usually in the tests/ directory. For example, to debug an issue with
extract-vec-bench, you can run the following commands:
# install samply
cargo install --locked samply
# build a profile build which includes debug symbols
cargo build --profile profiling
# run the egglog file and profile
samply record ./target/profiling/egglog tests/extract-vec-bench.egg
# [optional] run the egglog file without logging or printing messages, which can help reduce the stdout
# when you are profiling extracting a large expression
env RUST_LOG=error samply record ./target/profiling/egglog --no-messages tests/extract-vec-bench.egg
CodSpeed
We run all of our "examples" as benchmarks in CodSpeed.
These are in CI for every commit in main and for all PRs. It will run the
examples with extra instrumentation added so that it can capture a single trace
of the CPU interactions
(src):
This is the beginning of the README. Read the rest at the original. Read the full README ↗
