C++ 提速的新发现

雷达

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

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

( M7 ]9 w1 p5 V% Y1 z4 T3 a速度优化问题真的很有意思啊。
9 }6 P2 l3 H  d1 X$ J3 \
欢迎大家继续讨论

数值分析

拉下来？拉多少？
把代码贴上来看看？
- H1 Z! h* n  c
. a7 n' ]- m& X) \难道分支预测不准破坏流水线执行？不该啊。

沉宝

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

风雨无阻

Maybe Debug mode?

雷达

数值分析 发表于 2022-9-24 23:04
拉下来？拉多少？
* z) D- v) T4 `把代码贴上来看看？

) H9 b5 m/ V/ c# ?3 L
void xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
{
6 {8 E2 ?8 s9 a; P; X        comp temp, xtimesy;
4 B3 P* z0 \8 @1 \0 _1 m3 }        xtimesy.re = 0;
        xtimesy.im = 0;
9 F; S% C  n$ O! {( o# I        int j0 = lenB - 1;
        int    i, j, i1, reali;
) d) B) X3 N" Y7 m) M2 n+ v$ a) @4 p- y! v        if (lenA % 2 == 1)
0 p% A4 ?7 q0 O3 [                reali = lenA + 1;
        else
' }/ c% I: T$ i% q3 D: K. m4 t/ ]+ }! i                reali = lenA;
$ y3 U$ z8 C0 i( E0 {: f0 H9 W7 b        reali /= 2;

8 @* D/ z% T6 i) ~. M6 d2 Y        int nconv = reali + lenB;
        //#pragma omp parallel for
/ B2 @* W; R, M6 ^8 m2 X8 s* e/ o        for (i = reali; i < nconv; i++)
' s3 J" [& r; w* p) s6 n        {
9 f* J% t) i: z, T  e9 `8 v+ j$ }                temp.re = 0;
. Q! J  ?, m% d" A; K- b                temp.im = 0;
* u+ e5 Z! Z! M% d4 E5 j  z                i1 = i;
                for (j = j0; j >= 0; j--)
1 W( i7 o! E: C- r( n                {
                        /* floating date operation */
  a" ]% S: v6 K; K6 V- R                }
1 C! w& {  w+ U& m; J6 h        }
  ]( f& w2 U. a8 D}

6 m3 ?  S3 r! t  m% g" rxcorr函数代码如上，comp是复数struct, 做过长度为11、19两个矢量的测试，和octave结果完全一样
) u0 r( I3 i3 D8 O
+ j% O5 _* c5 |( M: Y红色部分是内循环，现在其内部操作都comment out 了, j0大概是 6000。
2 ?4 C, X5 k6 i5 w现在call xcorr 100次，耗时78s.
, k* m! F$ t+ I
6 H  ~! J* x4 i/ \' f) N如果把红色部分内循环本身完全comment out， call xcorr 1000次，耗时 <1s.
/ t1 b3 \/ o, K+ c: v0 K
" Z% ^8 B/ J. K( |1 q9 \0 g" B! K

雷达

风雨无阻 发表于 2022-9-24 23:33
$ q) X; t' V- C, C( b  E% `' _9 sMaybe Debug mode?

6 E4 t6 f% v& i
不应该，看我上面的回复。

& Y5 n  ?6 _, F6 C) Y我更怀疑是 VS 社区版的问题

数值分析

" J6 D1 P1 y4 S

雷达 发表于 2022-9-24 23:54
2 a8 M, d3 v' b4 R9 J) |& n0 yvoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
- z; g. q* Z. d& C1 k5 `, g{
        comp temp, xtimesy;

* M. x, D4 P1 v6 s( K) ]0 ?5 V7 y这个不是这么比的吧。。。
. h  o" \! Q! ?3 @; p: C
- Q! B' p) P, f5 ?您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。
% u7 U$ D, Z$ V: x2 x$ J
. h' d0 Q/ Y6 x1 _* W  Y, O- }而加上内循环，光jmp和dec指令就至少多执行了6000个，慢个几十倍不是正常的么？

雷达

6 @3 b. ], ]4 l3 ^, y

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

5 R) G3 y3 r- t; U) H您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

4 z' _, {/ |' o8 w" u6 S+ \
有道理。
1 r- y: Q& f" C# D! `9 L所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，记得 numeric 库里有算向量内积的，我回头试试。

4 o; X5 W! e. M% d我先尝试尽量用标准库，一个小程序，不想搞得太复杂。多谢了

沉宝

雷达 发表于 2022-9-25 00:46
/ ]3 v' f9 k' r3 i有道理。
所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，这大 ...

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

