V8의 Sea of Nodes 탈출기 — 왜 우아한 이론이 실전에서 무너졌는가

컴파일러 이론에서 Sea of Nodes는 한때 혁신의 상징이었다. 데이터 의존성만 있는 연산은 실행 순서에 묶이지 않고 그래프 위를 자유롭게 떠다니며, 이론적으로는 더 많은 최적화 기회를 열어준다. V8 팀도 그 가능성을 믿고 Turbofan 컴파일러에 이 구조를 채택했다. 그리고 10년 가까이 사용한 끝에, 팀은 이것을 버렸다.

---

Sea of Nodes가 뭔가

Sea of Nodes(이하 SoN)는 프로그램을 표현하는 중간 표현(IR) 방식이다. 전통적인 컴파일러는 코드를 기본 블록(basic block) 단위로 묶고, 블록 간 제어 흐름을 명시적으로 연결한다. 반면 SoN은 모든 것을 노드로 분해하고, 노드 사이에 세 종류의 엣지를 연결한다.

[💡 잠깐! 이 용어는?] 기본 블록(basic block): 분기가 없는 연속된 명령 집합이다. 블록 중간에서 점프가 일어나지 않고, 시작부터 끝까지 순서대로 실행된다. 전통적인 CFG(Control Flow Graph)의 기본 단위다.

세 종류의 엣지는 각각 역할이 다르다.

• Value edges: 데이터 의존성. a + b에서 a와 b가 + 노드를 향하는 것.
• Control edges: 제어 흐름. if/else, 루프, 함수 호출 순서.
• Effect edges: 메모리 연산 순서. 같은 주소를 읽고 쓰는 연산이 순서를 유지하도록 묶어준다.

핵심은 value edges만 있는 순수 연산은 실행 위치가 고정되지 않는다는 것이다. 이를 "floating"이라 부른다. 그래프 스케줄러가 최적의 위치를 찾아서 배치하면 된다는 발상이다. 레고 블록을 조립할 때 완성된 형태가 아니라 느슨하게 연결된 부품 상태로 가지고 다니다가, 필요할 때 최적의 자리에 끼워 넣는 것과 비슷하다.

---

이론과 실전의 간격

SoN의 매력은 분명했다. 순수 연산이 자유롭게 이동하면 루프 불변 코드를 밖으로 끌어내거나, 불필요한 중복 계산을 제거하기가 쉬워진다. 그래서 Cliff Click과 Michael Paleczny가 1995년에 이 아이디어를 발표했을 때, 컴파일러 연구자들은 주목했다.

그런데 V8 팀이 Turbofan을 실제로 운영하면서 발견한 것은 달랐다. 이론이 아름다울수록 실전의 마찰이 더 크게 느껴졌다.

1. JS에서 순수 연산은 생각보다 드물다

JavaScript는 동적 타입 언어다. a + b처럼 단순해 보이는 연산도 런타임에 타입 검사가 필요하다. 숫자인지, 문자열인지, 객체인지를 먼저 확인해야 실제 연산을 수행할 수 있다. 배열 접근에는 범위 검사가 붙는다. 힙 객체 접근에는 맵(hidden class) 확인이 따라온다.

이 말은 대부분의 연산에 control 또는 effect 입력이 필요하다는 뜻이다. floating할 수 있는 순수 연산이 드물다. SoN의 핵심 이점인 자유로운 노드 이동이 JS에서는 제한적으로만 작동한다.

2. 복잡성 비용이 비대칭적이다

Turbofan 팀이 분석한 수치가 있다. 노드를 20번 방문할 때마다 실제 변경은 1번 일어난다. 대부분의 방문은 "이 노드는 지금 바꿀 필요 없다"는 결론으로 끝난다. 그럼에도 방문 자체는 해야 한다. 옳은 방향인지 확인하려면 일단 찾아가야 하기 때문이다.

이건 마치 창고 정리를 할 때, 물건 하나를 원래 자리에 두기로 결정하더라도 들었다 놓는 행동 자체는 반드시 해야 하는 것과 같다. 20번 들었다가 1번만 자리를 바꾼다면, 나머지 19번의 노력은 순 낭비다.

3. 캐시를 죽인다

[💡 잠깐! 이 용어는?] L1 dcache: CPU가 데이터를 읽을 때 가장 먼저 확인하는 1차 데이터 캐시다. 용량이 작고(수십 KB) 속도가 빠르다. 여기서 데이터를 찾지 못하면 메인 메모리까지 가야 해서 수십~수백 배 느려진다.

SoN의 그래프 노드들은 메모리 상에 흩어져 있다. 서로 연결되어 있지만 물리적으로 인접하지 않다. 노드를 따라가려면 포인터를 타야 하고, 포인터를 탈 때마다 캐시 미스가 발생할 가능성이 높다.

