C++ 提速的新发现

雷达

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

7 r7 L) W9 v* D' w0 i  o自相关两层循环，内层循环涉及浮点数计算，试验了一下把内层循环内部全都 comment out 只留个壳子,  但空的内层循环本身就把速度拉下来了，看来问题并不在浮点计算。
* R4 B  p1 A& B2 \! j
* K+ t1 Z* n. u速度优化问题真的很有意思啊。
" A3 }9 S8 n$ c% ?# x) s9 L; f2 l6 M. L
欢迎大家继续讨论

数值分析

拉下来？拉多少？
2 K0 d/ v: F' O把代码贴上来看看？

; Q8 l& {2 T! Y2 V' ?% x5 C4 n难道分支预测不准破坏流水线执行？不该啊。

沉宝

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

风雨无阻

Maybe Debug mode?

雷达

数值分析 发表于 2022-9-24 23:04
1 W) D0 D( l: s! v# ~7 T拉下来？拉多少？
把代码贴上来看看？

- V3 B; r  W/ l. A
* A  j6 X% I- R  N% Dvoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
' i7 `" w" F+ X! g* a, X* c{
1 _& @7 g' N6 ^4 L# r  ~        comp temp, xtimesy;
2 v: ]# E  ]1 l5 }! z        xtimesy.re = 0;
* N# N1 Z/ b$ ?  Z; H1 Q        xtimesy.im = 0;
        int j0 = lenB - 1;
        int    i, j, i1, reali;
        if (lenA % 2 == 1)
                reali = lenA + 1;
1 S1 B% t, Z! G: e5 e* _2 ~: j; }( w        else
                reali = lenA;
        reali /= 2;
% f% S3 |" b8 ~/ a6 X4 k: g' B- C
        int nconv = reali + lenB;
1 Z2 h: X* k/ I9 B& ~) E        //#pragma omp parallel for
3 \7 Y$ y9 f$ V. v9 Y        for (i = reali; i < nconv; i++)
* M# e( X, F6 V# i: {8 J- J        {
/ i- O) y- G$ ^2 S$ N0 M# \8 _                temp.re = 0;
                temp.im = 0;
- Y- l4 u1 F% U+ u                i1 = i;
                for (j = j0; j >= 0; j--)
, f4 {" D( }. `% e4 z+ x                {
( U, i( M1 u* n6 t7 s5 f, o6 _9 [                        /* floating date operation */
                }
/ f: S' H! b4 z; ]" O8 Q7 |/ O' h: m3 x        }
; u$ N1 b7 B. v7 w! I}
7 E: L. j* v% E3 y
. |9 i/ V; p. r! }xcorr函数代码如上，comp是复数struct, 做过长度为11、19两个矢量的测试，和octave结果完全一样
+ j4 Q: M9 ~5 j6 g: E; b
红色部分是内循环，现在其内部操作都comment out 了, j0大概是 6000。
4 m5 f. o3 J0 Y8 f$ P# T1 P现在call xcorr 100次，耗时78s.

如果把红色部分内循环本身完全comment out， call xcorr 1000次，耗时 <1s.

. P- l- ?; J$ I

雷达

风雨无阻 发表于 2022-9-24 23:33
0 g* w" e+ _4 G1 j' bMaybe Debug mode?

