Overview

Reduce Python overhead in FreeKVCacheBlockQueue by reading block links and queue sentinels once into local variables, reusing them for validation and link updates, and handling popleft_n(1) inline. The intrusive doubly linked list, eviction order, detached-block link clearing, and existing error checks are preserved.

Claims

• Singleton allocation/free cycles take about 20% less time on GB300's Grace CPU and 17% less time on Xeon Platinum 8562Y+, with CPython 3.12.13.
• Single pop/append and remove/append cycles also improve; larger batches are mostly unchanged.
• These are isolated queue measurements. End-to-end serving performance and model output evaluations have not been measured.

Validation

The benchmark compares the original and modified class definitions in separate namespaces using the same actual slotted KVCacheBlock class. It measures repeated allocation/free cycles, excluding setup. Both hosts use CPython 3.12.13, one pinned CPU, warmup, randomized baseline/candidate order, pools of 2,048 and 100,000 blocks, and 11 fresh processes with 9 samples per case. A separate 9-process run confirms singleton/two-block batches and removal across two alternating shuffled block orders.

For 100,000 blocks, times are nanoseconds per complete cycle. Percentages are time reductions, computed from the median of per-process candidate/baseline ratios; intervals bootstrap those process ratios. Baseline and modified times are independently aggregated medians.

The confirmation run found 20.1% less time for singleton batches on Grace and 17.6% on Xeon. Two-block batches improved by 1.1% on Grace but regressed by 3.6% on Xeon. The synthetic mix contains 90 one-block, 5 two-block, 4 eight-block, and 1 thirty-two-block allocations in a shuffled order; it is not a serving workload.

Hardware: ARM Neoverse V2 / Grace on a GB300; Intel Xeon Platinum 8562Y+

Correctness and static checks:

.venv/bin/python -m pytest tests/v1/core/test_prefix_caching.py \
  tests/v1/core/test_single_type_kv_cache_manager.py \
  tests/v1/core/test_kv_cache_utils.py -q
.venv/bin/pre-commit run --files vllm/v1/core/kv_cache_utils.py \
  tests/v1/core/test_kv_cache_utils.py
.venv/bin/pre-commit run mypy-3.12 --hook-stage manual \
  --files vllm/v1/core/kv_cache_utils.py tests/v1/core/test_kv_cache_utils.py

On the clean PR branch based on upstream main: 389 passed; all applicable pre-commit hooks and mypy-3.12 passed.

The benchmark also validates each implementation against a Python list model for 60,000 randomized operations before timing. It checks ordering, counts, forward/backward links, detached links, prepend/append, and cursor iteration after every operation. Both implementations passed on Grace, Xeon, and local ARM macOS. Nine invalid-operation comparisons also preserved exception types/messages and queue state. The added pytest covers complete draining and refilling for batches of 1, 2, and 16. The existing tests/v1/core suites are covered by Buildkite.

Full benchmark harness, raw samples, and reproduction commands: benchmark code, raw samples, and reproduction commands. No third-party dependencies are needed for the isolated benchmark. The queue and block class definitions are unchanged between the measured baseline and the PR base commit.

Details

Normal allocations use popleft_n(), while remove() is used when touching a cached block whose reference count is zero. The singleton path avoids range() iteration and growing the return list with append(). For example, remove() reads block.prev_free_block and block.next_free_block into local variables, then uses those same references for the validity check and to reconnect the neighboring blocks. Previously, those steps repeatedly accessed the attributes on block. Similarly, popleft() and the append methods reuse local references to the head or tail sentinel. This reduces Python attribute accesses; it does not add a cache or change KV-cache behavior. This small path is inlined because calling popleft() adds function-call and validation overhead; it preserves the original bulk method's checks and mutations.

The singleton branch is a workload-dependent tradeoff: two-block batches regress by approximately 3–5% on Xeon, although they improve slightly on Grace. Larger batches show little change. This PR deliberately claims only the measured queue effects; no end-to-end throughput, accuracy, or model-output claim is made.

Duplicate-work checks searched open PRs for FreeKVCacheBlockQueue, popleft_n, and free-block queue performance. Related #59283 and #55841 change eviction/contiguity policy; #40459 explores a Rust control-plane replacement. None implements this Python-only optimization with the existing queue contract. Issue #40244 concerns restoring allocation order; this PR does not address that behavior and is not linked as its fix.

AI assistance was used (OpenAI Codex) for implementation, testing, benchmarking, and this description. The human submitter reviewed the changes before publication.