[cpython] Python 리스트 삽입/삭제 성능 개선: free-threaded 빌드 최적화 분석

2026년 10월 7일수정: 2026년 10월 7일

PR 링크: python/cpython#158791 상태: Merged | 변경: +40 / -5

들어가며

Python 3.13 개발 과정에서 list.insert()와 del list[i] 연산의 성능을 획기적으로 개선하는 Pull Request (PR)가 병합되었습니다. 이 PR은 특히 Python의 free-threaded 빌드 환경에서 발생하는 성능 저하 문제를 해결하는 데 중점을 두고 있습니다. 기존에는 리스트의 요소를 이동시키는 과정에서 원자적(atomic) 연산을 반복적으로 사용하면서 컴파일러의 최적화가 제한되었고, 이로 인해 대규모 리스트 작업 시 성능이 저하되는 문제가 있었습니다. 본 글에서는 이 PR의 코드 변경 사항을 상세히 분석하고, 왜 이러한 변경이 성능 향상으로 이어졌는지, 그리고 이 최적화가 주는 일반적인 교훈은 무엇인지 살펴보겠습니다.

문제 정의: Free-threaded 빌드에서의 성능 병목

Python의 free-threaded 빌드는 Global Interpreter Lock (GIL) 없이 여러 스레드가 동시에 Python 바이트코드를 실행할 수 있도록 하는 실험적인 기능입니다. 이는 멀티코어 CPU 활용도를 높여 특정 워크로드에서 성능 향상을 기대할 수 있게 합니다. 하지만, 스레드 간의 안전한 데이터 공유를 보장하기 위해 리스트와 같은 공유 데이터 구조에 대한 접근은 동기화 메커니즘을 필요로 합니다.

기존 CPython 구현에서 list.insert()와 del list[i] 연산은 내부적으로 리스트의 요소를 이동시켜야 할 때 ins1() 및 list_ass_item_lock_held() 함수를 사용했습니다. Free-threaded 빌드에서는 이러한 요소 이동 시, 각 요소를 원자적 스토어(atomic store) 연산을 통해 처리했습니다. 예를 들어, ins1 함수는 다음과 같이 구현되어 있었습니다:

// Before
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    // ...
    items = self->ob_item;
    for (i = n; --i >= where; )
        FT_ATOMIC_STORE_PTR_RELEASE(items[i+1], items[i]);
    // ...
}

이러한 FT_ATOMIC_STORE_PTR_RELEASE와 같은 원자적 연산은 컴파일러가 루프를 벡터화(vectorize)하거나 다른 최적화를 수행하는 것을 방해했습니다. 결과적으로, 대규모 리스트에서 많은 요소를 이동해야 하는 경우, memmove()와 같은 더 효율적인 메모리 복사 함수를 사용하는 것보다 훨씬 느린 성능을 보였습니다.

코드 변경 분석

이번 PR의 핵심은 free-threaded 빌드에서 리스트 요소 이동 시, 기존의 개별 원자적 스토어 대신 memmove()를 활용할 수 있는 ptr_wise_atomic_memmove() 헬퍼 함수를 도입하고, 이를 적절한 조건에서 사용하도록 로직을 수정한 것입니다.

1. `Objects/listobject.c` 변경 사항

가장 중요한 변경은 ins1() 함수와 list_ass_item_lock_held() 함수 내부에서 요소 이동 로직을 수정한 부분입니다. 새로운 list_shift_items_right_lock_held() 및 list_shift_items_left_lock_held() 함수가 도입되었으며, 이 함수들은 #ifdef Py_GIL_DISABLED 매크로를 통해 free-threaded 빌드에서만 새로운 로직을 사용하도록 분기 처리됩니다.

Before:

ins1 함수 내 요소 이동 로직:

-    for (i = n; --i >= where; )
-        FT_ATOMIC_STORE_PTR_RELEASE(items[i+1], items[i]);
+    if (where < n) {
+        list_shift_items_right_lock_held(self, where, n);
+    }

list_ass_item_lock_held 함수 내 요소 이동 로직:

-        for (Py_ssize_t idx = i; idx < size - 1; idx++) {
-            FT_ATOMIC_STORE_PTR_RELEASE(a->ob_item[idx], a->ob_item[idx + 1]);
-        }
+        if (i < size - 1) {
+            list_shift_items_left_lock_held(a, i, size - 1);
+        }

After:

새롭게 도입된 list_shift_items_right_lock_held 함수 (free-threaded 빌드):

+static inline void
+list_shift_items_right_lock_held(PyListObject *self, Py_ssize_t first, Py_ssize_t last)
+{
+#ifdef Py_GIL_DISABLED
+    ptr_wise_atomic_memmove(self, &self->ob_item[first + 1],
+                            &self->ob_item[first], last - first);
+#else
+    PyObject **items = self->ob_item;
+    for (Py_ssize_t i = last; --i >= first; ) {
+        items[i + 1] = items[i];
+    }
+#endif
+}

list_shift_items_left_lock_held 함수 역시 유사하게 구현되었습니다.

핵심은 Py_GIL_DISABLED 조건 하에서 ptr_wise_atomic_memmove 함수를 호출하는 것입니다. 이 함수는 다음과 같은 스마트한 동작을 수행합니다:

memmove() 활용: 리스트가 현재 스레드에 의해 소유되고 다른 스레드에서 관찰되지 않는 경우 (즉, 안전하게 memmove()를 사용할 수 있는 경우), memmove()를 사용하여 대량의 메모리를 한 번에 복사합니다. 이는 매우 빠릅니다.
원자적 이동 유지: 리스트가 다른 스레드에서 관찰될 수 있는 경우, 기존과 같이 요소별 원자적 스토어(FT_ATOMIC_STORE_PTR_RELEASE)를 사용하여 안전성을 보장합니다.