5 \. U4 ~- ~9 X* z# x  R& k
! \  R( L0 f8 o. {2 l  Y不应该，看我上面的回复。
1 y# z( {5 o- z* {$ }
我更怀疑是 VS 社区版的问题

数值分析

$ p0 n0 M5 T" c% K1 ~; k" c

雷达 发表于 2022-9-24 23:54
void xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
{
; q& v! o: U. Y/ d( Z        comp temp, xtimesy;

9 w7 ^3 ^% Q6 U+ s
这个不是这么比的吧。。。

) V! [3 ?5 K' a  u) B; r; j您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。
: z7 u% _4 C/ ]$ I5 L4 g5 O
而加上内循环，光jmp和dec指令就至少多执行了6000个，慢个几十倍不是正常的么？

雷达

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

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

有道理。
4 f4 _* G: [& ]; S! m4 I所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，记得 numeric 库里有算向量内积的，我回头试试。

: s/ f4 w: G2 D: q2 ~4 ~我先尝试尽量用标准库，一个小程序，不想搞得太复杂。多谢了

沉宝

雷达 发表于 2022-9-25 00:46
有道理。
+ A7 Q* O* k* V  ?/ z所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，这大 ...

- X" j+ C* A; W" v1 E. i. e你两个试验之间就差了一个空循环， 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; Z  L+ g0 s) V$ Y这个不是这么比的吧。。。

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

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

( r' ?! C, e& \/ z2 |* U
现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果循环这样跑，花不了多少时间。

数值分析

沉宝 发表于 2022-9-25 01:48
- V" f# v$ Q7 Y0 ^: C" d  F现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果 ...

是的，兄台说的对。

其实我想说的是 真正数值计算部分和代码中其他不直接计算的overhead的比值这个事儿。

3 f$ q/ W- V! z+ A雷达兄构造测试用例的时候，屏蔽掉了所有计算的部分，使得剩下的都是overhead，这样run time比较的结果就显得好像不合理了。如果把计算加回去，计算部分的run time会dominate，结果就不那么离谱了。因为不好说，所以用指令数对比的方式试图直观地说明这一点。
9 ]& f1 h# ?9 q6 `& L& [" ~4 x. v$ Q
比如说，如果有计算，那么跑六千个循环相对于计算应该用不了多少时间。但是如果一边是什么都不做，另一边是六千个循环，那六千个循环比什么都不做慢几十倍了，就不是那么不合理了。

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

雷达

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

& j0 b0 M5 W2 v  y; V* z/ W) ^
又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差一倍，我上面这个差的太多了。
3 b( C% B' F& c  t: B+ ]
$ L0 M6 y% |7 \2 [, S0 w1 |我已经完全懵了。

沉宝

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

时间差一倍的结果可以接受。
2 i4 |9 P2 I& y* Q' I- V6 G
' g$ L0 T3 Z5 A7 J% g$ ]6 t5 y- v你还是用profile工具看看吧。现在大家都主观瞎猜。

数值分析

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

0 I' @3 P% \' C8 h! o: N
; s5 D6 t9 K9 d3 D, X: E
; G) O) q  x1 X4 N/ `能不能把这个也贴上来，看看和上一个有什么不同？

雷达

' s, a" O( h" m% m( _

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

; L, s; M, ?& {& N1 e7 W* z" F1 U理了理思路，重新做了一个测试。
6 ?5 G% n7 x$ l) h1 }做了两个 vector 和 两个 float *, 都长 100000
外循环 6000，里面先做随机数生成，模拟真实环境，避免数据的 cache.

5 W  @+ Y+ F) R# V' z8 w/ ^+ W0 r) e内循环试了4种方法，
4 b5 t1 l7 z9 n6 J2 s( Y0 Y- P1 g  q1. 直接调用 vector inner_product 247s
! r/ _' h. f' Q2. vector 循环点乘累加 237s
6 h1 W. w0 `! r& v9 |9 a! X3. float * 循环点乘累加 204s
9 G) m! h8 o+ U0 X5 z8 \+ M1 L; D4. 空循环 100000 次 202s

; h  t$ }: m$ O& R不做内循环 200s

& D/ p0 p' w. s4 T( I你昨天说的对，内循环本身占比是很小的，大头在其他处理。
另外可以看到， float * 循环点乘累加 并不差，比用vector 还更快。

