Calls to `memcpy` are slow for `2^k+1` elements (AMD-specific)

[bjorn-martinsson]

Bug report

Bug description:

Consider the following two Python programs that make 14 copies of a big list

([0] * 262145) * 14

([0] * 265665) * 14

On both of my windows computers, running the latest release of CPython, version 3.13.5, it takes 5 times longer to run the first program (even though its size is smaller). But on older versions of CPython, such as 3.10.11, both programs run equally fast. From my testing, this seems to be an issue only affecting windows. More investigation points to this being an issue for certain AMD processors on both windows and linux.

I also noticed that PyPy has the same issue, starting with version PyPy v7.3.17. I've not been able to reproduce it in versions <= PyPy v7.3.16.

As for what is happening, I am not sure. I think it has to do with 262145=2^18 + 1 being one off from a power of two, which somehow makes copying the list super slow.

Edit: The culprit seems to be calls to memcpy(dst, src, count) when dst-src is slightly larger than a power of two. The algorithm used by the current versions of both CPython and PyPy to copy lists causes this to happen over and over whenever a list of size 2^k + 1 is being copied, while the previous algorithm did not. This explains why I've been unable to reproduce the bug in older versions of CPython and PyPy. See microsoft/STL#5658 for more details about the issue of memcpy being slow.

CPython versions tested on:

3.14, 3.13

Operating systems tested on:

Windows, Linux

[JasonMendoza2008]

Two things:

---

