C++ 提速的新发现

雷达

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

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

速度优化问题真的很有意思啊。

- Q4 [. c' w' f5 n1 d% h+ P; y欢迎大家继续讨论

数值分析

拉下来？拉多少？
把代码贴上来看看？

难道分支预测不准破坏流水线执行？不该啊。

沉宝

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

风雨无阻

Maybe Debug mode?

雷达

* h3 b. K5 a# M. m

数值分析 发表于 2022-9-24 23:04
2 _# ?+ o; c9 v5 q% s- h拉下来？拉多少？
3 |  Z' C9 M: p0 {( b5 {4 r把代码贴上来看看？

void xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
; D7 e% ]- @8 I7 S0 X2 V# n& a{
& x' }- _5 @& ?- o# R9 ~$ m        comp temp, xtimesy;
" H1 L7 n& M$ T5 B) @        xtimesy.re = 0;
        xtimesy.im = 0;
        int j0 = lenB - 1;
        int    i, j, i1, reali;
# a+ x- n9 A. n2 F4 I        if (lenA % 2 == 1)
4 k. l8 T+ D8 I* E                reali = lenA + 1;
        else
                reali = lenA;
5 K& l# F! J$ E2 K" D3 N        reali /= 2;

        int nconv = reali + lenB;
( y7 Y- _* T/ C. w( Q1 L        //#pragma omp parallel for
+ X8 a# S& f' G, ]        for (i = reali; i < nconv; i++)
0 u( [: y( B/ ?& Q6 \+ e: J' }+ N# x        {
; ?$ v( `" O: f3 {* E" n                temp.re = 0;
; \1 V7 W& Y( p# L& e8 e                temp.im = 0;
6 }# Q  j6 n1 ~7 J1 P2 L, H2 A( ^                i1 = i;
  U7 i" [1 S4 D9 k                for (j = j0; j >= 0; j--)
) _$ m4 M! D3 ^: L4 _; h1 H                {
                        /* floating date operation */
& U/ ], v3 {/ j. v0 E0 c                }
        }
7 ?7 B/ S% j+ y3 u0 n}
' I* S9 Y: e0 ~# V
4 R0 {- ~* M0 K* l! b% Zxcorr函数代码如上，comp是复数struct, 做过长度为11、19两个矢量的测试，和octave结果完全一样

" P3 d7 L- D( T2 A: g" h. W红色部分是内循环，现在其内部操作都comment out 了, j0大概是 6000。
0 d& `) _+ x( j4 J" y, E' Z8 N现在call xcorr 100次，耗时78s.
6 e5 n! O  m0 Y- ]! E9 o! d
. k/ w% |- w$ C  r3 K( h如果把红色部分内循环本身完全comment out， call xcorr 1000次，耗时 <1s.

雷达

风雨无阻 发表于 2022-9-24 23:33
. J" X( R6 M4 z/ i+ CMaybe Debug mode?

0 m7 h  }% V" ^! ~% _8 D9 D$ z
不应该，看我上面的回复。

1 h9 A, u. ^0 s我更怀疑是 VS 社区版的问题

数值分析

雷达 发表于 2022-9-24 23:54
& H! `) A2 ?% [9 @. O" ?+ n6 f% {void xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
8 [8 ]9 |' l  m+ ^8 x6 E{
        comp temp, xtimesy;

0 R7 ~4 r# o1 _1 q8 ~4 j$ D
, k) T5 E% }2 y6 A  v这个不是这么比的吧。。。

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

, d2 C. ]5 O0 h+ F' a) s# e, u而加上内循环，光jmp和dec指令就至少多执行了6000个，慢个几十倍不是正常的么？

雷达

; i" B* e: {# }+ E+ L, H

数值分析 发表于 2022-9-25 00:20
这个不是这么比的吧。。。

7 `5 m0 }$ b+ H2 y+ M9 S- h9 C6 j您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

有道理。
所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，记得 numeric 库里有算向量内积的，我回头试试。
8 n8 N5 s" ]$ y8 W, N4 y$ C
我先尝试尽量用标准库，一个小程序，不想搞得太复杂。多谢了

沉宝

雷达 发表于 2022-9-25 00:46
" P0 x9 _# z0 |6 I有道理。
所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，这大 ...

' m1 d' C$ O; k/ C, D* o你两个试验之间就差了一个空循环， call 1000次按理不会有秒级差异，可能还是编译器优化的问题。举个例子，把循环本身翻译成机器指令loop或dec/jnz，两者速度上会差很多
% ?+ _) V4 B3 n" P' b: \Why is the loop instruction slow? Couldn't Intel have implemented it efficiently?

沉宝

数值分析 发表于 2022-9-25 00:20
这个不是这么比的吧。。。
- A& L6 N; H: f/ p+ X. F% m# f7 B
. Z- }) c  T& ]8 \您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

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

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

