번뜩이는 빠른 파싱, 1부: 스캐너 최적화
JavaScript 프로그램을 실행하려면 V8이 이를 이해할 수 있도록 소스 텍스트를 처리해야 합니다. V8은 먼저 소스를 추상 구문 트리(AST)로 파싱합니다. AST는 프로그램 구조를 나타내는 객체 집합입니다. Ignition이 이 AST를 바이트 코드로 컴파일합니다. 이러한 파싱 + 컴파일 단계의 성능은 중요합니다. 컴파일이 완료되기 전에 V8은 코드를 실행할 수 없습니다. 이 블로그 게시물 시리즈에서는 파싱과 V8에서 초고속 파서를 제공하기 위해 수행한 작업에 대해 집중적으로 다룹니다.
사실, 우리는 파서 한 단계 이전부터 시리즈를 시작합니다. V8의 파서는 '스캐너'가 제공하는 '토큰'을 소비합니다. 토큰은 문자열, 식별자, ++와 같은 연산자 등 단일 의미를 가진 하나 이상의 문자 블록입니다. 스캐너는 기본 문자 스트림에서 연속적인 문자를 결합하여 이러한 토큰을 구성합니다.
스캐너는 Unicode 문자 스트림을 소비합니다. 이러한 Unicode 문자는 항상 UTF-16 코드 유닛 스트림에서 디코딩됩니다. 다양한 인코딩에 대해 스캐너와 파서를 분기하거나 특수화하는 것을 피하기 위해 단일 인코딩만 지원하며, JavaScript 문자열 인코딩이 바로 UTF-16이기 때문에 이를 선택했습니다. 소스 위치는 해당 인코딩과 상대적으로 제공되어야 합니다. UTF16CharacterStream은 Chrome이 네트워크에서 얻은 Latin1, UTF-8 또는 UTF-16 인코딩에서 V8이 받는 것을 (버퍼링된) UTF-16 뷰로 제공합니다. 여러 인코딩을 지원하는 것 외에도 스캐너와 문자 스트림 사이의 분리는 V8이 전체 소스가 사용 가능하지 않더라도 데이터의 일부만 네트워크를 통해 받은 경우에도 마치 전체 소스를 스캔하는 것처럼 투명하게 스캔할 수 있게 합니다.
스캐너와 문자 스트림 간의 인터페이스는 Utf16CharacterStream::Advance()라는 메서드로, 다음 UTF-16 코드 유닛이 반환되거나, 입력의 끝을 표시하기 위해 -1이 반환됩니다. UTF-16은 모든 Unicode 문자를 한 코드 유닛으로 인코딩할 수 없습니다. 기본 다국어 평면 외의 문자는 두 개의 코드 유닛(서로게이트 페어)으로 인코딩됩니다. 하지만 스캐너는 UTF-16 코드 유닛이 아닌 Unicode 문자로 작업하므로, 이 저수준 스트림 인터페이스를 Unicode 문자로 디코딩하는 Scanner::Advance() 메서드로 포장합니다. 현재 디코딩된 문자는 버퍼링되고 Scanner::ScanString()과 같은 스캔 메서드에서 수집됩니다.
스캐너는 JavaScript에서 가장 긴 애매한 문자 시퀀스1인 최대 4개의 문자를 보고 특정 스캐너 메서드나 토큰을 선택합니다. ScanString과 같은 메서드가 선택되면 해당 토큰에서 나머지 문자를 사용하고, 토큰에 속하지 않는 첫 번째 문자를 다음 스캔된 토큰을 위해 버퍼링합니다. ScanString의 경우에는 이스케이프 시퀀스를 디코딩하면서 스캔된 문자를 Latin1 또는 UTF-16으로 인코딩된 버퍼에 복사하기도 합니다.
공백 문자
토큰은 공백 문자(예: 개행, 스페이스, 탭, 한 줄 주석, 여러 줄 주석 등)로 구분될 수 있습니다. 하나의 공백 유형 다음에 다른 공백 유형이 올 수 있습니다. 공백은 두 토큰 사이에 줄 바꿈이 발생하면 의미를 추가합니다: 이는 자동 세미콜론 삽입을 유발할 수 있습니다. 따라서 다음 토큰을 스캔하기 전에, 새 줄이 발생했는지 추적하면서 모든 공백을 건너뜁니다. 대부분의 실제 프로덕션 JavaScript 코드는 압축되어 있어서 다중 문자 공백은 다행히도 흔하지 않습니다. 이러한 이유로 V8은 각 유형의 공백을 일반 토큰처럼 개별적으로 균일하게 스캔합니다. 예를 들어, 첫 번째 토큰 문자가 /이고 뒤에 또 다른 /가 있다면, V8은 이를 Token::WHITESPACE를 반환하는 한 줄 주석으로 스캔합니다. 이 루프는 다른 토큰을 찾을 때까지 단순히 토큰 스캔을 계속합니다. 이것은 다음 토큰 앞에 공백이 없다면 즉시 적절한 토큰 스캔을 시작하며, 공백 여부를 명시적으로 확인할 필요가 없음을 의미합니다.
그러나 이 루프 자체는 스캔된 각 토큰에 오버헤드를 추가합니다: 우리가 방금 스캔한 토큰을 확인하는 분기를 요구합니다. 방금 스캔한 토큰이 Token::WHITESPACE일 수 있는 경우에만 루프를 계속하는 것이 더 나을 것입니다. 그렇지 않은 경우, 우리는 단순히 루프를 탈출해야 합니다. 이것은 루프 자체를 별도의 도우미 메서드로 이동하여 실행됩니다. 여기에서, 토큰이 Token::WHITESPACE가 아님이 확실한 경우 즉시 반환합니다. 이러한 종류의 변경 사항이 매우 사소하게 보일 수 있지만, 이는 각 스캔된 토큰의 오버헤드를 제거합니다. 특히 구두점과 같은 매우 짧은 토큰에 대해 차이를 만듭니다:
식별자 스캔
가장 복잡하지만 가장 일반적인 토큰은 식별자 토큰으로, 이는 JavaScript에서 변수 이름(기타 항목 포함)을 위해 사용됩니다. 식별자는 Unicode 문자의 속성인 ID_Start로 시작하고, 선택적으로 ID_Continue 속성을 가진 문자 시퀀스로 이어집니다. Unicode 문자가 ID_Start 또는 ID_Continue 속성을 가지는지 여부를 확인하는 것은 상당히 비용이 많이 듭니다. 캐시를 추가하여 문자에서 속성으로 매핑을 설정하면 이를 조금 더 빠르게 만들 수 있습니다.
그러나 대부분의 JavaScript 소스 코드는 ASCII 문자를 사용하여 작성됩니다. ASCII 범위의 문자 중, a-z, A-Z, $ 및 _만이 식별자 시작 문자입니다. ID_Continue는 추가로 0-9를 포함합니다. 각 ASCII 문자에 대해 해당 문자가 ID_Start인지, ID_Continue 문자인지 등을 나타내는 플래그가 있는 표를 생성하여 식별자 스캔을 가속화합니다. 우리가 보는 문자가 ASCII 범위 내에 있는 동안, 이 표에서 각각의 플래그를 조회하고 단일 분기로 속성을 확인합니다. ID_Continue 속성이 없는 첫 번째 문자를 볼 때까지 문자는 식별자의 일부입니다.
이 포스트에서 언급된 모든 개선 사항은 식별자 스캔 성능에서 다음과 같은 차이를 만듭니다:
더 긴 식별자가 더 빨리 스캔되는 것이 직관적이지 않을 수 있습니다. 이는 식별자 길이를 늘리는 것이 성능에 이점이 있다고 생각하게 만들 수 있습니다. 더 긴 식별자를 스캔하는 것은 단순히 MB/s 관점에서 더 빠르며, 파서로 돌아가지 않고 매우 타이트한 루프 내에 더 오래 머물기 때문입니다. 그러나 애플리케이션 성능 관점에서 중요한 것은 전체 토큰을 얼마나 빨리 스캔할 수 있는지입니다. 다음 그래프는 토큰 길이에 비례하여 우리가 초당 스캔하는 토큰 수를 대략적으로 보여줍니다:
여기서 더 짧은 식별자를 사용하는 것이 애플리케이션의 파싱 성능에 유리하다는 것이 분명해집니다: 우리는 초당 더 많은 토큰을 스캔할 수 있습니다. 이는 MB/s 측면에서 더 빨리 파싱되는 것처럼 보이는 사이트가 실제로는 정보 밀도가 낮고, 초당 생성되는 토큰이 적음을 의미합니다.
압축된 식별자의 내부화
모든 문자열 리터럴과 식별자는 스캐너와 파서의 경계에서 중복 제거됩니다. 파서가 문자열이나 식별자의 값을 요청하면, 가능한 각 리터럴 값에 대해 고유한 문자열 객체를 받습니다. 이것은 일반적으로 해시 테이블 조회를 필요로 합니다. JavaScript 코드가 종종 압축되어 있기 때문에, V8은 단일 ASCII 문자 문자열에 대해 단순 조회 테이블을 사용합니다.
키워드
키워드는 언어에서 정의된 식별자의 특별한 하위 집합으로, if, else, function 등이 있습니다. V8의 스캐너는 키워드에 대해 식별자와 다른 토큰을 반환합니다. 식별자를 스캔한 후에는 해당 식별자가 키워드인지 인식해야 합니다. JavaScript의 모든 키워드에는 a-z 소문자만 포함되어 있으므로, ASCII 문자가 키워드 시작 및 지속 문자일 가능성을 나타내는 플래그를 유지합니다.
플래그에 따라 식별자가 키워드일 수 있는 경우, 식별자의 첫 번째 문자에 따라 키워드 후보의 하위 집합을 찾을 수 있습니다. 식별자보다 키워드의 길이가 더 적으므로, 후속 분기의 수를 줄입니다. 각 문자에 대해, 가능한 키워드 길이를 기반으로 분기하고, 길이도 일치하는 경우에만 식별자와 키워드를 비교합니다.
완벽 해싱이라는 기법을 사용하는 것이 더 좋습니다. 키워드 목록이 고정되어 있으므로, 각 식별자에 대해 최대 하나의 후보 키워드를 제공하는 완벽 해시 함수를 계산할 수 있습니다. V8은 이 함수를 계산하기 위해 gperf를 사용합니다. 결과는 길이와 첫 두 문자로 해시를 계산하여 단일 후보 키워드를 찾습니다. 우리는 키워드의 길이가 입력 식별자의 길이와 일치할 때만 식별자를 키워드와 비교합니다. 이는 특히 식별자가 키워드가 아닌 경우 브랜치 수를 줄여 더 빠르게 결과를 알아내므로 성능이 향상됩니다.
서러게이트 페어(Surrogate pairs)
앞서 언급했듯이, 스캐너는 UTF-16로 인코딩된 문자 스트림에서 동작하지만 유니코드 문자들을 처리합니다. 보조 평면(supplementary planes)에 있는 문자는 식별자 토큰에만 특별한 의미를 가집니다. 예를 들어, 문자열에 그러한 문자가 나타나더라도 문자열을 종료시키지 않습니다. JS는 고립된 서러게이트(lone surrogate)를 지원하며, 소스에서 단순히 복사합니다. 이러한 이유로 서러게이트 페어를 결합하려고 하지 않고, 스캐너가 유니코드 문자 대신 UTF-16 코드 단위에서 직접 작동하도록 하는 것이 좋습니다. 문자열을 스캔할 때, 우리는 서러게이트 페어를 찾거나 결합하거나 나중에 이를 분리하여 리터럴을 생성할 필요가 없습니다. 스캐너가 서러게이트 페어를 처리해야 하는 경우는 오직 두 가지가 남아있습니다. 토큰 스캔 시작 시, 다른 방식으로 문자를 인식하지 못하면 서러게이트 페어를 결합하여 결과가 식별자 시작인지 확인해야 합니다. 마찬가지로, 비-ASCII 문자들을 처리하는 식별자 스캔의 느린 경로에서도 서러게이트 페어를 결합해야 합니다.
AdvanceUntil
스캐너와 UTF16CharacterStream 간의 인터페이스는 경계를 꽤 상태 지향적으로 만듭니다. 스트림은 버퍼에서 자신의 위치를 추적하며, 소비된 코드 단위마다 이를 증가시킵니다. 스캐너는 요청한 문자를 받기 전에 코드를 임시 저장(buffering)한 후 스캔 메서드로 돌아갑니다. 해당 메서드는 버퍼에 저장된 문자를 읽고 그 값에 따라 계속 진행합니다. 이는 좋은 계층화를 제공하지만 비교적 느립니다. 작년 가을, 우리 인턴 Florian Sattler는 계층화의 이점을 유지하면서 스트림에서 코드 단위에 훨씬 더 빠르게 접근할 수 있는 향상된 인터페이스를 생각해냈습니다. 템플릿화된 함수 AdvanceUntil는 특정 스캔 헬퍼에 맞게 특화되며, 헬퍼가 false를 반환할 때까지 스트림의 각 문자에 대해 호출됩니다. 이는 본질적으로 추상화를 깨지 않고 스캐너가 기본 데이터를 직접 사용할 수 있도록 합니다. 실제로 EndOfInput을 다룰 필요가 없어 스캔 헬퍼 함수가 간단해집니다.
AdvanceUntil은 많은 문자들을 소비해야 할 수 있는 스캔 함수들의 속도를 높이기에 특히 유용합니다. 우리는 앞서 이미 식별자의 성능을 향상시키기 위해 이를 사용했으며, 문자열2 및 주석에서도 사용했습니다.
결론
스캔 성능은 파서 성능의 초석입니다. 우리는 스캐너를 최대한 효율적으로 조정했습니다. 이는 전반적으로 약 1.4배의 단일 토큰 스캔 성능, 1.3배의 문자열 스캔 성능, 2.1배의 다중 라인 주석 스캔 성능, 그리고 식별자 길이에 따라 1.2~1.5배의 식별자 스캔 성능을 향상시키는 결과를 가져왔습니다.
그러나 우리 스캐너가 할 수 있는 것은 한계가 있습니다. 개발자로서 프로그램의 정보 밀도를 높임으로써 파싱 성능을 더욱 향상시킬 수 있습니다. 가장 쉬운 방법은 소스 코드를 축소(minify)하고, 불필요한 공백을 제거하며, 가능하다면 비-ASCII 식별자를 피하는 것입니다. 이상적으로는 이러한 단계가 빌드 프로세스의 일부로 자동화되어 코드 작성 시 이를 신경 쓸 필요가 없어야 합니다.