C#统计rockyou.txt密码频次各实现方法性能差异原因咨询

我尝试使用C#统计rockyou.txt文件中每个唯一密码的出现次数，由于算法基础较为薄弱，在Release编译配置下实现了所有能想到的朴素统计方法，对各方法的运行耗时进行测量。得到的测试结果出乎我的意料，现对各方法性能存在高低差异的原因做解释。

问题更新 #

为便于后续参考，在此公布最新的测试配置与结果。

测试初始化设置 #

ConcurrentDictionary<string, int> conDict = new();
Dictionary<string, int> dict = new();
string[] lines = File.ReadAllLines(@"rockyou.txt");
IEnumerable<string> linesEnum = File.ReadLines(@"rockyou.txt");

各实现方法代码 #

• 方法一：异常捕获实现计数
  实现思路为遍历每一个密码（即文件每一行内容），若密码已存在于字典中，则将其出现次数加1；若密码不存在会触发异常，通过try-catch块捕获异常后将该密码加入字典，初始计数设为1。

  foreach (var line in lines)
  {
      try
      {
          dict[line] += 1;
      }
      catch
      {
          dict[line] = 1;
      }
  }
  

• 方法二：ContainsKey判断后计数

  foreach (var line in lines)
  {
      if (dict.ContainsKey(line))
          dict[line] += 1;
      else
          dict[line] = 1;
  }
  

• 方法三：单线程ConcurrentDictionary AddOrUpdate

  foreach (var line in lines)
      conDict.AddOrUpdate(line, 1, (id, count) => count + 1);
  

• 方法四：并行ConcurrentDictionary AddOrUpdate

  Parallel.ForEach(lines, line => conDict.AddOrUpdate(line, 1, (id, count) => count + 1));
  

• 方法五：数组GroupBy转Dictionary

  var res = lines.GroupBy(line => line).ToDictionary(group => group.Key, group => group.Count());
  

• 方法六：LINQ查询表达式分组转List

  var wordCounts = from w in lines
                   group w by w into g
                   select new { Word = g.Key, Count = g.Count() };
  
  var result = wordCounts.ToList();
  

• 方法七：File.ReadLines枚举器GroupBy转Dictionary

  var dict = linesEnum.GroupBy(line => line).ToDictionary(group => group.Key, group => group.Count());
  

• 方法八：TryGetValue单次查找计数

  foreach (var line in lines)
      dict[line] = (dict.TryGetValue(line, out var count) ? count : 0) + 1;
  

基准测试结果 #

性能差异核心原因解释 #

1. 单线程普通Dictionary实现（方法一、二、八）性能接近的原因 #

这三个方法都是单线程操作普通Dictionary<string,int>，核心开销都是字符串哈希计算、哈希桶查找，性能差异来自查找次数和异常开销：

• 方法二最慢：每次循环先调用ContainsKey做一次哈希查找，key存在的话再通过索引器赋值做第二次查找，每个已存在的key要做2次哈希查找，重复开销最大。
• 方法一和方法八性能几乎一致：方法一只对不存在的key触发异常，rockyou.txt中重复密码占比极高，首次添加新key的异常触发次数占总循环次数比例极低，.NET异常在不触发时几乎没有开销，整体表现和最优写法差距极小；方法八用TryGetValue只做一次查找就拿到计数值，是普通字典计数的标准最优写法，和方法一的微小差异属于正常测试波动范围。

2. ConcurrentDictionary单线程实现（方法三）偏慢的原因 #

ConcurrentDictionary为了支持线程安全，所有读写操作都加了细粒度锁和额外的线程安全校验逻辑，即使单线程调用，这些额外的校验和锁开销也不会消失，比普通单线程字典慢70%左右属于正常表现。

3. 并行ConcurrentDictionary实现（方法四）最快的原因 #

rockyou.txt总共有超过1400万行密码，属于典型的计算密集型场景，Parallel.ForEach会利用多核CPU并行处理哈希计算和字典更新操作，ConcurrentDictionary的细粒度锁设计在多核下锁冲突概率被充分分摊，最终获得接近线性的多核加速比，成为所有方法里最快的实现。

4. LINQ GroupBy系列方法（方法五、六、七）性能极差的原因 #

这三个方法慢的核心原因是GroupBy的原生实现逻辑不是直接做增量哈希计数：

• LINQ的GroupBy会为每个key创建独立的分组对象，把同key的所有字符串引用都存到分组的内部集合里，之后再遍历所有分组计算Count，整个过程会产生天量的临时对象内存分配。从测试结果看这几个方法分配了2~3.5GB的内存，触发了上万次GC回收（Gen0/Gen1/Gen2回收次数极高），GC停顿占了绝大多数耗时。
• 方法七比另外两个GroupBy方法略慢，是因为File.ReadLines是逐行读取的延迟枚举器，没有预先把所有行加载到内存数组，GroupBy处理时除了分组开销还要叠加IO读取开销，内存分配也更高。
• 方法六比方法五略快，只是因为最后转List不需要构造Dictionary的哈希表结构，少了一步哈希查找开销，但核心的分组产生巨量内存分配的问题没有解决，依然比直接字典计数慢一个数量级。

内容的提问来源于stack exchange，提问作者K-RUSHer