V8 분석하기 - 문자열

V8의 코드를 보며 문자열을 어떻게 관리하는지 작성하였다.

문자열은 기본적으로 1바이트 배열 / 2바이트 배열로 구분된다. 대부분의 경우 효율을 위해 1바이트를 사용하되, 표현 불가능한 문자가 포함되어 있으면 2바이트로 전환한다.

• 유니코드 처리를 다른 언어들, 예를 들면 Go는 rune, Rust는 grapheme처럼 별도의 타입이 존재하고 개발자가 이를 신경써야 하는 경우가 많다. 혹은 UTF-8처럼 가변 길이 인코딩을 써서 문자열 랜덤 액세스가 $O(N)$이거나...
• 이와 달리 JS에선 유니코드 문자열에 고통받을 일을 크게 줄였다. 개인적으로 다른 언어들에 비하면 평범한 개발자에게 매우 친화적인 구현이라고 생각한다. 물론 반대로 말하면 개발자의 선택권이 제약된단 뜻이기도 하고, 다음처럼 지식이 요구되는 상황이 종종 등장하기도 한다.
• 우선 1바이트는 당연히 ASCII고, 2바이트는 UCS-2 문자열이다. 그런데 '\u{1F600}' ('😀')와 같이 2바이트로 표현 불가능한 문자는 '\uD83D\uDE00' 처럼 변환되어 저장된다. (Surrogate pair)
• 때문에 크롬이나 Node에서 '😀'[0]을 해보면 '\uD83D'가 나오는 모습을 볼 수 있다. 글자는 하나이고, 길이는 2이며, 4바이트로 표현되는 셈이다. 아무튼 이것때문에 인코딩을 잘 다뤄야 하는 상황에선 생각할 게 많아진다고 하는데... 그런 상황에 마주칠 일은 적을 것 같긴 하다.
• SpiderMonkey 개발진에 따르면, 2014년 당시 중국 사이트 중 트래픽 상위 10위까지를 방문했을 때, 2바이트 문자열은 전체 문자열에서 28%만을 차지했다고 한다.
• 아래에서 kMinLength는 상수로 정의되어 있으며, 값은 13이다.

문자열 concat은 두 문자열의 길이 합이 kMinLength 미만이면 복사해서 새 문자열을 만들고, 이상이면 그냥 두 문자열의 주소를 이진 트리처럼 이은 ConsString을 만든다.

• 이러면 연산 자체는 시간복잡도와 공간복잡도가 $O(1)$이므로 자주 사용하는 연산인 문자열 덧셈을 무지성으로 사용해도 된다는 것, 그리고 복사된 새 문자열을 만드는 것에 비해 메모리 사용량을 절감할 수 있단 게 장점이다.
• 후자는 1과 시너지를 일으키는데, 1바이트 문자열과 2바이트 문자열을 합칠 때 1바이트 문자열을 2바이트로 확장하지 않아도 되기 때문이다.
• 단점은 물론 $K$개의 문자열이 이어져 있을 때, 인덱스를 통한 랜덤 접근이 $O(K)$라는 것이다. 예를 들어 다음 코드는 M1 맥북 에어에서 약 45초가 걸린다.

  

• 다만 위는 극단적인 케이스이고, 일반적으론 중간중간에 문자열이 펴지는(Flatten) 연산도 일어나기 마련이라 문자열 덧셈과 랜덤 액세스만 극도로 하는 상황은 잘 없긴 하다.
• Flatten 메서드는 문자열 리스트가 주어질 경우 일자로 편 일반 문자열(복사본)을 반환한다. 당연하지만 펼 필요가 없는, 리스트가 아닌 문자열이 주어지면 복사도 안 일어나고 아무 작업도 안 한다.
  • 내부적으로 SlowFlatten 함수를 실행한다.

문자열 substring은 추출할 구간의 크기가 kMinLength 미만이면 복사해서 새 문자열을 만들고, 이상이면 그냥 해당 문자열의 주소와 시작 인덱스, 길이를 저장한 SlicedString을 만든다.

• 2와 마찬가지로 시간복잡도와 공간복잡도가 $O(1)$이란 점은 참 매력적이다. 하지만 독립적인 사본이 아닌, 원본 문자열을 가리키는 slice를 만드는 것이라 GC가 원본을 건드릴 수 없는 게 단점이다.
• 즉 원본이 수백MB ~ 수십GB쯤 되는 문자열이고 거기서 일부분만 추출해 쓰려는 상황에서 메모리 사용량이 치솟게 된다. 만약 큰 텍스트를 많이 활용하는 프로그램을 짜려고 한다면 상당히 문제가 된다.
• 본인도 로그 파일 분석을 하려고 JS를 썼었는데, 10GB씩 메모리를 잡아먹더니 크래시가 나 그냥 Go로 다시 짠 경험이 있다... 엔진에서 끼워넣는 마법이 대체로 일반 사용자들을 타겟으로 하다 보니, 무거운 작업을 하기엔 비대한 메모리 사용량, 아주 빠르진 못한 속도에 발목을 잡히는 게 아쉽다.

