egglog

egraphs + datalog!

https://github.com/egraphs-good/egglog

Science Score: 54.0%

This score indicates how likely this project is to be science-related based on various indicators:

✓
CITATION.cff file
Found CITATION.cff file
✓
codemeta.json file
Found codemeta.json file
✓
.zenodo.json file
Found .zenodo.json file
○
DOI references
○
Academic publication links
✓
Committers with academic emails
4 of 35 committers (11.4%) from academic institutions
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Low similarity (16.3%) to scientific vocabulary

Keywords from Contributors

equality-saturation term-rewriting

Last synced: 6 months ago · JSON representation ·

Repository

egraphs + datalog!

Basic Info

Host: GitHub
Owner: egraphs-good
License: mit
Language: Rust
Default Branch: main
Homepage: https://egraphs-good.github.io/egglog/
Size: 5.95 MB

Statistics

Stars: 597
Watchers: 14
Forks: 68
Open Issues: 49
Releases: 0

Created about 4 years ago · Last pushed 6 months ago

Metadata Files

Readme Changelog License Citation Codeowners

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 also can 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 git@github.com: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.
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 = "1.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.

Community extensions

The community has maintained egglog extensions for IDEs. However, they are outdated at the time of writing.

@hatoo maintains an egglog-language extension in VS Code (just search for "egglog" in VS Code). (Outdated)
@segeljakt maintains a Neovim plugin for egglog using tree-sitter. (Outdated)

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:

```bash

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 ```

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).

We use rayon's global thread pool for parallelism, and the number of threads used is set to 1 by default when egglog's CLI is run. If you use egglog as a library, you can control the level of parallelism by setting rayon's num_threads.

Codspeed specifics

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):

CodSpeed instruments your benchmarks to measure the performance of your code. A benchmark will be run only once and the CPU behavior will be simulated. This ensures that the measurement is as accurate as possible, taking into account not only the instructions executed but also the cache and memory access patterns. The simulation gives us an equivalent of the CPU cycles that includes cache and memory access.

Since many of the shorter running benchmarks have unstable timings due to non deterministic performance (like in the memory allocator), we "ignore" them in codspeed. That way, we still capture their performance, but their timings don't show up in our reports by default.

We use 50ms as our cutoff currently, any benchmarks shorter than that are ignored. This number was selected to try to ignore any benchmarks with have changes > 1% when they haven't been modified. Note that all the ignoring is done manually, so if you add another example that's short, an admin on the codspeed project will need to manually ignore it.

Owner

Name: egraphs-good
Login: egraphs-good
Kind: organization

Website: https://egraphs-good.github.io
Repositories: 11
Profile: https://github.com/egraphs-good

Using e-graphs to build cool stuff

Citation (CITATION.bib)

