相关疑难解决方法(0)

我为Project Euler Q14编写了这两个解决方案,在汇编和C++中.它们是用于测试Collat​​z猜想的相同蛮力方法.装配解决方案与组装

nasm -felf64 p14.asm && gcc p14.o -o p14

C++是用.编译的

g++ p14.cpp -o p14

部件, p14.asm

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2 …

给定std::bitset<64> bits任意数量的位和位位置X(0-63)

在X位或更低位计数位的最有效方法是什么,如果未设置X位,则返回0

注意:如果设置该位,则返回始终至少为1

蛮力方式很慢:

int countupto(std::bitset<64> bits, int X)
{
  if (!bits[X]) return 0;
  int total=1;
  for (int i=0; i < X; ++i)
  {
    total+=bits[i];
  }
  return total;
}

这个count()方法bitset将为您popcount提供所有位,但bitset不支持范围

注意:这不是如何计算32位整数中的设置位数？因为它询问所有位而不是0到X的范围

在测量某些东西的同时,我测量的吞吐量比我计算的要低得多,我将其缩小到LZCNT指令(它也发生在TZCNT中),如以下基准所示:

  xor ecx, ecx
_benchloop:
  lzcnt eax, edx
  add ecx, 1
  jnz _benchloop

和:

  xor ecx, ecx
_benchloop:
  xor eax, eax  ; this shouldn't help, but it does
  lzcnt eax, edx
  add ecx, 1
  jnz _benchloop

第二个版本要快得多.它不应该.LZCNT没有理由对其输出有输入依赖性.与BSR/BSF不同,xZCNT指令总是覆盖其输出.

我在4770K上运行它,所以LZCNT和TZCNT没有被执行为BSR/BSF.

这里发生了什么？

我想知道各种大小的循环如何在最近的x86处理器上执行,作为uop数的函数.

以下是彼得·科德斯(Peter Cordes)的一句话,他在另一个问题中提出了非多数的问题:

我还发现,如果循环不是4 uop的倍数,则循环缓冲区中的uop带宽不是每个循环的常数4.(即它是abc,abc,......;不是abca,bcab,......).遗憾的是,Agner Fog的microarch doc对循环缓冲区的这种限制并不清楚.

问题是关于循环是否需要是N uop的倍数才能以最大uop吞吐量执行,其中N是处理器的宽度.(即最近的英特尔处理器为4).在谈论"宽度"和计算微动时,有很多复杂因素,但我大多想忽略这些因素.特别是,假设没有微观或宏观融合.

Peter给出了以下一个循环,其中包含7个uop的循环:

一个7-uop循环将发出4 | 3 | 4 | 3 | ...的组我没有测试更大的循环(不适合循环缓冲区),看看是否有可能从下一个指令开始迭代发布在与其分支相同的组中,但我不假设.

更一般地说,声称是x在其体内具有uops 的循环的每次迭代将至少进行ceil(x / 4)迭代,而不是简单地迭代x / 4.

对于部分或全部最新的x86兼容处理器,这是真的吗？

我想用AVX2指令加快以下操作,但我无法找到一种方法.

我得到了uint64_t data[100000]一大堆uint64_t和一个unsigned char indices[100000]字节数组.我想输出一个数组uint64_t Out[256],其中第i个值是所有data[j]这样的xor index[j]=i.

我想要的直接实现是这样的:

uint64_t Out[256] = {0};     // initialize output array
for (i = 0; i < 100000 ; i++) {
    Out[Indices[i]] ^= data[i];
}

我们可以使用AVX2指令更有效地实现这一点吗？

编辑:这是我的代码现在的样子

uint64_t Out[256][4] = {0};   // initialize output array
for (i = 0; i < 100000 ; i+=4) {
    Out[Indices[i  ]][0] ^= data[i];
    Out[Indices[i+1]][1] ^= data[i+1];
    Out[Indices[i+2]][2] ^= data[i+2];
    Out[Indices[i+3]][3] ^= data[i+3];
}