Hi,
> > 3) Fill gaps by pulling from the tail instead of rewriting the whole
> queue?
> >
> > I misunderstood at first—this is a generally helpful optimization.
> > I'll integrate it into the current patch.
>
> Great, thank you.
>
I dug deeper into the “fill gaps from the tail” optimization and
implemented a version of it. The tricky part is not the copy itself but
guaranteeing that the queue ends up hole-free and that tail really points
at the slot after the last live request. With a twin-cursor gap-fill we
refuse to move SYNC_FORGET_REQUEST / SYNC_FILTER_REQUEST (they’re
order-sensitive fences).
If the final survivor is one of those barriers, the cursors meet while a
hole still exists immediately before the barrier:
head → A [hole] FILTER(X) …unused…
If we then compute tail = (head + remaining_requests) % max_requests, the
value lands inside the live region (on the barrier itself). The
invariant (head
+ num_requests) % max_requests == tail is broken, so the next enqueue
overwrites live data or the checkpointer under-scans the queue.
Alternatively, we may allow relocating SYNC_FORGET_REQUEST and
SYNC_FILTER_REQUEST entries, but ensuring their ordering semantics remain
correct would be quite challenging. That concern is why the implementation
uses a forward-scan compaction. As the source comment noted:
/*
* The basic idea here is that a request can be skipped if it's followed
* by a later, identical request. It might seem more sensible to work
* backwards from the end of the queue and check whether a request is
* *preceded* by an earlier, identical request, in the hopes of doing less
* copying. But that might change the semantics, if there's an
* intervening SYNC_FORGET_REQUEST or SYNC_FILTER_REQUEST, so we do it
* this way.
Best,
Xuneng
