demikernel icon indicating copy to clipboard operation
demikernel copied to clipboard

[pdpix] Use `ready_offset` in `demi_wait_any` as Input to Avoid Low Bias

Open mgravell opened this issue 1 year ago • 0 comments

Context

Currently, ready_offset is used to pass out the index of the completed operation; in the scenario of a non-trivial num_qts where multiple operations have completed in a short time (i.e. multiple operations have completed), we'll be biasing the start of the list, spending unnecessary CPU cycles repeatedly scanning the start of the list, potentially offering triangular performance

Proposed Solution

Interpret the inbound value of ready_offset as a start position for the first (only) sweep of the list; I would anticipate that the common demi_wait_any consumption loop would be to fill removed items from the top of the list (to avoid having to shuffle everything down), so in the common scenario either simply leaving ready_offset or incrementing it by one would be sufficient as a "continue looking at things you didn't get to last time", rather than "start at the start"

As a precaution, note that some existing callers may have an undefined value in this argument currently, if they're expecting it purely outwards, so the value should probably be clamped between 0 and num_qts - 1, to avoid invalid start positions.

Alternative solutions

The alternative would be to add an additional parameter, but that seems unnecessary if the same functionality can be supported using the existing value.

mgravell avatar Nov 28 '22 11:11 mgravell