Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter

[Junio C Hamano <gitster@pobox.com>]

Kristofer Karlsson <krka@spotify.com> writes:

> That's an excellent approach! Much cleaner in general.
>
> I benchmarked it against the counter on a monorepo with wide-frontier DAGs
> (2.4M commits, component import merges). Using merge-base --all to bypass
> the early-exit optimization from kk/paint-down-to-common-optim:
>
>                Baseline    Cache   Counter
>     import(A)    8079ms   3686ms    3723ms
>     import(B)    5498ms   3993ms    4038ms
>     import(C)    4350ms   1748ms    1766ms
>
> The cache performs on par with the counter - within noise on all three
> cases. No new flags needed, much simpler diff.
> The amortized O(1) is just as good as true O(1) in practice, and it avoids
> the ENQUEUED flag and counter bookkeeping entirely.

Nice.

> I went with back-to-front scanning as you suggested, and also clear
> the cache when the cached entry goes stale. Applied to both
> paint_down_to_common and ahead_behind.
>
> I can rewrite the patchset with this approach and add you as co-author or
> suggested-by? Or I think I can wait for you to push it yourself.
> You did all the work here, and just didn't have enough data points to
> motivate it?

I can take from either of you two ;-).  Thanks for working so well
together, as always.