数值分析

, [) P# F, ^5 e  P' {

沉宝 发表于 2022-9-25 01:48
8 k% m* r3 Q; n& P" L) B5 Q现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果 ...

是的，兄台说的对。
: B7 r1 ~, R6 F( g
其实我想说的是 真正数值计算部分和代码中其他不直接计算的overhead的比值这个事儿。
! o9 Z, s0 S7 s; y) G' V! @# @3 q4 t
雷达兄构造测试用例的时候，屏蔽掉了所有计算的部分，使得剩下的都是overhead，这样run time比较的结果就显得好像不合理了。如果把计算加回去，计算部分的run time会dominate，结果就不那么离谱了。因为不好说，所以用指令数对比的方式试图直观地说明这一点。
+ `8 G$ D8 k) V. [4 ^7 B
比如说，如果有计算，那么跑六千个循环相对于计算应该用不了多少时间。但是如果一边是什么都不做，另一边是六千个循环，那六千个循环比什么都不做慢几十倍了，就不是那么不合理了。

当然也有可能像兄台说的，是优化参数的问题，但我觉得更多地是测试用例设计的不合理。

雷达

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

9 C+ S0 ^2 s& m- q
5 ]* ]6 L: ?. p4 _; P3 s& K又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差一倍，我上面这个差的太多了。
, M9 a) j9 p; X( T8 \
我已经完全懵了。

沉宝

雷达 发表于 2022-9-25 04:47
" S5 N1 P; ^6 }& H4 u% A又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差 ...

; ~5 r  u/ p) `. H8 i4 B4 h时间差一倍的结果可以接受。

6 ^' S; r, u" @你还是用profile工具看看吧。现在大家都主观瞎猜。

数值分析

3 k5 U" _6 I$ ]/ v+ `

雷达 发表于 2022-9-25 04:47
7 U+ C) v, L: \* M% T' [又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差 ...

. z% M# b# c7 N5 ^

- [/ \5 z* W3 B; o
能不能把这个也贴上来，看看和上一个有什么不同？

雷达

数值分析 发表于 2022-9-25 14:58
能不能把这个也贴上来，看看和上一个有什么不同？

! }; M4 a2 T  K& F  @理了理思路，重新做了一个测试。
% \+ a- x9 t6 p; m+ W做了两个 vector 和 两个 float *, 都长 100000
( s# R+ o+ R. d6 ?+ l) L" V" t# P外循环 6000，里面先做随机数生成，模拟真实环境，避免数据的 cache.
$ {7 G; K: A' S( ?5 z) B( M
  p; r- Y: W+ O1 c2 x0 @内循环试了4种方法，
2 o' n9 R1 r/ y, C1. 直接调用 vector inner_product 247s
2. vector 循环点乘累加 237s
3. float * 循环点乘累加 204s
4. 空循环 100000 次 202s

, n- Q# s$ e8 s( a8 n不做内循环 200s
. v$ p5 e! o8 C7 u
你昨天说的对，内循环本身占比是很小的，大头在其他处理。
0 I% E7 \$ V- N# P7 h另外可以看到， float * 循环点乘累加 并不差，比用vector 还更快。
5 O" m5 o" B0 m% r
至于我那个原始程序，还有一些疑问，见5楼，其他都不变仅仅是有无空的内循环就有很大不同，这是不对的，也许有一些其他缺陷我没有看到。（也许可以改成 while 试试）
! U- E; ?- {$ s0 J$ M) R" o
0 H2 N( K( J2 _' L! g: C3 R（为什么下面我贴的  b1 加 方括号里的 i , 显示出来却是 b1 ？方括号 i 消失了。 LOL . 改成  jj 好了，原来 方括号里的 i 是斜体标志  LOL）

* J0 G* c( W1 M2 D/ G! W/ U

        std::vector < float > vec1(N);
        std::vector < float > vec2(N);
        float* b1 = new float[N];
        float* b2 = new float[N];

9 y* W0 @$ z: D0 Y% a        for (int j = 0; j < 6000; j++)
' X" h2 B$ o/ n) t+ J        {
6 d! J' f- z5 y! w' x                std::generate(vec1.begin(), vec1.end(), []() {
                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 23.23));;
                        });

; a4 n# R* _8 X' R% q' ^/ p                std::generate(vec2.begin(), vec2.end(), []() {
                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 24.31));;
) f: k' |2 U& X4 E4 o' ~                        });
$ C2 c0 \/ X- B  ]# |
                for (size_t jj = 0; jj < vec1.size(); jj++)
) s+ G8 H3 Q! E) O' i                {
                        b1[jj] = vec1[jj];
                }
