List<T>.RemoveAt and Array.Copy: same-array left-shift with <64-byte offset runs at ~5 GB/s (17x slower than right-shift)
- Dominant language
- C#
- Stars
- 18.3k
- Forks
- 5.6k
- PR merge metrics
- PR metrics pending
Description
### Description
Same-array **left-shift** copies with a small source/destination offset hit a slow path. `Array.Copy(arr, 1, arr, 0, len-1)` (shift left by one element) runs at **~5 GB/s**, while the mirrored right-shift, non-overlapping copies, and left-shifts with offset >= 64 bytes all run at **~88 GB/s** (inlined AVX2).
The threshold is exactly **64 bytes**, independent of element type (measured: `int[]` src>=16 fast / src<16 slow, `long[]` src>=8 fast, `byte[]` src>=64 fast).
This directly degrades real BCL APIs: `List.RemoveAt(i)` / `List.RemoveRange` shift the tail of the backing array left by one element, so **every value type with `sizeof(T) < 64` takes the slow path on every removal**. Measured on .NET 8.0.30 (identical on 10.0.11), x64, i7-14700KF, Release, 100k-element list, 10k removals:
| operation | time |
|---|---|
| `List.RemoveAt(0)` | ~694 ms |
| `List.RemoveAt(0)` | ~90 ms |
The int copy moves *half* the bytes of the string copy, yet is ~8x slower. Reference types are immune because they take `Buffer.BulkMoveWithWriteBarrier` (chunked, direction-aware, ~88 GB/s) instead of the blittable `SpanHelpers.Memmove` path. `ArrayList` (all boxed references) dodges it for the same reason.
### Repro
```csharp
// dotnet run -c Release (net8.0+)
using System;
using System.Diagnostics;
var arr = new int[100_000];
for (int i = 0; i < arr.Length; i++) arr[i] = i;
var sw = Stopwatch.StartNew();
for (int i = 0; i < 10_000; i++)
Array.Copy(arr, 1, arr, 0, arr.Length - 1); // left shift, 4-byte offset
sw.Stop();
Console.WriteLine($"left-shift (4B offset) : {sw.ElapsedMilliseconds} ms");
sw.Restart();
for (int i = 0; i < 10_000; i++)
Array.Copy(arr, 0, arr, 1, arr.Length - 1); // right shift
sw.Stop();
Console.WriteLine($"right-shift : {sw.ElapsedMilliseconds} ms");
sw.Restart();
for (int i = 0; i < 10_000; i++)
Array.Copy(arr, 16, arr, 0, arr.Length - 16); // left shift, 64-byte offset
sw.Stop();
Console.WriteLine($"left-shift (64B offset) : {sw.ElapsedMilliseconds} ms");
```
Output on this machine (net10.0, x64, i7-14700KF, affinity pinned to a P-core):
```
left-shift (4B offset) : 729 ms (~5 GB/s)
right-shift : 43 ms (~88 GB/s)
left-shift (64B offset) : 45 ms (~88 GB/s)
```
### Root cause observation
With `DOTNET_ReadyToRun=0` + `DOTNET_JitDisasm=SpanHelpers.Memmove`, the JIT generates a tail-call to `Buffer.MemmoveInternal` (QCall -> native `Buffer_MemMove`) for overlapping in-array copies with src != dst, instead of the inlined vectorized loop used for non-overlapping ranges. The native path measures ~5 GB/s here — slower than a plain scalar managed loop (~11 GB/s measured). The 64-byte cliff suggests the fallback is only selected for small displacements, but the exact codegen condition is what makes left-shifts slow while right-shifts of the same size stay fast. (R2R behavior matches the JIT numbers; the threshold sweep was done in default R2R mode.)
### Related
- #4847 (2015): `Array.Copy` / `Buffer.BlockCopy` small-copy slowness; a 64-byte drop-off was noted there. This report is the large-copy + destructive-overlap case, with concrete `List` API impact.
### Configuration
- .NET 8.0.30 and 10.0.11 (identical behavior), x64, Windows 11, i7-14700KF, Release + TieredPGO
Contributor guide
Research direction
Start with the named SpanHelpers.Memmove entry point and trace its calls to Buffer.MemmoveInternal and native Buffer_MemMove, comparing the overlapping left-shift path with the inlined path. Reproduce the measurements using Array.Copy and List.RemoveAt; done means small-offset left shifts no longer show the reported performance cliff while overlap behavior remains correct.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- csharp
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100