像PEXT这样的组装说明实际用于什么？

Question

我在youtube上看了一个关于十大最疯狂的汇编语言指令的视频，其中一些指令对我来说没有明显的应用。像PEXT这样的东西有什么意义，它只接受第二个参数中与第一个参数中的1s索引匹配的位？编译器如何知道何时使用这条指令？关于无进位乘法的相同/类似问题。

免责声明：我对汇编语言知之甚少。也许我应该读一读！

我希望这个问题适合堆栈溢出。

Answer 1

以下内容与PDEP/PEXT的用法没有直接关系，因为它与性能有关，但它会影响其使用是否合理。我在Windows 11下有一个Zen2 Ryzen Threaddropper 3990X CPU，我在Windows下使用MSVC和Intel C的内部函数测试了PDEP和PEXT的吞吐量，在Linux下使用了clang和g。代码如下：

c++++ prettyprint-override">#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cstdint>
#include <atomic>
#if defined(_MSC_VER)
    #include <intrin.h>
#elif defined(__GNUC__) || defined(__llvm__)
    #include <immintrin.h>
#endif

using namespace std;
using namespace chrono;

atomic_uint64_t aSum( 0 );

int main()
{
    constexpr size_t
        N = 0x1000,
        ROUNDS = 10'000;
    vector<uint64_t> data( N, 0 );
    mt19937_64 mt;
    uniform_int_distribution<uint64_t> uid( 0, -1 );
    for( uint64_t &d : data )
        d = uid( mt );
    auto pdep = []( uint64_t data, uint64_t mask ) -> uint64_t { return _pdep_u64( data, mask ); };
    auto pext = []( uint64_t data, uint64_t mask ) -> uint64_t { return _pext_u64( data, mask ); };
    auto bench = [&]<typename Permute>( Permute permute ) -> double
    {
        uint64_t sum = 0;
        auto start = high_resolution_clock::now();
        constexpr uint64_t MASK = 0x5555555555555555u;
        for( size_t r = ROUNDS; r--; )
            for( uint64_t d : data )
                sum += permute( d, MASK );
        double ns = (double)(int64_t)duration_cast<nanoseconds>( high_resolution_clock::now() - start ).count() / ((double)N * ROUNDS);
        ::aSum = sum;
        return ns;
    };
    cout << bench( pdep ) << endl;
    cout << bench( pext ) << endl;
}

根据agner.org的数据，在我的Zen2 CPU上，PDEP / PEXT的延迟和吞吐量应该略低于20个时钟周期。在英特尔自Haswell CPUs上，延迟仅为3个时钟周期，而吞吐量却高达一个时钟周期。< br >但是根据我的测量，每条指令大约需要35ns，也就是说，在我的CPU上大约需要150个时钟周期。没有测量误差，我检查的反汇编与你在汇编中写的相符。所以很好奇其他CPU的数据。也许你会在这里举报。评估使用PDEP或PEXT是否有意义会有所帮助。

Answer 2

PDEP（并行存取）和 PEXT（并行存取）旨在成为提取和存放位字段的便捷方法。我敢打赌，它们有很好的低级用例。

对于实际用途 - 我编写了一个数独求解器，它在几个函数中使用 PEXT 来提取位值。多亏了 PEXT，我能够在一条指令中提取 4 个元素（而正常方法为 1 个）。真的很方便。如果你真的想要，我可以在编译器资源管理器上放一个代码片段来显示差异。

Answer 3

您可以找到论文中列出的有关PDEP/PEXT硬件单元的一些应用

有许多新兴的应用，如密码学、成像和生物识别，需要更高级的位操作操作。虽然这些可以通过更简单的逻辑和移位操作来构建，但是如果处理器能够支持更强大的位操作指令，使用这些高级位操作操作的应用程序将会显著加速。这种操作包括任意位置换、并行执行多个位字段提取操作以及并行执行多个位字段存放操作。我们分别将这些操作称为置换(perm)、并行提取(pex)或位聚集，以及并行存放(pdep)或位分散操作。

在通用处理器中有效地执行高级位操作

位排列在位板中极为常见，例如反向字节/字或镜像位数组。其中有很多算法需要大量的位操作，在PEXT/PDEP时代之前，人们必须创造性地做到这一点。后来，许多纸牌游戏引擎也使用这种技术来处理一个或几个寄存器中的单个游戏集。

PDEP/PEXT还用于大大提高位交错性能，这在Morton代码等算法中很常见。这方面的一些例子：

• 如何解交错位（UnMorton化？）
• 如何对像素数据进行位条带化？
• 有什么快速的方法可以将单词中的位空格？
• 如何从8个bool值中创建一个字节（反之亦然）？

为位板发明的乘法技术也常用于Bit Twiddling Hacks中的许多算法，例如将位与64位乘法交织。当PDEP/PEXT可用时，不再需要此技术

你可以在比特排列和黑客的喜悦中找到更详细的信息

PDEP/PEXT的另一个用途是提取/合并位不在连续位置的字段，例如，反汇编立即数分散的RISC-V指令，以使硬件设计更简单，但也使在没有PDEP/PEXT的软件上工作更混乱

其他一些应用程序：

我认为pext/pdep指令对4-着色问题、3-SAT、约束求解器等有巨大的影响。更多的研究人员可能应该研究这两个指令。

只要看看二元决策图，和其他这样的组合数据结构，你肯定能看到PEXT / PDEP的潜在用途无处不在。

https://news.ycombinator.com/item?id=19137260

编译器如何知道何时使用这条指令？

编译器可以识别常见模式并优化指令序列，但是对于像这样的高级东西，程序员通常需要从高级代码中显式调用内部函数