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

Reply via email to