GIL 빌드의 경우, 기존의 루프 기반 코드가 유지됩니다. 이는 GIL 빌드에서는 컴파일러가 해당 루프를 호출하는 함수 내에서 직접 최적화할 수 있으며, 벤치마크 결과에 따르면 이 방식이 더 나은 성능을 보이기 때문입니다. 이 PR은 free-threaded 빌드에만 영향을 미치며, 기존 GIL 빌드의 성능을 저하시키지 않습니다.

2. `Misc/NEWS.d/next/Core_and_Builtins/` 변경 사항

NEWS.d 파일에 이번 변경 사항에 대한 설명이 추가되었습니다. 이는 Python 3.13 릴리스 노트에 포함되어 사용자들에게 성능 개선 사실을 알리는 역할을 합니다.

--- /dev/null
+++ b/Misc/NEWS.d/next/Core_and_Builtins/2026-10-04-01-40-31.gh-issue-158790.F3kQ7z.rst
@@ -0,0 +1 @@
+Speed up :meth:`list.insert` and item deletion via :keyword:`del` in free-threaded builds by using :manpage:`memmove(3)`.

리뷰어 picnixz는 :meth: 대신 :func:를 사용하도록 제안했으며, 이는 최종적으로 반영되었습니다. 또한, 전체적인 성능 향상 수치 (기하 평균 2.23x)를 포함하도록 권장했습니다.

왜 이게 좋은가: 성능 향상과 일반화된 교훈

성능 수치

PR 설명과 리뷰 댓글에 제시된 벤치마크 결과는 이 최적화의 효과를 명확하게 보여줍니다.

Free-threaded release build (--disable-gil, -O3) 결과:

del l[0]: 2.26x 더 빠름
del l[len(l)//2]: 2.14x 더 빠름
l.insert(0, x): 1.95x 더 빠름
l.insert(len(l)//2, x): 1.86x 더 빠름
insert(0)+del[0], n=1000: 2.86x 더 빠름
sliding window, n=1000: 2.46x 더 빠름

전체 기하 평균 (Geometric Mean): 2.23x 더 빠름

이 수치들은 특히 리스트의 중간이나 시작 부분에서 요소를 삽입하거나 삭제할 때 발생하는 요소 이동 작업이 free-threaded 빌드에서 얼마나 큰 성능 병목이었는지를 보여줍니다. memmove()를 활용한 최적화는 이러한 작업들을 훨씬 효율적으로 처리하여 상당한 속도 향상을 가져왔습니다.

리뷰 과정에서 corona10은 free-threaded 전용 로직 추가의 유지보수 비용과 그 가치에 대해 의문을 제기했습니다. 하지만 hetaozdh는 다음과 같이 반박하며 이 최적화의 타당성을 입증했습니다:

GIL 빌드 영향 없음: 이 PR은 GIL 빌드의 기존 루프 로직을 그대로 유지하므로 성능 회귀가 없습니다.
memmove()의 GIL 빌드 성능: GIL 빌드에서 memmove()를 강제로 사용하면 짧은 리스트에서는 오히려 성능이 저하될 수 있습니다. (약 10% 느려짐)
Free-threaded 빌드의 큰 이점: free-threaded 빌드에서는 2.23배의 기하 평균 성능 향상이 있습니다.
유지보수 비용: static inline 헬퍼 함수 두 개와 #ifdef 분기 정도의 적은 유지보수 비용으로 큰 성능 향상을 얻을 수 있습니다.

결론적으로, free-threaded 빌드라는 특정 환경에서 발생하는 성능 병목을 정확히 진단하고, 해당 환경에 최적화된 솔루션(memmove())을 적용하되, 다른 환경(GIL 빌드)에는 영향을 주지 않도록 분기 처리한 점이 매우 훌륭합니다.

일반적인 교훈

환경별 최적화의 중요성: 모든 환경에서 동일한 코드가 최적은 아닙니다. 특히 동시성 모델(GIL vs. free-threaded)에 따라 성능 특성이 달라질 수 있습니다. 특정 환경의 병목을 찾아내고 해당 환경에 맞는 최적화를 적용하는 것이 중요합니다.
memmove()의 강력함: 대규모 메모리 블록을 복사해야 할 때는 가능한 한 memmove()와 같은 저수준의 최적화된 함수를 활용하는 것이 좋습니다. 컴파일러 최적화가 어려운 복잡한 루프보다 더 효율적일 수 있습니다.
안전성과 성능의 균형: free-threaded 환경에서는 데이터 경쟁을 피하기 위해 원자적 연산이 필수적입니다. 하지만 이 PR은 ptr_wise_atomic_memmove를 통해 memmove()의 성능 이점을 취하면서도, 필요시에는 원자적 연산을 유지하는 균형 잡힌 접근 방식을 보여줍니다.
벤치마킹의 중요성: 제안된 변경 사항이 실제 성능에 미치는 영향을 정량적으로 측정하는 것은 필수적입니다. 이 PR은 다양한 시나리오에 대한 상세한 벤치마킹 결과를 제시하여 변경의 타당성을 입증했습니다.
점진적 개선: 모든 변경 사항이 모든 환경에서 이득을 보장할 필요는 없습니다. 특정 환경에서의 큰 이득이 다른 환경에서의 약간의 손실이나 영향 없음으로 상쇄될 수 있다면, 이는 충분히 가치 있는 개선일 수 있습니다.