실측 결과는 뚜렷했다. CFG 기반 방식 대비 L1 dcache miss가 평균 3배, 최대 7배까지 많았다. 컴파일 시간만 5%가 이 캐시 미스로 날아갔다. 이론적으로 더 나은 최적화를 찾으러 돌아다니는 동안, CPU 캐시는 계속 비워지고 채워지는 낭비가 반복됐다.

4. 스케줄러가 자멸했다

floating 노드를 실제 코드로 배치하는 스케줄러도 문제였다. 처음엔 division(나눗셈) 연산 2개를 1개로 합치는 최적화를 구현했다. 중복 제거는 당연히 좋은 일이다.

그런데 이 최적화가 다른 패스와 충돌하자, 팀은 합쳤던 division을 다시 2개로 복제하는 로직을 추가했다. 합치고, 다시 나누고. 이 순환은 구조적 문제를 증상 치료로 덮은 결과였다. 코드베이스에 반대 방향의 로직이 공존하면서, 수정 하나가 어디서 무엇을 깨뜨릴지 예측하기 어려워졌다.

5. 그래프가 읽히지 않는다

현실적인 이유도 있다. 복잡한 함수의 SoN 그래프를 시각화하면 노드와 엣지가 얽혀서 "messy soup of nodes"가 된다. 엔지니어가 최적화 패스를 디버깅하거나 새 기능을 추가하려면, 이 국수 그릇 같은 그래프에서 원하는 흐름을 추적해야 한다.

[💡 잠깐! 이 용어는?] 최적화 패스(optimization pass): 컴파일러가 IR을 반복적으로 순회하며 코드를 개선하는 단계다. 인라이닝, 상수 폴딩, 루프 최적화 등 각 최적화마다 별도의 패스가 존재한다.

코드 가독성이 유지보수성에 직결되듯, IR 가독성도 컴파일러 개발 속도에 직결된다. 이론적으로 더 강력한 도구가 실제로는 팀의 속도를 늦추고 있었다.

6. 타입 정보가 흐름을 따라가지 못한다

마지막으로 근본적인 한계가 있었다. CheckedAdd 같은 연산은 순수 연산이라 floating된다. 그런데 이 연산이 어느 제어 흐름 경로에 속하는지 모르면, 이미 다른 경로에서 같은 검사가 수행됐는지 알 수 없다. 중복 타입 검사를 제거하려면 제어 흐름 정보가 필요한데, floating 연산은 정의상 제어 흐름에 고정되어 있지 않다.

이건 구조적 모순이다. SoN이 최적화를 위해 선택한 자유로움이, 또 다른 최적화를 막는 장벽이 됐다.

---

Turboshaft — 새 컴파일러의 선택

V8 팀이 선택한 대안은 전통으로의 회귀다. Turboshaft는 CFG 기반 IR을 사용한다. 기본 블록이 있고, 블록 내 명령의 순서가 명시적으로 정해진다.

항목	Turbofan (SoN)	Turboshaft (CFG)
IR 구조	그래프 노드, floating	기본 블록 + 명시적 순서
제어 흐름	control edges로 암묵적	블록 분기로 명시적
메모리 지역성	낮음 (포인터 추적)	높음 (순차 배열)
타입 정보 추적	제어 흐름과 분리	제어 흐름에 통합
디버깅 용이성	낮음	높음

결과는 측정값으로 드러났다.

• 컴파일 속도 약 2배 향상
• Load elimination 패스: 대형 그래프에서 최대 190배 빠름
• 메모리 사용량 대폭 감소

190배는 타이포가 아니다. SoN에서는 이 패스가 그래프 전체를 반복 순회하며 각 노드의 메모리 상태를 추적해야 했는데, CFG에서는 블록 단위로 처리하면서 불필요한 순회가 사라졌다.

마이그레이션은 단계적으로 진행됐다. JavaScript 백엔드는 완전히 Turboshaft로 전환됐고, WebAssembly 파이프라인도 Turboshaft를 사용한다. 빌트인(built-ins)은 점진적으로 교체 중이다.

---

정리

• Sea of Nodes는 이론적으로 강력하지만, JavaScript의 동적 타입 특성상 순수 연산이 드물어 실익이 제한됐다
• 캐시 비친화적 메모리 구조가 컴파일 시간의 5%를 잠식했고, 최악의 경우 L1 dcache miss가 7배에 달했다
• 이론적 자유로움(floating)이 타입 정보 추적이라는 실용적 최적화를 막는 구조적 모순을 만들었다
• Turboshaft는 전통적 CFG로 돌아가면서 컴파일 속도 2배, load elimination 최대 190배 향상을 달성했다
• "우아한 이론"보다 "측정 가능한 개선"이 프로덕션 컴파일러의 기준임을 V8의 전환이 보여준다

---

참고:

• V8 Blog — Land ahoy: leaving the Sea of Nodes: https://v8.dev/blog/leaving-the-sea-of-nodes