C++ 提速的新发现

雷达

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

5 {% ^) \! d8 Y$ h7 O3 y自相关两层循环，内层循环涉及浮点数计算，试验了一下把内层循环内部全都 comment out 只留个壳子,  但空的内层循环本身就把速度拉下来了，看来问题并不在浮点计算。
7 B4 |. i  ?; [5 J6 F0 U7 N
2 q$ Z! |0 A2 a# U! z速度优化问题真的很有意思啊。
! U+ ~, j. g$ n" `3 A
' K1 {, i6 y/ k' j  E" u欢迎大家继续讨论

数值分析

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

& y; E6 X  R8 ]7 b6 t' ^难道分支预测不准破坏流水线执行？不该啊。

沉宝

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

风雨无阻

Maybe Debug mode?

雷达

数值分析 发表于 2022-9-24 23:04
/ O6 G7 H0 `! h7 ^. h; j拉下来？拉多少？
! ?, ^# m, X" s4 |: q3 K把代码贴上来看看？

5 X% Y/ H2 `: Pvoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
{
        comp temp, xtimesy;
; \0 R2 ?0 M/ l6 r1 t1 O        xtimesy.re = 0;
( M' K  |7 p& b$ q        xtimesy.im = 0;
        int j0 = lenB - 1;
        int    i, j, i1, reali;
        if (lenA % 2 == 1)
" g! n3 }# S0 q                reali = lenA + 1;
        else
, O+ u- O+ b, V2 Y4 ]2 [9 v: h! \. ]9 ]                reali = lenA;
- ]. g- }7 ^$ p) E1 x9 ?: k7 k        reali /= 2;

9 N5 b: Z/ R  d% a        int nconv = reali + lenB;
# A9 ^# ~. N. _# Y0 p; h        //#pragma omp parallel for
        for (i = reali; i < nconv; i++)
# h4 \8 Z) F, M5 j* D4 F        {
3 J, j7 S7 E! E# c                temp.re = 0;
5 @' l0 l& M9 f4 z$ j                temp.im = 0;
( L8 S& {, T( l1 y                i1 = i;
# t" f9 y* t3 F0 b: p! J, X! u  ]                for (j = j0; j >= 0; j--)
                {
                        /* floating date operation */
                }
        }
8 T% J( t9 k( k) [# U" H}

xcorr函数代码如上，comp是复数struct, 做过长度为11、19两个矢量的测试，和octave结果完全一样

8 E# g* l+ N% N* U( Q& m红色部分是内循环，现在其内部操作都comment out 了, j0大概是 6000。
现在call xcorr 100次，耗时78s.

' r% v" X; P5 M  s' {" z. {% U如果把红色部分内循环本身完全comment out， call xcorr 1000次，耗时 <1s.

% ~) p3 q& Z9 {: K2 }* _, d7 i, ?

雷达

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

0 R+ d! T1 d# K0 J3 b( L+ o4 b( y7 U
不应该，看我上面的回复。

我更怀疑是 VS 社区版的问题

数值分析

  `- R8 ]  F5 c0 t% x7 n

雷达 发表于 2022-9-24 23:54
* t. C1 Y  {7 i  h  y1 P2 svoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
/ X/ t* U& y( U9 p+ b8 t{
        comp temp, xtimesy;

: O7 r7 ^4 l- Q! v这个不是这么比的吧。。。
0 D! N; C) \" M& c- @
2 Y4 Y! Z7 e) f% ], H2 a. r您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。
. J9 R/ o1 n. r
/ s3 ^5 e4 }1 U  G& [* i2 Y而加上内循环，光jmp和dec指令就至少多执行了6000个，慢个几十倍不是正常的么？

雷达

! E- K& S6 ]  J) m1 P0 n% U

数值分析 发表于 2022-9-25 00:20
( P! }! h: ?& z这个不是这么比的吧。。。
' d) n) v! X0 w: t9 C1 ]: `3 }
: B/ |4 F- e$ J3 f/ K! R您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

4 n: z$ F6 v7 ?% s2 g* i: ~有道理。
所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，记得 numeric 库里有算向量内积的，我回头试试。
/ i  q2 o  z. I) k5 d) [# n
我先尝试尽量用标准库，一个小程序，不想搞得太复杂。多谢了

沉宝

雷达 发表于 2022-9-25 00:46
有道理。
0 N' @. x) |4 ?7 P; l" e4 Z% w  W所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，这大 ...

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

沉宝

数值分析 发表于 2022-9-25 00:20
8 U5 x# A3 I# }4 F* B这个不是这么比的吧。。。
0 C; Y; S& X: P( |  R& r
6 H$ H  l, V" r您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

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

3 m9 d5 H: O7 F" \* D( V# c
现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果循环这样跑，花不了多少时间。

数值分析

; K  |9 O* P+ w

沉宝 发表于 2022-9-25 01:48
; T- n9 D8 d) o3 x' D. i现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果 ...

$ t' [4 d% D( P是的，兄台说的对。
5 g) ^% E7 A+ a& V  r$ K
其实我想说的是 真正数值计算部分和代码中其他不直接计算的overhead的比值这个事儿。

雷达兄构造测试用例的时候，屏蔽掉了所有计算的部分，使得剩下的都是overhead，这样run time比较的结果就显得好像不合理了。如果把计算加回去，计算部分的run time会dominate，结果就不那么离谱了。因为不好说，所以用指令数对比的方式试图直观地说明这一点。
' h8 r* x: z2 [2 M5 d) Y' p
比如说，如果有计算，那么跑六千个循环相对于计算应该用不了多少时间。但是如果一边是什么都不做，另一边是六千个循环，那六千个循环比什么都不做慢几十倍了，就不是那么不合理了。
* U. i) `; }. G8 S5 l
; S7 R* P& q( [5 i$ V8 p+ ]( t当然也有可能像兄台说的，是优化参数的问题，但我觉得更多地是测试用例设计的不合理。

雷达

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

! r* X1 b- T) x
又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差一倍，我上面这个差的太多了。
8 s4 o0 y5 q$ A1 k6 F  D+ Y. J
' y0 }+ R8 H6 o5 N) _我已经完全懵了。

沉宝

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

5 n) T! h1 q0 I& O时间差一倍的结果可以接受。

1 B5 c$ ^" f* D& O8 n7 Y- Y1 m# i你还是用profile工具看看吧。现在大家都主观瞎猜。

数值分析

9 u" L& ^* Q2 o8 j

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

/ y7 o3 L. a3 @1 g
; J  r( r+ i* \! e4 b5 M
. M; o* s' `3 C7 C# J能不能把这个也贴上来，看看和上一个有什么不同？

