1.1 복잡도 분석과 벤치마크 — 점근 표기가 말하지 않는 것

점근 표기는 후보를 거르는 도구이고, 후보 사이의 선택은 실측이 결정한다. 이 문서는 점근 표기가 보장하는 것과 보장하지 않는 것을 구분하고, 같은 O(n)이 실측에서 147배 갈리는 것을 재현한 뒤, 그 실측 자체를 신뢰할 수 있게 만드는 벤치마크 방법론을 세운다. 여기서 세운 방법론은 챕터 1의 나머지 문서와 실습 과제가 그대로 사용한다.

학습 목표

• 점근 표기가 보장하는 것(성장률)과 보장하지 않는 것(상수 인자, 메모리 접근 비용)을 구분해 설명한다.
• 최악·평균·amortized 복잡도의 차이를 동적 배열과 해시 테이블 사례로 계산하고, amortized 보장이 지연 시간 백분위에 남기는 함정을 식별한다.
• 같은 점근 복잡도의 코드가 실측에서 수십 배 갈리는 사례를 재현하고 원인을 메모리 접근 패턴으로 설명한다.
• JIT 워밍업, 죽은 코드 제거, GC 노이즈를 통제한 마이크로벤치마크를 작성하고, 신뢰할 수 없는 벤치마크를 판별한다.

배경: 왜 이것이 존재하는가

알고리즘을 비교하려면 기계와 언어에 독립적인 기준이 필요하다. 1960~70년대에 정립된 방법은 계산을 RAM 모델(random-access machine) 위에 올려놓는 것이었다. 이 모델은 두 가지를 가정한다. 모든 기본 연산(산술, 비교, 메모리 접근)은 같은 상수 시간이 걸리고, 어떤 메모리 주소든 접근 비용이 균일하다. 이 가정 위에서 연산 횟수를 입력 크기 n의 함수로 세고, 성장률만 남기고 나머지를 버린 것이 점근 표기(asymptotic notation)다.

이 추상화는 대단히 성공적이었다. 언어, 컴파일러, CPU가 바뀌어도 "이진 탐색은 선형 탐색보다 빠르게 확장된다"는 결론은 유지된다. 문제는 RAM 모델의 두 번째 가정이 현대 하드웨어에서 무너졌다는 점이다. L1 캐시 접근과 주 메모리 접근은 대략 두 자릿수 배율로 차이가 난다. 즉 "메모리 접근 1회"의 비용이 접근 패턴에 따라 백 배 가까이 달라지는데, 점근 표기는 이 차이를 정의상 볼 수 없다. 상수 인자로 취급해 버렸기 때문이다.

그래서 점근 표기와 실측은 서로를 대체하지 못한다. 점근 분석은 n이 커질 때 살아남을 수 없는 후보를 걸러내고, 실측은 살아남은 후보 사이에서 실제 환경의 승자를 가린다. 이 문서의 목표는 두 도구를 각자의 한계 안에서 정확하게 쓰는 것이다.

핵심 개념

점근 표기의 정확한 의미

f(n) = O(g(n))은 "충분히 큰 n에 대해 f가 c·g(n)을 넘지 않는 상수 c가 존재한다"는 뜻이다. 정의에서 바로 따라오는 성질 세 가지가 실무 판단의 근거가 된다.

1. 상수 인자는 정의상 버려진다. 2n도 200n도 똑같이 O(n)이다. 두 구현의 점근 복잡도가 같다는 말은 "n을 키웠을 때 비슷하게 확장된다"는 뜻이지 "비슷하게 빠르다"는 뜻이 아니다.
2. 낮은 차수 항도 버려진다. n² + 1000n은 O(n²)이다. n이 작은 구간에서는 버려진 1000n이 지배할 수 있다.
3. 상한(upper bound)일 뿐이다. O(n²)인 알고리즘은 O(n³)이기도 하다. 성장률을 위아래로 조이는 표기는 Θ(theta), 하한만 말하는 표기는 Ω(omega)다. 관행적으로 O를 Θ의 의미로 쓰는 경우가 많지만, 문헌을 읽을 때는 구분해야 한다.

