코테 문제를 풀다가 문득 궁금해졌다.

a = [1, 2, 3]
print(len(a))

"len() 내장 함수는 a리스트의 길이를 어떻게 알고 값을 리턴하는걸까?"
"a를 할당할 때, 스택에 a리스트 길이와 요소 값하고 힙 메모리 주소를 함께 저장했다가 함수가 호출될 때 반환하는 건가?"

정작 풀어야 하는 문제는 안 풀고 딴생각만 하다 시간 날린건 아님

---

🐍 CPython 내부 들여다보기: 내장 함수는 어떻게 구현되었을까?

1. 인터프리터와 CPython의 개념

인터프리터란?

인터프리터는 프로그래밍 언어로 작성된 소스 코드를 한 줄씩 읽고 즉시 실행하는 프로그램이다. 컴파일 과정 없이 코드를 바로 실행할 수 있어 개발 속도가 빠르지만, 실행 속도는 컴파일 언어에 비해 상대적으로 느린 특징이 있다.

Python은 대표적인 인터프리터 언어로, 작성한 코드를 바로 실행하며 대화형 셸(REPL)을 통해 즉각적인 피드백을 받을 수 있다.

CPython이란?

CPython은 Python 프로그래밍 언어의 공식 구현체(reference implementation)다. Guido van Rossum이 C 언어로 작성했다고 한다.

CPython의 특징

• C로 구현: Python의 핵심 로직이 C 언어로 작성되어 있어 상대적으로 빠른 성능을 제공
• 바이트코드 컴파일: Python 소스 코드를 먼저 바이트코드(.pyc 파일)로 컴파일한 후 Python 가상 머신(PVM)에서 실행
• 확장 가능: C API를 통해 확장 모듈을 작성하여 성능이 중요한 부분을 C로 최적화할 수 있다.
• 참조 카운팅: 가비지 컬렉션에 참조 카운팅(reference counting) 방식을 사용한다.

다른 Python 구현체들?

• PyPy: JIT 컴파일러를 사용하여 CPython보다 빠른 실행 속도를 제공
• Jython: Java 플랫폼에서 실행되는 Python 구현체
• IronPython: .NET 플랫폼에서 실행되는 Python 구현체
• MicroPython: 마이크로컨트롤러와 임베디드 시스템용 경량 Python 구현체

백준에서 PyPy로 제출하면 실행시간이 빨리지는 순간이 있다.

CPython의 실행 과정

CPython은 Python 코드를 바이트코드로 변환한 후, 이를 가상 머신에서 한 명령씩 실행한다. 이 과정에서 내장 함수들은 C로 작성된 네이티브 코드를 직접 호출하여 빠른 성능을 제공한다.

---

2. 내장 함수(Built-in)와 메서드의 개념

내장 함수 (Built-in Functions)

내장 함수는 Python 인터프리터에 기본적으로 포함되어 있어 별도의 import 없이 어디서든 사용할 수 있는 함수다. CPython은 약 70여 개의 내장 함수를 제공한다.

⭐ 대표적인 내장 함수들

# 데이터 타입 변환
int(), float(), str(), list(), dict(), set(), tuple()

# 시퀀스 관련
len(), max(), min(), sum(), sorted(), reversed()

# 객체 관련
type(), isinstance(), id(), dir(), hasattr()

# 입출력
print(), input(), open()

# 함수형 프로그래밍
map(), filter(), zip(), enumerate(), range()

# 기타
abs(), round(), pow(), all(), any(), eval(), exec()

🔎 내장 함수의 특징

• 전역 네임스페이스: builtins 모듈에 정의되어 있어 항상 접근 가능
• C 레벨 구현: 대부분 C로 구현되어 순수 Python 코드보다 훨씬 빠름
• 다형성 지원: 다양한 타입의 인자를 받아 적절히 처리

메서드 (Methods)

메서드는 특정 객체에 속한 함수로, 객체의 데이터를 조작하거나 객체의 상태에 접근하는 데 사용됩니다. 점(.) 표기법을 사용하여 호출한다.

1. 리스트 메서드 예시

my_list = [1, 2, 3]