沉宝

数值分析 发表于 2022-9-25 00:20
5 G* T% n* q8 I8 u7 y这个不是这么比的吧。。。

6 K" g4 M0 p5 ~+ }8 G/ [' P6 j  {您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

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

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

数值分析

8 o; O8 D$ N% ]* v% E+ ?+ f# z

沉宝 发表于 2022-9-25 01:48
0 [2 W/ |0 P; F. z( r5 _( y8 v0 s现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果 ...

. P# H9 N" Q1 j0 V! f* ~& P
: Z- E9 |: `$ \# R是的，兄台说的对。
+ M/ W* H" T: p8 Q  S5 B9 |  c* e8 [
, K7 S- m" M3 d* i其实我想说的是 真正数值计算部分和代码中其他不直接计算的overhead的比值这个事儿。

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

比如说，如果有计算，那么跑六千个循环相对于计算应该用不了多少时间。但是如果一边是什么都不做，另一边是六千个循环，那六千个循环比什么都不做慢几十倍了，就不是那么不合理了。
% J' q+ E$ \0 P' m
# p3 A" t1 [* ^. S2 c2 _; \/ K/ \) L当然也有可能像兄台说的，是优化参数的问题，但我觉得更多地是测试用例设计的不合理。

雷达

* N; h& N( k9 {9 D0 Y- g. r

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

4 p2 X! @& q! q3 j又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差一倍，我上面这个差的太多了。

' Q  x+ g+ A) R& L! F# l" b. ?我已经完全懵了。

沉宝

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

时间差一倍的结果可以接受。
4 ~, `' x& n& ?5 ], R$ `6 n; K
% b; I& F+ B& }3 W- \你还是用profile工具看看吧。现在大家都主观瞎猜。

数值分析

雷达 发表于 2022-9-25 04:47
3 n7 H: Z4 }9 Y( r$ [% |# P又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差 ...

, T4 K+ e2 z2 L$ k; B


9 k+ d( L; _2 c- v能不能把这个也贴上来，看看和上一个有什么不同？

雷达

数值分析 发表于 2022-9-25 14:58
1 g# m, L# O% B2 W" v4 Y) r能不能把这个也贴上来，看看和上一个有什么不同？

理了理思路，重新做了一个测试。
做了两个 vector 和 两个 float *, 都长 100000
. w% G2 `, c/ z' ]3 |外循环 6000，里面先做随机数生成，模拟真实环境，避免数据的 cache.
/ b2 ^* a" ^2 B7 w) s! V! C+ D  p
内循环试了4种方法，
4 b  x; }6 B; J1 q; j8 V! E; `1. 直接调用 vector inner_product 247s
2. vector 循环点乘累加 237s
3. float * 循环点乘累加 204s
. g4 E. n, q4 w) O6 A% k7 m4. 空循环 100000 次 202s

不做内循环 200s
% k2 t) s( [2 E9 X* C5 p, W
你昨天说的对，内循环本身占比是很小的，大头在其他处理。
4 W. G  {) y/ i8 k另外可以看到， float * 循环点乘累加 并不差，比用vector 还更快。

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

' k* G% l5 V: a7 u3 q（为什么下面我贴的  b1 加 方括号里的 i , 显示出来却是 b1 ？方括号 i 消失了。 LOL . 改成  jj 好了，原来 方括号里的 i 是斜体标志  LOL）

        std::vector < float > vec1(N);
1 w/ k& T$ X) k  |, t        std::vector < float > vec2(N);
( R3 a: `; o( ]3 N! T& e        float* b1 = new float[N];
        float* b2 = new float[N];
! d! e( r$ m/ `0 e
+ n! f; {$ ^5 x- i0 }& W" ?2 G4 E) d        for (int j = 0; j < 6000; j++)
        {
                std::generate(vec1.begin(), vec1.end(), []() {
# X3 X" Y6 o! m                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 23.23));;
                        });

                std::generate(vec2.begin(), vec2.end(), []() {
" j) t1 h7 i. j! p" X                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 24.31));;
5 E4 [- _2 K0 a& T7 R' I6 J                        });

                for (size_t jj = 0; jj < vec1.size(); jj++)
                {
                        b1[jj] = vec1[jj];
                }

, b& J  [7 }0 N                for (size_t jj = 0; jj < vec2.size(); jj++)
                {
                        b2[jj] = vec2[jj];
8 s: }0 q: G( I& L! t. J, \                }

3 v1 X8 W5 a+ |2 U1 `+ }6 o* H5 _                //Method - 1  N=100000 247s  
- i8 ~5 y% G  h- B: a                //fresult = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
$ l' i5 [' v1 d5 C; @                                
9 [! v+ a3 F# f" z! ?                //Method - 2  N=100000  237s
4 w7 a9 z6 q/ _  d# Q( @                /*
/ \! a6 a: }7 f  h* s  v! h                for (int jj = 0; jj < N ; jj++)
/ B" G  ]5 w( ^' k; E' Q8 w& f                {
                        fresult += vec1[jj] * vec2[jj];
                }
  c8 E  `0 c# e9 @, _) Z                */
                                
                //Method - 3  N=100000 204s
: I4 H; H2 u6 l* I                /*
0 }/ b1 C- Q0 n- k- o                for (int jj = 0; jj < N; jj++)
4 f) a$ d2 L% ^& F4 ]. N' f                {
                        fresult += b1[jj] * b2[jj];
                }
+ H8 P' K3 v& v. v( ]                */
, L- O& O* j1 P& y8 M0 M! S1 a
! R5 F2 }+ b, t9 C) a* i' Y                //Method - 4   202s
% W( u- R7 n, Z5 e9 G0 F* U$ e                /*
* \" f! {2 c- N                for (int jj = 0; jj < N; jj++)
5 J) x6 c8 x# |5 `$ R+ H                {
                        
                }
% C, {" c0 M6 E+ s                */
( u, o) C1 M4 E! D                //comment out all methods, N=100000  202s               
3 M  f- u: P, Z3 L4 a, I" l! S/ U        }

: z$ ?+ n* u4 E# u0 S        delete []b1;
        delete []b2;

. V/ h$ o2 ^( H. {( h0 v5 o

机器猫

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

- v% ]  |% c" i1 v你第二个试验里面的j在循环里面又重新定义了啊，你确定真的跑了6000次？
4 {3 F5 l  l, N. H

雷达

机器猫 发表于 2022-9-27 00:15
瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？
0 i. v+ D$ S+ C/ n: L  j
/ R0 V1 z; ?7 D; ?8 ~+ M" S你第二个试验里面的j在循环里面又重新定义 ...

: `: {1 L4 H0 u, ]3 t: N" l  [- Z内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL
1 T9 q0 O' l7 u: {2 S
不和它较劲了，瞎耽误工夫，我已经转到 ubuntu, 也准备顺便试试 avx2 向量化。

机器猫

雷达 发表于 2022-9-27 01:16
内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL
3 E5 X3 U4 ?# J, p6 G; U4 |
不和它 ...

/ i- e. c, x/ G- C" K5 E1 Y
, n* Q8 h( O- B2 }) n不过可以试试我说的register变量。前一个试验j是混在一堆其它变量里一起定义的，很有可能是在stack上，这样内存读写会更多，要是再碰上每次都需要加载cache就更慢了。
  F: e, j& f2 d+ t后面一个是在循环那里定义的，说不定编译器就把它优化成register变量了

opensrc

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

雷声

雷达 发表于 2022-9-24 23:54
void xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
{
/ b; N8 G9 A+ Y$ R        comp temp, xtimesy;

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