자주 섞이는 두 축을 분리해 두자. O/Θ/Ω는 함수의 성장률에 대한 표기이고, 최악·평균·최선은 입력에 대한 구분이다. "퀵 정렬은 O(n log n)"이라는 문장은 이 두 축을 뭉갠 것이다. 정확히 말하면 퀵 정렬의 평균 실행 시간이 Θ(n log n)이고, 최악(이미 정렬된 입력에 첫 원소 피벗 같은 경우)은 Θ(n²)다. 최악과 평균 중 어느 쪽이 판단 기준이 되어야 하는지는 상황이 정한다. p99 지연 시간에 SLO가 걸려 있다면 평균이 아니라 최악과 분포를 봐야 한다.

amortized 분석 — 동적 배열은 왜 push가 O(1)인가

동적 배열(dynamic array)은 원소 수(length)보다 큰 저장 공간(capacity)을 미리 잡아 두고, 공간이 차면 더 큰 공간을 할당해 전체를 복사한다. 재할당이 일어나는 push 한 번은 O(n)이다. 그런데도 push를 O(1)이라 부르는 근거가 amortized(분할 상환) 분석이다.

성장 계수(growth factor)를 2라고 하자. 빈 배열에서 n번 push하면 재할당은 용량 1, 2, 4, …, n/2를 넘길 때마다 일어나고, 복사되는 원소의 총합은 1 + 2 + 4 + … + n/2 < n이다. n번의 push에 복사 비용 n을 나눠 지우면 push 한 번당 평균 O(1) — 이것이 amortized O(1)의 의미다. 어떤 입력 분포를 가정한 평균이 아니라, 최악의 실행 경로에서도 성립하는 총비용의 보장이라는 점에서 평균 복잡도와 다르다.

성장 계수가 1.5면 재할당은 더 잦아지지만 낭비되는 공간이 줄어든다. 총 복사량은 여전히 O(n)이라 amortized O(1)은 유지된다. 시간과 공간 낭비 사이의 이 트레이드오프는 1.2 자료구조의 메모리 배치에서 런타임별 실제 성장 정책과 함께 다룬다.

amortized 보장에는 함정이 하나 있다. 총비용을 보장할 뿐 개별 연산의 비용 스파이크는 그대로 남는다. 수백만 원소를 담은 배열의 재할당 한 번, 해시 테이블의 리사이징 한 번은 밀리초 단위 지연을 만들 수 있고, 이것이 지연 시간 백분위(p99)에 그대로 찍힌다. 처리량 관점에서는 O(1)이지만 꼬리 지연 관점에서는 아니다. 스파이크가 문제가 되는 경로에서는 용량 사전 할당이나 점진적(incremental) 리사이징이 대응책이 된다.

해시 테이블의 "평균 O(1)"은 또 다른 종류의 보장이다. 이것은 해시 함수가 키를 고르게 분산시킨다는 확률적 가정 위의 평균이고, 가정이 깨지면(모든 키가 한 버킷으로 몰리면) 최악 O(n)으로 퇴화한다. 이 퇴화를 의도적으로 일으키는 공격이 존재하는데, 1.2의 해시 테이블 절에서 다룬다.

실측 1 — 같은 O(n), 147배의 차이

배열 순회와 연결 리스트 순회는 둘 다 원소당 한 번씩 방문하는 Θ(n)이다. 다음 코드로 세 가지 경우를 측정한다: 배열, 노드를 생성한 순서대로 연결한 리스트, 노드를 무작위 순서로 연결한 리스트. 측정 하네스(harness.mjs)는 아래 벤치마크 방법론 절의 것을 같은 디렉터리에 두고 실행한다.

// traverse.mjs — node traverse.mjs 로 실행 (harness.mjs가 같은 디렉터리에 필요)
import { bench, shuffle } from './harness.mjs';

const N = 1_000_000;

const arr = [];
for (let i = 0; i < N; i++) arr.push(i);

// 연결 리스트 A: 노드 생성 순서 = 순회 순서
function makeSequentialList() {
  const head = { value: 0, next: null };
  let tail = head;
  for (let i = 1; i < N; i++) {
    tail.next = { value: i, next: null };
    tail = tail.next;
  }
  return head;
}

// 연결 리스트 B: 노드를 모두 만든 뒤 무작위 순서로 연결
function makeShuffledList() {
  const nodes = [];
  for (let i = 0; i < N; i++) nodes.push({ value: i, next: null });
  shuffle(nodes);
  for (let i = 0; i < N - 1; i++) nodes[i].next = nodes[i + 1];
  nodes[N - 1].next = null;
  return nodes[0];
}

const seqList = makeSequentialList();
const shufList = makeShuffledList();
let sink = 0; // 죽은 코드 제거 방지용

