apply_patch gets much slower when replacing thousands of lines in a large file

What happened

apply_patch gets disproportionately slow when it replaces thousands of lines near the beginning of a large text file. This adds avoidable latency to coding-agent turns that make large edits.

Using fixed-width text on Linux with an Intel Core Ultra 9 185H, the public apply-patch path produced these median timings for a 10 MiB file:

The measured operation includes file I/O and patch processing. Fixture reset is excluded.

What I expected

Large replacements should be bounded mainly by reading and rewriting the file, rather than repeatedly shifting the in-memory line list for every removed or inserted line.

Any optimization should preserve patch matching and errors, LF normalization, trailing-newline behavior, exact line endings in preservation mode, and historical handling of overlapping EOF chunks in legacy mode.

Steps to reproduce

1. Build the current apply_patch tool in release mode.
2. Generate a 10 MiB LF text file containing fixed-width 96-byte lines.
3. Apply one patch that replaces the first 1, 100, 1,000, or 5,000 lines with equal-width lines.
4. Measure only the public patch operation, resetting the fixture outside the timed section.
5. Compare how latency grows as the replacement size increases.

Additional context

The slowdown comes from removing and inserting lines individually, which shifts the remaining line list on each operation.

A one-pass proof of concept reduced the 1,000-line case from 163.8 ms to 23.77 ms and the 5,000-line case from 567 ms to 25.57 ms. The reference commit also contains the Divan benchmark and compatibility coverage:

https://github.com/HACKE-RC/codex/commit/c529be01d65d9f2e1e33f78a7e92ce204f5f821a

The proof was checked with the 101-test codex-apply-patch suite and the workspace benchmark smoke test. The synthetic benchmark isolates one contiguous replacement; it does not measure many independent hunks or concurrent writes.

Start by reviewing the linked reference commit and the current public apply-patch implementation, then run the codex-apply-patch suite and workspace benchmark smoke test. Done means large contiguous replacements no longer scale with repeated line shifts while preserving patch matching, errors, newline behavior, preservation mode, and legacy overlapping EOF handling.