T29 — 미션장부.한선 PSV 유니크최신·대기티켓찾기 스케일링 실측
개요
집사회 티켓 T29(레벨3): 500~5000행 합성 장부로_PSV파일유니크최신 / 대기티켓찾기의
"O(R)" 주장을 실측 검증. 대상=격리 사본 /Users/ef/crowny-deacon-scale-test
(원본 /Users/ef/crowny-deacon은 건드리지 않음 — _데이터루트만 격리 경로로 패치).방법
gen_ledger.pl로 합성 티켓.psv 생성(유니크ID=R/3, 나머지는 append 갱신으로 churn 유발 — 실서비스의 재기동 리플레이 패턴 재현)- R = 100,200,300,400,500,600,700,800,900,1000,2000,3000 (5000은 2분 타임아웃으로 미완주)
driver.한선이대기티켓찾기("소넷")+티켓목록()(=_PSV파일유니크최신) 호출- 컴파일(
hanseonc_high)은 1회만 수행해/tmp/driver.toau재사용,crownyc run만 R별로 반복 측정(/usr/bin/time -p)
결과 (real 초)
| R | 유니크수 | 실행시간(s) |
|---|---|---|
| 100 | 33 | 0.45 |
| 200 | 66 | 1.72 |
| 300 | 100 | 3.81 |
| 400 | 133 | 6.77 |
| 600 | 200 | 15.35 |
| 700 | 233 | 20.83 |
| 800 | 266 | 27.10 |
| 900 | 300 | 31.71 |
| 1000 | 333 | 31.69 |
| 2000 | 666 | 31.63 |
| 3000 | 860 | 31.91 |
| 5000 | (미완주) | >120 타임아웃 |
판정 — O(R) 주장 반증
R≤900 구간은 명백히 O(R²)에 가깝다, O(R)이 아니다. R 2배(100→200)에 시간
3.8배, R 3배(100→300)에 시간 8.5배, R 4배(100→400)에 시간 15배 — R² 배율(4배,
9배, 16배)에 근접한다. 코드 주석(미션장부.한선 76~110행)이 주장하는 "맵 기반
단일패스 O(R)"은 _PSV파일유니크최신엔 실제로 구현돼 있으나(맵넣어/맵꺼내
1회 스캔), 대기티켓찾기는 여전히 매 실행마다 티켓목록()(=_PSV파일유니크최신
전체)을 호출한 뒤 선형 재스캔하므로 논리적으로는 O(R)이어야 하는데, 실측은
전혀 O(R)로 나오지 않았다 — 병목은 알고리즘이 아니라 VM/런타임 레이어
(문자열 분리()/꺼내()/맵 연산의 상수항, 혹은 GC)에 있는 것으로 추정된다.
R=900~3000 구간은 실행시간이 31.6~31.9초로 완전히 정체(plateau) — R이 3000/900≈3.3배 늘어도 시간이 거의 불변. 이는 두 가지 중 하나를 시사:
- crownyc VM에 암묵적 스텝/시간 예산 캡이 있어 그 이상은 다른 코스트(디스크 I/O,
- 900 근방에서 병목 구조가 바뀌는 변곡점이 있음(예: 해시맵 내부 배열 리사이즈
R=5000은 2분 타임아웃 내 완주하지 못함 — 실서비스 규모(500~5000행)에서 현재 구현은 사실상 사용 불가능한 지연을 보인다.
결론
- O(R) 주장은 기각. 실측 곡선은 소구간 O(R²)에 가깝고, 중간 구간은 원인불명의
- 근본 원인은 알고리즘(맵 기반 단일패스는 코드상 맞음)이 아니라 VM 문자열/맵
분리()/꺼내()
가 진짜 O(1)/O(n)인지 VM 레벨 재확인 권고).
대기티켓찾기가 매 호출마다티켓목록()전체(유니크최신 재계산)를 다시 돌리는
관련 파일
- 대상 원본:
/Users/ef/crowny-deacon/한선씨/미션장부.한선 - 격리 사본:
/Users/ef/crowny-deacon-scale-test/(한선씨/미션장부.한선의_데이터루트만 격리 경로로 수정) - 합성 장부 생성기:
/Users/ef/crowny-deacon-scale-test/gen_ledger.pl - 드라이버:
/Users/ef/crowny-deacon-scale-test/driver.한선 - 합성 데이터:
/Users/ef/crowny-deacon-scale-test/data/티켓_{100..5000}.psv
잔여 이슈
- R=5000 완주 측정(타임아웃 연장 또는 배치 실행) 미완
- 900 근방 변곡점의 정확한 원인(해시맵 리사이즈 vs 배열 1023 캡) 미규명 — 프로파일링 필요
- VM 레벨(
crownyc.c) 문자열/맵 연산 실제 시간복잡도 재검증 필요