C++ 提速的新发现

雷达

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

自相关两层循环，内层循环涉及浮点数计算，试验了一下把内层循环内部全都 comment out 只留个壳子,  但空的内层循环本身就把速度拉下来了，看来问题并不在浮点计算。
4 l; y$ g5 R" e# G
速度优化问题真的很有意思啊。
/ i6 k6 i2 t0 R! E3 ~
" i. J2 c3 Q( H" \7 ~欢迎大家继续讨论

数值分析

拉下来？拉多少？
  G4 [; f; R: ?" C/ s把代码贴上来看看？
4 A' @0 h2 D6 l! x& l1 c( Q  `/ P
难道分支预测不准破坏流水线执行？不该啊。

沉宝

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

风雨无阻

Maybe Debug mode?

雷达

数值分析 发表于 2022-9-24 23:04
0 }5 i6 [" r5 ~9 p; Z( F拉下来？拉多少？
把代码贴上来看看？

) C/ \) N9 m! j  x6 O! A
void xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
5 ?) |  \5 q7 [* X( c{
        comp temp, xtimesy;
0 |. Q$ y1 ]8 c        xtimesy.re = 0;
. @$ v- T9 F$ W' y2 }+ g4 O        xtimesy.im = 0;
" |3 M+ E* j+ B* u% y3 I        int j0 = lenB - 1;
& T( \% X. d5 K0 v% [+ A        int    i, j, i1, reali;
        if (lenA % 2 == 1)
                reali = lenA + 1;
6 c' `9 ?1 y/ f  E& D- ], E% {" ^        else
                reali = lenA;
        reali /= 2;
$ @7 z5 ]0 }* v/ O& N
0 Q- u/ Q5 Y: b' J        int nconv = reali + lenB;
        //#pragma omp parallel for
, c. w+ O( U! A& z0 Z6 a        for (i = reali; i < nconv; i++)
. X( B9 A7 ^" ?6 k        {
0 B* ], E  x! x3 L2 t2 U1 e                temp.re = 0;
& j! U& [) d# C6 r$ z' B                temp.im = 0;
                i1 = i;
                for (j = j0; j >= 0; j--)
                {
& ^& L( c" M! R; @! b                        /* floating date operation */
* V, P$ t: R, g                }
        }
}

0 H/ {% q3 o" a& H* Nxcorr函数代码如上，comp是复数struct, 做过长度为11、19两个矢量的测试，和octave结果完全一样

红色部分是内循环，现在其内部操作都comment out 了, j0大概是 6000。
现在call xcorr 100次，耗时78s.
! j' w7 b" u5 U- ^1 m" F; m( h/ m
如果把红色部分内循环本身完全comment out， call xcorr 1000次，耗时 <1s.
! u  A: ?  }) D  G" Q
; l! e/ k9 Z8 C0 Y: P" A

雷达

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

& b6 j' [, s( ^3 D不应该，看我上面的回复。

4 d+ `5 r0 @% I9 j$ t我更怀疑是 VS 社区版的问题

数值分析

$ c" l  b7 G% I; L5 ^  {

雷达 发表于 2022-9-24 23:54
/ |6 V1 O. m0 g1 B7 w# Evoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
" V# d$ f+ }# n. V' r{
( [- o2 A* B: D7 B0 @) f3 p        comp temp, xtimesy;

0 `' I! b" b  h3 E: g+ K这个不是这么比的吧。。。

您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。
1 E" {; ]# _2 `& D, _# l
% V. ~1 m- Z  i4 ^; w而加上内循环，光jmp和dec指令就至少多执行了6000个，慢个几十倍不是正常的么？

雷达

数值分析 发表于 2022-9-25 00:20
' p9 V; l+ U; J9 x这个不是这么比的吧。。。
/ {# a9 b8 s" {5 _
2 u, X' g7 a. h3 |# _# ^- @您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

& j; D% P! w( x  e% B# h/ f$ h
, x) T7 {  q  Y* G有道理。
% d( }) n& K) r/ Q, \所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，记得 numeric 库里有算向量内积的，我回头试试。
$ \) P( ~* l1 m, D
我先尝试尽量用标准库，一个小程序，不想搞得太复杂。多谢了

沉宝

雷达 发表于 2022-9-25 00:46
6 ?$ Z2 d$ K" z  T/ Z有道理。
所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，这大 ...

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

沉宝

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

' F; B5 ^4 N9 t5 D1 s您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

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

. i/ g) Y' h- S3 Q5 M
. L4 z! g$ `; u! w现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果循环这样跑，花不了多少时间。

数值分析

沉宝 发表于 2022-9-25 01:48
4 L1 O- g/ ?. P8 M' c% }% `% _现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果 ...

