Performance issues with merge functions for containers

[yihozhang]

Merge functions are often used with containers like Set to track things like sets of free variables or to implement aggregation (with set-contains). However, they are currently very slow for non-trivial workloads:

Both of the programs below require gigabytes of memory and never finish.

(sort IntSet (Set i64))
(relation R (i64))
(function f () IntSet :merge (set-union old new))

(R 0)
(rule 
    ((R i) (< i 50000))
    ((R (+ i 1))
     (set (f) (set-of i))))

(run-schedule
    (saturate (run)))

(sort IntSet (Set i64))
(relation R (i64))
(function f () IntSet :merge (set-union old new))

(R 0)
(ruleset init)
(rule 
    ((R i) (< i 50000))
    ((R (+ i 1)))
    :ruleset init)

(rule ((R i))
      ((set (f) (set-of i))))


(run-schedule
    (saturate (run init)
    (run)))

[MilkBlock]

One workaround of Rust API might be define a user-defined base type storing a struct with a ptr and a version number to IndexSet. So that egglog will only clone the ptr but not the whole set.

If user try to access the IndexSet with old version number it should panic.

If user really want to access the old IndexSet, just change IndexSet implementation to be PersistentIndexSet and force user to give version number when access.

[saulshanabrook]

Would using immutable data structures solve this set example?

[saulshanabrook]

I had a go at implementing function containers in #702, but then after doing some profiling I realize they probably won't help for this example.

I ran this code with the samply profiler:

;; https://github.com/egraphs-good/egglog/issues/665
(sort IntSet (Set i64))
(relation R (i64))
(function f () IntSet :merge (set-union old new))

(R 0)
(rule
    ((R i) (< i 10000))
    ((R (+ i 1))
     (set (f) (set-of i))))

(run-schedule
    (saturate (run)))

See the full profile here.

It looks like 88% of total time is spent in bookkeeping around containers:

egglog/core-relations/src/containers/mod.rs

Line 249 in e28e4e0

fn get_or_insert(&self, container: &C, exec_state: &mut ExecutionState) -> Value {

It's not spent in the actual meat of running any of the primitives operations, so speeding those up won't help much.

If I am interpreting this profile correctly:

It looks like most of the time is spent updating this index mapping values to all of the containers that have them inside:

egglog/core-relations/src/containers/mod.rs

Line 315 in e28e4e0

self.val_index.entry(val).or_default().insert(value);

This would make sense that maybe this get very expensive once you have a value inside 10000 sets, since I don't believe any of them get garbage collected.

EDIT: Yeah I have confirmed that it's these three lines taking a majority of the time, commenting them out reduces the time on my machien to run this benchmark from 11 seconds to 2 seconds!

diff --git a/core-relations/src/containers/mod.rs b/core-relations/src/containers/mod.rs
index 63ca81f4..0a4000a6 100644
--- a/core-relations/src/containers/mod.rs
+++ b/core-relations/src/containers/mod.rs
@@ -274,9 +274,9 @@ impl<C: ContainerValue> ContainerEnv<C> {
             dashmap::Entry::Vacant(vac) => {
                 // Common case: insert the mapping in to_id and update the index.
                 vac.insert(value);
-                for val in container.iter() {
-                    self.val_index.entry(val).or_default().insert(value);
-                }
+                // for val in container.iter() {
+                //     self.val_index.entry(val).or_default().insert(value);
+                // }
                 value
             }
             dashmap::Entry::Occupied(occ) => {
 

[MilkBlock]

1. optimize eggcc by 3% (by Immutable data structure)
2. optimize current issue's reproduce example by 30% with lazy insertion comparing to Saul's PR.

[MilkBlock]

@saulshanabrook

Hello Saul,

Currently I'm trying to Instruments egglog, would you mind teach me some knowledge about Instruments on Mac?

I use

cargo instruments -t "time" --release -- ./tests/eggcc-extraction.egg

but I did't got source code available to read on Instruments.

[saulshanabrook]

Yeah you have to do it with a profile that preserves debug symbols, like:

cargo instruments -t time --profile profiling -- ./tests/no-messages/repro-665-set-merge.egg

Might be good to add this to the readme

[MilkBlock]

Thanks a lot. I just switched to samply + firefox profiler and it works well!

[saulshanabrook]

I believe this performance issue was addressed in #708 but that PR I think needs to be rebased to see if it solves this benchmark.