为何JavaScript双端字符串字面量插值时间复杂度非O(n²)？

在JavaScript中，如下经典的双端字符串拼接操作，按常规理解应该是O(n²)时间复杂度，但实际在Firefox 124和Chromium 123中却表现为O(n)，这是为什么？

s = "";
for (i = 0; i < 1000000; i++) {
  s = `( ${s} )`
};
console.log(s.length)

该操作在Firefox 124和Chromium 123中均为O(n)时间复杂度。

而在Python中，类似操作符合预期为O(n²)：

s = ""
for i in range(50_000):  # 翻倍循环次数，耗时变为4倍
  s = f"( {s} )"
print(len(s))

这种“魔法”实现的原理是什么？浏览器是如何优化的？该行为是否受ECMAScript规范保障？ #

核心原理：字符串的rope（绳索）结构优化 #

主流JS引擎（V8、SpiderMonkey）并没有用传统的连续字符数组存储字符串，而是采用了rope（绳索）结构——一种基于链表的字符串表示方式：

• 每次执行( ${s} )拼接时，引擎不会立即复制原字符串的所有内容，而是创建一个新的rope节点，指向原字符串节点和新增的( 、 )片段，彻底避免了大量内存拷贝操作。
• 只有当需要直接访问字符（比如调用charAt、slice，或者最终输出到控制台）时，引擎才会按需将rope结构扁平化（flatten）为连续字符数组，这个扁平化的总开销仅为O(n)。

浏览器/JS引擎的具体优化逻辑 #

• V8引擎（Chromium）：
  • 针对字符串拼接操作（包括模板字符串、+拼接），会自动识别“重复在两端追加固定片段”的模式，优先使用rope结构而非直接复制原字符串。
  • 当rope的深度或节点数达到阈值时，会触发部分扁平化操作，平衡内存占用和字符访问性能。
• SpiderMonkey引擎（Firefox）：
  • 同样采用rope结构存储字符串，并且对双端追加这类拼接模式的检测更敏感，即使是百万级别的循环拼接也能维持线性时间复杂度。

是否受ECMAScript规范保障？ #

不受规范强制保障。ECMAScript规范仅定义了字符串的对外行为和接口，并未规定底层存储结构或优化策略：

• 这种O(n)的性能表现是JS引擎的实现层面优化，而非规范要求。如果使用未实现rope结构的老旧或小众JS引擎，该操作可能会回归O(n²)的时间复杂度。
• 而Python的字符串基于不可变的连续字符数组实现，每次拼接都必须创建新数组并拷贝原内容，因此严格遵循O(n²)的时间复杂度，这是Python语言实现的固有特性。

内容的提问来源于stack exchange，提问作者nh2