[JSC] Iterate Strings without allocating a JSStringIterator

Component: JSC bytecode / LLInt, Baseline, DFG | 5330149

JSTests/stress/for-of-fast-string-and-iterator-with-known-structure.js

+ function* first() { yield "a"; yield "b"; yield "c"; }
+ function* second() { yield "a"; yield "b"; yield "c"; }
+ const withGenerator = { [Symbol.iterator]: first };
+
+ function collect(iterable) { let seen = []; for (let x of iterable) seen.push(x); return seen.join(); }
+ function breakAtTwo(iterable) { let seen = []; for (let x of iterable) { seen.push(x); if (seen.length === 2) break; } return seen.join(); }
+ function firstTwo(iterable) { let [a, b] = iterable; return a + "," + b; }
...
+ for (let iterable of ["abc", withGenerator]) {
+     shouldBe(collect(iterable), "a,b,c");
+     shouldBe(breakAtTwo(iterable), "a,b");
+     shouldBe(firstTwo(iterable), "a,b");
+ }

ES의 iteration은 보통 iterable[Symbol.iterator]()를 호출해 iterator 객체를 얻는 것으로 시작합니다. 이후 매 단계마다 해당 객체의 next 메서드를 호출하고, 루프를 중간에 빠져나갈 때는 return 메서드를 호출합니다.

한편 JSC에는 FastArray, FastString 같은 fast mode가 있습니다. built-in iterator prototype이 변경되지 않은 동안에는, 이 mode에서 iterator 객체가 외부에서 관찰되지 않습니다. 이 전제가 여전히 유효한지는 stringIteratorProtocolWatchpointSet 같은 watchpoint set이 추적합니다.

FastArray는 이미 iteration 상태를 bytecode register에 보관하고 있었습니다. iterator에는 sentinel 값이, next에는 index가, iterable에는 배열이 들어가는 식입니다. 이번 commit은 같은 기법을 문자열에도 적용했습니다.

이제 FastString mode에서 String에 대해 for-of나 destructuring을 수행하더라도, LLInt, Baseline, DFG 어느 tier에서도 JSStringIterator를 allocate하지 않도록 변경되었습니다. 먼저 iterator register에는 문자열 전용 sentinel이 저장되고, next에는 현재 index가 Int32로 저장됩니다. iterable에는 이전과 마찬가지로 문자열이 그대로 남습니다.

op_iterator_next와 op_iterator_close_check는 iterator를 먼저 Array sentinel과 비교하고, 이어서 String sentinel과 비교합니다. 루프를 닫는 시점에 stringIteratorProtocolWatchpointSet이 이미 무효화된 상태라면, 실제 JSStringIterator를 생성해 return을 조회할 수 있게 했습니다.

Before (FastString):                     After (FastString):
  iterator_open                            iterator_open
    └─► alloc JSStringIterator                 ├─► iterator = fastStringSentinel
        iterator = JSStringIterator            ├─► next     = Int32(0)
        next     = cached next fn              └─► iterable = JSString
  iterator_next                            iterator_next
    └─► call/inline next(iterator)             ├─► iterator == arraySentinel?  -> array path
        (reads iterator's string+index)        ├─► iterator == stringSentinel? -> index++ (no alloc)
  iterator_close_check                         └─► else -> generic call
    └─► return absent (watchpoint valid)     iterator_close_check
                                               └─► iterator == stringSentinel?
                                                    ├─► watchpoint valid   -> skip close
                                                    └─► watchpoint invalid -> materialize
                                                        JSStringIterator, run generic close

Significance

문자열 루프마다 발생하던 heap allocation이 한 번씩 줄어들었습니다. 그 결과 문자열 iteration microbenchmark에서 1.06x~1.29x의 속도 향상이 확인되었습니다.

FastArray 설계가 두 번째 iterable 타입으로 확장되면서, sentinel과 register 상태 invariant에 의존하는 bytecode·JIT 경로가 더 늘어났습니다. 원래 callable과 iterator 객체를 담던 register에 이제 sentinel과 raw integer가 들어갑니다. 따라서 interpreter, 두 JIT tier, DFG parser, GC, OSR entry/exit가 모두 이 encoding을 동일하게 해석해야 합니다.

Audit directions

이번 변경은 LLInt (LowLevelInterpreter64.asm), Baseline (JITCall.cpp), DFG (DFGByteCodeParser.cpp)의 register 의미를 한꺼번에 바꿨습니다. 게다가 변경 대상이 보안상 민감한 type assumption 영역이라는 점에서 주의가 필요합니다.

next와 iterator register를 읽는 지점. 이 register를 읽으면서 callee나 객체라고 가정하는 곳을 살펴볼 필요가 있습니다. OSR exit/entry 시의 상태 재구성, DFG value profiling, 그리고 sentinel 비교를 모두 통과하지 못해 next를 호출하는 경로가 대상입니다. raw Int32나 sentinel이 호출 대상이 되거나 JSCell cast에 도달한다면 type confusion에 해당합니다.
JSStringIterator의 lazy materialization. 루프 도중 watchpoint가 fire된 상태에서 op_iterator_close_check가 실행되면 iterator가 다시 생성됩니다. 이때 재생성된 iterator의 index와 문자열은 register 상태와 일치해야 합니다. tier 간 OSR이 일어난 뒤에도 마찬가지입니다. osr-late-close와 fresh-realm 테스트는 문제가 예상되는 지점을 드러냅니다.
Sentinel lifetime과 GC visiting. VM::visitAggregateImpl에서 fastStringSentinel이 fastStringValuesSentinel을 대체한 부분을 확인해야 합니다. 또한 이 sentinel이 Array sentinel로 오인되거나, 다른 realm에서 실제 값으로 착각될 여지가 있는지도 점검이 필요합니다.
Index 처리. 긴 문자열이나 rope 문자열에 대한 Int32 index 처리를 살펴볼 필요가 있습니다. iteration 도중의 rope resolution, surrogate pair 단위 이동, wide operand bytecode variant도 함께 점검 대상입니다.
DFG의 multi-kind 호출 지점. 하나의 site가 여러 iterable 종류를 관찰하는 경우(handleIteratorOpen/handleIteratorNext), String 처리와 함께 inlined generator iteration으로 변환되는 과정을 확인해야 합니다. 이와 함께 invalidation 이후에도 speculation과 watchpoint 가정이 일관되게 유지되는지 점검할 필요가 있습니다.