이 글은 2021년에 기고한 옛 글을 들고온 것 입니다.
GPT에 따르면 Python3.11에 개선이 됐긴 했다지만 여전히 영향이 있을것 같고, 다른데서는 이 내용을 다룬곳을 없어서 들고 왔습니다.

TL;DR

파이썬은 함수·변수를 선언할 때 __dict__에 Hashmap 형태로 저장한다.

이때, 해시맵의 키 충돌 (bucket collision)이 발생하면 probe에 조금 더 걸려서 "느려 질 수 있다". 그래서 "함수 이름을 바꿨더니 함수의 실행 속도가 빨라졌어요" 또는 "변수 이름을 바꿨더니 변수의 실행 속도가 빨라졌어요"가 실제로 가능한 이야기 이다.

 

과거 있었던 일

21년도에 알고리즘 스터디에 참여했었다. 그 때 조원 중 한분이 완전 같은 코드인데 어떤 코드는 시간 제한에 합격하고, 어떤 코드는 시간 제한에 지나쳐버린다라는 말을 했었다. 그래서 다들 실험해 봤더니 "함수명에 따라서 실행 시간이 차이가 났다"는 것을 확인 할 수 있었다.

cpython의 바이트 코드를 디컴파일 해보고, 몇시간 정도 코드 호출 흐름을 cpython 코드로서 직접 분석해 보니 HashMap Collision이 매우 의심됐다. 코드를 수 회 재제출 해도 똑같은 결과가 나왔다. 어차피 input도 매번 동일하고 통제된 환경임에도 현상이 발생한 것이다.

알고리즘 문제 특성상 함수를 굉장히 많이 호출하고 사용한다. 빡빡하게 시간 제한이 맞춰저있다 보니, 해시 충돌로 인해 조금의 실행 시간 차이가 발생해서 실패가 발생한 사례가 생긴 것이다!

실제 현실에서는 함수명 충돌에 따른 시간 차이가 미미한 수준이다. 하지만, 이 사례를 통해 Python의 내부 구조를 한번 보도록 하자. 다들 파이썬을 쓰기만 하지, 내부적으로는 어떻게 도는지 잘 모르지 않는가!

그 정도로 성능에 집착할 정도면 파이썬 말고 다른걸 쓰던가, 내부 구조 최적화를 하는게 맞다

Python의 함수

아래는 Python에서 간단하게 함수를 정의한 코드이다.

def test():
   return "esukmean";
	 
def test2():
   return "[email protected]";
	 
test();
test2();

이 코드는 인터프리터에 의해 아래처럼 컴파일 된다:

# Compilation provided by Compiler Explorer at https://godbolt.org/
  0           RESUME                   0

  1           LOAD_CONST               0 (<code object test at 0x59f23edb21e0, file "example.py", line 1>)
              MAKE_FUNCTION
              STORE_NAME               0 (test)

  4           LOAD_CONST               1 (<code object test2 at 0x59f23edb0f30, file "example.py", line 4>)
              MAKE_FUNCTION
              STORE_NAME               1 (test2)

  7           LOAD_NAME                0 (test)
              PUSH_NULL
              CALL                     0
              POP_TOP

  8           LOAD_NAME                1 (test2)
              PUSH_NULL
              CALL                     0
              POP_TOP
              LOAD_CONST               2 (None)
              RETURN_VALUE

Disassembly of <code object test at 0x59f23edb21e0, file "example.py", line 1>:
  1           RESUME                   0

  2           LOAD_CONST               0 ('esukmean')
              RETURN_VALUE

Disassembly of <code object test2 at 0x59f23edb0f30, file "example.py", line 4>:
  4           RESUME                   0

  5           LOAD_CONST               0 ('[email protected]')
              RETURN_VALUE

처음보면 이해하기 어려울 수 있다. 하지만 대충 읽어보면

• 1번째 줄에서 함수를 만들고, 3번째 줄에서 함수명으로 저장한다. (test)
• 4번째 줄에서 함수를 만들고, 6번째 줄에서 함수명으로 저장한다. (test2)
• 7번째 줄에서 test 라는것을 꺼내와서 실행(CALL) 한다.
• 8번째 줄에서 test2 라는것을 꺼내와서 실행(CALL)한다.