至于我那个原始程序，还有一些疑问，见5楼，其他都不变仅仅是有无空的内循环就有很大不同，这是不对的，也许有一些其他缺陷我没有看到。（也许可以改成 while 试试）
+ Y- U" j; y4 O8 V0 z
（为什么下面我贴的  b1 加 方括号里的 i , 显示出来却是 b1 ？方括号 i 消失了。 LOL . 改成  jj 好了，原来 方括号里的 i 是斜体标志  LOL）
* l6 g( h8 t" o  R

        std::vector < float > vec1(N);
8 c6 g% F* D: F0 B9 o% d9 c, Q0 A# X        std::vector < float > vec2(N);
8 O; [) ?& ]7 b6 e- u        float* b1 = new float[N];
5 {( [0 T4 @: B) m# f7 Z2 \2 T        float* b2 = new float[N];
- ^- \( k6 H% Q8 O) P
        for (int j = 0; j < 6000; j++)
/ W, |+ U8 ^) p        {
" L' G' ?% u1 G5 T: G) ]$ r                std::generate(vec1.begin(), vec1.end(), []() {
                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 23.23));;
7 X2 j8 @* m7 R! F( }# H                        });
# [9 y& j9 Z% R- V- z4 Z
                std::generate(vec2.begin(), vec2.end(), []() {
( G* d2 n6 A/ m5 b                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 24.31));;
                        });
$ O9 y) z1 M4 H+ k. `
$ v0 o, ^( b% x6 s* s( W                for (size_t jj = 0; jj < vec1.size(); jj++)
                {
                        b1[jj] = vec1[jj];
4 n1 Q3 x# r( W                }

3 m4 i4 r4 ^. M2 J- w8 u                for (size_t jj = 0; jj < vec2.size(); jj++)
' z' `8 L% A* p- b) ]' X. \                {
                        b2[jj] = vec2[jj];
                }

; I1 I, c1 Z* m) S/ N7 J4 ]                //Method - 1  N=100000 247s  
                //fresult = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
& b; k9 v1 {6 m                                
                //Method - 2  N=100000  237s
                /*
                for (int jj = 0; jj < N ; jj++)
+ u* A6 K5 ~" S5 C; I% u* J$ m                {
                        fresult += vec1[jj] * vec2[jj];
                }
                */
& A% w; D2 V7 B" t2 A                                
: v+ b9 n: w. {  A6 \/ {9 g                //Method - 3  N=100000 204s
                /*
$ k1 @8 E; Z$ L% U8 A0 C                for (int jj = 0; jj < N; jj++)
: H' ~4 |9 c. t                {
4 c0 i* A! A6 {: a                        fresult += b1[jj] * b2[jj];
                }
                */

                //Method - 4   202s
                /*
                for (int jj = 0; jj < N; jj++)
                {
                        
                }
                */
  ?: Y( S) f' F                //comment out all methods, N=100000  202s               
8 ?! p" z$ s" K; _' Z2 r- A9 O$ a+ H  J: x        }
! b; z+ G) I* Q' |7 l; B
% d! ]2 |7 D" Z. U4 A1 H        delete []b1;
0 B/ c+ l( E: o1 n3 @5 i        delete []b2;

机器猫

瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？
2 \6 k: K4 x# o( z* w9 Q/ T
你第二个试验里面的j在循环里面又重新定义了啊，你确定真的跑了6000次？
3 M3 ]& B& @" v2 e; X, ~. e4 ?' }

雷达

机器猫 发表于 2022-9-27 00:15
$ X4 x) R3 g0 \6 ~/ {瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？
, f/ R% o" a' T4 P; n# O4 x+ A
你第二个试验里面的j在循环里面又重新定义 ...

内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL
$ D% p* _3 }' ?3 v
不和它较劲了，瞎耽误工夫，我已经转到 ubuntu, 也准备顺便试试 avx2 向量化。

机器猫

雷达 发表于 2022-9-27 01:16
9 I4 e/ S$ R2 }3 a7 L内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL
* I: ?) g  K4 w" g$ `( l
" x1 h1 [( n8 h/ c不和它 ...

. c1 Q: m$ c& c$ q" I不过可以试试我说的register变量。前一个试验j是混在一堆其它变量里一起定义的，很有可能是在stack上，这样内存读写会更多，要是再碰上每次都需要加载cache就更慢了。
. t: o% i+ o2 k后面一个是在循环那里定义的，说不定编译器就把它优化成register变量了

opensrc

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

雷声

雷达 发表于 2022-9-24 23:54
" {, ~9 U$ ?6 }" H+ u8 R; vvoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
{
        comp temp, xtimesy;

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