C++ 提速的新发现

雷达

C++ 比 Octave 慢好多，怎么破？

自相关两层循环，内层循环涉及浮点数计算，试验了一下把内层循环内部全都 comment out 只留个壳子,  但空的内层循环本身就把速度拉下来了，看来问题并不在浮点计算。

* x' s9 U3 E* ]4 F速度优化问题真的很有意思啊。
0 }0 i( o4 |# G) L! h7 y; A! f/ }7 k" D
欢迎大家继续讨论

数值分析

拉下来？拉多少？
把代码贴上来看看？
$ `! y6 A. e' S& B& a
: Q/ n+ m4 y9 L/ i, ?难道分支预测不准破坏流水线执行？不该啊。

沉宝

会不会代码本身的缺陷阻止了自动优化？另外，硬件配置和开发环境可能也有关系。

风雨无阻

Maybe Debug mode?

雷达

数值分析 发表于 2022-9-24 23:04
1 ]: w; A* T+ ^/ w% B5 I拉下来？拉多少？
把代码贴上来看看？

void xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
7 w" r1 D) Y+ i. |{
        comp temp, xtimesy;
        xtimesy.re = 0;
        xtimesy.im = 0;
        int j0 = lenB - 1;
        int    i, j, i1, reali;
2 y8 V# _' M, r, B+ Q        if (lenA % 2 == 1)
+ n. `# t4 H2 H, ~                reali = lenA + 1;
        else
                reali = lenA;
2 v- @1 L5 H. g, l        reali /= 2;
8 B' Q- h4 v, F) Z& _1 c/ y" l
        int nconv = reali + lenB;
* z  l1 Y- a0 G! P/ X+ t0 V" a' ?7 l4 s) ?        //#pragma omp parallel for
        for (i = reali; i < nconv; i++)
        {
                temp.re = 0;
: p& n1 ]" V, N. @  K* g                temp.im = 0;
                i1 = i;
                for (j = j0; j >= 0; j--)
                {
6 [4 Q6 g" I9 e9 F# t                        /* floating date operation */
                }
5 n# r1 T) O6 ^% O! V7 J        }
}

; N! H: H8 m; f6 y; Z7 w  J0 @) ^xcorr函数代码如上，comp是复数struct, 做过长度为11、19两个矢量的测试，和octave结果完全一样

0 J* e/ C8 z/ E, K' L) q红色部分是内循环，现在其内部操作都comment out 了, j0大概是 6000。
1 _  ]8 A- R' b% q" N# @现在call xcorr 100次，耗时78s.
7 C1 B$ D/ d" k% d
如果把红色部分内循环本身完全comment out， call xcorr 1000次，耗时 <1s.
4 m3 J2 O9 o0 w" ?& O2 s
% L$ M/ Q4 e: @, p

雷达

风雨无阻 发表于 2022-9-24 23:33
Maybe Debug mode?

不应该，看我上面的回复。
2 S: i# B& J" ^0 N4 F
* M( g& }5 {. j5 o9 F% C( x& [) P我更怀疑是 VS 社区版的问题

数值分析

雷达 发表于 2022-9-24 23:54
& }3 d* J2 I* o! `- Mvoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
0 F9 B' T3 a/ n! U6 P{
* M+ z7 c5 V+ L* `        comp temp, xtimesy;

  o! E* _: @, a, }% f4 S