3 Z3 }; `" q0 D1 B' T
; X0 l6 ~* N- D; ]: M( J9 d                for (size_t jj = 0; jj < vec2.size(); jj++)
8 e  {) Z* M0 C1 d+ e! r; @3 T                {
                        b2[jj] = vec2[jj];
7 c; j" V$ K/ e                }
. _5 C- a$ u  C
" D, A" E$ p0 f4 w% {3 y                //Method - 1  N=100000 247s  
                //fresult = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
, `1 H- c! q2 G) @! ^7 t* o4 \, P                                
9 A# t# u( j; v1 ?2 u# I1 A( f- i7 a                //Method - 2  N=100000  237s
                /*
                for (int jj = 0; jj < N ; jj++)
' Q9 D! D3 Y3 p- I: A4 h                {
                        fresult += vec1[jj] * vec2[jj];
( S/ P: y' x7 _5 R4 I# `6 `                }
' N( j; o. ~, H* l( Q) J& q                */
                                
                //Method - 3  N=100000 204s
, R. k2 {4 I  ?9 C/ I/ Y                /*
                for (int jj = 0; jj < N; jj++)
                {
                        fresult += b1[jj] * b2[jj];
3 v% M, t0 G$ P! J- q- g# B/ o                }
                */
# ~( F  H( }% f
3 [* i6 z0 i1 d  n2 Q, X                //Method - 4   202s
                /*
- I/ ^9 w- {( e. ]4 ^1 V0 F7 h2 Y                for (int jj = 0; jj < N; jj++)
                {
                        
                }
                */
                //comment out all methods, N=100000  202s               
        }

4 ?. l" U4 B) X' i, e! ^        delete []b1;
9 D1 x, P; ]+ [: R        delete []b2;

9 s( _# F% w) k' `1 d$ x+ X; e2 G

机器猫

瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？
5 P) R! M  i! J$ x9 y5 K
* H/ `+ b; C8 c你第二个试验里面的j在循环里面又重新定义了啊，你确定真的跑了6000次？

雷达

机器猫 发表于 2022-9-27 00:15
瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？

) Y, M8 O: k7 P# i1 c0 c你第二个试验里面的j在循环里面又重新定义 ...

! O/ e1 _3 ~/ N& }% _$ \: L4 |9 @内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL

不和它较劲了，瞎耽误工夫，我已经转到 ubuntu, 也准备顺便试试 avx2 向量化。

机器猫

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

. V" L* w. @% J) O2 q. v# [+ ]* q
  t# ], I  H! L5 ]* [# e不过可以试试我说的register变量。前一个试验j是混在一堆其它变量里一起定义的，很有可能是在stack上，这样内存读写会更多，要是再碰上每次都需要加载cache就更慢了。
$ Q% Z: g; a: F$ L, d" r# k2 m$ d后面一个是在循环那里定义的，说不定编译器就把它优化成register变量了

opensrc

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

雷声

雷达 发表于 2022-9-24 23:54
# x3 E% M- K' w7 K9 t; t9 Ovoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
{
) K. D1 Z  E5 l& |( P. B        comp temp, xtimesy;

- @3 ~! _' Z: w" V这个code里面如果Openmp没有被注释掉的话，那么temp那个变量应该是定义在循环里面，否则线程之间会存在争夺写入那个temp的风险。
4 a" {$ t0 a8 h& O) ?内层for循环如果没有内部操作的话，编译时应该被优化掉了，和你完全注册掉整个循环是一回事。可能你的编译设置没有打开优化？
VS社区版没有问题，我工作用的就是社区版，设置正常的话不会比商业版差。以前游说头头用Intel Compiler，他说不想花钱，而且差不了多少，就一直用到现在。