IndexOf와 같은 문자열 검색은 기본적으로 문자열을 Flatten한 뒤 Boyer–Moore–Horspool 알고리즘을 쓴다. 참고로 practical하게 자주 사용되는 알고리즘은 다음 사진과 같다. (사진엔 안 나와있는데 BNDM과 BOM은 공간복잡도가 $O(m)$인 걸로 안다.)

• 구현은 다음처럼 되어 있다.
  1. 패턴의 길이가 1이면 따로 구현된 단순 탐색을 시도한다.
  2. 패턴의 길이가 6 이하면 평범한 단순 탐색을 시도한다.
  3. 그 외의 경우 평범한 단순 탐색을 시도하다가, 문자를 읽어들인 횟수가 $4m + 10$번 이상이 될 때까지 찾지 못했다면, BMH로 알고리즘을 전환한다.
  4. 만약 BMH에서도 문자를 읽어들인 횟수가 $m$번 이상(알고리즘을 이해 못해서 정확하지 않음)일 때까지 찾지 못했다면, Boyer-Moore로 전환한다.
• C의 strstr과 파이썬의 .find, 러스트의 Pattern은 Two-Way를 사용한다.
• Go의 strings.Index는 라빈 카프를 사용한다.
• Go의 strings.Replacer와 지금 보고 있는 V8의 JS는 Boyer-Moore를 사용한다.
• 대체로 공간복잡도가 $O(1)$ 내지는 알파벳의 범위 $k$에 대해 $O(k)$인 알고리즘을 선호하는 것을 알 수 있다.

ToNumber 함수는 이름 그대로 문자열을 수로 변환한다.

• 구현은 다음처럼 되어 있다.
  1. 첫 글자가 이상하면 즉시 NaN을 반환한다.
  2. 10자 미만의 정수로 확인되면 바로 Smi (Small integer)로 던진다.
  3. 그 외의 경우 느리지만 복잡한 케이스도 처리하는 StringToDouble 함수로 변환을 진행한다.
• 궁금한 점 - 예외처리나 지원하는 문자열의 종류가 굉장히 많은데, 입력이 어떻게 들어올지 알고 있다면 JS에서 직접 구현해 쓰는 게 빠를 수도 있을까?
  • StringToDouble과 비교했을 때, 또 그냥 Smi 변환과 비교했을 땐 어떤지 확인해보자

ComputeAndSetHash 함수는 문자열을 해싱하고 값을 저장해둔다. 해당 문자열을 key로 사용해 해시 테이블에 접근할 때 속도 개선을 위해 사용하는 것 같다. (Set/Map, 객체 property 접근 등에 사용될 것으로 추정)

• Flat하지 않은 문자열에는 사용 불가능한 것으로 보인다. 호출하는 쪽에서 ConsString이면 Flatten을 하고 써야 하는 걸까?
• 구현은 다음처럼 되어 있다.
  1. 문자열의 길이가 kMaxHashCalcLength (16383)을 초과하면 따로 해시를 계산하지 않고 길이를 해시로 사용한다.
  2. 문자열이 array index인 경우 정수를 파싱한 뒤 MakeArrayIndexHash(index)를 반환한다.
  3. 아니라면 Jenkins one_at_a_time 해시 함수를 사용해 해시값을 계산한다.
     • HashSeed(GetReadOnlyRoots())로 시드를 구해 초기값으로 사용하는데, 해시를 예측하기 어렵게 만들기 위한 것으로 보인다. 사전에 해시값이 충돌하는 문자열을 구해두고 공격한 케이스가 있었을까, 아니면 그냥 해시 퀄리티를 위한 것뿐일까?
     • 시스템이 64비트이고 문자열이 integer index인 경우 다음과 같은 약간의 작업을 거친다.

hash |= 1;
// The hash accidentally looks like a cached index. Fix that by setting a bit that looks like a longer-than-cacheable string length.
if (Name::ContainsCachedArrayIndex(hash))
    hash |= (String::kMaxCachedArrayIndexLength + 1) << String::ArrayIndexLengthBits::kShift;

ConsString이 Flatten되는 연산들: (정리 예정)

• 버전이나 환경에 따라 언제든 동작이 바뀔 수 있으니 주의해야 한다. 나도 당했다...

읽어볼만한 글

• https://blog.mozilla.org/javascript/2014/07/21/slimmer-and-faster-javascript-strings-in-firefox/
• https://gist.github.com/badboy/6267743