IDLSet

IDLSet - 快速u64整数集合操作

IDLSet是一个专门用于快速对u64执行逻辑集合操作的库。例如，这意味着集合的并集（或）、交集（与）和非操作。在最佳情况下，速度提高了15倍，而一般情况下的性能大约比基于Vec的实现快4倍。

这些操作在数据库的索引逻辑的低级实现中得到了广泛使用，但也适用于需要逻辑集合操作的其他领域，如统计分析。

它是如何工作的？

每个集合最初是“稀疏”的。这以你期望的传统方式存储，内部使用 Vec<u64>。

::

[ 0, 1, 2, 3, ... , 1024 ]

然后你可以在集合上调用 maybe_compress，这将检查内容并确定是否压缩该集合是有益的。当压缩时，每个值被转换成一个包含 range 和 mask 的元组对。范围代表这组64个值的起始值，而掩码确定该范围内的值是否存在。例如

由于现在包含位掩码，我们可以使用CPU操作进行逻辑操作，如 AND、OR 和 AND NOT。以下示例演示了 AND 操作。

由于这种压缩，在高密度集合中，内存减少，同时CPU缓存行为得到改进，因为缓存压力降低。它还允许更快地遍历集合以确定值是否存在。

在压缩集与未压缩集之间的操作中，根据输入和执行的操作，"更好"的压缩或未压缩选择将被保留，以便于结果集。换句话说，结果集可能是压缩的或未压缩的，这取决于操作及其交互，以提高后续操作的性能。这有助于将这些优化选择传递给结果集，从而在执行链式和多个集合操作时减少中间集结果在操作中的内存消耗。

贡献

请提交一个问题、pull request或通过电子邮件直接联系我（见github）