标签: micro-optimization

我应该如何编写一个高效的异常类来显示可以通过在运行时修复源代码错误来防止的错误？

这就是我选择的原因std::invalid_argument。

我的异常类（显然不起作用）：

class Foo_Exception : public std::invalid_argument
{
private:
    std::string Exception_Msg;
public:
    explicit Foo_Exception( const std::string& what_arg );
    virtual const char* what( ) const throw( );
};

explicit Foo_Exception::Foo_Exception( const std::string& what_arg ) // how should I write this function???
{
    Exception_Msg.reserve( 130000 );

    Exception_Msg = "A string literal to be appended, ";
    Exception_Msg += std::to_string( /* a constexpr int */ );
    Exception_Msg += /* a char from a const unordered_set<char> */;
}

const char* Foo_Exception::what( ) …

英特尔建议使用指令前缀来减轻 JCC 勘误对性能的影响。

如果使用 MSVC 进行编译，则会/QIntel-jcc-erratum遵循建议，并插入带前缀的指令，如下所示：

3E 3E 3E 3E 3E 3E 3E 3E 3E 48 8B C8   mov rcx,rax ; with redundant 3E prefixes

他们说，当前缀不可用时，MSVC 会求助于 NOP。

Clang 有-mbranches-within-32B-boundaries这个选项，nop如果需要，它更喜欢多字节（https://godbolt.org/z/399nc5Msq通知xchg ax, ax）

3E 前缀的后果是什么，具体来说：

• 为什么 Intel 推荐这个而不是多字节 NOP？
• 对于未受影响的 CPU 会产生什么后果？
• 据报道，AMD 上的程序运行速度更快/QIntel-jcc-erratum，可能的解释是什么？

明确的 DNA 序列仅由核碱基腺嘌呤 (A)、胞嘧啶 (C)、鸟嘌呤 (G)、胸腺嘧啶 (T) 组成。对于人类消费，基数可以用相应的char大写或小写字母表示：A, C, G, T, 或a, c, g, t。然而，当需要存储长序列时，这种表示方式效率低下。由于只需要存储四个符号，因此可以为每个符号分配一个2位代码。UCSC指定的常用.2bit格式正是这样做的，使用以下编码：T = 、C = 、A = 、G = 。0b000b010b100b11

下面的 C 代码显示了为清晰起见而编写的参考实现。转换表示为序列的基因组序列的各种开源软件通常使用由每个序列char索引的 256 条目查找表。char这也与 的内部表示隔离char。然而，即使访问的是片上高速缓存，存储器访问也非常昂贵，并且通用表查找很难进行 SIMDize。因此，如果可以通过简单的整数算术来完成转换，则将是有利的。鉴于 ASCII 是占主导地位的char编码，我们可以对此进行限制。

将 ASCII 字符给出的核碱基转换为其.2bit表示形式的有效计算方法是什么？