변수를 선언·저장 하는것도 비슷하게 흘러간다.

>>> dis.dis('x=1')
  1           0 LOAD_CONST               0 (1)
              2 STORE_NAME               0 (x)
              4 LOAD_CONST               1 (None)
              6 RETURN_VALUE
>>> dis.dis('xyz=1')
  1           0 LOAD_CONST               0 (1)
              2 STORE_NAME               0 (xyz)
              4 LOAD_CONST               1 (None)
              6 RETURN_VALUE

그러면 이 함수·변수는 어디에 저장되나..?

아마 학부 시절에 간단한 인터프리터를 만들어봤다면 충분히 예측할 수 있다. (몰라도 큰 문제 없다.)

내부적으로는 Dict(HashMap) 같은데에 변수·함수를 저장하고 있을 것이다. 조금 과하게 이야기 하자면 Python에서 객체를 만드는것은 내부적으로 프로토타입을 거진 새로운 __dict__을 만드는 것에 지나지 않는다. 즉, 모든 클래스 인스턴스나 글로벌 환경은 사실 딕셔너리인 것이다!

이것을 잘 이해하면 closure의 environemnt capturing 같은 문제를 건들 수 있다.

cpython 기준으로 전역 변수는 globals()로 볼 수 있다. javascript의 window에 해당하는 객체에 접근할 수 있다. 그러면 이 안에 len()과 같은 기본 함수가 있을것인데 이것은 __builtins.__dict__로 볼 수 있다. 다른 언어에 익숙하다면 lookup path에 (global context).__builtins__가 등록되어 있다고 생각하면 된다.