This is the case for any $\text{size} = 2^k + 1$ (isn't a necessary condition for the slowdown but seems sufficient from testing values that are testable).

Comparing (3.14.0rc1, Windows 11) $2^k + 1$ with $2^k + 10$ gives:

Elements (2^k)	2^k+1 (s)	2^k+10 (s)
15	0.00183018843332926	0.00092578252156575
16	0.00456350326538086	0.00232616106669108
17	0.01047532558441162	0.00626289844512939
18	0.02173492272694905	0.01349142392476399
19	0.04511809190114339	0.02755439440409342
20	0.09261749426523845	0.05655954202016194
21	0.18645869572957358	0.11373299121856689

MRE

import time

for i in range(15, 22):
    r = 5000 if i < 15 else 150

    start_time = time.time()
    for _ in range(r):
        a = ([0] * (2**i + 1)) * 14
    print((time.time() - start_time) / r)

    start_time = time.time()
    for _ in range(r):
        a = ([0] * (2**i + 10)) * 14
    print((time.time() - start_time) / r)

    print("---")

---

The fact that the bug starts with version PyPy v7.3.17 and that in PyPy v7.3.17's changelog we can see:

copy lists in multiplication with log2(n) arraycopys instead of just copying n times (string multiplication does it like this too)

is probably related. Current CPython implementation matches those log2(n) arraycopys:

cpython/Include/internal/pycore_list.h

Lines 56 to 65 in a852c7b

	_Py_memory_repeat(char* dest, Py_ssize_t len_dest, Py_ssize_t len_src)
	{
	assert(len_src > 0);
	Py_ssize_t copied = len_src;
	while (copied < len_dest) {
	Py_ssize_t bytes_to_copy = Py_MIN(copied, len_dest - copied);
	memcpy(dest + copied, dest, (size_t)bytes_to_copy);
	copied += bytes_to_copy;
	}
	}

[JasonMendoza2008]

The issue might be due to memcpy with the MSVC compiler. Running this C code with Microsoft (R) C/C++ Optimizing Compiler Version 19.44.35211 for x86:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define COUNT1 262144   // 2^18
#define COUNT2 262145   // 2^18 + 1
#define COUNT3 262154   // 2^18 + 10
#define REPEATS 10000

void benchmark_copy(const int *src, int *dst, size_t count, const char *label) {
    size_t size_bytes = count * sizeof(int);

    clock_t start = clock();
    for (int i = 0; i < REPEATS; ++i) {
        memcpy(dst, src, size_bytes);
    }
    clock_t end = clock();

    double total_sec = (double)(end - start) / CLOCKS_PER_SEC;
    printf("%s: Copied %zu bytes (%zu ints) %d times\n", label, size_bytes, count, REPEATS);
    printf("%s: Total time: %.6f sec\n", label, total_sec);

    // Prevent optimizing away
    printf("%d \n", dst[14]);
}

int main(void) {
    static int src1[COUNT1], dst1[COUNT1];
    static int src2[COUNT2], dst2[COUNT2];
    static int src3[COUNT3], dst3[COUNT3];

    for (size_t i = 0; i < COUNT1; ++i) src1[i] = (int)i;
    for (size_t i = 0; i < COUNT2; ++i) src2[i] = (int)i;
    for (size_t i = 0; i < COUNT3; ++i) src3[i] = (int)i;

    benchmark_copy(src1, dst1, COUNT1, "COUNT1 (2^18)");
    benchmark_copy(src2, dst2, COUNT2, "COUNT2 (2^18 + 1)");
    benchmark_copy(src3, dst3, COUNT3, "COUNT3 (2^18 + 10)");
    benchmark_copy(src1, dst1, COUNT1, "COUNT1 (2^18)");
    benchmark_copy(src2, dst2, COUNT2, "COUNT2 (2^18 + 1)");
    benchmark_copy(src3, dst3, COUNT3, "COUNT3 (2^18 + 10)");
    return 0;
}

I get:

COUNT1 (2^18): Copied 1048576 bytes (262144 ints) 10000 times
COUNT1 (2^18): Total time: 0.149000 sec
14
COUNT2 (2^18 + 1): Copied 1048580 bytes (262145 ints) 10000 times
COUNT2 (2^18 + 1): Total time: 2.065000 sec
14
COUNT3 (2^18 + 10): Copied 1048616 bytes (262154 ints) 10000 times
COUNT3 (2^18 + 10): Total time: 0.160000 sec
14
COUNT1 (2^18): Copied 1048576 bytes (262144 ints) 10000 times
COUNT1 (2^18): Total time: 0.149000 sec
14
COUNT2 (2^18 + 1): Copied 1048580 bytes (262145 ints) 10000 times
COUNT2 (2^18 + 1): Total time: 2.073000 sec
14
COUNT3 (2^18 + 10): Copied 1048616 bytes (262154 ints) 10000 times
COUNT3 (2^18 + 10): Total time: 0.160000 sec
14

[picnixz]

If the issue is with memcpy() I can suggest two solutions:

• Do nothing. It's a Windows' issue in this case and we shouldn't be trying to do "too" smart things.
• Or handle those special cases differently if we can.

I think it'd be better to not be too smart. There are likely other places in the CPython project where we would hit such cases and we don't want to specialize them.

cc @colesbury @serhiy-storchaka

[bjorn-martinsson]

One possiblity is to switch _Py_memory_repeat to use an algorithm like this:

def make_k_copies(A, k):
    if k == 0:
        return []
    n = len(A)
    m = n * k
    B = [None] * m
    B[:n] = A
    i = n
    pow2 = 1
    while i + pow2 <= m:
        j = i % n
        B[i:i+pow2] = B[j:j+pow2]
        i += pow2
        pow2 *= 2
    pow2 = 1
    while i < m:
        if (m - i) & pow2:
            j = i % n
            B[i:i+pow2] = B[j:j+pow2]
            i += pow2
        pow2 *= 2
    return B

This would only call memcpy with counts of powers of two. This should in principle guarantee that no "bad input" could ever exist, since the kind of calls to memcpy would be the same for every input.

[picnixz]

I'm really not fond of fixing such cases in CPython and would rather see them fixed upstream because that's likely not the only place which may suffer from this. OTOH, the issue is affecting a critical component of the project, namely lists, but at the same time, it's about copying lists. Is it a common pattern? maybe, maybe not. Most of the time I need to copy a list n times because I want to initialize it to some sentinel values (e.g., [None] * n) but that's it.

[serhiy-storchaka]

Was it caused by #91247? Would reverting it make the worst case faster or all other cases equally slower?

cc @eendebakpt

[JasonMendoza2008]

Was it caused by #91247? Would reverting it make the worst case faster or all other cases equally slower?

cc @eendebakpt

I think that, since the problem comes from MSVC, although reverting it would make the cases mentioned in this issue faster, we are likely to be able to find other ways of making it slow because the old version also used memcpy and the problem comes from memcpy being slow for certain array sizes (still unknown how to exactly reproduce).

[ZeroIntensity]

One possiblity is to switch _Py_memory_repeat to use an algorithm like this:

It sounds like the problem is with all memcpy calls, right? It would be better to invent our own _Py_memcpy that avoids slowdown on MSVC.

But anyways, this definitely sounds like a MSVC bug. cc @zooba @chris-eibl as our Windows experts.