雷达

* v  ]5 ?  r: Z

数值分析 发表于 2022-9-25 14:58
% W6 ?+ U  V& u0 u能不能把这个也贴上来，看看和上一个有什么不同？

; P1 a" j3 I2 q7 L+ _: J: l8 X理了理思路，重新做了一个测试。
做了两个 vector 和 两个 float *, 都长 100000
  {* v7 m; s1 g, B3 @外循环 6000，里面先做随机数生成，模拟真实环境，避免数据的 cache.
+ l9 s7 R, r& o
, Z" Z2 J6 A# W内循环试了4种方法，
1. 直接调用 vector inner_product 247s
0 L6 e, |$ d( Y/ Q% v; i; o2. vector 循环点乘累加 237s
2 o0 d( l2 N" f; v4 k# e8 o3. float * 循环点乘累加 204s
8 F) x" ]) {/ `' F* ^$ U, J# i/ w4. 空循环 100000 次 202s
# L+ A5 d! V  R: o" o" E9 p* D
2 [% o; }: ?$ ?' q4 b8 b7 ?/ ^不做内循环 200s

. Y  H; ]* s& g4 E1 j6 k0 [你昨天说的对，内循环本身占比是很小的，大头在其他处理。
另外可以看到， float * 循环点乘累加 并不差，比用vector 还更快。
7 m0 w& R& m# F0 h* J
7 w8 n2 p5 l& q4 C至于我那个原始程序，还有一些疑问，见5楼，其他都不变仅仅是有无空的内循环就有很大不同，这是不对的，也许有一些其他缺陷我没有看到。（也许可以改成 while 试试）
9 j4 B( q/ p8 c  j* |& s7 [
' X8 s1 @( Z; c- C4 Q（为什么下面我贴的  b1 加 方括号里的 i , 显示出来却是 b1 ？方括号 i 消失了。 LOL . 改成  jj 好了，原来 方括号里的 i 是斜体标志  LOL）

        std::vector < float > vec1(N);
        std::vector < float > vec2(N);
0 S( e& Z0 _7 ?$ J) T+ a% l- ?        float* b1 = new float[N];
        float* b2 = new float[N];

8 `5 T5 u: _0 l$ K9 I/ D        for (int j = 0; j < 6000; j++)
! r; V2 v" h. {. W! Z0 k% g3 A3 u        {
                std::generate(vec1.begin(), vec1.end(), []() {
8 [) t  v9 x# [* X) q                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 23.23));;
6 S( s+ P1 b1 i7 n) L" H; J                        });

- @. u* K% f& Z/ G" Y& g                std::generate(vec2.begin(), vec2.end(), []() {
4 Y- T" w" `) l; E                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 24.31));;
                        });

