相关疑难解决方法(0)

32位的比较比64位的比较快吗？

我在看这个文件http://www.netlib.org/fdlibm/s_cos.c

他们有这段代码

    /* |x| ~< pi/4 */
    ix &= 0x7fffffff;
    if(ix <= 0x3fe921fb) return __kernel_cos(x,z);

我理解第一行，它计算x的绝对值。但为什么比较如此复杂？通过比较前 32 位而不是全部 64 位，性能是否有任何改进？我能写吗

long unsigned int ix = *(long unsigned int * (&x));
ix &= 0x7fffffffffffffff;
if (ix < 3fe921fb54442d18) 
/* What comes next */

并期望在 64 位机器上获得相同的速度性能？虽然我同意这会消耗更多内存。

0x3fe921fb54442d18 是 pi/2。

英特尔建议使用指令前缀来减轻 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，可能的解释是什么？

当谈到从容器中删除多个元素时，C++ 中有一个“擦除-删除”习惯用法，并且有关于替代“调整大小-删除”方式的讨论，例如，此处。人们说“擦除删除”比“调整大小删除”更好，但根据我的测试，后者在矢量上（稍微）更快。那么，当涉及到矢量时我应该使用“调整大小删除”吗？

这是我的基准测试代码：

#include <benchmark/benchmark.h>

#include <algorithm>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

using namespace std;

constexpr size_t N_ELEMS = 1000000;
constexpr int MAX_VAL = N_ELEMS / 10;
constexpr int THRESH = MAX_VAL / 5 * 3;

static vector<int> generate_input() {
  vector<int> nums(N_ELEMS);

  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution<> dist(0, N_ELEMS);

  std::generate(nums.begin(), nums.end(), std::bind(dist, std::ref(gen)));

  return std::move(nums);
}

static void bm_erase_remove(benchmark::State &state) {
  for (auto _ : state) {
    state.PauseTiming();
    auto nums = generate_input();
    state.ResumeTiming();
    nums.erase(std::remove_if(nums.begin(), …

[底部加粗的问题]

当汇编程序生成二进制编码时,它需要决定是使每个分支变长还是短,如果可能的话,短路更好.汇编程序的这一部分称为分支位移优化(BDO)算法.一种典型的方法是汇编程序使所有分支编码变短(如果它们小于某个阈值),然后迭代地增加任何分支跳转到未到达的long.当然,这可以导致其他分支转换为跳远.因此,汇编程序必须不断通过跳转列表,直到不再需要升迁.这种二次时间方法对我来说似乎是一种最优算法,但据推测BDO是NP完全的,这种方法实际上并不是最优的.

兰德尔海德提供了一个反例:

                  .386 
                  .model  flat, syscall
00000000          .code
00000000          _HLAMain        proc


00000000  E9 00000016          jmpLbl:         jmp     [near ptr] target
00000005 = 00000005            jmpSize         =       $-jmpLbl
00000005  00000016 [                           byte    32 - jmpSize*2
dup
(0)
            00
           ]
0000001B                       target:
0000001B                       _HLAMain        endp
                                                end

通过在括号"[near ptr]"中添加部分并强制进行5字节编码,二进制实际上最终会变短,因为分配的数组比跳跃大小的两倍小.因此,通过使跳转编码更短,最终代码实际上更长.

这对我来说似乎是一个非常病态的情况,并不是真正相关的,因为分支编码仍然较小,它只是对程序的非分支部分的这种奇怪的副作用,导致二进制变大.由于分支编码本身仍然较小,我并不认为这是"开始小"算法的有效反例.

我可以将start-small算法视为最佳BDO算法,还是存在一个实际情况,即它不能为所有分支提供最小的编码大小？

我有一个在 C++ 中计算字符串编辑距离的函数：

#include <string>
#include <vector>
#include <algorithm>

size_t sed_diff(const std::string & a, const std::string & b) {

    std::vector<size_t> cp(b.length() + 1);
    std::vector<size_t> cc(b.length() + 1);

    // Edit distance on postorder traversal.
    for (int j = 0; j <= b.length(); ++j) {
        cp[j] = j;
    }
    for (int i = 1; i <= a.length(); ++i) {
        cc[0] = i;
        for (int j = 1; j <= b.length(); ++j) {
            unsigned int c1 = a[i - 1];
            unsigned int c2 …

我从同事那里听说 C++ 比 Java 更快，在寻求最高性能时，特别是对于金融应用程序，这是一条必经之路。但我的观察有点不同。谁能指出我实验的失败或在讨论中添加一些科学变量？

注1：我在 C++ 编译器中使用-O3（最大优化）和-O2 。

注2：包含每种语言的简短完整源代码。您可以随意在自己的机器上运行、进行更改、得出结论并分享。

注意3：如果将两个源代码并排放在编辑器中，您将看到它们的实现是等效的。

更新：我尝试clang++过g++各种优化选项（-O2、-O3、-Os、-march=native等），它们都产生了比 Java 慢的结果。我认为此时为了使 C++ 更快，我必须深入研究生成的汇编代码并进行一些汇编编程。我想知道在编写大型实际应用程序时这种方法（汇编编程和汇编调试）有多实用。

基准测试有什么作用？

• 在堆中（而不是在堆栈中）创建一个int数组
• 启动时钟
• 填充数组
• 使用冒泡排序对数组进行排序
• 停止时钟

执行 1000 万次，丢弃前 100 万次进行预热，并输出平均、最短和最长时间。

对于C++我得到：（使用 -O3 和 -O2）

$ g++ --version
g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

$ g++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -O3
$ ./TimeBubbleSort 10000000 1000000 60
Value …

我有一个繁重的数字运算程序,可以进行图像处理.它主要是卷积.它是用C++编写的,用Mingw GCC 4.8.1编译.我在配备Intel Core i7 4900MQ(SSE高达SSE4.2和AVX2)的笔记本电脑上运行它.

当我告诉GCC使用SSE优化(使用-march = native -mfpmath = sse -msse2)时,与使用默认的x87 FPU相比,我看不到加速.

当我使用双打而不是浮动时,没有减速.

我的理解是,当使用浮动而不是双重时,SSE应该给我2倍的加速.我错了吗？

我正在尝试编写一个与numpy.sum双精度数组一样快的 C 程序，但似乎失败了。

以下是我衡量 numpy 性能的方法：

import numpy as np
import time

SIZE=4000000
REPS=5

xs = np.random.rand(SIZE)
print(xs.dtype)

for _ in range(REPS):
    start = time.perf_counter()
    r = np.sum(xs)
    end = time.perf_counter()
    print(f"{SIZE / (end-start) / 10**6:.2f} MFLOPS ({r:.2f})")

输出是：

float64
2941.61 MFLOPS (2000279.78)
3083.56 MFLOPS (2000279.78)
3406.18 MFLOPS (2000279.78)
3712.33 MFLOPS (2000279.78)
3661.15 MFLOPS (2000279.78)

现在尝试在 C 中做类似的事情：

float64
2941.61 MFLOPS (2000279.78)
3083.56 MFLOPS (2000279.78)
3406.18 MFLOPS (2000279.78)
3712.33 MFLOPS (2000279.78)
3661.15 MFLOPS (2000279.78)

编译并gcc -o main …