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

Question

简而言之

如果已经看到很多小字节数组，则需要检查它们，如果没有，则存储它们并移至下一批。这同时发生。 HashSet 确实很神奇，但当元素超过 100 万时（每个数组可以产生 0、1 或 n 个以上的后继者），它就会完全崩溃。我们对删除元素不感兴趣，只是保持跟踪。什么样的数据结构足够灵活，性能好，多线程可用？

更长

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

最初他们使用 Trie 数据结构来存储所有以前的状态，但我们发现它在使用多线程时表现不佳。相反，我们现在使用 HashSet with a simple lock in case we want to write to it. We found it to work extremely well with this FNV 哈希函数 "Fowler/Noll/Vo (FNV) 32-bit hash function"。与单线程参考实现相比，性能提升了约 300%。

失败的最坏情况是：

考虑了 6600 万字节数组
740 万最终出现在我们的 HashSet 中（其余都是骗子）
这使得小字节数组的 700 万个散列与 6600 万个检查之前是否考虑过一个数组（通过对它们进行散列并检查该散列是否已经存在）。

编辑我们尝试了 System.Collections.Concurrent 中的集合，问题是我们从其中大部分获得的性能。有些提供太多，有些提供太少。理想情况下，我们只存储唯一的哈希值，这样我们就不会得到 700 万字节的数组。这就是我们使用 HashSet 的原因，它对于这个应用程序具有令人难以置信的性能，但当添加量呈指数增长时速度会大大降低。

一些实际的运行数据：

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

对于上述两种情况，使用 HashSet 这会产生以下结果：

运行时间 2017 毫秒
经过的时间 17010 毫秒

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

使用 ConcurrentDictionary（值为字节 0）我们得到这些结果：

经过时间 2898 毫秒
运行时间 32155 毫秒

使用 ConcurrentBag 我们得到这些结果：

40000 毫秒后终止
没打扰

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

考虑 704 字节数组，找到 85 个重复项并将 619 添加到 HashSet：耗时 799 毫秒
考虑了9931个字节的数组，发现了1183个重复项，将8748个添加到HashSet；经过时间 294 毫秒
考虑了3890个字节的数组，发现了603个重复项，将3287个添加到HashSet；经过时间 319 毫秒
考虑64字节数组，发现8个重复项，将56个添加到HashSet；经过时间 288 毫秒

在查看这些数字时要知道的重要一点是，继任者的生成可能会失败（哈哈）。以上几种情况是为了找出我们程序中可能存在的错误。

Answer 1

根据数据的分布情况，您可以考虑保留 Trie 方法，但根据第一个字节（或其他一些分布更好的字节，使用一些重新排序将其放在 'first' Trie), 'partition byte' 的每个值都有一个单独的锁。如果您选择的字节分布良好，这将大大减少锁争用，因为大多数时候您的各个线程将访问不同的独立尝试。

Answer 2

从概念上讲，HashSet 听起来很适合您要做的事情，但是 .NET 的实现有一个致命的缺陷：它不允许您设置初始容量。（例如，不同于 C++ 的 ordered_set，它允许您在构造时指定桶计数）。因此，当您反复达到 collection 的容量时，您的大部分时间都花在了重新散列上。奇怪的是他们不允许你这样做，因为 reference source 中的评论表明调整大小会造成伤害。

那么让我们测量一下 resizing/rehashing 对您的伤害有多大（使用 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);
}

我在具有足够容量的 "warmed-up" 哈希集上显示了近 2 倍的加速：

New HashSet: 27914.5131
Warmed HashSet: 17683.5115

（顺便说一下，这是在英特尔 NUC 运行 a laptop-grade i5 上。）

好的，现在让我们加速哈希实现：

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

...为了更大的胜利！

那么，您的应用有什么方法可以在您的 collection 上进行类似这样的预热吗？否则，您可能需要考虑 creating/finding 允许您配置初始容量的 HashSet 实现。

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

Storing and reading a high volume of small elements concurrently in C#

c#

arrays

concurrency

multithreading

hashset