# 리스트 메서드들
my_list.append(4)      # 요소 추가
my_list.insert(0, 0)   # 특정 위치에 삽입
my_list.pop()          # 마지막 요소 제거
my_list.remove(2)      # 특정 값 제거
my_list.sort()         # 정렬
my_list.reverse()      # 역순 정렬

2. 문자열 메서드 예시

text = "Hello, World!"

text.upper()           # 대문자 변환
text.lower()           # 소문자 변환
text.split(",")        # 분리
text.replace("H", "h") # 치환
text.strip()           # 공백 제거

🌟내장 함수 vs 메서드

구분	내장 함수	메서드
호출 방식	len(obj)	obj.append(value)
소속	builtins 모듈	특정 클래스/객체
범용성	여러 타입에 적용 가능	특정 타입에만 적용
구현 위치	bltinmodule.c	각 타입별 C 파일 (예: listobject.c)

❓그렇다면 왜 len()은 함수이고 append()는 메서드일까?

len()이 메서드가 아닌 내장 함수인 이유는 Python의 철학이 담겨있기 때문!

1. 일관성: 다양한 타입(list, tuple, str, dict 등)에 동일한 방식으로 적용
2. 가독성: len(my_list)가 my_list.len()보다 더 명확하고 간결
3. 성능: C 레벨에서 직접 객체의 크기 정보에 접근하여 더 빠름

---

3. CPython의 내장 함수 구현과 작동 방식

3.1 PyObject: 모든 Python 객체의 기반

CPython에서 모든 Python 객체는 PyObject 구조체를 기반으로 한다. 이는 Python의 동적 타이핑과 객체 지향 특성을 가능하게 하는 핵심 구조이기 때문!

typedef struct _object {
    Py_ssize_t ob_refcnt;           // 참조 카운트
    struct _typeobject *ob_type;    // 객체 타입 포인터
} PyObject;

🌟 PyObject의 역할

• 참조 카운팅: ob_refcnt는 해당 객체를 참조하는 횟수를 추적하여 메모리 관리에 사용
• 타입 정보: ob_type은 객체의 타입을 가리키는 포인터로, 이를 통해 어떤 메서드를 호출할 수 있는지 결정
• 동적 타이핑: 런타임에 ob_type을 확인하여 객체의 타입과 가능한 연산을 파악

3.2 PyVarObject: 가변 크기 객체

리스트, 문자열, 튜플처럼 가변 크기를 가진 객체는 PyVarObject 구조체를 사용한다.

typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size;    // 객체의 크기(요소 개수)
} PyVarObject;

ob_size는 시퀀스의 요소 개수를 저장하며, 이것이 바로 len() 함수가 반환하는 값이다.

3.3 PyListObject: 리스트의 내부 구조

Python 리스트는 CPython에서 PyListObject 구조체로 구현된다.

typedef struct {
    PyVarObject ob_base;
    PyObject **ob_item;       // 요소들을 가리키는 포인터 배열
    Py_ssize_t allocated;     // 할당된 메모리 크기
} PyListObject;

🏗️ 구조 설명

• ob_base: PyVarObject를 포함하여 ob_refcnt, ob_type, ob_size를 가진다.
• ob_item: 실제 요소들을 가리키는 포인터들의 배열이다. (요소 자체가 아님!)
• allocated: 현재 할당된 메모리 공간 (over-allocation을 통한 성능 최적화)
• 불변 조건: 0 <= ob_size <= allocated

Python 리스트의 메모리 구조

3.4 len() 함수의 내부 작동 방식

a = [1, 2, 3]
length = len(a)
print(length)  # 3

Step 1: len() 함수 호출

len() 함수는 Python/bltinmodule.c 파일에 다음과 같이 구현되어 있다.

static PyObject *
builtin_len(PyObject *module, PyObject *obj)
{
    Py_ssize_t res;
    
    // PyObject_Size()를 호출하여 크기 얻기
    res = PyObject_Size(obj);
    
    // 에러 처리
    if (res < 0) {
        assert(PyErr_Occurred());
        return NULL;
    }
    
    // C의 Py_ssize_t를 Python int 객체로 변환
    return PyLong_FromSsize_t(res);
}

Step 2: PyObject_Size() 호출

PyObject_Size() 함수는 객체의 타입에 따라 적절한 크기 계산 함수를 호출한다.