/* Convert nucleobases A, C, G, T represented as either uppercase or lowercase
   ASCII characters …

int main()
{
00211000  push        ebp  
00211001  mov         ebp,esp  
00211003  sub         esp,10h  
    char charVar1;
    short shortVar1;
    int intVar1;
    long longVar1;
    
    charVar1 = 11;
00211006  mov         byte ptr [charVar1],0Bh  

    shortVar1 = 11;
0021100A  mov         eax,0Bh  
0021100F  mov         word ptr [shortVar1],ax  

    intVar1 = 11;
00211013  mov         dword ptr [intVar1],0Bh 
 
    longVar1 = 11;
0021101A  mov         dword ptr [longVar1],0Bh  
}

其他数据类型不通过寄存器，但只有短类型通过寄存器。怎么了？

我这里有一些例程，它们都做同样的事情：它们将浮点数限制在 [0,65535] 范围内。令我惊讶的是，编译器（gcc -O3）使用三种不同的方式来实现 float-min 和 float-max。我想了解为什么它会生成三种不同的实现。好的，这是 C++ 代码：

float clamp1(float x) {
    x = (x < 0.0f) ? 0.0f : x;
    x = (x > 65535.0f) ? 65535.0f : x;
    return x;
}

float clamp2(float x) {
    x = std::max(0.0f, x);
    x = std::min(65535.0f, x);
    return x;
}

float clamp3(float x) {
    x = std::min(65535.0f, x);
    x = std::max(0.0f, x);
    return x;
}

这是生成的程序集（删除了一些样板）。可在https://godbolt.org/z/db775on4j上使用 GCC10.3重现-O3。（还显示 clang14 的选择。）

CLAMP1:
    movaps  %xmm0, %xmm1
    pxor    %xmm0, %xmm0
    comiss …

Agner发现，在大多数支持这些指令的处理器上，应用于内存操作数的 x86 位操作指令（btr bts btc、无锁）比其他读-修改-写指令（如 add、xor 等）慢。为什么是这样？这些说明似乎非常容易实施。

是否因为实际加载的地址与内存操作数指定的地址不同，这混淆了一些跟踪内存访问的前端机制？这似乎是合理的，但我不认为它会影响吞吐量（至少不会影响那么多）；只有延迟。

对于只有两个可能的代码执行分支的情况，在 c++20 中使用[[likely]]和属性的一般准则是什么？[[unlikely]]是否建议仅将[[likely]]or[[unlikely]]放在执行路径的一个分支上，或者我们应该将其中之一放在一个代码分支上，将另一个放在其余分支上。例如，我们应该做

if (condition) [[likely]]
{
}
else [[unlikely]]
{
}

或者

if (condition) [[likely]]
{
}
else
{
}

当我们知道 if 条件中的分支更有可能被执行时。

我想对设置位的所有索引求和。

http://bitmath.blogspot.com/2023/01/weighted-popcnt.html?m=1 \n有一个有趣的实现：

// sum of indexes of set bits\nint A073642(uint64_t n)\n{\n    return __popcnt64(n & 0xAAAAAAAAAAAAAAAA) +\n          (__popcnt64(n & 0xCCCCCCCCCCCCCCCC) << 1) +\n          (__popcnt64(n & 0xF0F0F0F0F0F0F0F0) << 2) +\n          (__popcnt64(n & 0xFF00FF00FF00FF00) << 3) +\n          (__popcnt64(n & 0xFFFF0000FFFF0000) << 4) +\n          (__popcnt64(n & 0xFFFFFFFF00000000) << 5);\n}\n

（Godbolt：针对 MSVC、GCC 和 clang 的 x86-64-v3（AVX2，如 Haswell）编译器生成的 asm，有趣的是，它自动矢量化了四个 popcount。）

但是，我正在寻找一种无需多次使用 popcount 即可实现的方法。

我尝试在装配中执行此操作。popcount 操作相当快，但它可以用较少数量的指令完成，因为在每个 popcount 中我们重复相同的阶段（特别是如果硬件 popcount 不可用，比如在 RISC-V 上，或者 Nehalem 之前的 x86） 。

这就像一个“位拼图\xe2\x80\x9d”，我可能应该使用一些智能掩码和汇编的基本指令（算术/逻辑运算、条件移动/设置/跳转），但我不\xe2\x80\ x99不知道怎么做。 …

举个简单的例子：

struct has_destruct_t {
    int a;
    ~has_destruct_t()  {}
};

struct no_destruct_t {
    int a;
};


int bar_no_destruct(no_destruct_t);
int foo_no_destruct(void) {
    no_destruct_t tmp{};
    bar_no_destruct(tmp);
    return 0;
}

int bar_has_destruct(has_destruct_t);
int foo_has_destruct(void) {
    has_destruct_t tmp{};
    bar_has_destruct(tmp);
    return 0;
}

foo_has_destruct代码生成稍差一些，因为析构函数似乎强制tmp进入堆栈：

foo_no_destruct():                   # @foo_no_destruct()
        pushq   %rax
        xorl    %edi, %edi
        callq   bar_no_destruct(no_destruct_t)@PLT
        xorl    %eax, %eax
        popq    %rcx
        retq
foo_has_destruct():                  # @foo_has_destruct()
        pushq   %rax
        movl    $0, 4(%rsp)
        leaq    4(%rsp), %rdi
        callq   bar_has_destruct(has_destruct_t)@PLT
        xorl    %eax, %eax
        popq    %rcx
        retq

https://godbolt.org/z/388K1EfYa

但是，考虑到析构函数是 1）普通内联的并且 2）空的，为什么需要这样的情况呢？ …

在二分搜索中,我们有两个比较,一个用于大于,另一个用于小于,否则是中间值.您将如何优化以便我们只需要检查一次？

bool binSearch(int array[], int key, int left, int right)
{

    mid = left + (right-left)/2;
    if (key < array[mid])
        return binSearch(array, key, left, mid-1);
    else if (key > array[mid])
        return binSearch(array, key, mid+1, right);
    else if (key == array[mid])
        return TRUE; // Found

    return FALSE; // Not Found
}