@article{egglog,
  author = {
    Zhang, Yihong and
    Wang, Yisu Remy and
    Flatt, Oliver and
    Cao, David and
    Zucker, Philip and
    Rosenthal, Eli and
    Tatlock, Zachary and
    Willsey, Max
  },
  title = {Better Together: Unifying Datalog and Equality Saturation},
  year = {2023},
  issue_date = {June 2023},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  volume = {7},
  number = {PLDI},
  url = {https://doi.org/10.1145/3591239},
  doi = {10.1145/3591239},
  abstract = {
    We present egglog, a fixpoint reasoning system that unifies Datalog and equality saturation (EqSat). 
    Like Datalog, egglog supports efficient incremental execution, cooperating analyses, and lattice-based reasoning. 
    Like EqSat, egglog supports term rewriting, efficient congruence closure, and extraction of optimized terms. 
    We identify two recent applications -- a unification-based pointer analysis in Datalog and an EqSat-based floating-point term rewriter -- 
    that have been hampered by features missing from Datalog but found in EqSat or vice-versa. 
    We evaluate our system by reimplementing those projects in egglog. 
    The resulting systems in egglog are faster, simpler, and fix bugs found in the original systems.
  },
  journal = {Proc. ACM Program. Lang.},
  month = {jun},
  articleno = {125},
  numpages = {25},
  keywords = {Equality saturation, Program optimization, Datalog, Rewrite systems}
}

Committers

Last synced: 9 months ago

All Time

Total Commits: 858
Total Committers: 35
Avg Commits per committer: 24.514
Development Distribution Score (DDS): 0.789

Past Year

Commits: 301
Committers: 13
Avg Commits per committer: 23.154
Development Distribution Score (DDS): 0.691

Top Committers

Name	Email	Commits
Yihong Zhang	y**9@c**u	181
Saul Shanabrook	s**k@g**m	165
oflatt	o**t@g**m	141
Max Willsey	me@m****m	137
Alex Fischman	a**n@g**m	101
Philip Zucker	p**8@g**m	22
Iurii Zamiatin	n**i@g**m	12
Basile Gros	8****s	11
hatoo	h**0@g**m	10
Eli Rosenthal	e****t	9
Gus Smith	g**s@g**m	9
James R. Wilcox	w**y@g**m	7
DaniPopes	5****s	7
Asger Alstrup Palm	a**r@a**k	7
yzy	y**9@u**u	7
Ryan Tjoa	5****a	5
Ryan Zambrotta	r**m@c**u	3
Thalia Archibald	t**a@a**v	3
Trevor Hansen	t**d@y**m	3
Tobias Nießen	t**n@t**e	2
Hessam Mehr	h**r@g**m	2
jmjumper	j**r@g**e	1
david cao	6****o	1
bohan	b**g@f**m	1
Yisu Remy Wang	r**e@g**m	1
Wil Thomason	w****n	1
Ryan Berger	r**r@g**m	1
Michael Greenberg	m**l@g**e	1
Majid alDosari	m**b@y**m	1
Kirsten	3****g	1
and 5 more...

Committer Domains (Top 20 + Academic)

cs.washington.edu: 3 greenberg.science: 1 foxmail.com: 1 gmx.de: 1 tnie.de: 1 archibald.dev: 1 uw.edu: 1 area9.dk: 1 mwillsey.com: 1

Issues and Pull Requests

Last synced: 6 months ago

All Time

Total issues: 140
Total pull requests: 393
Average time to close issues: 7 months
Average time to close pull requests: 15 days
Total issue authors: 37
Total pull request authors: 23
Average comments per issue: 1.89
Average comments per pull request: 2.14
Merged pull requests: 290
Bot issues: 0
Bot pull requests: 0

Past Year

Issues: 58
Pull requests: 322
Average time to close issues: 16 days
Average time to close pull requests: 7 days
Issue authors: 18
Pull request authors: 16
Average comments per issue: 1.45
Average comments per pull request: 2.11
Merged pull requests: 243
Bot issues: 0
Bot pull requests: 0

View more stats

Top Authors

Issue Authors

oflatt (27)
yihozhang (24)
saulshanabrook (18)
gussmith23 (9)
MilkBlock (7)
AzizZayed (5)
jafioti (4)
Alex-Fischman (4)
FTRobbin (3)
mwillsey (3)
remi-delmas-3000 (3)
rix0rrr (2)
cyk2018 (2)
ricardoV94 (2)
cloudhan (2)

Pull Request Authors

Alex-Fischman (119)
yihozhang (85)
saulshanabrook (60)
oflatt (36)
RiscInside (17)
FTRobbin (17)
DaniPopes (15)
ezrosent (9)
gussmith23 (8)
thaliaarchi (4)
MilkBlock (4)
tniessen (3)
rtzam (2)
hessammehr (2)
DeLectionnes (2)

Top Labels

Issue Labels

enhancement (2) refactor (2) good first issue (2) documentation (1) bug (1)

Pull Request Labels

Packages

Total packages: 1
Total downloads:
- cargo 14,571 total
Total docker downloads: 18,696,325

Total dependent packages: 0
Total dependent repositories: 0
Total versions: 5
Total maintainers: 2

crates.io: egglog

egglog is a language that combines the benefits of equality saturation and datalog. It can be used for analysis, optimization, and synthesis of programs. It is the successor to the popular rust library egg.

Documentation: https://docs.rs/egglog/
License: MIT
Latest release: 0.5.0
published 9 months ago

Versions: 5
Dependent Packages: 0
Dependent Repositories: 0
Downloads: 14,571 Total
Docker Downloads: 18,696,325

Rankings

Dependent repos count: 30.7%

Dependent packages count: 36.2%

Average: 55.1%

Downloads: 98.4%

Maintainers (2)

oflatt yihozhang

Last synced: 6 months ago

Dependencies

.github/workflows/build.yml actions

Swatinem/rust-cache v2 composite
actions/checkout v3 composite

.github/workflows/deploy.yml actions

Swatinem/rust-cache v2 composite
actions/checkout v3 composite
peaceiris/actions-gh-pages v3 composite

Cargo.lock cargo

119 dependencies

Cargo.toml cargo

datatest-stable 0.1.3 development
clap 4
env_logger 0.10
hashbrown 0.13
indexmap 1.9
instant 0.1
lalrpop-util 0.19.8
lazy_static 1.4
log 0.4
num-integer 0.1.45
num-rational 0.4.1
num-traits 0.2.15
ordered-float 3.4
regex 1
rustc-hash 1.1
smallvec 1.10
thiserror 1

web-demo/Cargo.toml cargo

vscode/eggsmol-1.0.0/package.json npm

egglog

Science Score: 54.0%

Keywords from Contributors

Repository

Basic Info

Statistics

Metadata Files

README.md

egglog: The Next-Generation Equality Saturation Engine

Prerequisites & compilation

Usage

Development

Community extensions

Benchmarks

install samply

build a profile build which includes debug symbols

run the egglog file and profile

[optional] run the egglog file without logging or printing messages, which can help reduce the stdout

when you are profiling extracting a large expression

Parallelism

Codspeed specifics

Owner

Citation (CITATION.bib)

Committers

All Time

Past Year

Top Committers

Committer Domains (Top 20 + Academic)

Issues and Pull Requests

All Time

Past Year

Top Authors

Issue Authors

Pull Request Authors

Top Labels

Issue Labels

Pull Request Labels

Packages

crates.io: egglog

Rankings

Maintainers (2)

Dependencies