>>> globals()
{'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <class '_frozen_importlib.BuiltinImporter'>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>}

<module 'builtins' (built-in)>
>>> print(__builtins__)
<module 'builtins' (built-in)>

>>> print(__builtins__.__dict__)
{
  '__name__': 'builtins',
  'len': <built-in function len>,
  'print': <built-in function print>,
  'range': <class 'range'>,
  ...
}

각 클래스의 변수·데이터는 클래스.__dict__로 접근할 수 있다.

>>> class ESukmeanTest:
...    def test():
...      return "esm";
...
>>> ESukmeanTest.__dict__
mappingproxy({'__module__': '__main__', 'test': <function ESukmeanTest.test at 0x7f9522783240>, '__dict__': <attribute '__dict__' of 'ESukmeanTest' objects>, '__weakref__': <attribute '__weakref__' of 'ESukmeanTest' objects>, '__doc__': None})

그렇기에, 개념만으로 본다면 객체 ESukmeanTest는 프로토타입에 해당하고, ESukmeanTest()로 객체를 생성한다는 말은 프로토타입으로 찍어낸 dictionary 객체 인스턴스를 찍어내는것과 동일하다.

이 내용을 알면 IDE가 없는 환경에서도 어느정도 코딩이 가능해진다. 제한된 폐쇄망에서 급하게 파이썬 스크립트를 작성할 때는 __dict__를 조회해서 클래스 변수·함수를 찾아내는것 만큼 도움 되는게 없다.

요즘에도 성능 문제가 발생하는가?

_fast opcode

위에서 opcode disassembly를 했을때는 LOAD_NAME 또는 LOAD_GLOBAL 등의 opcode만을 사용했다. 이 기능들은 개념적으로 name lookup이 필요하다.

  7           LOAD_NAME                0 (test)
              PUSH_NULL
              CALL                     0
              POP_TOP

하지만, 파이썬에는 LOAD_FAST 같은 opcode가 있다. 이 opcode를 사용하면 배열에서 객체 접근을 할수 있다. 지역 변수의 경우에는 이름으로 접근하는 대신 index 번호로 접근한다. (컴파일 타임에 고정된다.) 이 경우 해시 함수를 돌릴 필요도, HashMap을 따라갈 필요도 없다. 배열에 직접 접근하기 때문에 빠른 속도는 물론, 진짜 상수 시간(O(1))을 보장 한다.

파이썬에서 배열 / list를 어떻게 생성·메모리 확장을 하는지 보는것도 cpython 코드를 통해 가능하다.

일반적인 함수 호출일 경우에도 cpython 인터프리터에서 자주 사용하는 함수에 대해서는 빠르게 호출 하도록 함수 호출 opcode를 런타임에 수정한다. 다만에 아직 필자가 알기로는 Javascript의 V8 엔진 처럼 타입별로 Quick-path 함수를 생성하거나 캐싱하는 기능은 없는것으로 알고있다. 아마 이것까지 들어온다면 파이썬의 JIT도 대단해 지지 않을까 생각한다.

Hash 함수의 개선

필자는 당해본 적이 없지만, Hash Collision을 유도해서 서비스 장애(DoS)를 유발하는 공격이 있었다. xxhash, sip 와 같이 주로 자료구조에서 쓰이는 함수들은 성능적으로나 해시 구조상으로나 DoS를 방어하게 구성되어 있다. 파이썬에서도 3.3부터는 SIP hash를 쓰게 되어 있다. 그렇기 때문에 실제로 성능 문제를 인식하기란 대단히 어려워졌다.

필자는 개발시 HashMap에 SIMD 버전의 xxhash를 자주 사용한다.

맨 위에서 언급한 문제는 이론상 아직도 가능한 부분이다. 하지만 가능성이 낮고(필자도 맨 위의 사례에서 딱 한번 관측해 봤다), 이제는 해시 함수에 랜덤시드가 들어가기 때문에 프로그램을 껏다켜면 문제가 사라질 것이다. 그러므로 Hash Collision을 걱정할 필요는 없다. 이론적으로는 아직도 가능할 수도 있겠지만, 이것을 걱정할 시간에 다른 코드 최적화·알고리즘 최적화를 하는게 더 유익하다.

하지만 파이썬에서 실제 어떻게 돌아가는지 구조를 알고 쓴다면 어디가서 있어보이는(?) 사람이 될 수 있다.

python의 특정 내부 동작이 어떻게 돌아가는지 보고 싶다면 cpython 소스를 보자. 필자도 몇번 까봤는데 PyObject 만 잘 따라가면 충분히 이해 할 수 있다.

 

번외: NodeJS는 어떤가?

python의 __dict__ 개념은 인터프리터라면 다들 들고 있을 수 밖에 없는 개념이다. 인터프리터가 아니더라도 Duck-Type (덕타이핑) 시스템을 쓰는 언어·구현체라면 있을 수 밖에 없는 개념이다. 언어의 발전 상태와 개발자의 의도에 따라 이런 메타 정보가 노출될 수도, 구현채 내부에서만 쓰일지가 달라진다.

node.js (javascript)도 global environment (context)가 노출되어 있다. 이것은 global (브라우저에선 window) 객체를 통해 접근 할 수 있다. 이쪽은 진짜 "프로토타이핑" 타입을 사용한다. 다만, 실행 중간중간에 lexical environment라는 환경 속에서 데이터가 보관되기도 한다. 이 데이터들은 직접적으로 볼 수 있는 방법이 없다.

Lexical Scope (Environment)를 이용해서 데이터를 은닉하는 것도 JS의 패턴 중 하나이다.

번외2 - 파이선의 dict 구현 설명

친절하게도 Python 코드에는 dictnotes.txt 라는게 있다. 실제 python의 dict 코드를 까지 않더라도 어느정도의 설계 방향을 볼 수 있다. __dict__ 또한 PyDictObject에 저장되는 바, 이 객체의 설명을 잠시 살펴보자. 아래는 ChatGPT-5.2가 번역해준 내용이다.

딕셔너리의 대표적인 사용 사례

키워드 인자 전달 (Passing keyword arguments)

• 보통 1~3개의 원소에 대해 읽기 1번, 쓰기 1번 정도 수행된다.
• 일반적인 파이썬 코드에서 매우 자주 등장한다

클래스 메서드 조회 (Class method lookup)

• 딕셔너리 크기는 다양하지만, 보통 8~16개 정도의 원소가 흔하다.
• 한 번 만들어진 뒤, 읽기(lookup)가 매우 많이 일어난다.
• 베이스 클래스를 사용하는 경우, 현재 클래스에서 여러 번 조회가 실패한 뒤 베이스 클래스 딕셔너리에서 다시 조회하는 패턴이 생긴다.

인스턴스 속성 조회 및 전역 변수 (Instance attribute lookup and Global variables)

• 딕셔너리 크기는 다양하며, 보통 4~10개의 원소가 흔하다.
• 읽기와 쓰기가 모두 자주 일어난다.

빌트인 (Builtins)

• 읽기가 매우 자주 일어난다.
• 거의 쓰기가 발생하지 않는다(변경 거의 없음).
• Python 3.3 기준, 약 150개의 interned string 키가 있다.
• 일부 키는 다른 키들보다 훨씬 자주 접근된다.

유일성 보장 / 중복 제거 (Uniquification)

• 딕셔너리 크기는 아무 크기나 될 수 있다.
• 작업 대부분은 딕셔너리를 만드는 과정에서 발생한다.
• 소수의 키 집합에 대해 반복적으로 쓰기(갱신)가 일어난다.
• 각 키는 한 번만 읽히는 경우가 많다.
• 어떤 경우에는 같은 키에 연속해서 두 번 접근하기도 한다

ESukmean 주: Count Sort 같은 중복 제거를 뜻함

멤버십 테스트 (Membership Testing)

• 딕셔너리 크기는 아무 크기나 될 수 있다.
• 한 번 만들어지면 거의 변하지 않는다.
• 각 키는 딱 한 번만 쓰이고, __contains__() 또는 has_key() 호출이 매우 많이 일어난다.
• 비슷한 접근 패턴이 치환용 딕셔너리에도 나타난다. (예: % 포매팅 연산자에 쓰이는 딕셔너리 등)

동적인 매핑 (Dynamic Mappings)

• 삭제와 추가/대체가 섞여서 계속 일어나는 패턴.
• 삭제된 자리에 만들어진 dummy 엔트리를 재사용할 수 있으면 성능에 큰 이득이 있다.

데이터 레이아웃

딕셔너리는 크게 세 부분으로 구성된다:

• dictobject 구조체 자체
• dict-keys 객체 (키와 해시를 저장)
• values 배열 (값을 저장)

(즉, 키/해시/값이 전부 한 덩어리에 박혀 있는 구조가 아니라, 키/해시 부분과 값 배열이 분리될 수 있는 구조라는 뜻.)

키와 데이터를 분리해서 얻는 이점

같은 클래스의 모든 인스턴스 딕셔너리는 하나의 키 테이블을 공유할 수 있게 되어, 메모리를 약 60% 정도 절약할 수 있다.

밀도/희소성(sparsity)과 순회 비용

딕셔너리를 더 “희소(sparse)”하게 만들면 해시 충돌은 줄어들지만, 대신 순회(iteration)와 키 리스트 생성이 느려진다. 이런 메서드들은 모든 슬롯을 순회해야 하기 때문이다.

딕셔너리 크기를 2배로 늘리면 아래 작업에서 겹치지 않는 메모리 접근이 2배로 늘어난다.

• keys(), items(), values(), __iter__(), iterkeys(), iteritems(), itervalues(), update()

ESukmean 주: dict의 밀도를 내리면(메모리 공간 = slot을 더주면) 순회시에 다 접근해야 하므로 느려진다.

해서, Python은 이런 모든 상황을 고려해서 안에 비어있는 항목의 수 (데이터 밀도) 등을 고려해서 bucket (=slot)의 크기를 결정한다.

dictobject.c 에서 참고할 것

아래는 실제 구현체의 주석에서 도움이 될만한것을 들고와봤다.

• dict의 기본 slot 갯수는 8임.

  pyDict_MINSIZE is the starting size for any new dict. 라인 참고

• dict이 2/3이상 채워지면 resize(공간 확장)을 함.

  To ensure the lookup algorithm terminates, there must be at least one Unused slot (NULL key) in the table. To avoid slowing down lookups on a near-full table, we resize the table when it's USABLE_FRACTION (currently two-thirds) full.

• dict는 "실제 사용중인 slot"의 3배만큼 slot이 커짐

  GROWTH_RATE. Growth rate upon hitting maximum load. Currently set to used*3.