bench('array sum          ', () => {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) sum += arr[i];
  sink = sum;
});
bench('list sum (seq)     ', () => {
  let sum = 0;
  for (let node = seqList; node !== null; node = node.next) sum += node.value;
  sink = sum;
});
bench('list sum (shuffled)', () => {
  let sum = 0;
  for (let node = shufList; node !== null; node = node.next) sum += node.value;
  sink = sum;
});
console.log('checksum', sink);

Node.js v24.14.0(V8 13.6), Apple M5 Pro, macOS 26.5에서의 실측이다. 절대값은 환경에 따라 다르지만 배율의 구도는 재현된다.

측정 대상	중앙값	배열 대비
배열 순회	0.55 ms	1×
연결 리스트(생성 순서 연결)	1.00 ms	약 2×
연결 리스트(무작위 연결)	81.1 ms	약 147×

세 코드의 점근 복잡도는 같다. 차이는 전부 RAM 모델이 버린 "상수 인자" 안에 있다.

• 배열은 원소가 메모리에 연속으로 놓인다. 순차 접근은 캐시 라인 단위로 한꺼번에 올라오고, 하드웨어 프리페처가 다음 접근을 예측해 미리 가져온다.
• 생성 순서대로 연결한 리스트는 노드들이 힙에 대략 연속으로 할당되어, 포인터를 따라가도 실제 메모리 접근은 순차에 가깝다. 그래서 2배 정도로 선방한다. 할당 순서까지 성능에 개입한다는 뜻이기도 하다. 실제 워크로드에서 리스트 노드는 오랜 시간에 걸쳐 흩어져 할당되므로, 무작위 연결 쪽이 현실에 가깝다.
• 무작위 연결 리스트는 다음 노드 주소를 읽기 전까지 어디로 갈지 알 수 없고(포인터 추적, pointer chasing), 접근 대상이 힙 전체에 흩어져 있어 접근마다 캐시 미스 가능성이 높다.

캐시 계층이 왜 이런 배율을 만드는지(캐시 라인 크기, 프리페처, TLB)는 7.2 메모리 계층과 캐시 일관성에서 하드웨어 메커니즘으로 다룬다. 챕터 1에서 필요한 것은 판단 기준이다: 접근 패턴이 순차인 자료구조와 포인터 추적인 자료구조는 점근 표기가 같아도 다른 부류로 취급해야 한다.

실측 2 — 최악 복잡도가 같아도 입력에 적응하는 알고리즘

점근 표기가 놓치는 또 하나의 축은 입력의 기존 구조다. V8의 Array.prototype.sort는 Timsort(팀소트)를 사용한다. Timsort는 이미 정렬된 구간(run)을 감지해 활용하는 적응형(adaptive) 정렬로, 최악은 O(n log n)이지만 이미 정렬된 입력에는 O(n)으로 동작한다.

// sort-adaptive.mjs — node sort-adaptive.mjs 로 실행
import { bench, shuffle } from './harness.mjs';

const N = 1_000_000;
const sorted = Array.from({ length: N }, (_, i) => i);
const reversed = sorted.slice().reverse();
const random = shuffle(sorted.slice());
const nearly = sorted.slice();
for (let i = 0; i < N / 100; i++) { // 원소의 1%만 무작위로 교환
  const a = Math.floor(Math.random() * N);
  const b = Math.floor(Math.random() * N);
  [nearly[a], nearly[b]] = [nearly[b], nearly[a]];
}

const cmp = (a, b) => a - b;
bench('sort sorted  ', () => sorted.slice().sort(cmp));
bench('sort nearly  ', () => nearly.slice().sort(cmp));
bench('sort reversed', () => reversed.slice().sort(cmp));
bench('sort random  ', () => random.slice().sort(cmp));

같은 환경에서의 결과다.

입력	중앙값	정렬된 입력 대비
이미 정렬됨	6.8 ms	1×
역순 정렬	7.1 ms	1×
1% 교란	25.0 ms	3.7×
완전 무작위	143.0 ms	21×

네 경우 모두 같은 알고리즘, 같은 O(n log n) 상한이다. 역순 입력이 빠른 이유는 Timsort가 감소 run을 감지해 통째로 뒤집기 때문이다. 실무 데이터는 완전 무작위인 경우가 드물다 — 타임스탬프순으로 쌓인 로그, 거의 정렬된 상태에서 소수만 갱신된 목록이 흔하다. "정렬은 O(n log n)이니 어떤 입력이든 비용이 같다"는 가정으로 용량을 산정하면 한쪽 방향으로 크게 틀린다.