Py_ssize_t
PyObject_Size(PyObject *o)
{
    // 객체의 타입 정보에서 시퀀스 메서드 테이블 가져오기
    PySequenceMethods *m = o->ob_type->tp_as_sequence;
    
    // 리스트의 경우 list_length() 함수 호출
    if (m && m->sq_length) {
        return m->sq_length(o);
    }
    
    // 매핑 타입(dict 등)의 경우
    PyMappingMethods *mp = o->ob_type->tp_as_mapping;
    if (mp && mp->mp_length) {
        return mp->mp_length(o);
    }
    
    // 에러: __len__ 메서드가 없음
    PyErr_SetString(PyExc_TypeError, 
                    "object has no len()");
    return -1;
}

Step 3: list_length() 실행

리스트 객체의 경우, Objects/listobject.c에 정의된 list_length() 함수가 호출된다.

static Py_ssize_t
list_length(PyListObject *a)
{
    // PyVarObject의 ob_size를 직접 반환
    return Py_SIZE(a);
}

// Py_SIZE 매크로 정의
#define Py_SIZE(ob) (((PyVarObject*)(ob))->ob_size)

작동 흐름 요약

1. len(a) 호출
2. builtin_len() 실행
3. PyObject_Size(a) 호출
4. a의 ob_type 확인 → PyList_Type
5. list_length() 호출
6. a의 ob_size 필드 읽기 → 3
7. PyLong_FromSsize_t(3) → Python int 객체 생성
8. 반환: 3

⭐ 핵심 포인트

• len()은 O(1) 시간 복잡도: 단순히 이미 저장된 ob_size 값을 읽기만 하므로 상수 시간이 소요된다.
• 계산하지 않음: 리스트를 순회하며 개수를 세는 것이 아니라, 메모리에 미리 저장된 값을 반환한다.
• 타입별 최적화: 각 타입마다 최적화된 크기 계산 함수를 가진다.

3.5 list.append() 메서드의 작동 방식

a = [1, 2, 3]
a.append(4)

CPython 내부 구현 (Objects/listobject.c)

static PyObject *
list_append(PyListObject *self, PyObject *object)
{
    // app1()을 호출하여 요소 추가
    if (app1(self, object) == 0)
        Py_RETURN_NONE;
    return NULL;
}

static int
app1(PyListObject *self, PyObject *v)
{
    Py_ssize_t n = PyList_GET_SIZE(self);
    
    // 공간이 부족하면 리사이징
    if (n == self->allocated) {
        if (list_resize(self, n + 1) < 0)
            return -1;
    }
    
    // v의 참조 카운트 증가
    Py_INCREF(v);
    
    // 마지막 위치에 요소 추가
    PyList_SET_ITEM(self, n, v);
    return 0;
}

list_resize() - 동적 메모리 할당

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    size_t new_allocated;
    size_t num_allocated_bytes;
    PyObject **items;
    
    // 새로운 크기 계산 (over-allocation 전략)
    // newsize + (newsize >> 3) + 6
    // 즉, 약 12.5% 추가 공간 할당
    new_allocated = (newsize >> 3) + 
                    (newsize < 9 ? 3 : 6) + newsize;
    
    // 메모리 재할당
    items = PyMem_Realloc(self->ob_item, 
                          new_allocated * sizeof(PyObject *));
    
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

🔥 Over-Allocation 전략

CPython은 리스트에 요소를 추가할 때마다 메모리를 재할당하지 않고, 미리 추가 공간을 확보한다!

import sys

a = []
for i in range(10):
    a.append(i)
    print(f"len={len(a)}, allocated={sys.getsizeof(a)}")

len=1, allocated=88   # 4개 공간
len=2, allocated=88   # 여유 공간 사용
len=3, allocated=88   
len=4, allocated=88   
len=5, allocated=120  # 8개로 확장
len=6, allocated=120
len=7, allocated=120
len=8, allocated=120
len=9, allocated=184  # 16개로 확장
len=10, allocated=184

메모리 구조 변화

초기 상태: a = [1, 2, 3]
┌─────────────────────┐
│ ob_size: 3         │
│ allocated: 4       │
│ ob_item: [1,2,3,-] │
└─────────────────────┘