( T- u- Z" X$ g- `* g                for (size_t jj = 0; jj < vec1.size(); jj++)
                {
8 S" `( ~. n' z+ d4 u- Q8 t                        b1[jj] = vec1[jj];
                }
/ Y: ^- n: R, V9 Q2 j
% X" M; U0 |- x9 U) o! S7 w! \# b                for (size_t jj = 0; jj < vec2.size(); jj++)
                {
7 C4 b0 ]% L# ]) j                        b2[jj] = vec2[jj];
+ Q0 _* i4 s' s& E                }

- a1 l5 X) I1 V2 M* E                //Method - 1  N=100000 247s  
+ h/ @* {# Y) V2 _  G                //fresult = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
                                
                //Method - 2  N=100000  237s
                /*
9 H# F9 D, d+ `  D; J! {                for (int jj = 0; jj < N ; jj++)
- L' H1 P) C: e0 e# c7 X                {
3 d+ V" w% i3 r; v7 x                        fresult += vec1[jj] * vec2[jj];
                }
                */
+ _3 b/ M! X9 S; E+ h                                
                //Method - 3  N=100000 204s
" o% a. T  R2 Z8 e! Z                /*
  N: ?. O% \+ r                for (int jj = 0; jj < N; jj++)
5 z! D' E) O& H                {
  i  w  ]0 L/ {                        fresult += b1[jj] * b2[jj];
                }
" A+ Z/ q2 L' e                */
: L9 r% s! m) ~& @
& V$ d( {; B& l  c2 \" s: r                //Method - 4   202s
5 U; D) C4 l* ]) ?" b' C" Q                /*
                for (int jj = 0; jj < N; jj++)
7 v/ |' x' q+ _3 R! |& z1 z                {
                        
; z% S7 e( ]- W4 a- ^4 N* r                }
+ J4 Z, Z: A: y: h8 V; X8 N                */
' @9 j# b" z+ I& H2 w$ Y                //comment out all methods, N=100000  202s               
        }

9 ~% C* b* g; {/ F* F9 X& f* b3 d        delete []b1;
, Q7 \9 f; W& [, e" T! t        delete []b2;

, {4 F/ B0 D0 ]3 c3 U* T! T* Y

机器猫

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

你第二个试验里面的j在循环里面又重新定义了啊，你确定真的跑了6000次？
5 F/ ]& Z/ q! E* E: [

雷达

机器猫 发表于 2022-9-27 00:15
瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？
6 I! d. f& }6 G2 E5 `' Z" L
9 L. ^' O+ t) E8 }# V: b# Q) }( @你第二个试验里面的j在循环里面又重新定义 ...

' l5 `: e. d5 |& G7 U! w  E内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL
( z! Y4 P, S1 U( y" z& F
  N: q5 v; F' U$ ^不和它较劲了，瞎耽误工夫，我已经转到 ubuntu, 也准备顺便试试 avx2 向量化。

机器猫

雷达 发表于 2022-9-27 01:16
1 J4 P) {) x2 i3 E; I内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL
; m; ~: K5 ]! ^8 d2 s  z
  w5 x* J1 U, r( w+ U; |0 ]  N不和它 ...

. X  B3 Q; K8 y
不过可以试试我说的register变量。前一个试验j是混在一堆其它变量里一起定义的，很有可能是在stack上，这样内存读写会更多，要是再碰上每次都需要加载cache就更慢了。
& D. i# d; `1 k$ Z+ z8 B5 G后面一个是在循环那里定义的，说不定编译器就把它优化成register变量了

opensrc

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

雷声

雷达 发表于 2022-9-24 23:54
$ Y& O! b5 f5 |3 mvoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
7 `0 q# X  e; R9 v' ?4 I{
6 }: M( T' n: c9 D% M9 v        comp temp, xtimesy;

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