在C#中同时存储和读取大量小元素

本文关键字：读取 元素 存储 | 更新日期: 2023-09-27 18:26:52

简而言之

许多小字节数组需要检查它们是否已经被看到，如果没有存储它们并移动到下一批。这种情况同时发生。HashSet会产生奇迹，但当元素超过100万时会完全崩溃（每个数组可以产生0、1或n个后续数组）。我们对删除元素不感兴趣，只对跟踪感兴趣。什么数据结构足够灵活，性能良好，可供多个线程使用？

更长

对于这个项目，我们需要存储大量特定状态的字节数组，以便跟踪我们看到的数组和没有看到的数组。该项目是在.NET框架的帮助下用C#完成的。实际程序是一个控制台应用程序。挑战在于使单线程引用解决方案成为更快的多线程解决方案。

最初，他们使用Trie数据结构来存储以前的所有状态，但我们发现当使用多个线程时，它的性能很差。相反，我们现在使用一个带有简单锁的HashSet，以防我们想写入它。我们发现它与这个FNV哈希函数"Fowler/Noll/Vo（FNV）32位哈希函数"配合得非常好。与单线程参考实现相比，性能提升了约300%。

失败的最坏情况是：

  • 考虑6600万字节阵列
  • 740万最终进入我们的哈希集中（其余都是重复）
  • 这就产生了700万个小字节数组的哈希，而6600万个则检查一个数组以前是否被考虑过（通过对它们进行哈希并检查该哈希是否已经存在）

编辑我们尝试了System.collections中的集合。当前，问题是大多数集合的性能。有些报价太高，有些报价太低。理想情况下，我们只存储唯一的散列，这样我们就不会得到700万字节的数组。这就是我们使用HashSet的原因，它对这个应用程序有着令人难以置信的性能，但当添加量呈指数级增长时，速度会减慢很多。

一些实际运行数据：

  • 考虑7001535字节数组，发现977689个重复项，并向哈希集添加6023846个（第二复杂）
  • 考虑了66478557个字节的数组，发现7460501个重复，并将59018056添加到哈希集（最坏情况）

使用HashSet可以为上述两种情况产生以下结果：

  • 运行时间2017毫秒
  • 运行时间17010毫秒

因此，我们在8.43倍的时间内大致完成了9.49倍的工作量，这是一个不错的缩放比例（略低于线性）。不过还不够。

使用ConcurrentDictionary（值为字节0），我们得到以下结果：

  • 运行时间2898毫秒
  • 运行时间32155毫秒

使用ConcurrentBag，我们得到以下结果：

  • 40000毫秒后终止
  • 没有打扰

在这种情况下，HashSet显然是赢家。更多运行：

  • 考虑704个字节的数组，发现85个重复，并将619个添加到哈希集：运行时间799毫秒
  • 考虑9931个字节数组，发现1183个重复，并向HashSet添加8748个；运行时间294毫秒
  • 考虑3890个字节的数组，发现603个重复，并向HashSet添加3287个；运行时间319毫秒
  • 考虑64字节数组，发现8个重复，并将56个添加到HashSet；运行时间288毫秒

当看到这些数字时，重要的是要知道，继任者的一代可能是不成功的（哈哈）。上述情况旨在找出我们程序中可能出现的错误。

在C#中同时存储和读取大量小元素

从概念上讲，HashSet听起来很适合你想要做的事情，但.NET的实现有一个致命的缺陷：它不允许你设置初始容量。（例如，与C++的ordered_set不同，后者允许您在构建时指定bucket计数）。因此，当你反复达到收藏的容量时，你的大部分时间都花在了重新洗衣服上。奇怪的是，他们不允许你这样做，因为参考源中的注释表明调整大小很痛苦。

因此，让我们来衡量调整大小/重新哈希对您的伤害有多大（使用8字节数组，粗略估计最坏的情况）：

static void Main(string[] args)
{
    const int COUNT = 66478557;
    const int UNIQUE_COUNT = 59018056;
    // create a bunch of 8-byte arrays:
    var arrays = new List<byte[]>(COUNT);
    for (long i = 0; i < COUNT; ++i)
        arrays.Add(BitConverter.GetBytes(i % UNIQUE_COUNT));
    // the HashSet we'll be abusing (i'll plug in a better comparer later):
    var hs = new HashSet<byte[]>(EqualityComparer<byte[]>.Default);
    //var hs = new HashSet<byte[]>(new ByteArrayComparer());
    var sw = Stopwatch.StartNew();
    for (int i = 0; i < COUNT; ++i)
        hs.Add(arrays[i]);
    sw.Stop();
    Console.WriteLine("New HashSet: " + sw.Elapsed.TotalMilliseconds);
    // clear the collection (doesn't reset capacity):
    hs.Clear();
    // Do the adds again, now that the HashSet has suitable capacity:
    sw.Restart();
    for (int i = 0; i < COUNT; ++i)
        hs.Add(arrays[i]);
    sw.Stop();
    Console.WriteLine("Warmed HashSet: " + sw.Elapsed.TotalMilliseconds);
}

我在一个有足够容量的"预热"哈希集上显示了近2倍的加速：

New HashSet: 27914.5131
Warmed HashSet: 17683.5115

（顺便说一句，这是在运行笔记本电脑级i5的英特尔NUC上。）

好的，现在让我们加快散列实现：

class ByteArrayComparer : IEqualityComparer<byte[]>
{
    public int GetHashCode(byte[] obj)
    {
        long myLong = BitConverter.ToInt64(obj, 0);
        // just XOR's upper and lower 4 bytes:
        return myLong.GetHashCode();
    }
    private EqualityComparer<byte[]> _defaultComparer = EqualityComparer<byte[]>.Default;
    public bool Equals(byte[] a1, byte[] a2)
    {
        return _defaultComparer.Equals(a1, a2);
    }
}

结果：

New HashSet: 5397.449
Warmed HashSet: 2013.0509

赢得更大的胜利！

那么，你的应用程序有什么方法可以对你的收藏进行这样的预热吗？否则，您可能需要考虑创建/查找允许您配置初始容量的HashSet实现。

根据数据的分布情况，您可能会考虑保留Trie方法，但基于第一个字节（或其他分布更好的字节，使用一些重新排序将其放在Trie中的"第一个"）进行分区，并为"分区字节"的每个值单独锁定。如果您选择的字节分布良好，这将大大减少锁争用，因为大多数时候，您的各个线程将访问不同的独立Tries。

相关文章：