1. 공간복잡도란,
프로세스가 동작하면서 사용하는 메모리의 총량을 의미한다. ( 선언한 변수 byte + 동적으로 사용되는 byte)
1) Stack과 Heap 저장공간
일반적인 메모리의 공간은 Stack과 Heap으로 나뉘어진다. Javascript에서는 두 공간을 어떻게 사용할까?
Stack에는 원시값(const)와 객체의 참조변수가 저장되고 Heap에는 객체의 데이터가 저장된다.
1-1) 원시값
아래와 같이 선언된 변수들은 Stack에 쌓이게 된다.
const name = 'hklee'
const age = 33
const isMale = true1-2) 객체
아래와 같이 선언된 변수들은 참조변수는 Stack에 쌓이고 데이터는 Heap에 쌓인다.
// res(stack) ----> ['1', '2', '3'](heap)
const res = ['1', '2', '3']
// name(stack) ----> LeeHunKyu(heap)
let name = 'LeeHunKyu'하지만 Heap의 경우 변수에 새로운 값을 할당하게 되면 Heap에 새로운 변수 영역을 할당받아 Stack의 참조를 변경하게 된다.
// name(stack) ----> LeeHunKyu(heap)
let name = 'LeeHunKyu'
// LeeHunKyu(heap)
// name(stack) ----> hklee(heap)
name = 'hklee'Reference가 없어진 Heap영역의 메모리는 가비지 컬렉션에 의해서 메모리가 해제된다.
가비지 컬렉션이 동작을 하는 트리거나 주기에 대한 정보를 찾지 못했지만, 위 내용을 토대로 판단해보면 Array에 새로운 변수를 할당하게 된다면 일시적으로라도 메모리 사용량이 증가할 수 있을것 같습니다.
하지만 C++의 경우에 smart pointer라는 개념이 있기 때문에 javascript engine에서도 동일하게 변수의 reference가 끊기게 되면 자동으로 메모리가 delete되지 않을까 예상됩니다. Java의 가비지 컬렉션의 동작방식으로 생각하지 않은 이유는 JVM 위에서 동작하는 Java의 방식보다는 v8이 C++로 구현되어 있기 때문에 smart pointer개념이 더 맞지 않을지 추측했습니다.
Javascript 가비지 컬렉션에 대한 설명링크는 아래와 같습니다.
https://developer.mozilla.org/ko/docs/Web/JavaScript/Memory_Management
2. Javascript Array Function 살펴보기
ECMAScript에서 구현되어 있는 함수를 사용할 때, 메모리 영역을 어떻게 사용하는지와 공간복잡도를 계산할 때 함수 선택을 고민해야하는지 살펴본다.
1) Array.prototype.slice()
const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];
console.log(animals.slice(2));
// expected output: Array ["camel", "duck", "elephant"]slice함수는 기존의 참조를 수정하지 않고 새로운 메모리 공간을 할당하여 주소를 전달해준다. (shallow copy)
// https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.slice
...
6. Else, let k be min(relativeStart, len).
...
10. Else, let final be min(relativeEnd, len).
11. Let count be max(final - k, 0).
12. Let A be ? ArraySpeciesCreate(O, count).
...
내부 구현 슈더코드를 살펴보면 새로운 메모리를 할당하는 크기는 return될 array의 크기 만큼이다.
(end - start) 혹은 (전체길이 - start)
2) Array.prototype.splice()
const months = ['Jan', 'March', 'April', 'June'];
months.splice(1, 0, 'Feb');
// inserts at index 1
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "April", "June"]slice함수는 기존의 참조를 수정하기 때문에 원본이 바뀌게 된다.
// https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.splice
Array.prototype.splice ( start, deleteCount, ...items )
...
4. If relativeStart is -∞, let actualStart be 0.
5. Else if relativeStart < 0, let actualStart be max(len + relativeStart, 0).
6. Else, let actualStart be min(relativeStart, len).
10. Else,
a. Let dc be ? ToIntegerOrInfinity(deleteCount).
b. Let actualDeleteCount be the result of clamping dc between 0 and len - actualStart.
11. If len + itemCount - actualDeleteCount > 253 - 1, throw a TypeError exception.
12. Let A be ? ArraySpeciesCreate(O, actualDeleteCount).
...
해당 함수에서 실제로 데이터를 할당받는 범위는 array에서 삭제되어서 return될 크기 만큼이다. 기존 함수는 property를 변경하기 때문에 추가적인 메모리를 사용하지 않는 것으로 파악된다.
const months = ['Jan', 'March', 'April', 'June'];
console.log(months.splice(1, 3));
// expected output: Array ['March', 'April', 'June']이외에 ArraySpeciesCreate 키워드로 슈더코드들을 살펴보니 array function의 return 값으로 array를 돌려주는 함수들의 경우에만 return될 length만큼 array를 만드는 것으로 파악되었습니다.
3. 결론
javascript에서 공간복잡도를 고려할 때, javascript array에서 제공하는 함수 구현 내부 동작 중에 메모리 남용(?)에 대해서 고민하지 않아도 된다. javascript heap영역에 새로이 할당되는 메모리는 return되는 메모리와 동일하다.
다만 ECMAScript슈더코드에서 보이듯 return 되는 함수를 사용할 경우 새로운 메모리 영역을 반복해서 할당받게 되므로 메모리 최적화를 하고자 한다면 기존의 메모리 상에서 데이터 조작을 하는게 올바른 접근이다.
추가적으로 시간복잡도는 개별 함수별로 상이하기 때문에 상황에 맞게 함수를 선택하거나 직접 index를 조작하여 최적화를 하는 것이 좋겠다.
Reference
- stack and heap https://felixgerschau.com/javascript-memory-management/#the-memory-heap-and-stack
- smart pointer http://www.tcpschool.com/cpp/cpp_template_smartPointer
- javascript array https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array
- ECMAScript document https://tc39.es/ecma262/multipage/indexed-collections.html