65.9K
CodeProject 正在变化。 阅读更多。
Home

提高字符串比较性能的 .NET 字符串驻留（C# 示例）

Ben Hall (failingfast.io)
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.83/5 (21投票s)

2017 年 12 月 6 日

CPOL

6分钟阅读

viewsIcon

27723

了解提高字符串比较性能的“什么”、“何时”和“为什么”是有价值的。在本文中，我将探讨一种方法——字符串驻留。

引言

字符串比较肯定是我们 C# 中最常见的操作之一；而字符串比较可能会非常耗时！因此，了解提高字符串比较性能的“什么”、“何时”和“为什么”是有价值的。

在本文中，我将探讨一种方法——字符串驻留。

什么是字符串驻留？

字符串驻留是指在 .NET 公共语言运行时 (CLR) 的一个字符串驻留池中，为每个唯一的字符串只保留 **一个副本**，该池通过哈希表实现。其中键是字符串的哈希值，值是对实际 String 对象的引用。

因此，如果同一个字符串出现 100 次，驻留将确保该字符串只在内存中实际分配一次。此外，当我想比较字符串时，如果它们被驻留，那么我只需要进行引用比较。

字符串驻留机制

在此示例中，我显式驻留字符串文字，仅用于演示目的。

var s1 = string.Intern("stringy"); 
var s2 = string.Intern("stringy");
var s3 = string.Intern("stringy");
线 1
  • 这个新的“stringy”将被哈希，并在我们的池中查找其哈希值（当然，它还没有在那里）。
  • 将创建“stringy”对象的副本。
  • 将在驻留哈希表中创建一个新条目，键是“stringy”的哈希值，值是对“stringy”副本的引用。
  • 假设应用程序不再引用原始的“stringy”，GC 可以回收该内存。
线 2
  • 这个新的“stringy”将被哈希，并在我们的池中查找其哈希值（我们刚刚在那里添加的）。将返回对“stringy”副本的引用。
第 3 行
  • 与第 2 行相同

驻留依赖于字符串的不可变性

以字符串不可变性的经典示例为例。

var s1 = "stringy";   
s1 += " new string";

我们知道，当执行第 2 行时，“stringy”对象将被取消引用并留给垃圾回收；然后 s1 指向新的 String 对象“stringy new string”。

字符串驻留之所以有效，是因为 CLR 能够明确地知道所引用的 String 对象不会改变。在这里，我在前面的示例中添加了第四行。

var s1 = string.Intern("stringy"); 
var s2 = string.Intern("stringy");
var s3 = string.Intern("stringy");
s1 += " new string";
第 4 行 

s1 不会改变，因为它不可变；它现在指向一个新的 String 对象“stringy new string”。
s2 和 s3 仍将安全地引用在第 1 行创建的副本。

.NET CLR 中的驻留使用

您在上面的示例中已经看到了一些。 .NET 提供了两个 static string 方法：

Intern(String str)

它对 string str 进行哈希处理，并检查驻留池哈希表，然后执行以下操作之一：

  • 如果 string 已驻留，则返回对（已）驻留 string 的引用；或者
  • 将 str 的引用添加到驻留池，并返回此引用。

IsInterned(String str)

它对 string str 进行哈希处理，并检查驻留池哈希表。它不返回标准的 bool 值，而是返回以下之一：

  • 如果未驻留，则返回 null。
  • 如果已驻留，则返回对（已）驻留 string 的引用。

字符串文字（不在代码中生成）会被自动驻留，尽管 CLR 版本在这方面可能有所不同，因此如果您期望字符串被驻留，最好始终在代码中显式进行。

我的简单测试：设置

我在家里老旧的 i5 Windows 10 PC 上进行了一些计时测试，以提供一些数字来帮助探索字符串驻留的潜在收益。我使用了以下测试设置：

  • 随机生成字符串。
  • 所有字符串比较都是序数的。
  • 所有字符串的长度都为 512 个字符，因为我想让 CLR 比较每个字符以强制执行最坏情况（CLR 会先检查字符串长度以进行序数比较）。
  • 最后添加到 List<T> 的字符串（因此是列表的末尾）也存储为“已知”搜索词。这是因为我只探索最坏情况的方法。
  • 对于驻留的 List<T>，添加到列表的每个 string 以及搜索词都被包装在 string.Intern(String str) 方法中。

我计时了填充每个集合所需的时间，然后是搜索已知搜索词所需的时间，精确到毫秒。

我的测试中使用的集合/方法：

  • 未使用驻留的 List<T>，通过 foreach 循环和每个元素的 string.Equals 进行搜索。
  • 未使用驻留的 List<T>，通过 Contains 方法进行搜索。
  • 使用驻留的 List<T>，通过 foreach 循环和 object.ReferenceEquals 进行搜索。
  • HashSet<T>，通过 Contains 方法进行搜索。

主要目标是观察使用 List<T> 进行字符串驻留的字符串搜索性能提升。HashSet 仅作为已知快速搜索的基线包含在内。

我的简单测试：结果

在下面的图 1 中，我将集合的大小（按添加的字符串数量）与添加这些随机生成字符串所需的时间绘制在了一起。显然，与没有驻留的 List<T> 相比，使用 HashSet<t> 时，此操作没有显著差异。也许如果它运行到更大的集合，趋势会显示差距会进一步扩大？

使用字符串驻留填充 List<T> 时，开销稍大，这最初无关紧要，但增长速度快于其他选项。

图 1：使用随机字符串填充 List<T> 和 HashSet<T> 集合

图 2 显示了搜索已知字符串的时间。对于这些集合大小，所有时间都非常短，但增长是明显的。

图 2：搜索最后添加的已知字符串所需的时间

正如预期的那样，HashSet 是 O(1)，而其他是 O(N)。不使用驻留的搜索在所需时间上的增长率明显更高。

结论

HashSet<T> 在本文中仅作为快速搜索的基线存在，并且在没有需要 List<T> 的约束时，显然应该是您速度方面的选择。

在您必须使用 List<T> 的场景中，例如您仍然希望快速枚举集合中的元素，通过使用字符串驻留可以获得一些性能提升，并且随着集合大小的增长，收益会增加。缺点是填充开销略有增加（尽管我认为可以公平地建议大多数实际用例不会一次性填充整个集合）。

字符串驻留的实用性和行为让我想起了数据库索引——添加新项目需要更长的时间，但找到该项目会更快。那么，对于数据库索引的相同考虑是否也适用于字符串驻留呢？

还有一个额外的优点是字符串驻留可以防止存储任何重复的字符串，在某些情况下这可能意味着内存大幅节省。

潜在优势

  • 通过对象引用进行更快的搜索。
  • 减少内存使用，因为重复的驻留字符串将只存储一次。

潜在性能损失

  • 驻留哈希表引用的内存可能在 CLR 终止之前不会被释放。
  • 您仍然需要创建要驻留的字符串，这将分配内存（当然，之后会被垃圾回收）。

来源

© . All rights reserved.