Batch Requests Without Blowing the Latency Budget

A GPU running one request at a time is mostly idle. Batching is where the throughput comes from, and where the tail latency goes to die, because a request that waits for a batch to fill has paid for someone else's throughput.

Write form_batches(arrival_times, max_batch, max_wait) returning a list of batches, each a list of request indices.

Requests arrive in the order given, at non-decreasing times. A batch is dispatched as soon as either condition is met:

1. It holds max_batch requests, or
2. max_wait seconds have passed since its first request arrived.

Anything arriving after a batch is dispatched belongs to the next one. Every request appears in exactly one batch, and indices stay in order.