a.append(4) 실행
┌─────────────────────┐
│ ob_size: 4         │ ← 증가
│ allocated: 4       │
│ ob_item: [1,2,3,4] │ ← 4 추가
└─────────────────────┘

a.append(5) 실행 → 공간 부족!
list_resize() 호출 → 새로운 배열 할당
┌─────────────────────────────┐
│ ob_size: 5                 │
│ allocated: 8               │ ← 확장
│ ob_item: [1,2,3,4,5,-,-,-] │
└─────────────────────────────┘

3.6 dict.get() 메서드의 작동 방식

Python 딕셔너리는 해시 테이블(Hash Table)로 구현된다.

d = {"name": "Alice", "age": 30}
value = d.get("name")  # "Alice"

PyDictObject 구조

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;      // 사용 중인 항목 수
    PyDictKeysObject *ma_keys;  // 키 테이블
    PyObject **ma_values;    // 값 배열
} PyDictObject;

dict_get() 내부 동작

static PyObject *
dict_get_impl(PyDictObject *self, PyObject *key, 
              PyObject *default_value)
{
    PyObject *val = NULL;
    Py_hash_t hash;
    Py_ssize_t ix;
    
    // 1. 키의 해시값 계산
    hash = PyObject_Hash(key);
    if (hash == -1)
        return NULL;
    
    // 2. 해시 테이블에서 검색
    ix = (self->ma_keys->dk_lookup)(self, key, hash, &val);
    
    // 3. 키를 찾지 못하면 default_value 반환
    if (ix == DKIX_ERROR)
        return NULL;
    
    if (val == NULL) {
        if (default_value != NULL) {
            val = default_value;
        } else {
            val = Py_None;
        }
    }
    
    Py_INCREF(val);
    return val;
}

해시 테이블 검색 과정

1. "name"의 해시값 계산: hash("name") → 예: 12345
2. 인덱스 계산: 12345 % table_size → 예: 3
3. 테이블[^3] 위치 확인
4. 충돌 처리 (필요시)
5. 값 반환: "Alice"

시간 복잡도: 평균 O(1), 최악 O(n) (해시 충돌이 많을 경우)

---

4. 내가 볼려고 만든 Python 내장 함수 및 메서드의 시간 복잡도 정리

4.1 리스트 (List) 연산

연산	코드 예시	시간 복잡도	설명
인덱스 접근	a[i]	O(1)	포인터 배열에서 직접 접근
길이 확인	len(a)	O(1)	ob_size 필드 읽기
끝에 추가	a.append(x)	O(1) 분할상환	over-allocation으로 평균 상수 시간
끝에서 제거	a.pop()	O(1)	ob_size만 감소
특정 위치 삽입	a.insert(i, x)	O(n)	i 이후 모든 요소 이동 필요
특정 위치 제거	a.pop(i)	O(n)	i 이후 모든 요소 이동 필요
특정 값 제거	a.remove(x)	O(n)	전체 검색 + 이동
특정 값 검색	x in a	O(n)	선형 검색
슬라이싱	a[i:j]	O(k)	k = j - i (복사할 요소 수)
확장	a.extend(b)	O(k)	k = len(b)
정렬	a.sort()	O(n log n)	Timsort 알고리즘
역순 정렬	a.reverse()	O(n)	in-place 역순
복사	a.copy()	O(n)	전체 복사
개수 세기	a.count(x)	O(n)	전체 순회

⭐ append()가 O(1) 분할상환인 이유

# n개 요소를 추가하는 경우
for i in range(n):
    a.append(i)

# 재할당 횟수: log₂(n) (크기가 2배씩 증가)
# 총 복사 횟수: 1 + 2 + 4 + ... + n/2 ≈ n
# 평균 비용: n / n = O(1)

4.2 딕셔너리 (Dictionary) 연산

