Asymmetry in performance and some suggestions for a maybe quick win?

[selasijean]

@wcharczuk

So I noticed some performance issues that I wanted to flag and bring to your attention. Running the simple benchmark tests defined below, Benchmark_SimpleReverse took unreasonably long to complete (~13s) vrs Benchmark_Simple which took ~0.5s. The expectation was that Benchmark_SimpleReverse would be at least slightly slower since it will deal with a lot of nodes in the recompute heap during the first stabilization.

Investigating further, I noticed that we were spending a long time in the adjustHeightHeap, and so I changed for x := 0; x <= ah.maxHeightSeen; x++ to for x := ah.heightLowerBound; x <= ah.maxHeightSeen; x++ { to match the JS implementation and the change made Benchmark_SimpleReverse take 1s to complete(a 13x speedup).

I noticed the comment:

NOTE (wc): we cannot start at heightLowerBound because of transient parallel recomputation issues. We use zero here to avoid locking the node metadata.

I don't think this change at the detriment of regular Stabilize, which is used more is worth it. Lmk what you think.

func Benchmark_Simple(b *testing.B) {
    g := incr.New(
        incr.OptGraphMaxHeight(4000),
    )
    ctx := context.Background()

    for n := 0; n < b.N; n++ {
        cache := make(map[string]incr.Incr[*int])
        for i := 1; i <= 1000; i++ {
            fi := f(g, i, cache)
            _, err := incr.Observe(g, fi)
            if err != nil {
                b.Fatal(err)
            }
            err = g.Stabilize(ctx)
            if err != nil {
                b.Fatal(err)
            }
        }
    }
}

func Benchmark_SimpleReverse(b *testing.B) {
    g := incr.New(
        incr.OptGraphMaxHeight(5000),
    )
    ctx := context.Background()

    for n := 0; n < b.N; n++ {
        cache := make(map[string]incr.Incr[*int])
        for i := 1000; i > 0; i-- {
            fi := f(g, i, cache)
            _, err := incr.Observe(g, fi)
            if err != nil {
                b.Fatal(err)
            }
            err = g.Stabilize(ctx)
            if err != nil {
                b.Fatal(err)
            }
        }
    }
}

// f(t) = f(t-1); f(0) = 0
func f(bs incr.Scope, t int, cache map[string]incr.Incr[*int]) incr.Incr[*int] {
    key := fmt.Sprintf("f-%d", t)
    if _, ok := cache[key]; ok {
        return cache[key]
    }
    r := incr.Bind(bs, incr.Var(bs, "fakeformula"), func(bs incr.Scope, formula string) incr.Incr[*int] {
        if t <= 0 {
            out := 0
            r := incr.Return(bs, &out)
            r.Node().SetLabel("f-0")
            return r
        }
        bindOutput := incr.Map(bs, f(bs, t-1, cache), func(r *int) *int {
            out := *r + 1
            return &out
        })
        bindOutput.Node().SetLabel(fmt.Sprintf("map-f-%d", t))
        return bindOutput
    })

    r.Node().SetLabel(fmt.Sprintf("f(%d)", t))
    cache[key] = r
    return r
}

[selasijean]

Miscellaneous and probably doesn't affect anything We have func (b *bind[A, B]) scopeHeight() int { return b.lhs.Node().height } instead of func (b *bind[A, B]) scopeHeight() int { return b.lhsChange.Node().height } per the JS impl

Deliberate?

[wcharczuk]

Addressed by #24