相关疑难解决方法(0)

我一直在寻找最快的方法来处理popcount大数据.我遇到了一个很奇怪的效果:改变从循环变量unsigned至uint64_t50%在我的电脑上所做的性能下降.

基准

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < …

如果我有一个整数n,并且我想知道最高位的位置(也就是说,如果最低有效位在右边,我想知道最左边位的位置是1),找出最快捷/最有效的方法是什么？

我知道POSIX支持ffs()strings.h中的一个方法来查找第一个设置位,但似乎没有相应的fls()方法.

是否有一些非常明显的方法可以解决这个问题？

如果你不能使用POSIX功能来实现可移植性呢？

编辑:如何在32位和64位架构上运行的解决方案(许多代码清单似乎只能在32位整数上运行).

我需要找到大于或等于给定值的2的最小幂.到目前为止,我有这个:

int value = 3221; // 3221 is just an example, could be any number
int result = 1;

while (result < value) result <<= 1;

它工作正常,但感觉有点幼稚.这个问题有更好的算法吗？

编辑.有一些很好的Assembler建议,所以我将这些标签添加到问题中.

我有一个位数组实现,其中第0个索引是数组中第一个字节的MSB,第8个索引是第二个字节的MSB,等等...

找到这个位数组中设置的第一个位的快速方法是什么？我查找的所有相关解决方案都找到了第一个最重要的位,但我需要第一个最重要的解决方案.所以,给定0x00A1,我想要8(因为它是左起第9位).

我有一个非常奇怪的编译器行为,其中G ++将计算拉入热循环,严重降低了生成的代码的性能.这里发生了什么？

考虑这个功能:

#include <cstdint>

constexpr bool noLambda = true;

void funnyEval(const uint8_t* columnData, uint64_t dataOffset, uint64_t dictOffset, int32_t iter, int32_t limit, int32_t* writer,const int32_t* dictPtr2){
   // Computation X1
   const int32_t* dictPtr = reinterpret_cast<const int32_t*>(columnData + dictOffset);
   // Computation X2
   const uint16_t* data = (const uint16_t*)(columnData + dataOffset);
   // 1. The less broken solution without lambda
   if (noLambda) {
        for (;iter != limit;++iter){
            int32_t t=dictPtr[data[iter]];
            *writer = t;
            writer++;
        }
   }
   // 2. The totally broken solution with lambda
   else …

对于min(ctz(x), ctz(y))，我们可以使用ctz(x | y)来获得更好的性能。但是关于max(ctz(x), ctz(y))？

ctz表示“计数尾随零”。

C++ 版本（编译器资源管理器）

#include <algorithm>
#include <bit>
#include <cstdint>

int32_t test2(uint64_t x, uint64_t y) {
    return std::max(std::countr_zero(x), std::countr_zero(y));
}

Rust 版本（编译器资源管理器）

pub fn test2(x: u64, y: u64) -> u32 {
    x.trailing_zeros().max(y.trailing_zeros())
}

如果你有一个输入数组和一个输出数组,但是你只想写那些通过某个条件的元素,那么在AVX2中这样做最有效的方法是什么？

我在SSE看到它是这样做的:(来自:https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afredriksson_simd.pdf)

__m128i LeftPack_SSSE3(__m128 mask, __m128 val)
{
 // Move 4 sign bits of mask to 4-bit integer value.
 int mask = _mm_movemask_ps(mask);
 // Select shuffle control data
 __m128i shuf_ctrl = _mm_load_si128(&shufmasks[mask]);
 // Permute to move valid values to front of SIMD register
 __m128i packed = _mm_shuffle_epi8(_mm_castps_si128(val), shuf_ctrl);
 return packed;
}

这对于4宽的SSE来说似乎很好,因此只需要16个入口LUT,但对于8宽的AVX,LUT变得非常大(256个条目,每个32个字节或8k).

我很惊讶AVX似乎没有简化此过程的指令,例如带有打包的蒙版存储.

我想通过稍微改变来计算左边设置的符号位数,你可以生成必要的排列表,然后调用_mm256_permutevar8x32_ps.但这也是我认为的一些指示......

有没有人知道用AVX2做这个的任何技巧？或者什么是最有效的方法？

以下是上述文件中左包装问题的说明:

谢谢

我想在标准 C++ 中将任何大小整数的前导零位设置为 1。

例如。

0001 0011 0101 1111 -> 1111 0011 0101 1111

我发现执行此操作的所有算法都需要相当昂贵的前导零计数。然而，这很奇怪。有非常快速且简单的方法来执行其他类型的位操作，例如：

 int y = -x & x; //Extracts lowest set bit, 1110 0101 -> 0000 0001

 int y = (x + 1) & x; //Will clear the trailing ones, 1110 0101 - > 1110 0100

 int y = (x - 1) | x; //Will set the trailing zeros, 0110 0100 - > 0110 0111

因此，这让我认为必须有一种方法可以在由基本位运算符组成的一行简单代码中设置整数的前导零。请告诉我还有希望，因为现在我正在准备反转整数中的位顺序，然后使用设置尾随零的快速方法，然后再次反转整数以将前导零设置为 1。这实际上比使用前导零计数要快得多，但与上面的其他算法相比仍然相当慢。

 template<typename T>
 inline constexpr void reverse(T& x)
 {
    T rev …

我有四个2位位域存储在一个字节中.因此,每个位域可以表示0,1,2或3.例如,以下是前3个位域为零的4个可能值:

00 00 00 00 = 0 0 0 0
00 00 00 01 = 0 0 0 1
00 00 00 10 = 0 0 0 2
00 00 00 11 = 0 0 0 3

我想要一种有效的方法来对四个位域进行求和.例如:

11 10 01 00 = 3 + 2 + 1 + 0 = 6

现代Intel x64 CPU上的8位查找表需要4个周期才能从L1返回答案.似乎应该有一些方法来比这更快地计算答案.3个周期为6-12个简单位操作提供了空间.作为首发,简单的面具和换挡在Sandy Bridge上需要5个周期:

假设位字段是:d c b a,并且该掩码是:00 00 00 11

从艾拉帮助澄清:这假设a,b,c,和d是相同的,都被设置为初始byte.奇怪的是,我想我可以免费做到这一点.因为我每循环可以做2次加载,而不是加载byte一次,我可以加载它四次:a …

我对这两个指令都有点困惑.首先,让我们丢弃的特殊情况下,当扫描的值是0和未定义/ BSR或bitsize/lzcnt结果 - 这种差异是明显的,而不是我的问题的一部分.

我们来看二进制值 0001 1111 1111 1111 1111 1111 1111 1111

根据英特尔的规格,结果为lzcnt3

根据英特尔的规格,结果为bsr28

lzcntcount,bsr从位0返回索引或距离(即lsb).

两个指令如何相同,如何在CPU上没有可用的BMI的情况下lzcnt进行仿真bsr？或者bsr在msb的情况下是0位？英特尔规范中的"代码操作"也不同,一个是左边的计数或索引,另一个来自右边.

也许有人可以提供一些线索这光,我没有CPU无BMI/lzcnt指令测试,如果退回到bsr同样的结果作品(如值为0的特殊情况下扫描从未发生过).