[Day 5] 자료구조&알고리즘 2

thru·2023년 6월 7일

FEDC-TIL

목록 보기

4/21

Object Array

오늘 공부한 내용 ⛅

큐와 해시, 그래프에 대한 내용을 학습하고 실습 문제를 하나씩 풀었다.
코테 공부할 때 많이 사용했던 자료구조이다.

새로 알게된 내용 🌱

배열 shift 성능 최적화

배열의 요소가 적을 때는 자바스크립트 엔진이 성능 최적화를 해서 선형 시간과 비슷하게 사용할 수 있다고 한다.

주로 C / C++ 로 구현된 Firefox의 JS 엔진 SpiderMonkey에서는 배열의 시작 주소를 옮김으로써 shift의 성능을 높였다는 것 같고, 크롬의 엔진인 v8도 비슷한 원리로 추측된다.
Firefox에서는 2017년부터 해당 개선점이 적용되었다고 한다.

단, 요소가 50,000개 이상인 배열에 위 방법을 수행하면 이차 배의 시간 복잡도가 나타나기 시작한다고 한다.
이 때문에 일정 길이 이상에서는 기존 방식을 선택하도록 구현되어 있다.

왜 5만개가 넘으면 저런 현상이 나타나는 지에 대해선 찾지 못했지만 메모리 관련 이슈일 것 같다

삼천포 ⚓

자바스크립트의 배열

지난 강의에서 자바스크립트의 배열은 사실상 해시 맵처럼 작동한다고 배웠다.
그런데 이번엔 배열이기 때문에 shift가 느리다는 내용을 배우니 뭔가 개념이 섞인 느낌이라서 내부적으로 어떻게 구현되어있는 지가 궁금했다.

결론부터 말하자면 상황에 따라 다르다

일반적인 배열 용도로 사용했을 때는 엔진의 베이스 언어인 C++의 배열을 기반으로 한다.
따라서 배열이 가지는 특징과 성능을 그대로 가진다.

차이는 자바스크립트만의 배열 특징을 사용할 때 나타난다.
길이를 늘리는 경우 기반 배열이 꽉 찼으면 적절한 메모리 공간을 찾아서 복사를 한뒤 추가한다.

현재 요소들의 것과 다른 타입의 요소를 삽입하면 기반 배열의 타입을 바꿔서 재할당을 하는 것으로 보인다.
배열 타입은 정수, 실수, 객체(포인터)로 나뉘어져 있다.

중간에 빈 요소를 만들면 hole이라는 값으로 빈 인덱스를 채운다.
그런데 요소를 너무 띄엄띄엄 배치하면 기반이 배열이 아닌 dictionary/hashtable로 변형되어 탐색과 순회의 성능이 하락한다.

shift에서도 볼 수 있듯이, 최적화 작업은 중간중간에 유연성과 성능을 복합적으로 보장하기 위해 겉으로는 보이지 않는 곳에서 엔진 개발자들이 설정한 기준에 따라 이루어진다.

자바스크립트의 배열이 자유롭게 사용할 수 있다고 하더라도 성능을 위해선 막 쓰면 안된다

자바스크립트 엔진

자바스크립트 자체로는 동작법이 정의되어 있는 것이 아니라 ECMAScript에서 제시하는 명세에 따라 각각의 자바스크립트 엔진이 동작법을 구현한다.

Day 2 에서 보았던 내용인 것 같은데 그 땐 너무 가볍게 넘겨버린 것 같다.

대표적으로 v8 엔진이 있는데 크롬에서만 사용하는 것이 아니라 자바스크립트 런타임 환경인 Node.js에서도 사용한다.

과거의 자바스크립트는 한 줄 한 줄 코드를 실행하는 인터프리터 언어였지만 v8 엔진이 자바스크립트의 성능을 높이기 위해 Just-in-time(JIT) 컴파일을 도입하면서 더이상 인터프리터 언어라고 말하기 어려워졌다.

🔺자바스크립트의 JIT 컴파일 과정

JIT의 과정은 기존의 컴파일 언어의 실행 과정과 거의 비슷하다.

단, 중간 과정에서 만들어지는 머신코드가 Portable file의 형태로 전달되는 것이 아닌 엔진 내부에서만 존재한다.
또한, 컴파일된 머신코드가 실행되기 전에 인터프리터가 코드를 실행해서 컴파일 이전에도 기능이 나타날 수 있도록 이중으로 실행 과정이 나뉜다.

컴파일이 완료되면 인터프리터의 코드는 컴파일된 코드로 프로그램 실행 중에 변경된다.
컴파일된 코드는 인터프리터의 코드보다 최적화되어있기 때문에 일반적인 인터프리터 언어의 프로그램보다 높은 성능으로 돌아갈 수 있다.

속도가 느려서 불만인가? 듀얼이다!

느낀점 🎬

오늘은 내용 자체는 양이 적으니 빨리 쓰고 다른 활동도 계획해봐야겠다고 생각했는데 array shift의 원리를 알아보기 위해 여기저기 찾고 구현 코드도 ~~알아보진 못하지만~~ 살펴보고 하다보니 시간이 훨씬 많이 소모된 것 같다.
그래도 내가 얼마나 자바스크립트 접시물에서 놀고 있었는지 반성하게되는 시간으로 느껴졌다. 책이든 포스팅이든 보면서 깊게 깊게 들어가고 싶다.