为什么在Nodejs中比较两个字符串时,'==='比逐个字符比较慢?

14
我发现在 Nodejs 中,通过比较两个字符串的每个字符来比较它们要比使用语句 'str1 === str2' 更快。这是为什么呢?而在 浏览器 中恰恰相反。
这是我尝试过的代码,两个长字符串是相等的。Node 版本是 v8.11.3

function createConstantStr(len) {
  let str = "";
  for (let i = 0; i < len; i++) {
    str += String.fromCharCode((i % 54) + 68);
  }

  return str;
}

let str = createConstantStr(1000000);
let str2 = createConstantStr(1000000);

console.time('equal')
console.log(str === str2);
console.timeEnd('equal')

console.time('equal by char')
let flag = true;
for (let i = 0; i < str.length; i++) {
  if (str[i] !== str2[i]) {
    flag = false;
    break;
  }
}

console.log(flag);
console.timeEnd('equal by char');


3
我看不到和你一样的速度提升 - 实际上,我的情况相反:true 相等:23.945毫秒 true 字符匹配相等:124.190毫秒 - Icehorn
如果我运行这段代码片段,使用 === 运算符花费了 23 毫秒,而使用 char 运算符则花费了 123.165 毫秒。 - Kiran Dash
4
这绝对不是重复的。你有读过问题吗? - idmean
2
我猜这取决于浏览器。 - Jaromanda X
对我来说,逐个比较每个字符的速度反而更慢。 - Chris
显示剩余6条评论
3个回答

27

已经有人指出,如果你调换两个测试的顺序,那么使用===比逐个字符比较更快。迄今为止,你所得到的解释并没有精确地界定原因。有一些问题会影响你的结果。

第一个console.log调用很昂贵

如果我尝试这样做:

console.time("a");
console.log(1 + 2);
console.timeEnd("a");

console.time("b");
console.log("foo");
console.timeEnd("b");

我得到的类似于:

3
a: 3.864ms
foo
b: 0.050ms

如果我把代码翻转过来,就会变成这样:

console.time("b");
console.log("foo");
console.timeEnd("b");

console.time("a");
console.log(1 + 2);
console.timeEnd("a");

然后我得到类似于这样的东西:

foo
b: 3.538ms
3
a: 0.330ms

如果我在任何计时被记录之前加入console.log代码,像这样:

console.log("start");

console.time("a");
console.log(1 + 2);
console.timeEnd("a");

console.time("b");
console.log("foo");
console.timeEnd("b");

然后我得到了类似下面的东西:

start
3
a: 0.422ms
foo
b: 0.027ms

在计时之前加入console.log,可以将调用console.log的初始成本从计时中排除。

根据您设置的测试方式,第一个console.log调用是由===或char-by-char测试中先出现的那个来执行的,因此第一个console.log调用的成本会被添加到该测试中。无论第二个测试是哪个,它都不承担这个成本。最终,对于像这样的测试,我更愿意将console.log移动到正在计时的区域之外。例如,第一个计时区域可以编写为:

console.time('equal');
const result1 = str === str2;
console.timeEnd('equal');
console.log(result1);

将结果存储在result1中,然后在定时区域之外使用console.log(result1)可确保您可以查看结果,并且同时不计算由console.log产生的成本。

无论哪个测试先运行,都会承担v8内部创建的字符串树展平的成本

Node使用v8 JavaScript引擎运行您的JavaScript。v8以多种方式实现字符串。objects.h在注释中显示了v8支持的类层次结构。以下是与字符串相关的部分:

//       - String
//         - SeqString
//           - SeqOneByteString
//           - SeqTwoByteString
//         - SlicedString
//         - ConsString
//         - ThinString
//         - ExternalString
//           - ExternalOneByteString
//           - ExternalTwoByteString
//         - InternalizedString
//           - SeqInternalizedString
//             - SeqOneByteInternalizedString
//             - SeqTwoByteInternalizedString
//           - ConsInternalizedString
//           - ExternalInternalizedString
//             - ExternalOneByteInternalizedString
//             - ExternalTwoByteInternalizedString

在我们的讨论中有两个重要的类:SeqStringConsString。它们之间的区别在于它们如何将字符串存储在内存中。 SeqString是一个直接的实现:字符串只是一个字符数组。(实际上,SeqString本身是抽象的。真正的类是SeqOneByteStringSeqTwoByteString,但这里不重要。)ConsString然而将字符串存储为二叉树。一个ConcString有一个first字段和一个second字段,它们是指向其他字符串的指针。

考虑以下代码:

let str = "";
for (let i = 0; i < 10; ++i) {
  str += i;
}
console.log(str);

如果V8使用SeqString来实现上面的代码,则:

  • 在迭代0时,它需要分配一个大小为1的新字符串,并将str的旧值("")复制到它上面,然后追加"0",并将str设置为新字符串("0")。

  • 在迭代1时,它需要分配一个大小为2的新字符串,并将str的旧值("0")复制到它上面,然后追加"1"),并将str设置为新字符串("01")。

  • ...

  • 在迭代9时,它需要分配一个大小为10的新字符串,并将str的旧值("012345678")复制到它上面,然后追加"9",并将str设置为新字符串("0123456789")。

