이미지 로딩 중...
AI Generated
2025. 11. 7. · 4 Views
캐시 친화적인 배열 vs 동적인 연결 리스트 완벽 가이드
배열과 연결 리스트의 메모리 구조부터 캐시 성능까지 실무 관점에서 비교 분석합니다. 초급 개발자도 쉽게 이해할 수 있도록 실제 코드와 성능 측정 예제를 통해 언제 어떤 자료구조를 선택해야 하는지 알려드립니다.
목차
- 배열의 메모리 구조와 캐시 친화성 - 연속된 메모리가 만드는 성능의 비밀
- 연결 리스트의 동적 구조 - 유연성과 메모리 오버헤드
- CPU 캐시의 동작 원리 - 공간 지역성과 시간 지역성
- 배열의 동적 확장 - 재할당 비용과 최적화
- 연결 리스트의 실전 활용 - LRU 캐시 구현
- 배열 기반 큐 vs 연결 리스트 기반 큐 - 실전 성능 비교
- 메모리 단편화와 할당 패턴 - 배열 vs 연결 리스트의 숨은 비용
- 벤치마크와 프로파일링 - 올바른 성능 측정 방법
1. 배열의 메모리 구조와 캐시 친화성 - 연속된 메모리가 만드는 성능의 비밀
시작하며
여러분이 수천 개의 사용자 데이터를 순회하면서 처리해야 하는 상황을 생각해보세요. 같은 로직인데도 어떤 자료구조를 쓰느냐에 따라 실행 시간이 2배, 심지어 10배까지 차이 날 수 있다는 사실, 알고 계셨나요?
이런 성능 차이는 단순히 알고리즘의 시간 복잡도 때문만은 아닙니다. 실제로는 CPU 캐시가 데이터를 얼마나 효율적으로 가져오느냐가 큰 영향을 미칩니다.
메모리에 접근하는 패턴이 캐시 친화적이지 않으면, 같은 O(n) 알고리즘이라도 수십 배 느려질 수 있습니다. 바로 이럴 때 배열의 메모리 구조를 이해하는 것이 중요합니다.
배열이 왜 "캐시 친화적"이라고 불리는지, 그리고 실무에서 어떻게 이 특성을 활용할 수 있는지 알아보겠습니다.
개요
간단히 말해서, 배열은 메모리상에서 연속된 공간에 데이터를 저장하는 자료구조입니다. [0번째 요소, 1번째 요소, 2번째 요소...]가 물리적으로 바로 옆에 붙어있는 형태죠.
왜 이게 중요할까요? CPU는 메모리에서 데이터를 가져올 때 한 번에 하나만 가져오는 게 아니라, 주변 데이터를 함께 캐시로 가져옵니다.
배열의 경우 다음에 접근할 데이터가 이미 캐시에 있을 확률이 높기 때문에, 메모리 접근 속도가 극적으로 빨라집니다. 예를 들어, 대량의 로그 데이터를 필터링하거나 통계를 계산하는 경우 배열을 사용하면 성능이 월등히 좋습니다.
전통적으로 자료구조 교육에서는 "배열은 인덱스 접근이 O(1)"이라고만 배웠다면, 이제는 "배열은 순차 접근 시 캐시 히트율이 높아 실제 성능이 훨씬 좋다"는 관점까지 이해해야 합니다. 배열의 핵심 특징은 세 가지입니다.
첫째, 연속된 메모리 할당으로 공간 지역성(spatial locality)이 뛰어나고, 둘째, 인덱스를 통한 직접 접근이 가능하며, 셋째, 크기가 고정되어 있거나 동적 확장 시 재할당이 필요합니다. 이러한 특징들이 실무에서 배열을 선택하는 주요 이유가 됩니다.
코드 예제
// 캐시 친화적인 배열 순회 예제
const users = new Array(100000).fill(0).map((_, i) => ({
id: i,
name: `User${i}`,
age: Math.floor(Math.random() * 50) + 20,
isActive: Math.random() > 0.5
}));
// 연속된 메모리를 순차적으로 접근 - 캐시 히트율 높음
console.time('Array Sequential Access');
let activeCount = 0;
for (let i = 0; i < users.length; i++) {
if (users[i].isActive) {
activeCount++;
}
}
console.timeEnd('Array Sequential Access');
console.log(`Active users: ${activeCount}`);
설명
이것이 하는 일: 위 코드는 10만 개의 사용자 객체를 배열에 저장하고, 활성 사용자 수를 카운트하는 전형적인 실무 시나리오를 시뮬레이션합니다. 실행 시간을 측정하여 배열의 순차 접근 성능을 확인할 수 있습니다.
첫 번째로, new Array(100000).fill(0).map()을 통해 대량의 데이터를 생성합니다. 여기서 중요한 점은 배열이 생성될 때 JavaScript 엔진이 연속된 메모리 공간을 확보한다는 것입니다.
V8 엔진의 경우 같은 타입의 객체들을 배열에 저장하면 "packed array"로 최적화하여 더욱 효율적인 메모리 배치를 만듭니다. 그 다음으로, for 루프가 실행되면서 배열을 순차적으로 순회합니다.
CPU는 users[0]을 메모리에서 가져올 때, 주변의 users[1], users[2] 등도 함께 캐시 라인(보통 64바이트)에 로드합니다. 따라서 다음 반복에서 users[1]에 접근할 때는 메인 메모리까지 갈 필요 없이 L1 캐시에서 바로 가져올 수 있어 수백 배 빠릅니다.
마지막으로, console.time()으로 성능을 측정하여 실제로 얼마나 빠른지 확인할 수 있습니다. 일반적으로 이 코드는 수 밀리초 내에 실행됩니다.
메모리 접근 패턴이 예측 가능하고 순차적이기 때문에, CPU의 하드웨어 프리페처(prefetcher)도 다음 데이터를 미리 가져와 성능을 더욱 향상시킵니다. 여러분이 이 코드를 사용하면 대량의 데이터 처리 작업에서 최적의 성능을 얻을 수 있습니다.
실무에서 로그 분석, 사용자 통계 계산, 대량 데이터 필터링 등의 작업에서 배열 기반 접근이 유리한 이유가 바로 이러한 캐시 친화성 때문입니다. 또한 배열은 JavaScript 엔진의 최적화 대상이기도 하여, JIT 컴파일러가 더 효율적인 머신 코드를 생성합니다.
실전 팁
💡 배열을 순회할 때는 가능한 한 순차적으로 접근하세요. for (let i = 0; i < arr.length; i++)가 arr.forEach()보다 약간 빠를 수 있지만, 가독성도 고려해야 합니다. 가장 중요한 건 역순이나 랜덤 접근을 피하는 것입니다.
💡 배열의 길이를 자주 변경하지 마세요. push()를 반복하면 내부적으로 재할당이 발생할 수 있습니다. 크기를 예측할 수 있다면 new Array(size)로 미리 할당하는 것이 좋습니다.
💡 "희소 배열(sparse array)"을 피하세요. const arr = []; arr[1000] = 'x'; 같은 코드는 엔진이 최적화를 포기하게 만듭니다. 항상 연속된 인덱스를 사용하세요.
💡 같은 타입의 데이터를 저장하세요. [1, 'string', {}, null] 같은 혼합 타입 배열보다 [1, 2, 3, 4]처럼 단일 타입 배열이 훨씬 빠릅니다. V8은 이를 "SMI array"나 "Double array"로 최적화합니다.
💡 성능이 정말 중요한 경우 TypedArray(Int32Array, Float64Array 등)를 고려하세요. 일반 배열보다 메모리 효율적이고 예측 가능한 성능을 제공합니다.
2. 연결 리스트의 동적 구조 - 유연성과 메모리 오버헤드
시작하며
여러분이 실시간으로 들어오는 데이터를 처리하는데, 크기를 미리 예측할 수 없는 상황이라면 어떻게 하시겠습니까? 배열은 크기 변경 시 전체 데이터를 복사해야 하는 비용이 발생하죠.
이런 상황에서 연결 리스트는 매력적인 대안처럼 보입니다. 각 노드가 다음 노드를 가리키는 포인터만 있으면 되니, 삽입과 삭제가 O(1)이라는 이론적 장점이 있습니다.
하지만 실무에서는 이론과 다른 성능 함정이 숨어있습니다. 연결 리스트의 동적 구조가 실제로 어떻게 작동하는지, 그리고 왜 대부분의 경우 배열보다 느린지 이해하면, 자료구조 선택에 대한 현명한 판단을 할 수 있습니다.
개요
간단히 말해서, 연결 리스트는 각 노드가 데이터와 다음 노드의 참조(포인터)를 가지는 자료구조입니다. 메모리상에서 연속적이지 않고 흩어져 있을 수 있습니다.
왜 이 개념이 필요할까요? 이론적으로는 크기 제한이 없고, 중간에 데이터를 삽입하거나 삭제할 때 배열처럼 전체를 이동시킬 필요가 없습니다.
예를 들어, 우선순위 큐나 LRU 캐시 같은 특수한 경우에는 연결 리스트의 특성이 유용할 수 있습니다. 하지만 대부분의 실무 상황에서는 성능 문제로 배열을 선호합니다.
기존에는 "삽입/삭제가 빈번하면 연결 리스트가 좋다"고 배웠다면, 이제는 "실제로는 캐시 미스 비용이 너무 커서 배열이 더 빠른 경우가 많다"는 현실을 이해해야 합니다. 현대 컴퓨터에서는 메모리 접근 패턴이 성능에 미치는 영향이 알고리즘의 시간 복잡도보다 클 수 있습니다.
연결 리스트의 핵심 특징은 세 가지입니다. 첫째, 비연속적 메모리 할당으로 캐시 미스가 빈번하고, 둘째, 포인터 저장을 위한 추가 메모리가 필요하며, 셋째, 순차 접근만 가능하여 인덱스 접근이 느립니다.
이러한 특징들이 왜 현대 프로그래밍에서 연결 리스트가 배열보다 덜 선호되는지 설명합니다.
코드 예제
// 연결 리스트 구현 - 메모리가 흩어져 있음
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// 끝에 노드 추가 - 포인터만 변경하면 되지만 순회 필요
append(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
// 캐시 미스 발생 가능성 높음 - 노드들이 메모리에 흩어져 있음
while (current.next) {
current = current.next;
}
current.next = newNode;
}
this.size++;
}
// 순회 - 각 노드 접근마다 캐시 미스 가능성
countActive() {
let count = 0;
let current = this.head;
while (current) {
if (current.value.isActive) {
count++;
}
current = current.next; // 다음 노드가 어디 있을지 예측 불가
}
return count;
}
}
// 사용 예제
const list = new LinkedList();
for (let i = 0; i < 100000; i++) {
list.append({
id: i,
name: `User${i}`,
isActive: Math.random() > 0.5
});
}
console.time('LinkedList Sequential Access');
const activeCount = list.countActive();
console.timeEnd('LinkedList Sequential Access');
console.log(`Active users: ${activeCount}`);
설명
이것이 하는 일: 위 코드는 연결 리스트를 직접 구현하고, 배열과 동일한 작업을 수행하여 성능을 비교할 수 있게 합니다. 10만 개의 노드를 생성하고 순회하면서 실제 성능 차이를 체감할 수 있습니다.
첫 번째로, Node 클래스는 값과 다음 노드 참조를 저장합니다. 여기서 중요한 점은 각 new Node()를 호출할 때마다 JavaScript 엔진이 힙 메모리의 임의의 위치에 노드를 할당한다는 것입니다.
즉, node1, node2, node3가 메모리상에서 전혀 인접하지 않을 수 있습니다. 가비지 컬렉션이 발생한 후에는 더욱 메모리가 단편화됩니다.
그 다음으로, append() 메서드에서 리스트의 끝까지 순회해야 하는 문제가 있습니다. 단순히 "O(1) 삽입"이라고만 생각하면 안 됩니다.
끝에 추가하려면 실제로는 O(n) 순회가 필요합니다(tail 포인터를 유지하더라도). 더 큰 문제는 순회 중 current = current.next를 할 때마다 다음 노드가 메모리 어디에 있을지 예측할 수 없어 캐시 미스가 발생한다는 점입니다.
CPU는 다음 데이터를 미리 가져올 수 없습니다. 세 번째로, countActive() 메서드에서 순회 성능을 확인할 수 있습니다.
배열과 동일한 로직이지만 실행 시간을 측정하면 보통 배열보다 5~10배 느립니다. 이는 순수하게 캐시 미스 때문입니다.
각 노드 접근이 메인 메모리까지 가야 하므로, L1 캐시 접근(약 1ns)과 메인 메모리 접근(약 100ns)의 차이가 누적됩니다. 마지막으로, 10만 개의 노드를 생성하는 과정 자체도 배열보다 느립니다.
각 노드마다 객체 할당과 포인터 설정이 필요하며, 추가 메모리도 소모합니다(값뿐만 아니라 next 포인터도 저장해야 하므로). 여러분이 이 코드를 실행해보면 이론과 실제의 차이를 직접 확인할 수 있습니다.
알고리즘 시간 복잡도만으로는 실제 성능을 예측하기 어렵습니다. 현대 컴퓨터 아키텍처에서는 메모리 접근 패턴, 캐시 지역성, CPU 파이프라인 등이 모두 성능에 영향을 미치기 때문입니다.
대부분의 실무 상황에서는 연결 리스트보다 배열이나 동적 배열(ArrayList)이 더 나은 선택입니다.
실전 팁
💡 연결 리스트는 LRU 캐시, 실행 취소/다시 실행 기능, 브라우저 히스토리 같은 특수한 경우에만 사용하세요. 일반적인 컬렉션으로는 배열을 선택하는 것이 거의 항상 더 좋습니다.
💡 JavaScript에서는 연결 리스트를 직접 구현하기보다 내장 Array나 Map을 활용하세요. 엔진 레벨에서 최적화되어 있어 훨씬 빠릅니다.
💡 "삽입/삭제가 빈번하다"고 무조건 연결 리스트를 선택하지 마세요. 배열도 끝에 추가/삭제는 O(1)이고, 중간 삽입도 데이터가 적으면 배열이 더 빠를 수 있습니다.
💡 메모리 사용량을 비교하세요. 연결 리스트는 각 노드마다 최소 하나의 포인터(8바이트)가 추가로 필요합니다. 작은 데이터를 많이 저장하면 메모리 낭비가 심합니다.
💡 성능이 정말 중요하다면 실제 데이터로 벤치마크를 작성하세요. 이론적 분석과 실제 성능은 다를 수 있으며, 프로파일러를 사용하면 캐시 미스율 등을 확인할 수 있습니다.
3. CPU 캐시의 동작 원리 - 공간 지역성과 시간 지역성
시작하며
여러분이 작성한 코드가 왜 예상보다 느린지 고민해본 적 있나요? 알고리즘은 O(n)으로 최적인데도 실행 시간이 기대에 못 미치는 경우가 있습니다.
문제는 종종 CPU와 메인 메모리 사이의 속도 차이에서 발생합니다. 현대 CPU는 초당 수십억 개의 명령을 실행할 수 있지만, 메인 메모리 접근은 수백 사이클이 걸립니다.
이 간극을 메우는 것이 바로 CPU 캐시입니다. CPU 캐시가 어떻게 작동하는지 이해하면, 여러분의 코드를 하드웨어 친화적으로 작성하여 성능을 2배, 10배까지 향상시킬 수 있습니다.
특히 자료구조 선택이 캐시 효율성에 얼마나 큰 영향을 미치는지 알아보겠습니다.
개요
간단히 말해서, CPU 캐시는 CPU와 메인 메모리 사이에 위치한 작고 빠른 메모리입니다. L1, L2, L3로 계층화되어 있으며, 자주 사용되는 데이터를 저장합니다.
왜 이게 중요할까요? CPU는 메모리에서 데이터를 가져올 때 하나만 가져오는 게 아니라 "캐시 라인" 단위(보통 64바이트)로 가져옵니다.
만약 여러분의 데이터가 메모리에 연속적으로 배치되어 있다면(배열처럼), 한 번의 메모리 접근으로 여러 데이터를 캐시에 로드할 수 있습니다. 예를 들어, 이미지 처리, 대량 데이터 분석, 게임 엔진 같은 성능 집약적 애플리케이션에서는 캐시 효율성이 전체 성능을 좌우합니다.
전통적으로는 "좋은 알고리즘 = 낮은 시간 복잡도"라고만 생각했다면, 이제는 "좋은 알고리즘 = 낮은 시간 복잡도 + 높은 캐시 효율성"이라는 관점을 가져야 합니다. 같은 O(n) 알고리즘도 메모리 접근 패턴에 따라 실제 성능이 천차만별입니다.
캐시의 핵심 특징은 두 가지입니다. 첫째, 공간 지역성(spatial locality): 한 데이터를 접근하면 인접한 데이터도 곧 접근할 가능성이 높다는 원칙으로, 배열은 이를 완벽히 활용합니다.
둘째, 시간 지역성(temporal locality): 최근에 접근한 데이터를 다시 접근할 가능성이 높다는 원칙으로, 루프 안의 변수들이 이에 해당합니다. 이러한 원칙들을 이해하고 코드를 작성하면 하드웨어의 잠재력을 최대한 끌어낼 수 있습니다.
코드 예제
// 캐시 친화적 접근 (행 우선 순회)
function rowMajorSum(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
let sum = 0;
// 메모리 배치 순서대로 접근 - 캐시 히트율 높음
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
sum += matrix[i][j]; // 연속된 메모리 접근
}
}
return sum;
}
// 캐시 비친화적 접근 (열 우선 순회)
function columnMajorSum(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
let sum = 0;
// 메모리 배치와 다른 순서로 접근 - 캐시 미스 빈번
for (let j = 0; j < cols; j++) {
for (let i = 0; i < rows; i++) {
sum += matrix[i][j]; // 불연속적 메모리 접근
}
}
return sum;
}
// 테스트
const SIZE = 1000;
const matrix = Array.from({ length: SIZE }, () =>
Array.from({ length: SIZE }, () => Math.random())
);
console.time('Row-major (cache-friendly)');
const sum1 = rowMajorSum(matrix);
console.timeEnd('Row-major (cache-friendly)');
console.time('Column-major (cache-unfriendly)');
const sum2 = columnMajorSum(matrix);
console.timeEnd('Column-major (cache-unfriendly)');
설명
이것이 하는 일: 위 코드는 2차원 배열을 두 가지 방식으로 순회하여 캐시 효율성의 차이를 실제로 측정합니다. 같은 작업인데도 접근 순서만 바꿨을 뿐인데 성능 차이가 확연합니다.
첫 번째로, JavaScript의 2차원 배열은 실제로는 "배열의 배열"입니다. matrix[0], matrix[1], matrix[2]가 각각 별도의 배열이지만, 각 행 내부의 요소들은 연속된 메모리에 저장됩니다.
따라서 matrix[0][0], matrix[0][1], matrix[0][2]는 메모리상에서 인접해 있습니다. 그 다음으로, rowMajorSum() 함수는 이 메모리 배치를 존중합니다.
외부 루프가 행을 순회하고 내부 루프가 열을 순회하므로, matrix[0][0] → matrix[0][1] → matrix[0][2] → ...처럼 메모리를 순차적으로 읽습니다. CPU가 matrix[0][0]을 읽을 때 캐시 라인에 matrix[0][1]부터 matrix[0][15]까지 함께 로드되므로(64바이트 캐시 라인 가정), 다음 16개 접근은 캐시에서 바로 처리됩니다.
반대로, columnMajorSum() 함수는 메모리 배치를 무시합니다. matrix[0][0] → matrix[1][0] → matrix[2][0] → ...처럼 서로 멀리 떨어진 메모리를 접근합니다.
matrix[0][0]을 읽을 때 캐시에 로드된 matrix[0][1~15]는 한참 후에야 사용되거나 아예 캐시에서 밀려날 수 있습니다. 각 행의 첫 요소에 접근할 때마다 캐시 미스가 발생하여 메인 메모리까지 가야 합니다.
실제로 테스트해보면 rowMajorSum()이 columnMajorSum()보다 2~5배 빠른 것을 확인할 수 있습니다. 행렬 크기가 커질수록 차이는 더 벌어집니다.
이는 순수하게 캐시 효율성 차이 때문이며, 알고리즘 자체는 동일합니다(둘 다 O(n²)). 여러분이 이런 원리를 이해하면 다차원 배열, 구조체 배열, 객체 지향 프로그래밍에서 성능을 크게 향상시킬 수 있습니다.
예를 들어, 게임 엔진에서 "구조체 배열(Array of Structures)" 대신 "배열 구조체(Structure of Arrays)"를 사용하는 것도 같은 원리입니다. 자주 함께 접근하는 데이터를 메모리상에서 가까이 배치하고, 순차적으로 접근하는 것이 핵심입니다.
실전 팁
💡 다차원 배열을 순회할 때는 항상 메모리 배치 순서를 고려하세요. JavaScript, C, Java는 행 우선(row-major)이므로 행을 먼저 순회해야 합니다. Fortran은 열 우선(column-major)입니다.
💡 "구조체 배열" vs "배열 구조체"를 고민하세요. [{x, y, z}, {x, y, z}, ...]보다 {xs: [...], ys: [...], zs: [...]}가 특정 속성만 순회할 때 캐시 효율적입니다.
💡 큰 객체를 많이 만들기보다는 primitive 값의 배열을 사용하세요. Float32Array, Int32Array 같은 TypedArray는 메모리 배치가 보장되어 최상의 캐시 성능을 제공합니다.
💡 루프 내에서 사용하는 변수는 최소화하세요. 자주 접근하는 변수는 CPU 레지스터나 L1 캐시에 머물 가능성이 높아 성능이 향상됩니다.
💡 프로파일링 도구를 사용하세요. Chrome DevTools의 Performance 탭이나 Node.js의 --prof 옵션으로 캐시 미스율을 분석할 수 있습니다(perf 같은 시스템 도구는 더 상세한 정보 제공).
4. 배열의 동적 확장 - 재할당 비용과 최적화
시작하며
여러분이 사용자 입력을 받아 리스트에 추가하는 기능을 만든다고 생각해보세요. 얼마나 많은 데이터가 들어올지 미리 알 수 없는 상황입니다.
그냥 push()를 반복하면 되는 걸까요? 겉보기에는 간단해 보이지만, 내부적으로는 복잡한 일이 일어납니다.
배열이 가득 차면 JavaScript 엔진은 더 큰 메모리를 할당하고 모든 데이터를 복사해야 합니다. 이런 재할당이 자주 일어나면 성능이 크게 떨어집니다.
하지만 걱정하지 마세요. 현대 JavaScript 엔진은 이 문제를 "동적 배열 확장 전략"으로 영리하게 해결합니다.
이 메커니즘을 이해하면 배열을 더 효율적으로 사용할 수 있습니다.
개요
간단히 말해서, JavaScript 배열은 내부적으로 고정 크기 메모리를 사용하지만, 꽉 차면 자동으로 더 큰 메모리를 할당하고 기존 데이터를 복사합니다. 이를 "동적 배열" 또는 "가변 배열"이라고 합니다.
왜 이 개념이 중요할까요? 매번 1개씩 크기를 늘리면 1000개 추가 시 약 500,000번의 복사가 필요합니다(1+2+3+...+1000).
하지만 실제로는 "배수 확장 전략"을 사용하여 꽉 찰 때마다 용량을 2배로 늘립니다. 이렇게 하면 1000개 추가 시 약 2000번의 복사만 필요하여 성능이 극적으로 향상됩니다.
실무에서 대량의 데이터를 동적으로 추가하는 경우(로그 수집, 스트림 처리, 사용자 이벤트 추적 등)에 이 차이가 체감됩니다. 전통적으로는 "배열은 고정 크기"라고만 배웠다면, 이제는 "동적 배열은 분할 상환 분석(amortized analysis)으로 O(1) 추가를 달성한다"는 것을 이해해야 합니다.
가끔 O(n) 재할당이 발생하지만, 충분히 드물어서 평균적으로는 O(1)입니다. 동적 배열의 핵심 특징은 세 가지입니다.
첫째, 용량(capacity)과 크기(size)를 구분하며, 둘째, 꽉 찰 때마다 보통 1.5배 또는 2배로 확장하고, 셋째, 재할당 시 모든 요소를 새 메모리로 복사해야 합니다. 이러한 특징을 이해하면 예측 가능한 크기의 데이터를 다룰 때 미리 용량을 예약하여 성능을 최적화할 수 있습니다.
코드 예제
// 비효율적: 매번 새 배열 생성 (안티패턴)
function inefficientAppend(n) {
let arr = [];
console.time('Inefficient append');
for (let i = 0; i < n; i++) {
arr.push(i); // 내부적으로 재할당이 빈번히 발생 가능
}
console.timeEnd('Inefficient append');
return arr;
}
// 효율적: 크기 예약
function efficientAppend(n) {
let arr = new Array(n); // 미리 용량 할당
console.time('Efficient append with pre-allocation');
for (let i = 0; i < n; i++) {
arr[i] = i; // 재할당 없이 직접 할당
}
console.timeEnd('Efficient append with pre-allocation');
return arr;
}
// 실무 패턴: 예상 크기 알 때
function realisticPattern(estimatedSize) {
// 예상 크기로 초기화
let arr = new Array(estimatedSize);
let actualSize = 0;
console.time('Realistic pattern');
for (let i = 0; i < estimatedSize * 1.5; i++) { // 예상보다 많이 들어올 수 있음
if (actualSize >= arr.length) {
// 수동 확장 (실제로는 push가 자동으로 처리)
const newArr = new Array(arr.length * 2);
for (let j = 0; j < arr.length; j++) {
newArr[j] = arr[j];
}
arr = newArr;
}
arr[actualSize++] = i;
}
console.timeEnd('Realistic pattern');
return arr.slice(0, actualSize);
}
// 테스트
const SIZE = 1000000;
inefficientAppend(SIZE);
efficientAppend(SIZE);
realisticPattern(SIZE);
설명
이것이 하는 일: 위 코드는 배열에 대량의 데이터를 추가하는 세 가지 방법을 비교합니다. 재할당 빈도와 성능의 상관관계를 실제로 측정할 수 있습니다.
첫 번째로, inefficientAppend() 함수는 일반적인 push() 사용 패턴입니다. 실제로는 JavaScript 엔진이 내부적으로 최적화하므로 생각보다 나쁘지 않지만, 초기 크기를 지정하지 않았기 때문에 여러 번 재할당이 발생합니다.
V8 엔진의 경우 처음에는 작은 배열로 시작하고, 1.5배씩 확장합니다. 100만 개를 추가하면 약 20번의 재할당이 발생하며, 총 복사 횟수는 약 200만 번입니다.
그 다음으로, efficientAppend() 함수는 new Array(n)으로 필요한 크기를 미리 할당합니다. 이렇게 하면 재할당이 전혀 발생하지 않습니다.
단, 주의할 점은 new Array(n)은 "희소 배열(sparse array)"을 만들 수 있으므로, arr[i] = value 형태로 값을 채워야 합니다. push()를 사용하면 길이가 n+1이 되어버립니다.
세 번째로, realisticPattern() 함수는 실무에서 자주 겪는 상황을 시뮬레이션합니다. 대략적인 크기는 알지만 정확하지 않은 경우입니다.
예상 크기로 시작하되, 초과하면 수동으로 2배 확장합니다. 이는 JavaScript 엔진이 내부적으로 하는 일을 명시적으로 구현한 것으로, 교육 목적입니다.
실제로는 push()를 쓰되 초기 크기를 적절히 설정하는 것이 좋습니다. 테스트 결과를 보면 efficientAppend()가 가장 빠르고, inefficientAppend()도 엔진 최적화 덕분에 크게 느리지 않습니다.
하지만 데이터 크기가 1000만, 1억으로 커지면 차이가 확연해집니다. 또한 재할당 시 메모리 단편화가 발생하고 가비지 컬렉션 부담도 증가합니다.
여러분이 이 원리를 알면 실무에서 성능 최적화의 기회를 찾을 수 있습니다. CSV 파싱, JSON 배열 구성, 대량 DOM 요소 생성 등에서 예상 크기를 기반으로 배열을 초기화하면 성능과 메모리 효율이 모두 향상됩니다.
특히 서버 사이드 JavaScript(Node.js)에서 메모리 압박이 있을 때 유용합니다.
실전 팁
💡 크기를 예측할 수 있다면 new Array(expectedSize)로 시작하세요. 정확하지 않아도 근사치만 있으면 재할당 횟수를 줄일 수 있습니다.
💡 push() vs arr[i] = value 성능은 상황에 따라 다릅니다. 사전 할당된 배열에는 인덱싱이, 동적 배열에는 push()가 적합합니다.
💡 concat()이나 스프레드 연산자([...arr1, ...arr2])는 매번 새 배열을 만듭니다. 루프 안에서 사용하면 O(n²)이 될 수 있으니 주의하세요.
💡 배열을 줄일 때도 메모리가 즉시 해제되지 않을 수 있습니다. 명시적으로 새 배열을 만들거나 arr.length = newSize로 잘라내세요.
💡 TypedArray(Uint32Array 등)는 크기가 고정되어 있어 재할당이 없습니다. 크기를 정확히 알고 primitive 타입만 저장한다면 최고의 성능을 제공합니다.
5. 연결 리스트의 실전 활용 - LRU 캐시 구현
시작하며
여러분이 웹 애플리케이션에서 API 응답을 캐싱하는 기능을 만든다고 상상해보세요. 하지만 메모리는 제한되어 있어서 오래된 항목은 삭제해야 합니다.
어떤 자료구조를 사용하시겠습니까? 이런 LRU(Least Recently Used) 캐시는 실무에서 매우 흔합니다.
브라우저 캐시, 데이터베이스 버퍼 풀, CDN 등에서 사용됩니다. 배열만으로는 O(n) 삭제가 필요하지만, 연결 리스트와 해시맵을 결합하면 O(1)에 구현할 수 있습니다.
바로 이것이 연결 리스트가 진정으로 빛나는 순간입니다. 이론적 장점이 실제로 의미 있는 몇 안 되는 사례를 알아보겠습니다.
개요
간단히 말해서, LRU 캐시는 가장 최근에 사용되지 않은 항목을 제거하는 캐싱 전략입니다. 이중 연결 리스트와 해시맵을 함께 사용하여 O(1) 접근, 삽입, 삭제를 모두 달성합니다.
왜 이 패턴이 필요할까요? 단순히 배열로 구현하면 항목을 찾는 데 O(n), 중간에서 삭제하는 데 O(n)이 걸립니다.
하지만 이중 연결 리스트는 노드의 이전/다음 포인터만 변경하면 되므로 삭제가 O(1)입니다. 여기에 해시맵으로 노드를 직접 찾을 수 있게 하면 완벽합니다.
예를 들어, Redis 같은 인메모리 데이터베이스가 내부적으로 사용하는 핵심 알고리즘입니다. 전통적으로는 "연결 리스트는 느리다"고만 생각했다면, 이제는 "특정 문제에서는 연결 리스트의 O(1) 삽입/삭제가 결정적 이점이 된다"는 것을 이해해야 합니다.
순회 성능은 희생하되, 빈번한 수정 작업에 최적화된 자료구조입니다. LRU 캐시의 핵심 특징은 세 가지입니다.
첫째, 이중 연결 리스트로 사용 순서를 추적하고, 둘째, 해시맵으로 O(1) 키 접근을 제공하며, 셋째, 용량 초과 시 가장 오래된 항목(리스트 끝)을 O(1)에 제거합니다. 이러한 특징이 실시간 시스템에서 예측 가능한 성능을 보장합니다.
코드 예제
// 이중 연결 리스트 노드
class DLLNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
// LRU 캐시 구현
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map(); // key -> node
this.head = new DLLNode(0, 0); // 더미 헤드
this.tail = new DLLNode(0, 0); // 더미 테일
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 노드를 리스트 앞으로 이동 (최근 사용)
_moveToFront(node) {
this._removeNode(node);
this._addToFront(node);
}
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_addToFront(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
get(key) {
if (!this.cache.has(key)) return -1;
const node = this.cache.get(key);
this._moveToFront(node); // O(1) 이동
return node.value;
}
put(key, value) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.value = value;
this._moveToFront(node);
} else {
const newNode = new DLLNode(key, value);
this.cache.set(key, newNode);
this._addToFront(newNode);
if (this.cache.size > this.capacity) {
// 가장 오래된 항목 제거 (O(1))
const lru = this.tail.prev;
this._removeNode(lru);
this.cache.delete(lru.key);
}
}
}
}
// 사용 예제
const cache = new LRUCache(3);
cache.put('a', 1);
cache.put('b', 2);
cache.put('c', 3);
console.log(cache.get('a')); // 1, 'a'를 최근 사용으로 이동
cache.put('d', 4); // 용량 초과, 'b' 제거 (가장 오래됨)
console.log(cache.get('b')); // -1, 제거되었음
설명
이것이 하는 일: 위 코드는 실무에서 사용 가능한 수준의 LRU 캐시를 구현합니다. 이중 연결 리스트의 포인터 조작으로 O(1) 성능을 달성하는 전형적인 예제입니다.
첫 번째로, DLLNode 클래스는 이전/다음 노드를 모두 가리킵니다. 단일 연결 리스트와 달리 이중 연결 리스트는 양방향 이동이 가능하여, 중간 노드를 삭제할 때 이전 노드를 찾기 위해 순회할 필요가 없습니다.
node.prev.next = node.next 한 줄로 삭제가 끝납니다. 더미 헤드와 테일을 사용하면 경계 조건(빈 리스트, 단일 노드 등) 처리가 간단해집니다.
그 다음으로, cache Map은 키에서 노드로의 직접 접근을 제공합니다. get(key) 호출 시 cache.get(key)로 O(1)에 노드를 찾고, _moveToFront()로 해당 노드를 리스트 앞으로 이동시킵니다.
리스트 앞쪽은 최근 사용, 뒤쪽은 오래 사용되지 않은 항목을 의미합니다. 세 번째로, put() 메서드에서 용량 체크를 합니다.
this.cache.size > this.capacity이면 tail.prev 노드(가장 오래된 항목)를 제거합니다. 여기서 연결 리스트의 진가가 발휘됩니다.
배열이었다면 arr.shift()로 O(n)이 걸렸겠지만, 연결 리스트는 _removeNode()로 O(1)에 처리합니다. 포인터 몇 개만 변경하면 됩니다.
마지막으로, 실제 테스트를 보면 항목 'd'를 추가할 때 'b'가 제거됩니다. 왜냐하면 'a'는 get()으로 접근하여 최근 사용으로 이동했고, 'c'는 가장 나중에 추가되었으며, 'd'는 방금 추가되었기 때문에 'b'가 가장 오래되었습니다.
이 모든 작업이 O(1)에 이루어집니다. 여러분이 이 패턴을 익히면 실무에서 다양하게 응용할 수 있습니다.
API 응답 캐싱, 이미지 썸네일 캐시, 데이터베이스 쿼리 결과 캐싱 등에서 메모리를 효율적으로 관리할 수 있습니다. 또한 브라우저의 Back/Forward 히스토리, 텍스트 에디터의 Undo/Redo도 유사한 원리로 구현됩니다.
연결 리스트가 배열보다 나은 드문 사례이므로 꼭 이해해두세요.
실전 팁
💡 JavaScript의 Map은 삽입 순서를 보장하므로, 간단한 LRU는 Map만으로도 구현 가능합니다. 하지만 대규모 시스템이나 성능이 중요한 경우 명시적 연결 리스트가 더 좋습니다.
💡 실무에서는 TTL(Time To Live)도 함께 고려하세요. 오래 사용하지 않았을 뿐 아니라 절대 시간도 체크해야 하는 경우가 많습니다.
💡 멀티스레드 환경에서는 동기화가 필요합니다. JavaScript는 싱글 스레드지만, Worker를 사용한다면 SharedArrayBuffer나 메시지 패싱을 고려하세요.
💡 LFU(Least Frequently Used)도 고려해보세요. 사용 빈도가 중요한 경우 우선순위 큐와 해시맵을 결합할 수 있습니다.
💡 메모리 누수를 조심하세요. 노드를 제거할 때 node.prev = null; node.next = null;로 참조를 명시적으로 끊으면 가비지 컬렉션이 더 빨라집니다.
6. 배열 기반 큐 vs 연결 리스트 기반 큐 - 실전 성능 비교
시작하며
여러분이 메시지 큐나 작업 스케줄러를 구현한다고 생각해보세요. 앞에서 데이터를 빼고(dequeue) 뒤에서 넣는(enqueue) 작업이 빈번합니다.
배열로 구현할까요, 연결 리스트로 구현할까요? 교과서에서는 "큐는 연결 리스트로 구현하는 게 효율적"이라고 배웁니다.
하지만 실제로 측정해보면 대부분의 경우 배열 기반 큐가 더 빠릅니다. 이론과 실제의 괴리가 가장 큰 사례 중 하나입니다.
두 구현을 직접 비교하면서 캐시 지역성, 메모리 오버헤드, 실제 성능의 관계를 명확히 이해해보겠습니다.
개요
간단히 말해서, 큐는 FIFO(First In First Out) 자료구조로, 배열이나 연결 리스트로 구현할 수 있습니다. 각각 장단점이 있지만 실제 성능은 이론과 다를 수 있습니다.
왜 이 비교가 중요할까요? 알고리즘 시간 복잡도만 보면 연결 리스트 큐가 O(1) enqueue/dequeue를 보장하는 반면, 배열 큐는 shift()가 O(n)이므로 비효율적으로 보입니다.
하지만 실제로는 배열의 캐시 친화성과 JavaScript 엔진의 최적화 덕분에 작은~중간 크기의 큐에서는 배열이 더 빠릅니다. 실무에서 웹 서버의 요청 큐, 이벤트 루프, BFS 알고리즘 등에 적용할 때 올바른 선택을 해야 합니다.
전통적으로는 "큐 = 연결 리스트"라고 단순화했다면, 이제는 "큐의 크기, 사용 패턴, 성능 요구사항에 따라 구현을 선택한다"는 실용적 관점을 가져야 합니다. 순수 이론보다 벤치마크가 중요합니다.
배열 큐와 연결 리스트 큐의 차이는 세 가지입니다. 첫째, 배열은 캐시 친화적이지만 shift()가 O(n), 연결 리스트는 O(1) dequeue이지만 캐시 미스가 많습니다.
둘째, 배열은 메모리 오버헤드가 적지만 재할당이 필요하고, 연결 리스트는 각 노드마다 포인터 오버헤드가 있습니다. 셋째, 원형 버퍼(circular buffer)를 사용하면 배열도 O(1) dequeue를 달성할 수 있습니다.
이러한 차이를 이해하고 상황에 맞게 선택하는 것이 핵심입니다.
코드 예제
// 배열 기반 큐 (단순 구현 - shift 사용)
class ArrayQueue {
constructor() {
this.items = [];
}
enqueue(item) {
this.items.push(item); // O(1) 분할 상환
}
dequeue() {
return this.items.shift(); // O(n) - 모든 요소 이동
}
get size() {
return this.items.length;
}
}
// 원형 버퍼 기반 큐 (최적화된 배열)
class CircularQueue {
constructor(capacity = 1000) {
this.items = new Array(capacity);
this.head = 0;
this.tail = 0;
this.size = 0;
}
enqueue(item) {
this.items[this.tail] = item;
this.tail = (this.tail + 1) % this.items.length;
this.size++;
}
dequeue() {
if (this.size === 0) return undefined;
const item = this.items[this.head];
this.head = (this.head + 1) % this.items.length;
this.size--;
return item;
}
}
// 연결 리스트 기반 큐
class LinkedListQueue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
enqueue(item) {
const node = { value: item, next: null };
if (!this.tail) {
this.head = this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
}
dequeue() {
if (!this.head) return undefined;
const item = this.head.value;
this.head = this.head.next;
if (!this.head) this.tail = null;
this.size--;
return item;
}
}
// 성능 비교
function benchmark(Queue, name, ops = 100000) {
const q = new Queue();
console.time(name);
for (let i = 0; i < ops; i++) {
q.enqueue(i);
if (i % 2 === 0) q.dequeue(); // 반 정도 dequeue
}
while (q.size > 0) {
q.dequeue();
}
console.timeEnd(name);
}
benchmark(ArrayQueue, 'Array Queue (shift)');
benchmark(CircularQueue, 'Circular Queue (optimized)');
benchmark(LinkedListQueue, 'LinkedList Queue');
설명
이것이 하는 일: 위 코드는 세 가지 큐 구현을 직접 비교하여 이론과 실제 성능의 차이를 보여줍니다. 10만 번의 enqueue/dequeue 작업을 수행하며 실행 시간을 측정합니다.
첫 번째로, ArrayQueue는 가장 단순한 구현입니다. push()는 O(1)로 빠르지만, shift()는 배열의 모든 요소를 한 칸씩 앞으로 이동시켜야 하므로 O(n)입니다.
10만 개 요소가 있을 때 shift() 한 번에 10만 번의 복사가 발생합니다. 하지만 놀랍게도 작은 큐(수백 개)에서는 캐시 효율성 덕분에 생각보다 빠릅니다.
그 다음으로, CircularQueue는 원형 버퍼 패턴을 사용합니다. head와 tail 인덱스를 추적하고, % this.items.length로 순환시킵니다.
이렇게 하면 실제로 요소를 이동시키지 않고 인덱스만 변경하므로 dequeue도 O(1)입니다. 게다가 배열이므로 캐시 친화적입니다.
단점은 최대 크기를 미리 정해야 한다는 것이지만, 동적 확장을 추가하면 해결됩니다. 이는 생산 환경에서 가장 추천하는 구현입니다.
세 번째로, LinkedListQueue는 이론적으로 완벽합니다. enqueue와 dequeue 모두 O(1)이고, 크기 제한도 없습니다.
tail.next = node로 끝에 추가하고, head = head.next로 앞에서 제거합니다. 하지만 각 노드가 메모리에 흩어져 있어 순회할 때마다 캐시 미스가 발생합니다.
또한 각 요소마다 next 포인터를 저장해야 하므로 메모리 오버헤드가 큽니다. 벤치마크 결과를 보면 일반적으로 CircularQueue가 가장 빠르고, ArrayQueue가 그 다음이며, LinkedListQueue가 가장 느립니다.
특히 원형 버퍼는 연결 리스트보다 5~10배 빠를 수 있습니다. 큐 크기가 매우 크고(수백만) 동적으로 크기가 변한다면 연결 리스트의 장점이 커지지만, 대부분의 실무 시나리오에서는 원형 버퍼가 최선입니다.
여러분이 이 비교를 통해 배운 교훈은 "이론적 시간 복잡도가 전부가 아니다"입니다. 캐시 지역성, 메모리 오버헤드, 언어/엔진 최적화 등이 모두 실제 성능에 영향을 미칩니다.
알고리즘을 선택할 때는 항상 실제 데이터로 벤치마크를 돌려보세요. 특히 Node.js 백엔드나 브라우저의 비동기 작업 큐를 구현할 때 이런 차이가 중요합니다.
실전 팁
💡 큐 크기가 예측 가능하다면 원형 버퍼를 사용하세요. 고정 크기 버퍼는 가장 빠르고 메모리 효율적입니다.
💡 JavaScript의 배열 shift()는 V8에서 최적화되었지만 여전히 O(n)입니다. 성능이 중요하다면 직접 원형 버퍼를 구현하세요.
💡 우선순위 큐가 필요하다면 힙(heap)을 사용하세요. 배열 기반 이진 힙이 연결 리스트보다 훨씬 효율적입니다.
💡 큐가 비는 경우를 처리하세요. dequeue()가 undefined를 반환하는지, 예외를 던지는지 명확히 정의하세요.
💡 생산 환경에서는 큐 크기 제한을 두세요. 무한정 커지는 큐는 메모리 부족으로 이어집니다. 백프레셔(backpressure) 메커니즘도 고려하세요.
7. 메모리 단편화와 할당 패턴 - 배열 vs 연결 리스트의 숨은 비용
시작하며
여러분의 애플리케이션이 몇 시간 실행되다가 점점 느려지는 경험을 해본 적 있나요? 메모리는 충분한데도 성능이 저하되는 이유가 뭘까요?
문제는 종종 메모리 단편화(memory fragmentation)입니다. 특히 연결 리스트처럼 작은 객체를 많이 생성하는 자료구조는 힙 메모리를 조각조각 사용하여 단편화를 가속화합니다.
이는 가비지 컬렉션 시간 증가와 메모리 효율 저하로 이어집니다. 배열과 연결 리스트가 메모리 할당 패턴에 미치는 영향을 이해하면, 장시간 실행되는 서버나 메모리 제약이 있는 환경에서 더 안정적인 코드를 작성할 수 있습니다.
개요
간단히 말해서, 메모리 단편화는 사용 가능한 메모리가 작은 조각으로 흩어져서 큰 연속 공간을 할당하기 어려워지는 현상입니다. 배열은 연속 할당으로 단편화를 줄이지만, 연결 리스트는 작은 할당을 반복하여 단편화를 증가시킵니다.
왜 이게 중요할까요? JavaScript는 가비지 컬렉션 언어이므로 명시적으로 메모리를 관리하지 않지만, 할당 패턴은 여전히 성능에 영향을 미칩니다.
배열은 한 번에 큰 연속 메모리를 할당하므로 메모리 관리자가 효율적으로 처리할 수 있습니다. 반면 연결 리스트는 노드마다 작은 할당이 발생하여 힙이 스위스 치즈처럼 구멍투성이가 됩니다.
예를 들어, 장시간 실행되는 Node.js 서버나 React Native 앱에서 메모리 압박이 발생할 수 있습니다. 전통적으로는 "가비지 컬렉션이 알아서 처리한다"고만 생각했다면, 이제는 "할당 패턴을 의식적으로 설계하여 GC 부담을 줄인다"는 관점을 가져야 합니다.
특히 대량의 단명 객체(short-lived objects)를 생성하는 패턴은 피해야 합니다. 메모리 단편화의 핵심 영향은 세 가지입니다.
첫째, 가비지 컬렉션이 더 자주, 오래 실행되어 애플리케이션이 멈춥니다(Stop-The-World). 둘째, 메모리 사용량이 실제 데이터보다 훨씬 커질 수 있습니다(메모리 오버헤드).
셋째, 캐시 효율이 떨어져 전반적인 성능이 저하됩니다. 이러한 영향을 최소화하려면 배열이나 객체 풀(object pool) 같은 패턴을 활용해야 합니다.
코드 예제
// 메모리 단편화를 유발하는 패턴 (연결 리스트)
function fragmentingPattern() {
const list = new LinkedListQueue(); // 이전 예제의 LinkedListQueue 사용
console.log('Initial memory:', process.memoryUsage().heapUsed / 1024 / 1024, 'MB');
// 100만 개의 작은 노드 생성 - 각각 별도 할당
for (let i = 0; i < 1000000; i++) {
list.enqueue({ id: i, data: `item_${i}` });
}
console.log('After enqueue:', process.memoryUsage().heapUsed / 1024 / 1024, 'MB');
// 절반 제거 - 메모리 구멍 생성
for (let i = 0; i < 500000; i++) {
list.dequeue();
}
console.log('After dequeue:', process.memoryUsage().heapUsed / 1024 / 1024, 'MB');
// GC 강제 실행 (Node.js --expose-gc 필요)
if (global.gc) {
global.gc();
console.log('After GC:', process.memoryUsage().heapUsed / 1024 / 1024, 'MB');
}
}
// 메모리 효율적인 패턴 (배열)
function efficientPattern() {
let arr = [];
console.log('Initial memory:', process.memoryUsage().heapUsed / 1024 / 1024, 'MB');
// 한 번에 큰 연속 메모리 할당
arr = new Array(1000000);
for (let i = 0; i < arr.length; i++) {
arr[i] = { id: i, data: `item_${i}` };
}
console.log('After allocation:', process.memoryUsage().heapUsed / 1024 / 1024, 'MB');
// 절반 제거 - 배열 크기 조정
arr.length = 500000;
console.log('After truncate:', process.memoryUsage().heapUsed / 1024 / 1024, 'MB');
if (global.gc) {
global.gc();
console.log('After GC:', process.memoryUsage().heapUsed / 1024 / 1024, 'MB');
}
}
// 객체 풀 패턴 (최적화)
class ObjectPool {
constructor(factory, initialSize = 100) {
this.factory = factory;
this.pool = [];
for (let i = 0; i < initialSize; i++) {
this.pool.push(factory());
}
}
acquire() {
return this.pool.length > 0 ? this.pool.pop() : this.factory();
}
release(obj) {
// 객체 재사용을 위해 초기화
Object.keys(obj).forEach(key => obj[key] = null);
this.pool.push(obj);
}
}
// 사용 예
const nodePool = new ObjectPool(() => ({ value: null, next: null }), 1000);
const node = nodePool.acquire();
node.value = 'data';
// 사용 후
nodePool.release(node); // 재사용 가능
설명
이것이 하는 일: 위 코드는 메모리 할당 패턴이 실제 메모리 사용량과 GC 성능에 미치는 영향을 측정합니다. Node.js의 process.memoryUsage()로 힙 사용량을 추적합니다.
첫 번째로, fragmentingPattern()은 연결 리스트의 문제를 드러냅니다. 100만 개의 노드를 생성할 때 각 노드마다 new 연산이 발생하여 힙에 100만 개의 작은 객체가 흩어집니다.
V8의 힙은 "새 공간(new space)"과 "오래된 공간(old space)"으로 나뉘는데, 노드들이 서로 다른 세대에 속하면 GC가 더 복잡해집니다. 절반을 dequeue()하면 메모리에 구멍이 생기지만 즉시 해제되지 않아 힙 사용량이 높게 유지됩니다.
그 다음으로, efficientPattern()은 배열의 효율성을 보여줍니다. new Array(1000000)으로 한 번에 큰 연속 메모리를 할당하므로 힙 관리자가 최적화하기 쉽습니다.
객체들도 배열 내부에 저장되므로 공간 지역성이 좋습니다. arr.length = 500000으로 절반을 잘라내면 참조가 사라져 GC가 효율적으로 회수할 수 있습니다.
실제로 GC 후 메모리 사용량이 크게 줄어드는 것을 확인할 수 있습니다. 세 번째로, ObjectPool 패턴은 게임 엔진이나 고성능 서버에서 사용하는 최적화 기법입니다.
객체를 미리 생성해두고 재사용하여 할당/해제를 최소화합니다. 예를 들어, 게임에서 총알 객체를 매번 생성/삭제하는 대신 풀에서 가져와 쓰고 반환합니다.
이렇게 하면 GC 압력이 극적으로 줄어들고 성능이 예측 가능해집니다. Node.js에서 --expose-gc 플래그로 실행하면 global.gc()로 수동 GC를 트리거할 수 있습니다.
일반적으로는 V8이 알아서 하지만, 벤치마크 목적으로 유용합니다. 실제 프로덕션에서는 수동 GC를 호출하지 마세요.
여러분이 이 개념을 적용하면 장시간 실행되는 애플리케이션의 안정성을 높일 수 있습니다. Node.js 서버가 며칠, 몇 주 동안 실행되는 경우 메모리 누수나 단편화가 큰 문제가 됩니다.
배열 기반 자료구조를 선호하고, 객체 풀을 활용하며, 불필요한 객체 생성을 줄이는 것이 핵심입니다. Chrome DevTools의 Memory 프로파일러로 힙 스냅샷을 비교하면 단편화 정도를 시각적으로 확인할 수 있습니다.
실전 팁
💡 객체 풀은 생성 비용이 큰 객체(DOM 요소, 버퍼, 복잡한 객체)에 사용하세요. 단순한 숫자나 문자열에는 오버헤드가 더 클 수 있습니다.
💡 Node.js의 --max-old-space-size 플래그로 힙 크기를 조정하세요. 기본값(약 2GB)이 부족하면 OOM(Out Of Memory) 에러가 발생할 수 있습니다.
💡 메모리 누수를 찾으려면 힙 스냅샷을 시간 간격을 두고 찍어 비교하세요. 계속 증가하는 객체를 찾아 수정합니다.
💡 WeakMap과 WeakSet을 활용하세요. 키가 GC되면 자동으로 항목이 제거되어 메모리 누수를 방지합니다.
💡 스트림과 이터레이터를 활용하여 대량의 데이터를 한꺼번에 메모리에 올리지 마세요. 필요한 만큼만 처리하는 "게으른 평가(lazy evaluation)" 패턴을 사용하세요.
8. 벤치마크와 프로파일링 - 올바른 성능 측정 방법
시작하며
여러분이 두 가지 구현 중 어느 것이 빠른지 판단해야 하는 상황이라면, 어떻게 하시겠습니까? 그냥 console.time()으로 측정하면 될까요?
성능 측정은 생각보다 까다롭습니다. JavaScript는 JIT 컴파일, 인라인 캐싱, 가비지 컬렉션 등 다양한 최적화가 런타임에 발생하기 때문에, 첫 실행과 반복 실행의 성능이 크게 다를 수 있습니다.
잘못된 벤치마크는 잘못된 결론으로 이어집니다. 올바른 벤치마킹 방법과 프로파일링 도구 사용법을 익히면, 데이터에 기반한 성능 최적화 결정을 내릴 수 있습니다.
추측이 아닌 측정이 핵심입니다.
개요
간단히 말해서, 벤치마킹은 코드의 실행 시간을 측정하고 비교하는 과정이고, 프로파일링은 실행 중 함수 호출, 메모리 사용, CPU 시간 등을 상세히 분석하는 과정입니다. 왜 제대로 된 측정이 중요할까요?
성능 최적화는 보통 가독성이나 유지보수성을 희생하므로, 실제로 의미 있는 개선이 있을 때만 해야 합니다. 잘못된 측정으로 "최적화"했다가 오히려 느려지거나, 중요하지 않은 부분을 최적화하는 낭비가 발생할 수 있습니다.
실무에서 API 응답 시간, 페이지 로딩 속도, 렌더링 성능 등을 정확히 측정해야 사용자 경험을 개선할 수 있습니다. 전통적으로는 "느낌상 빠른 것 같다"고 판단했다면, 이제는 "통계적으로 유의미한 차이가 있다"는 것을 증명해야 합니다.
P95, P99 같은 백분위수(percentile)를 보고, 단순 평균이 아닌 분포를 이해해야 합니다. 올바른 벤치마킹의 핵심은 세 가지입니다.
첫째, JIT 워밍업을 고려하여 여러 번 반복 실행합니다. 둘째, GC의 영향을 최소화하거나 측정에 포함시킵니다.
셋째, 실제 데이터와 사용 패턴을 반영합니다. 이러한 원칙을 지키면 신뢰할 수 있는 성능 비교가 가능합니다.
코드 예제
// 잘못된 벤치마크 (안티패턴)
function badBenchmark() {
const arr = Array.from({ length: 100000 }, (_, i) => i);
console.time('Bad benchmark');
arr.forEach(x => x * 2); // 결과를 저장하지 않음 - 최적화로 제거될 수 있음
console.timeEnd('Bad benchmark'); // 한 번만 실행 - JIT 영향 무시
}
// 올바른 벤치마크
function goodBenchmark() {
const ITERATIONS = 100;
const arr = Array.from({ length: 100000 }, (_, i) => i);
const times = [];
// 워밍업 (JIT 컴파일 유도)
for (let i = 0; i < 10; i++) {
let result = 0;
arr.forEach(x => result += x * 2);
}
// 실제 측정
for (let i = 0; i < ITERATIONS; i++) {
const start = performance.now();
let result = 0;
arr.forEach(x => result += x * 2); // 결과 사용하여 최적화 방지
const end = performance.now();
times.push(end - start);
// Dead code elimination 방지
if (result < 0) console.log('Never happens');
}
// 통계 계산
times.sort((a, b) => a - b);
const mean = times.reduce((a, b) => a + b) / times.length;
const median = times[Math.floor(times.length / 2)];
const p95 = times[Math.floor(times.length * 0.95)];
const p99 = times[Math.floor(times.length * 0.99)];
console.log(`Mean: ${mean.toFixed(2)}ms`);
console.log(`Median: ${median.toFixed(2)}ms`);
console.log(`P95: ${p95.toFixed(2)}ms`);
console.log(`P99: ${p99.toFixed(2)}ms`);
}
// 프로파일링과 함께 사용
function profiledBenchmark() {
console.profile('Array vs LinkedList');
// 배열 테스트
const arr = [];
for (let i = 0; i < 100000; i++) arr.push(i);
arr.forEach(x => x * 2);
// 연결 리스트 테스트
const list = new LinkedListQueue();
for (let i = 0; i < 100000; i++) list.enqueue(i);
console.profileEnd('Array vs LinkedList');
// Chrome DevTools에서 CPU 프로파일 확인 가능
}
// Benchmark.js 스타일 (프로덕션 권장)
// npm install benchmark 후 사용
/*
const Benchmark = require('benchmark');
const suite = new Benchmark.Suite;
suite
.add('Array#forEach', function() {
const arr = Array.from({ length: 1000 }, (_, i) => i);
let result = 0;
arr.forEach(x => result += x);
})
.add('for loop', function() {
const arr = Array.from({ length: 1000 }, (_, i) => i);
let result = 0;
for (let i = 0; i < arr.length; i++) {
result += arr[i];
}
})
.on('cycle', function(event) {
console.log(String(event.target));
})
.on('complete', function() {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run({ 'async': true });
*/
goodBenchmark();
설명
이것이 하는 일: 위 코드는 성능 측정의 올바른 방법과 흔한 실수를 비교합니다. 신뢰할 수 있는 벤치마크를 작성하는 실전 패턴을 제공합니다.
첫 번째로, badBenchmark()는 전형적인 실수를 보여줍니다. console.time()은 밀리초 정밀도만 제공하고, 한 번만 실행하면 JIT 컴파일 전 성능을 측정하게 됩니다.
또한 forEach의 결과를 사용하지 않으면 최적화 컴파일러가 "이 코드는 부작용이 없으니 실행하지 않아도 된다"고 판단하여 제거할 수 있습니다(dead code elimination). 이런 벤치마크는 0ms에 가까운 비현실적 결과를 낼 수 있습니다.
그 다음으로, goodBenchmark()는 모범 사례를 따릅니다. 먼저 10번의 워밍업 반복으로 V8의 TurboFan 최적화 컴파일러를 작동시킵니다.
JavaScript 엔진은 "핫 함수(hot function)"를 감지하여 최적화하므로, 처음 몇 번은 인터프리터나 기본 컴파일러가 실행합니다. 그 후 100번 측정하여 통계적 의미를 확보합니다.
performance.now()는 마이크로초 정밀도를 제공합니다. 세 번째로, 통계 분석이 핵심입니다.
평균(mean)만 보면 안 되고, 중앙값(median)과 꼬리 지연시간(tail latency)인 P95, P99를 확인해야 합니다. 예를 들어, 평균이 1ms이고 P99가 100ms라면, 100번 중 1번은 100ms 걸린다는 뜻으로 사용자 경험에 큰 영향을 미칩니다.
GC가 발생하면 특정 반복에서 급격히 느려져 P99가 튀므로, 이를 통해 GC 영향도 파악할 수 있습니다. profiledBenchmark()는 Chrome DevTools의 프로파일러를 활용합니다.
console.profile()과 console.profileEnd() 사이의 코드를 CPU 프로파일로 기록하여, 어느 함수가 시간을 많이 쓰는지(flame graph), 인라이닝이 발생했는지, 최적화가 실패했는지(deoptimization) 등을 확인할 수 있습니다. 브라우저에서는 Performance 탭에서 더 상세한 타임라인도 볼 수 있습니다.
실무에서는 Benchmark.js 같은 라이브러리를 사용하는 것이 좋습니다. 통계 분석, 여러 구현 비교, 플랫폼별 차이 등을 자동으로 처리해줍니다.
주석에 있는 예제처럼 forEach vs for 같은 미묘한 차이도 정확히 측정할 수 있습니다. 여러분이 이 방법을 적용하면 "premature optimization(조급한 최적화)"을 피하고, 정말 중요한 부분만 최적화할 수 있습니다.
Donald Knuth의 명언처럼 "97%의 시간을 차지하는 작은 비효율은 무시하라. 조급한 최적화는 만악의 근원이다." 하지만 나머지 3%는 프로파일러로 정확히 찾아내야 합니다.
측정하지 않고는 어디가 3%인지 알 수 없습니다.
실전 팁
💡 브라우저와 Node.js의 성능이 다를 수 있습니다. 타겟 환경에서 측정하세요. V8 버전도 성능에 영향을 미칩니다.
💡 마이크로벤치마크는 전체 애플리케이션 성능을 대표하지 않습니다. 실제 사용 시나리오로 종단간(end-to-end) 측정도 필요합니다.
💡 캐시 효과를 고려하세요. 같은 데이터를 반복 접근하면 CPU 캐시에 모두 들어가 비현실적으로 빠를 수 있습니다. 매번 새 데이터를 생성하거나 충분히 큰 데이터셋을 사용하세요.
💡 Node.js에서는 perf (Linux), Instruments (macOS), ETW (Windows) 같은 시스템 프로파일러를 사용하여 캐시 미스율, 브랜치 예측 실패 등 하드웨어 레벨 지표도 확인할 수 있습니다.
💡 A/B 테스트나 feature flag로 프로덕션에서 실제 사용자 데이터로 성능을 비교하세요. 실험실과 현실은 다를 수 있습니다.