On Tue, 26 May 2026 at 00:50, Junio C Hamano [off-list ref] wrote:

OK.  I guess an obvious alternative design would be to have an
associated hashtable for deduping, or tweak prio_queue_get() so
that it notices duplicated entry just before it returns (i.e.,
peek and discard until queue->array[0].data is different from
what you are going to return).  Both would not beat the cheap cost
of using a single bit per object, I guess ;-)

Yes, I think a hashtable or hashset would work here too. I realize that I
have done a lot of local experimentation with alternative approaches but I
forgot to mention the ones I discarded for various reasons - but that
would be useful information for you to have too. Let me rectify that here.

oidset instead of enqueued flag: Works fine, but is ~15-20% slower end-to-end.
Both are O(1) but the overhead is quite significant compared to a flag.

Peek and discard: the problem here is that the commits are not necessarily
ordered. We can have a sequence of A,B,A if we are unlucky. What I did try
however was an alternative to this - just change the fast-exit heuristic to
overshoot until comparison returns > 0 - i.e. consume some
extra commits in the queue. This works and in my example data we typically
would only need to walk ~16 extra commits with this heuristic, so it's not
bad at all. But the extra comparisons we need to run on each iteration make
it ~15-20% slower.

Another thing I tried was simply tracking the minimum generation seen and
terminate as soon as we have gone past it. This is fast and simple and does
not require deduping, but it only works if we have a commit graph and
generation numbers.

The advantage of the approach with deduping via the ENQUEUED flag and then
just tracking the most recently enqueued commit is that it works independently
of ordering guarantees. All it needs to work is the fact that we can prove
that we have reached a point where queue no longer has any non-stale commits
at all.

Summary:
  Approach        Dedup         Works w/o commit-graph?  Speed
  ENQUEUED flag   yes (1 bit)   yes                      fastest
  Hashtable       yes           yes                      15-20% slower
  Peek-discard    -             -                        broken
  Cmp overshoot   no            yes                      15-20% slower
  Gen overshoot   no            no                       same as ENQUEUED