[Performance]: Opportunities to speed up BlockPool processing

[Jialin]

Proposal to improve performance

Observations

The trace under block_pool.get_new_blocks seems quite fragmented. And we do see some optimization chances there.

• [Core] Avoid KVCacheBlock.__eq__ invocations in FreeKVCacheBlockQueue #21005
  • Avoid eq invocation against KVCacheBlock dataclass
• [WIP] [Core] Introduce popleft_n and append_n in FreeKVCacheBlockQueue to further optimize block_pool #21222
  • Introduce buck append and buck popleft to avoid unnecessary linked list operations
  • Avoid incr_ref function invocations
  • Avoid self.enable_caching check in the inner for loop

Reproduce

export VLLM_USE_MODELSCOPE=False;
export VLLM_TORCH_PROFILER_DIR=~/vllm_profile; # for profiling
vllm serve facebook/opt-125m \
    --swap-space 16 \
    --disable-log-requests \
    --no-enable-prefix-caching \
    --host :: \
    --dtype float16

export VLLM_TORCH_PROFILER_DIR=~/vllm_profile; # for profiling
vllm bench serve \
    --dataset-name random \
    --model facebook/opt-125m \
    --served-model-name facebook/opt-125m \
    --random-input-len 700 \
    --random-output-len 1 \
    --endpoint /v1/completions \
    --ignore-eos \
    --host localhost \
    --port 8000 \
    --request-rate 200 \
    --num-prompts 100 \
    --profile

Report of performance regression

N/A

Misc discussion on performance

N/A

Your current environment (if you think it is necessary)

The output of `python collect_env.py`

N/A

Before submitting a new issue...

• Make sure you already searched for relevant issues, and asked the chatbot living at the bottom right corner of the documentation page, which can answer lots of frequently asked questions.

[yeqcharlotte]

cc: @WoosukKwon @njhill @robertgshaw2-redhat @houseroad on some planned changes on scheduling performance

[robertgshaw2-redhat]

cc @LucasWilkinson fyi

[houseroad]

This is awesome progress, thanks a lot for looking into this optimization.

[github-actions]

This issue has been automatically marked as stale because it has not had any activity within 90 days. It will be automatically closed if no further activity occurs within 30 days. Leave a comment if you feel this issue should remain open. Thank you!