这10个步骤中复制的字符总数是1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55个字符。对于最终包含10个字符的字符串,移动了55个字符。

相反,V8实际上使用ConsString,方法如下:

  • 在迭代0时,分配一个新的ConcString,将其first设置为str的旧值,并将second设置为字符串"0",并将str设置为刚刚分配的这个新的ConcString

  • 在迭代1时,分配一个新的ConcString,将其first设置为str的旧值,并将second设置为字符串"1",并将str设置为刚刚分配的这个新的ConcString

  • ...

  • 在迭代9时,分配一个新的ConcString,将其first设置为str的旧值,并将second设置为字符串"9"

如果我们将每个ConcString表示为(<first>, <second>),其中<first>是其first字段的内容,<second>second字段的内容,则最终结果如下:

(((((((((("", "0"), "1"), "2"), "3"), "4"), "5"), "6"), "7"), "8"), "9")

通过这种方式,V8避免了在各个步骤中反复复制字符串。每个步骤只需进行一次分配和调整一些指针。虽然将字符串存储为树有助于加快连接速度,但它的缺点是其他操作变慢。V8通过扁平化ConsString树来缓解这一问题。将上面的示例扁平化后,它变成了:

("0123456789", "")
注意,当一个ConsString被展平时,这个非常的ConsString对象会被改变。(从JS代码的角度来看,字符串保持不变。只有它的内部v8表示发生了改变。)更容易比较展平的ConsString树,实际上这正是v8所做的(参考):
bool String::Equals(Isolate* isolate, Handle<String> one, Handle<String> two) {
  if (one.is_identical_to(two)) return true;
  if (one->IsInternalizedString() && two->IsInternalizedString()) {
    return false;
  }
  return SlowEquals(isolate, one, two);
}

我们所讨论的字符串并没有内部化,所以调用了 SlowEquals (参考链接):

bool String::SlowEquals(Isolate* isolate, Handle<String> one,
                        Handle<String> two) {
[... some shortcuts are attempted ...]
  one = String::Flatten(isolate, one);
  two = String::Flatten(isolate, two);

在此我已经说明了比较字符串相等时会使其内部变得扁平化,但是调用String::Flatten的情况在许多其他地方也可以找到。通过不同的方式,你的两个测试最终都会使字符串扁平化。

对于你的代码,重点在于:

  1. createConstantStr创建的字符串在内部存储为ConsString。因此,就v8而言,strstr2都是ConsString对象。

  2. 你运行的第一个测试导致strstr2被扁平化,因此:a)这个测试必须承担扁平化字符串的成本,b)第二个测试受益于使用已经被扁平化的ConcString对象。(记住,当一个ConcString对象被扁平化时,这个对象本身被改变了。因此,如果稍后再次访问它,它已经被扁平化。)


太棒了!非常详细和深入,我学到了更多超出问题本身的知识! - YDSS
“第一个 console.log 调用很耗费资源”的理论并不成立,使用这段代码 http://paste.debian.net/plain/1083758 ,无论哪个测试先运行,速度都会更快。在 Chrome 74.0.3729.131 和 Firefox 60.6.3esr 上都是如此。 - hanshenrik
@hanshenrik 我在 Node 中进行了测试。这解释了 OP 的时间,因为 OP 正在使用 Node。在 Node 中,console 的内部是惰性初始化的。请参见此处 输入和输出流被定义为 getter,它们不会从 process 获取其流,直到需要时(当调用该函数时,object 绑定到 process 全局对象)。process 本身也是惰性初始化其流。Chrome 和 Firefox 很可能急切地初始化 console - Louis
@Louis 刚刚在 Node 版本 10.15.3 中进行了测试,即使预先初始化 console.log ,第二个测试仍然快得多:https://i.imgur.com/KRL2ZGS.png(运行上面链接的测试函数) - hanshenrik
@hanshenrik 控制台初始化是一个因素,但并不是唯一的因素,解释了为什么 OP 得到了比逐个字符比较更差的 === 时间。当然,如果你修复了这个问题,你并没有解决所有问题。如果这是唯一的因素,我就不会指出将 ConcString 扁平化的成本由第一个测试承担。 - Louis
问题很明显是console.log。因此,我几乎关闭了这个问题并想打负分。但是,关于v8内部String实现的细节值得单独讨论! - Anatoli Klamer

4

我反转了比较操作符,看起来 === 在火狐浏览器上只需要 0毫秒(有时候是1毫秒)。所以可能与编译器内部的优化有关。就像这样:嘿,第二个比较操作中的字符串相同,而我已经进行了比较。所以我将重复使用结果。

这个视频讲得最清楚。

function createConstantStr(len) {
  let str = "";
  for (let i = 0; i < len; i++) {
    str += String.fromCharCode((i % 54) + 68);
  }

  return str;
}

let str = createConstantStr(1000000);
let str2 = createConstantStr(1000000);

console.time('equal by char')
let flag = true;
for (let i = 0; i < str.length; i++) {
  if (str[i] !== str2[i]) {
    flag = false;
    break;
  }
}