연산	코드 예시	평균 시간 복잡도	최악 시간 복잡도	설명
접근	d[key]	O(1)	O(n)	해시 테이블 조회
할당	d[key] = value	O(1)	O(n)	해시 테이블 삽입
삭제	del d[key]	O(1)	O(n)	해시 테이블 삭제
검색	key in d	O(1)	O(n)	해시 테이블 조회
get 메서드	d.get(key)	O(1)	O(n)	안전한 조회
길이	len(d)	O(1)	O(1)	ma_used 필드 읽기
keys 조회	d.keys()	O(1)	O(1)	뷰 객체 반환 (순회는 O(n))
values 조회	d.values()	O(1)	O(1)	뷰 객체 반환 (순회는 O(n))
items 조회	d.items()	O(1)	O(1)	뷰 객체 반환 (순회는 O(n))
순회	for k in d:	O(n)	O(n)	전체 키 순회
복사	d.copy()	O(n)	O(n)	전체 복사

💣 해시 충돌과 최악의 경우

# 해시 충돌이 많으면 O(n)으로 저하
# 예: 모든 키의 해시값이 같은 경우
class BadHash:
    def __hash__(self):
        return 1  # 항상 같은 해시값

d = {BadHash(): i for i in range(1000)}
# 이 경우 조회가 O(n)으로 느려짐

4.3 세트 (Set) 연산

연산	코드 예시	평균 시간 복잡도	최악 시간 복잡도	설명
추가	s.add(x)	O(1)	O(n)	해시 테이블 삽입
삭제	s.remove(x)	O(1)	O(n)	해시 테이블 삭제
검색	x in s	O(1)	O(n)	해시 테이블 조회
길이	len(s)	O(1)	O(1)	크기 필드 읽기
합집합	s1 \| s2	O(len(s1) + len(s2))	-	두 세트 병합
교집합	s1 & s2	O(min(len(s1), len(s2)))	-	작은 세트 순회
차집합	s1 - s2	O(len(s1))	-	s1 순회하며 확인

4.4 문자열 (String) 연산

연산	코드 예시	시간 복잡도	설명
인덱스 접근	s[i]	O(1)	불변 배열 접근
길이	len(s)	O(1)	ob_size 읽기
슬라이싱	s[i:j]	O(k)	k = j - i
연결	s1 + s2	O(n + m)	새 문자열 생성
반복	s * k	O(n * k)	새 문자열 생성
검색	x in s	O(n * m)	Boyer-Moore 변형
find	s.find(sub)	O(n * m)	부분 문자열 검색
replace	s.replace(old, new)	O(n)	전체 스캔
split	s.split()	O(n)	전체 스캔 + 리스트 생성
join	sep.join(list)	O(n)	n = 결과 문자열 길이
upper/lower	s.upper()	O(n)	모든 문자 변환

⭐ 문자열 연결 최적화 방법

# 나쁜 예 - O(n²)
result = ""
for s in strings:
    result += s  # 매번 새 문자열 생성

# 좋은 예 - O(n)
result = "".join(strings)  # 한 번에 메모리 할당

4.5 내장 함수

함수	시간 복잡도	설명
len(obj)	O(1)	ob_size 필드 읽기
min(iterable)	O(n)	전체 순회
max(iterable)	O(n)	전체 순회
sum(iterable)	O(n)	전체 순회
sorted(iterable)	O(n log n)	Timsort
reversed(iterable)	O(1)	역방향 이터레이터 생성
enumerate(iterable)	O(1)	이터레이터 래핑
zip(*iterables)	O(1)	이터레이터 래핑
map(func, iterable)	O(1)	이터레이터 생성
filter(func, iterable)	O(1)	이터레이터 생성
all(iterable)	O(n)	조건에 따라 조기 종료 가능
any(iterable)	O(n)	조건에 따라 조기 종료 가능

‼️참고: map(), filter(), zip(), enumerate() 등은 이터레이터를 반환하므로 생성 자체는 O(1)이지만, 실제로 요소를 소비할 때 O(n) 시간이 소요된다.

🌟 4.6 시간 복잡도 최적화 팁

1. 리스트 검색 → set 사용

# 나쁜 예 - O(n)
if item in my_list:
    ...

# 좋은 예 - O(1)
my_set = set(my_list)
if item in my_set:
    ...

2. 리스트 앞쪽 삽입/삭제 → deque 사용

from collections import deque

# 나쁜 예 - O(n)
my_list.insert(0, item)
my_list.pop(0)

# 좋은 예 - O(1)
my_deque = deque(my_list)
my_deque.appendleft(item)
my_deque.popleft()

3. 문자열 연결 → join 사용