* B* E3 v3 Z$ T
是的，兄台说的对。
2 Q* q5 J! X7 {
其实我想说的是 真正数值计算部分和代码中其他不直接计算的overhead的比值这个事儿。
  Q2 e8 \0 H( e
雷达兄构造测试用例的时候，屏蔽掉了所有计算的部分，使得剩下的都是overhead，这样run time比较的结果就显得好像不合理了。如果把计算加回去，计算部分的run time会dominate，结果就不那么离谱了。因为不好说，所以用指令数对比的方式试图直观地说明这一点。
3 M8 q' t; A1 |' \( u
比如说，如果有计算，那么跑六千个循环相对于计算应该用不了多少时间。但是如果一边是什么都不做，另一边是六千个循环，那六千个循环比什么都不做慢几十倍了，就不是那么不合理了。

9 c3 i) b2 E5 \* `8 h# Y当然也有可能像兄台说的，是优化参数的问题，但我觉得更多地是测试用例设计的不合理。

雷达

$ J1 V& T! ^" [( Z1 a

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

/ e+ Y& o+ {( }3 E  @% {又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差一倍，我上面这个差的太多了。
3 h0 l  k& ~$ O4 P- L0 W
' d4 s2 H7 p2 J" c) ?) S2 @我已经完全懵了。

沉宝

雷达 发表于 2022-9-25 04:47
4 A% u2 C. F, N1 D$ s) ^又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差 ...

时间差一倍的结果可以接受。
- d  c2 I( K( R
: ~, A' ]* Q2 {8 e4 S- A你还是用profile工具看看吧。现在大家都主观瞎猜。

数值分析

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

' o1 R: Y$ \: K6 B( N- e- ?


0 O' u) ?) `* J5 b能不能把这个也贴上来，看看和上一个有什么不同？

雷达

数值分析 发表于 2022-9-25 14:58
6 F2 N6 }. |7 Q- d能不能把这个也贴上来，看看和上一个有什么不同？

理了理思路，重新做了一个测试。
做了两个 vector 和 两个 float *, 都长 100000
6 t0 |6 d) j% Z) q4 z外循环 6000，里面先做随机数生成，模拟真实环境，避免数据的 cache.
" b% h: A1 Y8 T* k$ }, t
内循环试了4种方法，
4 \( N  e9 P0 o4 ^* K& Q3 H1. 直接调用 vector inner_product 247s
2. vector 循环点乘累加 237s
3. float * 循环点乘累加 204s
4. 空循环 100000 次 202s

不做内循环 200s
# p4 O$ Q6 [0 ^  G6 H' t- R
7 p& W  J2 [2 U- s* d你昨天说的对，内循环本身占比是很小的，大头在其他处理。
! P5 ^0 v: S  q: s( o% \另外可以看到， float * 循环点乘累加 并不差，比用vector 还更快。

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

# n5 S1 Q% L3 `" a. j% B7 T（为什么下面我贴的  b1 加 方括号里的 i , 显示出来却是 b1 ？方括号 i 消失了。 LOL . 改成  jj 好了，原来 方括号里的 i 是斜体标志  LOL）
; }/ v, K( C1 t8 ~
! t2 B1 m; w1 L2 T* w: a

        std::vector < float > vec1(N);
        std::vector < float > vec2(N);
0 h9 o! E; r  W* G. a& w        float* b1 = new float[N];
        float* b2 = new float[N];
8 ~* }5 o# k* Z- e; l
: F' l* R3 X, U! }4 u( J' P        for (int j = 0; j < 6000; j++)
        {
                std::generate(vec1.begin(), vec1.end(), []() {
                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 23.23));;
( L( u+ X8 _' t0 Q$ V/ J                        });
& K  w; h3 W8 J6 v. u6 I
                std::generate(vec2.begin(), vec2.end(), []() {
                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 24.31));;
                        });
5 v. C8 y2 T( {- y" A
                for (size_t jj = 0; jj < vec1.size(); jj++)
                {
                        b1[jj] = vec1[jj];
                }

                for (size_t jj = 0; jj < vec2.size(); jj++)
' V2 {, P, p& u9 {3 h1 P% m                {
                        b2[jj] = vec2[jj];
                }
- T7 K' F7 W6 {' y% G) g- c/ i) Y
0 w+ y7 a- a, K1 G* C* K  M                //Method - 1  N=100000 247s  
                //fresult = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
                                
( I2 F1 b# H( `0 }                //Method - 2  N=100000  237s
+ ]2 `+ O( }( I2 i2 V7 s                /*
                for (int jj = 0; jj < N ; jj++)
+ z7 W9 f# c5 D! Z+ @                {
                        fresult += vec1[jj] * vec2[jj];
                }
                */
! e# A( I6 ~, y4 |# u, S                                
                //Method - 3  N=100000 204s
" f9 ]0 S- Y0 E                /*
                for (int jj = 0; jj < N; jj++)
! n' l: |8 u$ t6 c% G5 v4 F' ^# m                {
                        fresult += b1[jj] * b2[jj];
                }
' C# [/ Q4 \$ P  U% @/ F4 q5 N) a5 M                */

                //Method - 4   202s
( x" I( Y0 M4 D: g6 Z. D3 R  W                /*
                for (int jj = 0; jj < N; jj++)
1 f( T1 t+ P1 m, s7 \2 B5 }                {
                        
6 ^  V" _7 @* G) H                }
1 `) T3 C+ i1 s                */
                //comment out all methods, N=100000  202s               
  I, X) I( y) S. ?: R        }

        delete []b1;
