erigontech / erigontech/erigon

execution/stagedsync: avoid quadratic held-back retry reinsertion

Open
#22,452 2 comments 0 reactions 1 assignee Claimed by @sudeepdino008 View on GitHub
performance
Dominant language
Go
Stars
3.6k
Forks
1.5k
Avg merge
1d 16h
Merged PRs (30d)
455

Description

## Context

Follow-up to #22336.

The parallel-executor refill loop stores gate-rejected retries in `holdBack`, then restores them by calling `pushPending` once per task:

https://github.com/erigontech/erigon/blob/c6dad71b5bb531f18d5985875db38848e5cedbaf/execution/stagedsync/exec3_parallel.go#L3287-L3288

## Problem

Consider a pending list with:

- many low-index retries that fail the speculative dispatch gate;
- enough fresh tasks to exhaust the input-queue budget; and
- a large untouched suffix of fresh pending tasks.

The loop consumes the sorted prefix into `holdBack` but leaves the untouched suffix in `pending`. Every held-back transaction sorts before that suffix, so restoring each transaction with `pushPending` shifts the suffix once per transaction. For `H` held-back retries and `R` remaining tasks, one refill call performs O(H × R) work.

Because refill runs after each processed result, this can reintroduce coordinator starvation on conflict-heavy, high-transaction-count blocks and can be more expensive than the previous linear pending-list rebuild.

A temporary microbenchmark exercising this exact reinsertion shape on an Apple M2 Max produced:

| Total pending entries | Time per reinsertion |
|---:|---:|
| 1,024 | 28 µs |
| 2,048 | 97 µs |
| 4,096 | 364 µs |
| 8,192 | 1.38 ms |

Doubling the list size costs approximately 4×, consistent with quadratic behavior.

## Expected behavior

Restore held-back tasks in O(H + R), for example by prepending or bulk-merging the already-sorted held-back prefix with the untouched pending suffix once.

## Acceptance criteria

- The scheduler does not perform one sorted insertion into the untouched pending suffix per held-back task.
- Pending order and status invariants remain unchanged.
- A focused regression benchmark or test covers held-back retries followed by a large fresh tail.
- `go test -race ./execution/stagedsync -short -count=1` passes.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.