dotnet / dotnet/runtime

List<T>.RemoveAt and Array.Copy: same-array left-shift with <64-byte offset runs at ~5 GB/s (17x slower than right-shift)

Open
#132,690 6 comments 1 reaction 0 assignees View on GitHub
area-System.Runtime tenet-performance tracking-external-issue
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.