console.log(flag);
console.timeEnd('equal by char');

console.time('equal')
console.log(str === str2);
console.timeEnd('equal')


2
JIT优化器可能会用内部版本的===替换循环,因为可以很容易地证明在比较之间strstr2没有被修改,所以它可以用true字面值替换第二个比较。 - idmean
@idmean 没错。链接的视频提供了一些关于你所描述的优化的见解。 - 1565986223
@idmean忘记提到我在nodejs中测试过它,而不是在浏览器中,抱歉我的错误。请再试一次。 - YDSS
@YDSS 相同的结果,你为什么认为会有不同呢? - 1565986223
OP明确表示问题存在于NodeJS中,而不是浏览器中,你应该尝试在NodeJS中进行调试。 - hanshenrik
火狐浏览器的版本是什么?在我的测试中,使用火狐浏览器60.6.3esr(64位)进行比较大约需要28-31毫秒,按字符计算大约需要3-6毫秒。 - hanshenrik

0

(感谢在irc://irc.freenode.net/##Javascript的TheWild发现了这个)

至少在Firefox、Chrome和Node中,str和str2是惰性初始化,实际的createConstantStr()调用是在需要结果时才运行的,而不是当你要js创建它时。如果你把它改成:

let str = createConstantStr(1000000);
let str2 = createConstantStr(1000000);
console.log(str[10],str2[20]);

然后字符串将在console.log()调用中创建,您将在基准测试中获得更合理的结果,并且 === 确实会更快。(在我的笔记本电脑上要快得多,从按字符计算的5ms到使用===的小于1ms)


原始信息:

我没有答案,但我想补充一下,在Firefox 60.6.3esr(64位)中我可以重现它,===大约需要28-31毫秒,按字符计算大约需要3-6毫秒:

function test(){
let createConstantStr=function(len) {
  let str = "";
  for (let i = 0; i < len; i++) {
    str += String.fromCharCode((i % 54) + 68);
  }

  return str;
};

let str = createConstantStr(1000000);
let str2 = createConstantStr(1000000);

console.time('equal')
console.log(str === str2);
console.timeEnd('equal')

console.time('equal by char')
let flag = true;
for (let i = 0; i < str.length; i++) {
  if (str[i] !== str2[i]) {
    flag = false;
    break;
  }
}

console.log(flag);
console.timeEnd('equal by char');
};

火狐浏览器结果:

test();
equal: 28ms
equal by char: 6ms
undefined
test();
equal: 29ms
equal by char: 4ms
undefined
test();
equal: 29ms
equal by char: 3ms
undefined
test();
equal: 31ms
equal by char: 5ms
undefined
test();
equal: 28ms
equal by char: 4ms
undefined

我可以在代码中重现这个问题。

Google Chrome   74.0.3729.131 (Official Build) (64-bit) (cohort: Stable)
Revision    518a41c1fa7ce1c8bb5e22346e82e42b4d76a96f-refs/branch-heads/3729@{#954}
JavaScript  V8 7.4.288.26

Chrome 结果:

test();
true
equal: 23.493896484375ms
true
equal by char: 11.197021484375ms
undefined
test();
true
equal: 22.749755859375ms
true
equal by char: 11.500244140625ms
undefined
test();
true
equal: 24.43505859375ms
true
equal by char: 11.48291015625ms
undefined
test();
true
equal: 23.84521484375ms
true
equal by char: 11.38720703125ms
undefined
test();
true
equal: 21.8798828125ms
true
equal by char: 11.0390625ms
undefined
test();
true
equal: 23.989013671875ms
true
equal by char: 10.934814453125ms
undefined
  • 笔记本电脑搭载Intel Core i7 6700处理器和1200MHz内存,不使用电池运行。

1
你仍然没有理解编译器优化。在“按字符相等”的测试之后运行“相等”测试(简而言之,反转测试),并查看结果。 - 1565986223
@1556089774 其实问题在于 str/str2 是延迟初始化的,createConstantStr() 函数只有在它们的返回值实际需要时才被执行!这就是为什么第一个测试,不管是哪个,似乎都要慢得多。 - hanshenrik
我认为字符串根本没有被懒惰地初始化。我剪切并粘贴了你在答案中展示的代码部分,并在其前后添加了时间调用。这里是一个fiddle,展示了我的运行结果。如果按原样运行,大约需要70毫秒。如果将计数乘以10,则需要大约10倍的时间。如果涉及到懒惰初始化,那么无论传递给createConstantStr的计数是多少,它都应该花费相同的时间。这是在Chrome 73上测试的。 - Louis
@Louis,这个结果并没有证明懒加载没有发生,但它证明死代码消除没有发生 =/(我想它是在变量析构函数中初始化的?尽管听起来很愚蠢) - hanshenrik
@Louis 是的,createConstantStr没有副作用,并且返回值也没有被使用。这个调用是死代码,可以为了性能而消除。 - hanshenrik
@hanshenrik 我明白你的意思,但这并不重要。将返回值存储在一个变量中,你会得到相同的结果。添加一行代码 window.foo = 1,你也会得到相同的结果。 - Louis

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接