问题 JavaScript字符串比较与数字比较一样快吗?


我想为JavaScript枚举编写一个小库。对我来说,我需要决定如何存储枚举值。因此,我想在比较时使用最快的方法,但我也想要一些可调试的东西,所以我在使用字符串或数字之间徘徊。我知道我也可以使用对象,但那将是另一个问题

例如

// I don't want this because when debugging, you'd see just the value 0
var Planets = {Earth:0, Mars:1, Venus: 2}

// I'd prefer this so that Planets.Earth gives me a nice readable value ("Earth")
var Planets = {Earth: 'Earth', Mars: 'Mars'}

但是我害怕当我用它们进行比较时 if (myPlanet === Planet.Earth),字符串比较可能需要更长的时间(比如它是否处于紧密循环中)。应该是这种情况,因为 http://ecma-international.org/ecma-262/5.1/#sec-11.9.6 说

如果Type(x)是String,则如果x和y完全相同的字符序列(相应位置的长度和字符相同),则返回true;否则,返回false。

但是当我写一个测试用例时,我发现他们花了相同的时间 http://jsperf.com/string-comparison-versus-number-comparison/2 所以它似乎不是在扫描整个字符串。

我知道这可能是一个微优化,但我的问题是:是否使用指针进行字符串相等比较,因此与数字相等比较一样快?


11021
2018-05-23 19:10


起源

这就像规范所说:如果字符序列相同,则两个不同的字符串是相同的。因为字符串是不可变的,所以它是 可能 对于运行时系统在它们相同时折叠单独的字符串实例,因此可以在逐个字符比较之前进行直接指针比较。 - Pointy
这正是我的问题,它似乎以这种方式进行了优化,我希望找到什么时候不是真的?什么时候会扫描字符串? - Juan Mendes
您可能会使用jsperf测试了解更多信息 不等式 而不是平等。 - Pointy
让我创建它并将其添加到jsperf - Juan Mendes
那么,每当发生字符串连接时,运行时系统就必须进行大量昂贵的查找 保证 每个字符串实例都是唯一的,并且所有相似值的引用都指向同一个实例。我怀疑是这样的。当然,解析器可以在任何单个代码块中为常量执行此操作。 - Pointy


答案:


字符串比较 可以 “同样快”(取决于实施和价值) - 或者它可能“慢得多”。

ECMAScript规范 描述了 语义不是 履行。知道肯定的唯一方法是创建一个 适用 运行它的性能基准测试 特定 实现。

琐碎的,我希望情况就是如此1,效果 字符串实习 为一个 特别实施 正在被观察。

也就是说,文字中的所有字符串值(不是字符串对象)都可以简单地插入到池中 implIdentityEq("foo", "foo") 是的 - 也就是说,只需要一个字符串对象。这种实习可以在恒定折叠之后进行,例如 "f" + "oo" -> "foo"  - 再次,根据特定的实现,只要它支持ECMAScript语义。

如果这样的实习完成,那么 implStringEq 第一次检查可能是评估 implIdentityEq(x,y) 并且,如果为真,则该比较非常简单并且在O(1)中执行。如果为false,则需要进行正常的字符串字符比较,即O(min(n,m))。

(立即虚假也可以用 x.length != y.length,但这似乎不太重要。)


1 虽然在上面我争论 对于 字符串实习是一个可能的原因,现代JavaScript实现执行 很多 优化 - 因此,实习只是 一小部分 可以(和)完成的各种优化和代码提升!

我创造了一个 “实习生断路器”jsperf。这些数字与上述假设一致。

  1. 如果字符串被实习,那么比较是性能的近似来测试“身份”  - 虽然它比数字比较慢,但它仍然比逐字符串比较快得多。

  2. 持有上述断言,尽管IE10确实使用了快速失败长度检查,但IE10似乎没有考虑传递快速字符串比较的对象标识。

  3. 在Chrome和Firefox中,两个不相等的实习字符串也会快速比较两个 - 很可能有一个比较两个字符串的特殊情况 不同 实习词串。

  4. 即使对于小弦(长度= 8),实习也可以快得多。 IE10再次显示它没有这种“优化”,即使它似乎有一个有效的字符串比较实现。

  5. 字符串比较可能会失败 不久 当遇到第一个不同的字符时:即使比较相等长度的长字符串也只能比较前几个字符。


  • 常见的JavaScript实现是否使用字符串实习? (但没有给出参考)

    是。通常,JS源中的任何文字字符串,标识符或其他常量字符串都是实体。然而,实施细节(例如,实际上是实施的内容)会有所不同,以及实施时的实施情况

  • 看到 JS_InternString (FF确实有字符串实习,虽然字符串在哪里/如何与JavaScript隐式交互,我不知道)


11
2018-05-23 20:06



我确实创建了测试:)从我的测试来看,似乎Firefox实际上甚至是动态生成的字符串,至少在某些情况下Chrome并没有。 IE浏览器也是最慢的,无论是否是文字。 - Juan Mendes
@JuanMendes经过多次失败后,我终于修复了 我的jsperf 这样就可以证明这种情况。 - user2864740


有些情况下,字符串比较可能会慢得多(比较动态生成的字符串)

以下是比所有其他测试慢77%(在chrome和IE中)

var StringEarth = 'Ear' + 'th';
for (var i = 0; i < ITERATIONS; i++) {
  x = StringPlanets.Venus === StringEarth;
}

问题中提到的测试中的缺陷是我们正在测试文字字符串。似乎JavaScript已经过优化,因此字符串文字的字符串比较只需通过测试指针即可完成。这可以通过动态创建字符串来观察。我最好的猜测是来自文字字符串池的字符串被标记,以便它们可以仅使用地址进行比较。

请注意,即使对于动态字符串,字符串比较在FF中也同样快。而且,即使是文字字符串也一样慢。

结论 所有浏览器的行为都不同,因此字符串比较可能会或可能不会更慢。


1
2018-05-23 19:33





通常,最好的字符串实习(将具有给定值的字符串转换为唯一引用或O(1)可比较符号)将花费O(n)时间,因为如果不全部查看它就无法有效地执行此操作涉及的人物。

然后,相对效率的问题相当于实际分摊的实际比较数量。

在极限中,一个非常聪明的优化器可以提取静态表达式,这些表达式构建字符串并实例化一次。

上面的一些测试,使用将被实习的字符串,在这种情况下,比较可能是O(1)。在枚举基于映射到整数的情况下,在任何实现中它都是O(1)。

当至少一个操作数是真正的动态字符串时,会出现昂贵的比较情况。在这种情况下,不可能在小于O(n)的情况下将相等性与它进行比较。

适用于原始问题,如果希望创造类似于某个东西的东西 enum 在另一种语言中,唯一的了望是确保实习只能在少数几个地方完成。如上所述,不同的浏览器使用不同的实现,因此可能很棘手,并且如指出的那样 IE10 也许不可能。

注意缺少字符串实习(在这种情况下你需要enum实现的整数版本),@ JuanMendes基于字符串的枚举实现将基本上是O(1),如果他安排的值的 myPlanet 变量在O(1)时间内设置。如果是这样设置的话 Planets.value 其中价值是一个既定的行星,它将是O(1)。


1
2018-05-31 16:14