replace 技術細節、性能影響因素
介紹
字符串是 JavaScript 中的重要數據類型，其重要性不僅體現在字符串是應用最多最廣泛的數據類型，更體現在V8中使用了大量的技術手段來修飾和優化字符串的操作。接下來的幾篇文章將集中講解字符串的相關操作。本文先講解 String.prototype.replace 的源碼以及相關數據結構，再通過測試用例演示 String.prototype.replace 的調用、加載和執行過程。我們會看字符串的類型、長度等因素如何影響 replace 的實現方式和效率。
注意 （1）Sea of Nodes 是本文的先導知識，請參考 Cliff 1993年發表的論文 From Quads to Graphs。（2）本文所用環境為：V8 7.9、win10 x64、VS2019。
String.prototype.replace 源碼
測試用例代碼如下：
var str="Visit Microsoft!Visit Microsoft!";var res=str.replace("Microsoft","Runoob");console.log(res);
replace() 采用 TF_BUILTIN 實現，replace() 在 V8 中的函數名是 StringPrototypeReplace，編號是 594，源碼如下：
1. TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) {2. Label out(this);3. TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));4. Node* const search = Parameter(Descriptor::kSearch);5. Node* const replace = Parameter(Descriptor::kReplace);6. TNode<Context> context = CAST(Parameter(Descriptor::kContext));7. TNode<Smi> const smi_zero = SmiConstant(0);8. RequireObjectCoercible(context, receiver, "String.prototype.replace");9. MaybeCallFunctionAtSymbol(/*省略.....*/);10. TNode<String> const subject_string = ToString_Inline(context, receiver);11. TNode<String> const search_string = ToString_Inline(context, search);12. TNode<IntPtrT> const subject_length = LoadStringLengthAsWord(subject_string);13. TNode<IntPtrT> const search_length = LoadStringLengthAsWord(search_string);14. {15. Label next(this);16. GotoIfNot(WordEqual(search_length, IntPtrConstant(1)), &next);17. GotoIfNot(IntPtrGreaterThan(subject_length, IntPtrConstant(0xFF)), &next);18. GotoIf(TaggedIsSmi(replace), &next);19. GotoIfNot(IsString(replace), &next);20. TNode<Uint16T> const subject_instance_type =21. LoadInstanceType(subject_string);22. GotoIfNot(IsConsStringInstanceType(subject_instance_type), &next);23. GotoIf(TaggedIsPositiveSmi(IndexOfDollarChar(context, replace)), &next);24. Return(CallRuntime(Runtime::kStringReplaceOneCharWithString, context,25. subject_string, search_string, replace));26. BIND(&next); }27. TNode<Smi> const match_start_index =28. CAST(CallBuiltin(Builtins::kStringIndexOf, context, subject_string,29. search_string, smi_zero));30. {31. Label next(this), return_subject(this);32. GotoIfNot(SmiIsNegative(match_start_index), &next);33. GotoIf(TaggedIsSmi(replace), &return_subject);34. GotoIf(IsCallableMap(LoadMap(replace)), &return_subject);35. ToString_Inline(context, replace);36. Goto(&return_subject);37. BIND(&return_subject);38. Return(subject_string);39. BIND(&next); }40. TNode<Smi> const match_end_index = SmiAdd(match_start_index, SmiFromIntPtr(search_length));41. VARIABLE(var_result, MachineRepresentation::kTagged, EmptyStringConstant());42. {43. Label next(this);44. GotoIf(SmiEqual(match_start_index, smi_zero), &next);45. TNode<Object> const prefix =46. CallBuiltin(Builtins::kStringSubstring, context, subject_string,47. IntPtrConstant(0), SmiUntag(match_start_index));48. var_result.Bind(prefix);49. Goto(&next);50. BIND(&next); }51. Label if_iscallablereplace(this), if_notcallablereplace(this);52. GotoIf(TaggedIsSmi(replace), &if_notcallablereplace);53. Branch(IsCallableMap(LoadMap(replace)), &if_iscallablereplace,54. &if_notcallablereplace);55. BIND(&if_iscallablereplace);56. {57. Callable call_callable = CodeFactory::Call(isolate());58. Node* const replacement =59. CallJS(call_callable, context, replace, UndefinedConstant(),60. search_string, match_start_index, subject_string);61. TNode<String> const replacement_string =62. ToString_Inline(context, replacement);63. var_result.Bind(CallBuiltin(Builtins::kStringAdd_CheckNone, context,64. var_result.value(), replacement_string));65. Goto(&out); }66. BIND(&if_notcallablereplace);67. {68. TNode<String> const replace_string = ToString_Inline(context, replace);69. Node* const replacement =70. GetSubstitution(context, subject_string, match_start_index,71. match_end_index, replace_string);72. var_result.Bind(CallBuiltin(Builtins::kStringAdd_CheckNone, context,73. var_result.value(), replacement));74. Goto(&out);}75. BIND(&out);76. {77. TNode<Object> const suffix =78. CallBuiltin(Builtins::kStringSubstring, context, subject_string,79. SmiUntag(match_end_index), subject_length);80. TNode<Object> const result = CallBuiltin(81. Builtins::kStringAdd_CheckNone, context, var_result.value(), suffix);82. Return(result);83. }}
上述代碼第 3 行代碼 receiver 代表測試用例字符串 “Visit Microsoft!Visit Microsoft!”；
第 4 行代碼 search 代表測試用例字符串 “Microsoft”；
第 5 行代碼 replace 代表測試用例字符串 “Runoob”；
第 9 行代碼當 search 為正則表達式時，使用 MaybeCallFunctionAtSymbol() 實現 replace 功能。
下面將 replace 源碼劃分為五個子功能單獨說明：
（1） 功能 1：receiver 長度大于 0xFF、search 長度大于 1 以及 replace 為 ConsString，這三個條件同時成立時
第 10-13 行代碼轉換 search 和 replace 的數據類型，并計算他們的長度；
第 16 行代碼判斷 search 的長度是否等于 1，不等于則跳轉到第 26 行；
第 17 行代碼判斷 receiver 的長度是否大于 0xFF，小于等于則跳轉到第 26 行；
第 18-19 行判斷 replace 是否為小整數或者 replace 不是字符串，結果為真則跳轉到第 26 行；
第 20-22 行判斷 replace 是否為 ConsString 類型，結果為假則跳轉到第 26 行；提示 ConsString不是一個獨立的字符串，它是使用指針把兩個字符串拼接在一起的字符串對。在 V8 中，兩個字符串相加的結果常是 ConsString 類型的字符串對。
第 23 行判斷 PositiveSmi 類型；
第 24 行采用 Runtime::kStringReplaceOneCharWithString() 完成 replace。
（2） 功能 2：計算 receiver 中的前綴字符串
第 27-32 行計算 search的第一個字符在 receiver 中的位置 match_start_index，如果 match_start_index 不是負數則跳轉到 39 行；
第 33-35 行判斷 replace 是否為 SMI 或 函數，是則跳轉到 37 行；
第 40 行計算 match_end_index；
第 44 行如果 match_start_index = 0（也就是 search[0]=receiver[0]），則跳轉到 49 行；
第 45 行取出 receiver 中 match_start_index 位置之前的字符，保存為 prefix；也就是獲取測試用例中的 “Visit ” 字符串；
第 50-54 行判斷 replace 是否為 SMI 或 函數，根據判斷結果跳轉到相應的行號。
（3） 功能 3：replace 是函數類型
第 58-63 行計算 replace 的結果，將該結果拼接在 prefix 后面組成新的字符串 var_result;
（4） 功能 4：replace 是字符串類型
第 58-72 行將 replace 拼接在 prefix 后面組成新的字符串 var_result;
（5） 計算 receiver 中的后綴字符串
第 77-82 行取出 receiver 中 match_end_index 之后的字符串 suffix，將 suffix 拼接在 var_result 后面組成并返回新的字符串，replace 完畢。
下面簡單說明 replace 中使用的 runtime 方法：
1. RUNTIME_FUNCTION(Runtime_StringReplaceOneCharWithString) {2. HandleScope scope(isolate);3. DCHECK_EQ(3, args.length());4. CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);5. CONVERT_ARG_HANDLE_CHECKED(String, search, 1);6. CONVERT_ARG_HANDLE_CHECKED(String, replace, 2);7. const int kRecursionLimit = 0x1000;8. bool found = false;9. Handle<String> result;10. if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,11. kRecursionLimit).ToHandle(&result)) {12. return *result;13. }14. if (isolate->has_pending_exception())15. return ReadOnlyRoots(isolate).exception();16. subject = String::Flatten(isolate, subject);17. if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,18. kRecursionLimit).ToHandle(&result)) {19. return *result;20. }21. if (isolate->has_pending_exception())22. return ReadOnlyRoots(isolate).exception();23. return isolate->StackOverflow();24. }
上述代碼中第 10 執行 StringReplaceOneCharWithString 方法，該方法實現了 replace 功能;
第 14 行代碼檢測到異常情況時，先執行 String::Flatten，將ConsString字符處理成為單一字符串之后再次執行 StringReplaceOneCharWithString 方法。
圖1給出 StringPrototypeReplace 的函數調用堆棧。
String.prototype.replace 測試
測試用例的字節碼如下：
1. //省略........2. 000001A2EE982AC6 @ 16 : 12 01 LdaConstant [1]3. 000001A2EE982AC8 @ 18 : 15 02 04 StaGlobal [2], [4]4. 000001A2EE982ACB @ 21 : 13 02 00 LdaGlobal [2], [0]5. 000001A2EE982ACE @ 24 : 26 f9 Star r26. 000001A2EE982AD0 @ 26 : 29 f9 03 LdaNamedPropertyNoFeedback r2, [3]7. 000001A2EE982AD3 @ 29 : 26 fa Star r18. 000001A2EE982AD5 @ 31 : 12 04 LdaConstant [4]9. 000001A2EE982AD7 @ 33 : 26 f8 Star r310. 000001A2EE982AD9 @ 35 : 12 05 LdaConstant [5]11. 000001A2EE982ADB @ 37 : 26 f7 Star r412. 000001A2EE982ADD @ 39 : 5f fa f9 03 CallNoFeedback r1, r2-r413. 000001A2EE982AE1 @ 43 : 15 06 06 StaGlobal [6], [6]14. 000001A2EE982AE4 @ 46 : 13 07 08 LdaGlobal [7], [8]15. 000001A2EE982AE7 @ 49 : 26 f9 Star r216. 000001A2EE982AE9 @ 51 : 29 f9 08 LdaNamedPropertyNoFeedback r2, [8]17. 000001A2EE982AEC @ 54 : 26 fa Star r118. 000001A2EE982AEE @ 56 : 13 06 02 LdaGlobal [6], [2]19. 000001A2EE982AF1 @ 59 : 26 f8 Star r320. 000001A2EE982AF3 @ 61 : 5f fa f9 02 CallNoFeedback r1, r2-r321. 000001A2EE982AF7 @ 65 : 26 fb Star r022. 000001A2EE982AF9 @ 67 : ab Return23. Constant pool (size = 9)24. 000001A2EE982A29: [FixedArray] in OldSpace25. - map: 0x022d5e100169 <Map>26. - length: 927. 0: 0x01a2ee9829c9 <FixedArray[8]>28. 1: 0x01a2ee9828c1 <String[#32]: Visit Microsoft!Visit Microsoft!>29. 2: 0x01a2ee9828a9 <String[#3]: str>30. 3: 0x02749a2ab821 <String[#7]: replace>31. 4: 0x01a2ee982909 <String[#9]: Microsoft>32. 5: 0x01a2ee982929 <String[#6]: Runoob>33. 6: 0x01a2ee9828f1 <String[#3]: res>34. 7: 0x02749a2b3699 <String[#7]: console>35. 8: 0x02749a2b2cd9 <String[#3]: log>
上述代碼中，第 2-5 行讀取字符串 “Visit Microsoft!Visit Microsoft!” 并保存到 r2 寄存器中；
第 6-7 行獲取 replace 函數地址并保存到 r1 寄存器中；
第 8-11 行讀取 “Microsoft” 和 “Runoob” 并分別保存到 r3 和 r4 寄存器中；
第 12 行調用 repalce 方法；
圖 2 給出了 CallNoFeedback 的調用堆棧。
技術總結
（1） receiver 長度大于 0xFF、search 長度大于 1 以及 replace為ConsString，三個條件同時成立時采用低效率的 runtime 方式處理；
（2） replace 的原理是計算前、后綴，并與 newvalue 拼接組成最終結果。
好了，今天到這里，下次見。
個人能力有限，有不足與紕漏，歡迎批評指正