같은 원리로, 최악 복잡도가 더 나쁜 알고리즘이 실전에서 선택되기도 한다. 작은 n에서는 Θ(n²)인 삽입 정렬이 상수 인자가 작고 캐시 친화적이라 더 빠르므로, Timsort를 포함한 하이브리드 정렬들은 작은 구간을 삽입 정렬로 처리한다.

신뢰할 수 있는 벤치마크 — 워밍업, 죽은 코드, 노이즈

위 실측이 의미를 가지려면 측정 자체가 신뢰할 수 있어야 한다. JIT 런타임 위의 마이크로벤치마크는 다음 함정들을 통제해야 한다.

1. 실행 티어(tiering) — 무엇을 측정하고 있는가. V8은 코드를 인터프리터(Ignition)로 실행하기 시작해, 뜨거워진 코드를 베이스라인 컴파일러(Sparkplug), 중간 최적화 컴파일러(Maglev), 최적화 컴파일러(TurboFan)로 점진적으로 승격시킨다. 워밍업 없이 첫 실행을 측정하면 인터프리터나 하위 티어의 성능을 측정하게 된다. 어느 쪽을 측정할지는 질문에 달렸다 — 자주 호출되는 핫 패스라면 최적화된 코드가, 한 번 실행되는 CLI 스크립트라면 첫 실행이 실제와 가깝다. 중요한 것은 자신이 어느 티어를 측정하는지 아는 것이다.

2. 죽은 코드 제거(dead code elimination, DCE). 결과를 아무 데도 쓰지 않는 계산은 최적화 컴파일러가 통째로 제거할 수 있다. 루프가 사라진 채 "0.0001ms"가 측정되면 알고리즘이 아니라 컴파일러의 제거 능력을 측정한 것이다. 결과를 외부 변수에 대입하거나 출력해서(위 코드의 sink) 계산이 관측 가능한 효과를 갖게 만든다.

3. 반복과 통계. 단발 측정은 GC, OS 스케줄링, CPU 클럭 변동(온도, 전원 정책)의 잡음에 오염된다. 여러 번 반복해 중앙값을 취한다. 평균은 꼬리 잡음(측정 중 GC 한 번)에 끌려가므로 중앙값보다 나쁜 대표값이다. 최소값·최대값을 함께 기록하면 잡음의 크기가 보인다.

4. GC 노이즈. 측정 루프 안에서 할당하면 GC 비용이 측정에 섞인다. 자료구조 자체를 측정할 때는 준비 단계에서 할당을 끝내고 측정 루프는 읽기만 하게 설계한다. 할당 비용 자체가 측정 대상이라면 반대로 그것을 명시한다.

5. 환경 명시. CPU, OS, 런타임 버전을 결과와 함께 기록한다. 이 문서의 수치가 "Node.js v24.14.0, Apple M5 Pro"를 달고 있는 이유다. 환경이 다르면 배율은 달라질 수 있고, 결론은 배율의 구도(순차 ≫ 포인터 추적)로 읽어야 한다.

이 문서의 모든 측정에 사용한 하네스다.

// harness.mjs — 챕터 1 공용 측정 하네스
export function bench(name, fn, { warmup = 3, runs = 10 } = {}) {
  for (let i = 0; i < warmup; i++) fn(); // JIT 티어 승격 유도
  const samples = [];
  for (let i = 0; i < runs; i++) {
    const start = performance.now();
    fn();
    samples.push(performance.now() - start);
  }
  samples.sort((a, b) => a - b);
  const median = samples[Math.floor(samples.length / 2)];
  console.log(
    `${name}: median ${median.toFixed(2)}ms ` +
    `(min ${samples[0].toFixed(2)} / max ${samples[samples.length - 1].toFixed(2)})`,
  );
  return median;
}

export function shuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

이 하네스는 교육용 최소 구현이다. 실무 측정에서는 통계 처리와 최적화 방어를 갖춘 러너(mitata, tinybench 등)를 쓰되, 러너가 위 함정들을 어떻게 다루는지 이해하고 쓰는 것이 전제다. V8 내부 상태를 직접 확인해야 할 때는 node --allow-natives-syntax로 열리는 V8 내장 함수(%DebugPrint 등)를 쓸 수 있는데, 1.2에서 사용한다.