# 나쁜 예 - O(n²)
result = ""
for s in strings:
    result += s

# 좋은 예 - O(n)
result = "".join(strings)

4. 중복 제거 → set 사용

# 나쁜 예 - O(n²)
unique = []
for item in items:
    if item not in unique:
        unique.append(item)

# 좋은 예 - O(n)
unique = list(set(items))

---

5. 마무리

CPython 내장 함수의 핵심 설계 원칙

CPython의 내장 함수와 메서드 구현을 살펴보면서 다음과 같은 핵심 설계 원칙을 확인할 수 있었다.

1. 메타데이터 저장을 통한 최적화

• 리스트의 길이(ob_size)를 미리 저장하여 len() 호출 시 O(1) 성능 보장
• 딕셔너리의 사용 중인 항목 수(ma_used)를 관리하여 빠른 크기 확인
• 참조 카운트(ob_refcnt)를 통한 효율적인 메모리 관리

2. Over-Allocation 전략

• 리스트 append() 시 약 12.5% 추가 공간을 미리 할당
• 잦은 메모리 재할당을 피하여 분할상환 O(1) 성능 달성
• 메모리와 성능 사이의 균형 있는 트레이드오프

3. 타입별 최적화

• 각 타입마다 최적화된 연산 구현 (예: list_length(), dict_get())
• 타입 객체(ob_type)를 통한 다형성 지원
• C 레벨 구현으로 순수 Python보다 10-100배 빠른 성능

4. 해시 테이블 활용

• 딕셔너리와 세트에서 평균 O(1) 검색/삽입/삭제 제공
• Python의 고성능 데이터 처리 능력의 핵심

🚀 성능 최적화를 위한 가이드

적절한 자료구조 선택

• 빈번한 검색: 리스트 → 세트 또는 딕셔너리
• 양쪽 끝 삽입/삭제: 리스트 → collections.deque
• 순서 유지 + 빠른 검색: 리스트 + 세트 → dict (Python 3.7+)
• 불변 시퀀스: 리스트 → 튜플 (메모리 효율)

시간 복잡도 인지

• in 연산자: 리스트 O(n) vs 세트 O(1)
• 문자열 연결: + 연산 O(n²) vs join() O(n)
• 정렬: 미리 정렬된 데이터 유지 vs 매번 정렬

CPython 구현 이해의 가치

• 왜 특정 연산이 느린지 이해하고 대안 찾기
• 프로파일링 결과를 해석하는 통찰력 확보
• 더 효율적인 알고리즘 설계 능력 향상

Python의 철학 - "배터리 포함(Batteries Included)"

CPython은 다양한 내장 함수와 최적화된 자료구조를 제공하여 개발자가 효율적인 코드를 쉽게 작성할 수 있도록 도와준다. len(), append(), get() 같은 간단한 함수 뒤에는 수십 년간 축적된 최적화 기술과 설계 철학이 담겨 있다고 한다..!

Python의 아름다움은 단순함에 있지만, 그 단순함 뒤에는 복잡하고 정교한 구현이 숨어 있었다. CPython 소스 코드를 직접 읽어보는 것은 Python을 더 깊이 이해하고, 더 나은 프로그래머가 되어보자!!!

import this  # The Zen of Python

# "Simple is better than complex."
# "복잡한 것보다 단순한 것이 낫다."

# 하지만 단순함을 구현하기 위해서는
# 때로는 복잡한 내부 구조가 필요하다.

+

CPython의 내장 함수 구현을 이해함으로써, 우리는 Python 코드를 작성할 때 더 현명한 선택을 할 수 있고, 성능 문제를 진단하고 해결하는 능력을 키울 수 있습니다. 이것이 바로 "어떻게 작동하는가"를 이해하는 것의 가치입니다.

면접 특강 때 커피챗을 통해 위에 말을 실제로 해주셨고 이를 바탕으로 글을 작성했다 ㅎㅎ..
정말 많은 얘기를 통해 여러 인사이트를 얻었고, 화려하고 트렌디한 기술보단 기술의 원천(源泉), 근본에 대해 알고 접근하면 그 흐름이 눈에 보인다고 말씀하신게 아직도 기억에 남는다.

좋은 말씀 감사합니다. 김익수 멘토님!