, P' G# x: f3 ^! p  P        delete []b2;

/ r8 B* Q9 o* F- w

机器猫

瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？

: K! L" X1 E' ~5 j% @2 i2 _# y+ n! w你第二个试验里面的j在循环里面又重新定义了啊，你确定真的跑了6000次？
! k6 _' I5 u* T( T

雷达

机器猫 发表于 2022-9-27 00:15
瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？
( c' ]; @& V. n: h) d6 ?4 S
8 u" Y7 u" c9 N你第二个试验里面的j在循环里面又重新定义 ...

# Y( m3 @6 A0 S6 n& P; x8 s内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL
) x% N0 ?9 X: y9 O! k/ ?2 L2 ]
不和它较劲了，瞎耽误工夫，我已经转到 ubuntu, 也准备顺便试试 avx2 向量化。

机器猫

雷达 发表于 2022-9-27 01:16
3 E" n  S- ?- E" v6 |+ C. t1 Z内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL
1 i4 m! Z% y$ q9 s: P3 m# f# g
不和它 ...

: F8 r+ g* Q; Y/ L9 g" I不过可以试试我说的register变量。前一个试验j是混在一堆其它变量里一起定义的，很有可能是在stack上，这样内存读写会更多，要是再碰上每次都需要加载cache就更慢了。
+ Q, T# C8 I# G  `. x后面一个是在循环那里定义的，说不定编译器就把它优化成register变量了

opensrc

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

雷声

雷达 发表于 2022-9-24 23:54
( @3 S7 I/ o/ avoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
{
        comp temp, xtimesy;

这个code里面如果Openmp没有被注释掉的话，那么temp那个变量应该是定义在循环里面，否则线程之间会存在争夺写入那个temp的风险。
5 f# G8 l) w4 S1 \7 L内层for循环如果没有内部操作的话，编译时应该被优化掉了，和你完全注册掉整个循环是一回事。可能你的编译设置没有打开优化？
# V) z* F, L& _1 D7 |VS社区版没有问题，我工作用的就是社区版，设置正常的话不会比商业版差。以前游说头头用Intel Compiler，他说不想花钱，而且差不了多少，就一直用到现在。