这个不是这么比的吧。。。
0 {2 X/ [1 R) p1 y, j0 _8 l' `" c2 r! y
您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

而加上内循环，光jmp和dec指令就至少多执行了6000个，慢个几十倍不是正常的么？

雷达

数值分析 发表于 2022-9-25 00:20
这个不是这么比的吧。。。
' e4 C, I. D# C, q) N7 K8 g
您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

有道理。
所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，记得 numeric 库里有算向量内积的，我回头试试。
( S% y$ `5 n. V2 H4 \
  }; o8 O4 O: v$ Y% P' j我先尝试尽量用标准库，一个小程序，不想搞得太复杂。多谢了

沉宝

雷达 发表于 2022-9-25 00:46
( X1 J& i# o* `% ^0 z8 y有道理。
( _$ T5 u/ D8 Y2 Q: _+ m. U2 [所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，这大 ...

你两个试验之间就差了一个空循环， call 1000次按理不会有秒级差异，可能还是编译器优化的问题。举个例子，把循环本身翻译成机器指令loop或dec/jnz，两者速度上会差很多
Why is the loop instruction slow? Couldn't Intel have implemented it efficiently?

沉宝

数值分析 发表于 2022-9-25 00:20
3 _0 L3 k# `2 z$ v这个不是这么比的吧。。。

您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

而加上内循环，光jmp和dec指令就至少多执行了6000个

现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果循环这样跑，花不了多少时间。

数值分析

8 D5 e2 A' O0 m0 W6 Z

沉宝 发表于 2022-9-25 01:48
1 R. @% c/ G8 H7 z现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果 ...

4 h, o; g" N4 J3 F7 ~1 Z2 q
是的，兄台说的对。
$ [: T$ @" ^1 g) u, ^2 b" n, y' |6 M
1 e3 Q4 G! q6 @" F1 H5 e其实我想说的是 真正数值计算部分和代码中其他不直接计算的overhead的比值这个事儿。

. Q' R/ u5 w7 p' o4 z雷达兄构造测试用例的时候，屏蔽掉了所有计算的部分，使得剩下的都是overhead，这样run time比较的结果就显得好像不合理了。如果把计算加回去，计算部分的run time会dominate，结果就不那么离谱了。因为不好说，所以用指令数对比的方式试图直观地说明这一点。

比如说，如果有计算，那么跑六千个循环相对于计算应该用不了多少时间。但是如果一边是什么都不做，另一边是六千个循环，那六千个循环比什么都不做慢几十倍了，就不是那么不合理了。
) v% v' }$ G4 ~
当然也有可能像兄台说的，是优化参数的问题，但我觉得更多地是测试用例设计的不合理。

雷达

( \" V* K# W: x' ~' b

沉宝 发表于 2022-9-25 01:27
你两个试验之间就差了一个空循环， call 1000次按理不会有秒级差异，可能还是编译器优化的问题。举个例子 ...

  t# i1 y' |' L2 F0 q  u
, T/ ^. H+ J- O- W( n8 |! Y$ N6 P. R又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差一倍，我上面这个差的太多了。
, ^! j* N0 j7 A8 f! N6 a
1 U7 p1 T  F6 x: a& s$ t4 j我已经完全懵了。

沉宝

雷达 发表于 2022-9-25 04:47
又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差 ...

! v: C- e/ x, i  P+ A* K. \! A时间差一倍的结果可以接受。
6 [" i: P! I6 k
  ~& f7 x/ q( S  k% V& }你还是用profile工具看看吧。现在大家都主观瞎猜。

数值分析

雷达 发表于 2022-9-25 04:47
1 ]5 u9 Z) Q" ?又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差 ...

' Z; a3 R2 {1 A8 @: s# {- i% [
能不能把这个也贴上来，看看和上一个有什么不同？

雷达

数值分析 发表于 2022-9-25 14:58
0 b" s5 O, `3 n- ?0 r能不能把这个也贴上来，看看和上一个有什么不同？

理了理思路，重新做了一个测试。
做了两个 vector 和 两个 float *, 都长 100000
- O/ f1 V4 ~. ]! f8 x, W2 g  ~( p, L外循环 6000，里面先做随机数生成，模拟真实环境，避免数据的 cache.

  R- ~* G) K5 C5 G8 r内循环试了4种方法，
1. 直接调用 vector inner_product 247s
2. vector 循环点乘累加 237s
3. float * 循环点乘累加 204s
& {6 P1 P, m+ J# p4 Y' s4. 空循环 100000 次 202s
6 _2 [1 J, R+ V2 _' I4 y5 z
不做内循环 200s
) a( t7 A9 r+ {/ y( D
6 J6 m; o! C5 x+ d8 H你昨天说的对，内循环本身占比是很小的，大头在其他处理。
另外可以看到， float * 循环点乘累加 并不差，比用vector 还更快。

至于我那个原始程序，还有一些疑问，见5楼，其他都不变仅仅是有无空的内循环就有很大不同，这是不对的，也许有一些其他缺陷我没有看到。（也许可以改成 while 试试）

（为什么下面我贴的  b1 加 方括号里的 i , 显示出来却是 b1 ？方括号 i 消失了。 LOL . 改成  jj 好了，原来 方括号里的 i 是斜体标志  LOL）
( _# A/ [5 D4 `+ i# q' w; ^/ @
8 E0 `! ~" N9 F1 ]# j1 d! q+ e; G

        std::vector < float > vec1(N);
  [; K) P$ e, @7 e        std::vector < float > vec2(N);
2 K" V/ ~$ q- E. _. a        float* b1 = new float[N];
        float* b2 = new float[N];

        for (int j = 0; j < 6000; j++)
        {
, k9 z3 @6 P8 ]- `7 m* x+ B! O                std::generate(vec1.begin(), vec1.end(), []() {
$ x; F# H0 J( ?; t5 o' b, Y                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 23.23));;
( G! V* r  [  D3 v7 b: }. B. F1 X6 P                        });

                std::generate(vec2.begin(), vec2.end(), []() {
                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 24.31));;
* l' u( P1 \. u  u                        });
2 E9 G( _# E' G6 j+ ?8 Y: }3 Y3 B
; W0 k5 V* n, }) x4 `% C) A                for (size_t jj = 0; jj < vec1.size(); jj++)
6 Z; N9 \+ _  p' L                {
                        b1[jj] = vec1[jj];
                }

' P! k4 w  I1 d; j                for (size_t jj = 0; jj < vec2.size(); jj++)
                {
                        b2[jj] = vec2[jj];
                }
5 M6 l0 T- a0 T
: W8 G8 |7 L4 f- N& F6 H: y' G                //Method - 1  N=100000 247s  
! I& @! S; k7 `& S# H3 O; d. o                //fresult = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
                                
                //Method - 2  N=100000  237s
6 t# C. p4 J* d8 P4 T                /*
                for (int jj = 0; jj < N ; jj++)
. k( [: Z5 q! h6 P! _& L6 y9 ?* _                {
3 s) v9 _  Y0 L7 r                        fresult += vec1[jj] * vec2[jj];
                }
+ ]" E7 U* ?! n) x( @                */
                                
4 q. Z+ W; _7 K% E" F" J                //Method - 3  N=100000 204s
! H% {$ b2 |, o5 A( t6 M                /*
                for (int jj = 0; jj < N; jj++)
. x% P( E# d, G2 `5 v; f% ^                {
! V5 G% u$ e( c                        fresult += b1[jj] * b2[jj];
                }
                */
1 c( q$ x- |* z, k( N1 o' ~
: F4 C% a# B8 ]' v                //Method - 4   202s
                /*
1 T9 q1 x$ u; f( f6 Q+ @; W/ x; ~                for (int jj = 0; jj < N; jj++)
) w5 m' O! I3 z6 K! t5 |                {
: E4 _1 Z# n: J! c4 E                        
7 M9 t6 O& u: O  s% O; E                }
4 `$ o; t& |3 m3 T* z+ z: c0 w                */
) B' r+ R; c# ]. Q  c& A2 {, p                //comment out all methods, N=100000  202s               
2 Q% |3 D+ E$ m! \4 u1 a* [        }
2 v- c* h) ?8 E& C) o3 `+ P
        delete []b1;
        delete []b2;

- a3 ^* m7 S, V, Q2 |

机器猫

瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？
; w$ w& ~6 I0 E/ t3 ^
你第二个试验里面的j在循环里面又重新定义了啊，你确定真的跑了6000次？
- Q: ~% n, ]$ |0 G& T) C

雷达

机器猫 发表于 2022-9-27 00:15
瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？
1 L$ r  G) z1 f$ O; i  p$ F' v) ?5 u
! q* g) W9 K& Y你第二个试验里面的j在循环里面又重新定义 ...

内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL
8 t, v" x8 k$ L; r3 m; S& i3 B
/ U' }. E9 K7 q1 R3 \不和它较劲了，瞎耽误工夫，我已经转到 ubuntu, 也准备顺便试试 avx2 向量化。

机器猫

雷达 发表于 2022-9-27 01:16
内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL

; }+ K1 \9 E& d* `( \" t% N不和它 ...

; j$ B6 j, ~! a" Q
不过可以试试我说的register变量。前一个试验j是混在一堆其它变量里一起定义的，很有可能是在stack上，这样内存读写会更多，要是再碰上每次都需要加载cache就更慢了。
后面一个是在循环那里定义的，说不定编译器就把它优化成register变量了

opensrc

一个无关问题，为什么爱坛的帖子里在我这里有好些奇怪的东东在里面，是防拷贝措施吗？

雷声

雷达 发表于 2022-9-24 23:54
void xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
{
        comp temp, xtimesy;

这个code里面如果Openmp没有被注释掉的话，那么temp那个变量应该是定义在循环里面，否则线程之间会存在争夺写入那个temp的风险。
内层for循环如果没有内部操作的话，编译时应该被优化掉了，和你完全注册掉整个循环是一回事。可能你的编译设置没有打开优化？
5 B5 `0 x8 l0 D- c3 |2 SVS社区版没有问题，我工作用的就是社区版，设置正常的话不会比商业版差。以前游说头头用Intel Compiler，他说不想花钱，而且差不了多少，就一直用到现在。