我有一个巨大的内存块(位向量),其大小N一个内存页内的位,考虑N平均为 5000,即 5k 位来存储一些标志信息。
在某个时间点(超频繁 - 关键),我需要找到整个大位向量中的第一个位集。现在我对每个 64 个单词执行此操作,即在__builtin_ctzll https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)。但当N增长并且搜索算法无法改进,可以通过扩展内存访问宽度来扩展此搜索。简而言之,这是主要问题
有一个汇编指令称为BSF https://www.felixcloutier.com/x86/bsf给出最高设置位的位置(GCC__builtin_ctzll()
)。
所以在x86-64 /questions/tagged/x86-64arch 我可以很便宜地找到 64 位字中设置的最高位。
但是通过内存宽度进行扩展又如何呢?
例如。有没有办法用 128 / 256 / 512 位寄存器有效地做到这一点?
基本上我对一些C API函数来实现这个感兴趣,但也想知道这个方法是基于什么。
UPD:至于 CPU,我对这种优化感兴趣,以支持以下 CPU 系列:
Intel Xeon E3-12XX、Intel Xeon E5-22XX/26XX/E56XX、Intel Core i3-5XX/4XXX/8XXX、Intel Core i5-7XX、Intel Celeron G18XX/G49XX(可选配 Intel Atom N2600、Intel Celeron N2807、Cortex- A53/72)
P.S.在最终位扫描之前提到的算法中,我需要求和k(平均20-40)N位向量与 CPU AND(AND 结果只是位扫描的准备阶段)。这对于内存宽度缩放也是可取的(即比每个 64 位字 AND 更有效)
另请阅读:找到第一组 https://en.wikipedia.org/wiki/Find_first_set
这个答案是不同的,但如果您事先知道您将维护 B 位的集合,并且需要能够有效地设置和清除位,同时还要弄清楚哪个位是第一个设置的位,你可能想使用像这样的数据结构范恩德博阿斯树 https://en.wikipedia.org/wiki/Van_Emde_Boas_tree or a y-快速特里 https://en.wikipedia.org/wiki/Y-fast_trie。这些数据结构旨在存储小范围内的整数,因此您可以添加或删除要设置/清除的位的索引,而不是设置或清除各个位。它们非常快 - 您可以在 O(log log B) 时间内添加或删除项目,并且它们可以让您在 O(1) 时间内找到最小的项目。如图所示,如果 B ≈ 50000,则 log log B 约为 4。
我知道这并不直接解决如何在巨大的位向量中找到最高位集。如果您的设置必须使用位向量,那么其他答案可能会更有帮助。但是,如果您可以选择以不涉及位向量搜索的方式重新构建问题,那么这些其他数据结构可能更适合。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)