실무 관점

분석과 측정의 분업

실무 판단의 순서는 다음과 같다.

1. 점근 분석으로 후보를 거른다. n이 백만인데 Θ(n²) 알고리즘이면 실측할 필요도 없이 탈락이다. 이 단계에서 점근 표기는 빠르고 정확하다.
2. 살아남은 후보는 실제 데이터 분포로 실측한다. O(n log n) 대 O(n log n), 해시 대 트리 같은 대결은 상수 인자·캐시·입력 분포가 결정하므로 점근 분석이 답을 주지 못한다.
3. 결론에 환경과 조건을 붙인다. "이 데이터 크기, 이 접근 패턴, 이 런타임에서 A가 B보다 몇 배 빠르다"까지가 재사용 가능한 결론이다.

마이크로벤치마크가 거짓말하는 상황

• 측정 대상이 제거됨: 결과를 쓰지 않아 DCE로 사라진 루프. 비현실적으로 빠른 수치가 신호다.
• 티어 혼선: 워밍업 부족으로 인터프리터를 측정하거나, 반대로 벤치마크에서만 단형(monomorphic)으로 호출되어 실제 서비스의 다형(polymorphic) 호출부보다 유리하게 측정되는 경우.
• 비현실적 데이터: 완전 무작위 입력으로 정렬을 측정했는데 실제 데이터는 거의 정렬되어 있는 경우(위 실측 2에서 21배 차이).
• 수치의 시효: 몇 년 전 블로그의 벤치마크 결과는 당시 런타임의 구현 세부를 측정한 것이다. V8의 최적화 파이프라인은 계속 바뀌므로, 통념이 된 수치일수록 현재 버전에서 재검증해야 한다. 1.2에서 실제로 재현에 실패하는 통념을 하나 다룬다.

amortized 비용과 꼬리 지연

처리량(throughput) 목표라면 amortized O(1)로 충분하지만, 지연 시간(latency) 목표라면 스파이크의 존재 자체가 문제다. 요청 처리 경로 한가운데에서 수백만 원소짜리 배열이 재할당되거나 해시 테이블이 리사이징되면 그 요청 하나가 p99를 뚫는다. 크기를 예측할 수 있으면 사전 할당하고, 예측할 수 없으면 리사이징을 경로 밖으로 빼는 설계(사전 워밍업, 점진적 마이그레이션)를 검토한다.

정리

• 점근 표기는 RAM 모델 위에서 성장률만 남긴 추상화다. 기계 독립적 비교라는 목적에는 강력하지만, 상수 인자와 메모리 접근 비용의 불균일성은 정의상 보지 못한다.
• O/Θ/Ω는 성장률의 표기이고 최악·평균·최선은 입력의 구분이다. 두 축을 뭉개면 "퀵 정렬은 O(n log n)" 같은 부정확한 문장이 된다.
• amortized 분석은 최악 실행 경로의 총비용 보장이다. 개별 연산의 스파이크는 남아 있으므로 꼬리 지연 요구사항과는 별개로 판단한다.
• 같은 Θ(n) 순회가 메모리 접근 패턴에 따라 147배 갈리고, 같은 O(n log n) 정렬이 입력 순서에 따라 21배 갈린다. 점근 분석은 후보를 거르는 데 쓰고, 후보 간 선택은 실측으로 한다.
• 신뢰할 수 있는 마이크로벤치마크의 조건: 측정 티어 인지(워밍업), DCE 방지, 반복과 중앙값, GC 격리, 환경 명시.

확인 문제

1. 팀 동료가 "조회가 O(1)인 해시 맵을 두고 O(log n)인 정렬 배열 + 이진 탐색을 쓸 이유는 없다"고 주장한다. n이 수십 개 수준으로 작고 조회가 매우 빈번한 핫 패스라면 이 주장은 어디서 무너질 수 있는가? 판단에 필요한 실험도 설계해 보라.

정답과 해설

점근 표기는 상수 인자를 버린다. n이 작으면 O(1)과 O(log n)의 차이는 몇 번의 비교에 불과하고, 승부는 상수 인자가 가른다. 해시 조회는 해시 계산 → 버킷 인덱스 → (충돌 시) 키 비교의 고정 비용이 있고 버킷 접근은 캐시 미스가 될 수 있다. 정렬 배열은 연속 메모리라 전체가 캐시 몇 라인에 들어가며, log₂(64) = 6번의 비교로 끝난다. 작은 n에서는 심지어 선형 탐색이 이기는 경우도 있다(분기 예측과 순차 접근에 유리). 실험 설계: 실제 키 타입과 실제 n 분포로, 이 문서의 하네스처럼 워밍업·반복·중앙값을 갖춰 두 구현의 조회를 측정한다. n을 8, 64, 512, 4096으로 바꿔 가며 교차점을 찾으면 판단 기준이 생긴다.

2. 어떤 함수의 실행 시간을 측정했더니 첫 호출은 4ms, 이후 호출은 0.1ms가 나온다. 이 40배 차이의 원인으로 가능한 것을 두 가지 이상 들고, "서비스에서 이 함수는 요청마다 새로 로드되는 워커에서 한 번씩만 호출된다"는 조건이 붙으면 벤치마크를 어떻게 설계해야 하는지 설명하라.

정답과 해설

원인 후보: (1) JIT 티어링 — 첫 호출은 인터프리터(Ignition)로 실행되고 이후 호출은 상위 티어로 컴파일된 코드가 실행된다. (2) 캐시 — 첫 호출에서 코드와 데이터가 캐시·메모리에 올라와 이후 호출이 빨라진다. (3) 지연 초기화 — 첫 호출에서만 수행되는 준비 작업(모듈 로드, 테이블 구축)이 포함됐을 수 있다. 워커에서 한 번만 호출된다는 조건이 붙으면 실제 서비스가 겪는 비용은 4ms 쪽이다. 따라서 워밍업 후 측정하는 통상의 방식은 현실과 다른 값을 내놓는다. 프로세스를 새로 띄워 첫 호출만 측정하는 것을 반복하고 그 분포를 보고해야 한다. "무엇을 측정해야 하는가"가 벤치마크 설계의 첫 질문인 이유다.

3. push 기반으로 로그 버퍼를 쌓는 서비스에서 평균 지연은 문제없는데 p99 지연에 주기적인 스파이크가 관찰된다. 동적 배열의 amortized 분석과 연결해 원인 가설을 세우고, 검증 방법과 두 가지 이상의 대응책을 제시하라.

정답과 해설

가설: 버퍼가 성장 임계에 도달할 때마다 재할당 + 전체 복사가 일어나고, 그 순간의 push가 O(n)이 되어 p99에 찍힌다. amortized O(1)은 총비용의 보장일 뿐 개별 연산의 스파이크를 없애 주지 않는다. 검증: 스파이크 발생 시점의 버퍼 길이를 기록해 성장 임계(용량 경계)와 일치하는지 확인하거나, push마다 소요 시간을 기록해 스파이크 간격이 기하급수적으로 벌어지는지(용량이 배수로 늘면 재할당 간격도 배수로 늘어난다) 본다. 대응: (1) 예상 최대 크기로 사전 할당해 재할당 자체를 없앤다. (2) 고정 크기 청크의 연결(세그먼트 배열, 링 버퍼)로 바꿔 복사를 없앤다. (3) 버퍼 플러시 주기를 용량 임계 앞으로 당겨 성장이 일어나기 전에 비운다.

참고 자료

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms 4th ed. (2022) — 점근 표기의 형식 정의(3장), 최악·평균 분석, amortized 분석(16장)의 표준 서술.
• Tim Peters, listsort.txt — Timsort 설계 문서(1차 자료). run 감지와 galloping이 어떤 입력 구조를 활용하는지 설계자의 서술로 확인할 수 있다.
• V8 blog, Getting things sorted in V8 — V8이 Array.prototype.sort를 Timsort로 바꾼 배경과 구현. 작은 run에 이진 삽입 정렬을 쓰는 이유도 다룬다.
• V8 blog, Sparkplug, Maglev — V8 실행 티어의 구조. 워밍업이 측정에 왜 필요한지의 근거.
• Brendan Gregg, Systems Performance 2nd ed. (2020), 12장 Benchmarking — 능동적 벤치마킹 방법론과 "벤치마크는 거의 항상 틀렸다"는 관점의 근거.
• Jonas Bonér 외가 정리한 Latency Numbers Every Programmer Should Know — 캐시·메모리·디스크·네트워크 접근 비용의 자릿수 감각. 연도별 변화도 볼 수 있다.
• Bjarne Stroustrup, GoingNative 2012 키노트 중 Why you should avoid Linked Lists — 배열 대 연결 리스트 실측의 고전. 1.2에서 재현한다.