C++ 提速的新发现

雷达

C++ 比 Octave 慢好多，怎么破？
) J. H. k# B8 R: }9 b' d9 Z
& }' g% S* D$ H9 T- ?4 ~/ K7 c自相关两层循环，内层循环涉及浮点数计算，试验了一下把内层循环内部全都 comment out 只留个壳子,  但空的内层循环本身就把速度拉下来了，看来问题并不在浮点计算。

  o/ ^9 W, {$ h, q* k5 Z6 u. v  X2 v速度优化问题真的很有意思啊。
# P# W( t1 s  p. i! D
欢迎大家继续讨论

数值分析

拉下来？拉多少？
/ D1 ]: R" o: Y, K8 C# U把代码贴上来看看？
6 G4 p1 p5 ?! U& y
难道分支预测不准破坏流水线执行？不该啊。

沉宝

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

风雨无阻

Maybe Debug mode?

雷达

4 ~* ]% ^9 G- U- E' S; G9 f% H

数值分析 发表于 2022-9-24 23:04
- s! }) W. F* k/ ~4 c( u拉下来？拉多少？
把代码贴上来看看？

* C0 M9 M" Z8 N6 W
2 I1 W0 s4 L! U8 Y! N% ivoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
$ q/ F2 f$ b0 q{
7 y2 {# m- L  }$ S- M        comp temp, xtimesy;
. O# p" Q8 d" D# P6 g        xtimesy.re = 0;
6 c& O+ Y2 _" I& @7 B& x  o' A9 A        xtimesy.im = 0;
        int j0 = lenB - 1;
        int    i, j, i1, reali;
        if (lenA % 2 == 1)
                reali = lenA + 1;
        else
: N& I  D" w& n+ N$ A                reali = lenA;
% i# n! s% W& U$ l" r6 W% f        reali /= 2;
" n' @' ]; C; U7 x$ d3 r0 E
# K' L9 b% E. t& y) j5 s        int nconv = reali + lenB;
        //#pragma omp parallel for
        for (i = reali; i < nconv; i++)
" C. s8 O! j8 @7 M4 m" p        {
, G( W/ o6 Y1 M' o4 r                temp.re = 0;
9 p. P% @# b" \- \                temp.im = 0;
6 `- h" B9 r; y& \( L% B                i1 = i;
                for (j = j0; j >= 0; j--)
3 G9 U7 c/ D9 X                {
                        /* floating date operation */
                }
        }
}

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

! w2 M; A. k1 p& n5 n8 n, Z+ O红色部分是内循环，现在其内部操作都comment out 了, j0大概是 6000。
现在call xcorr 100次，耗时78s.

如果把红色部分内循环本身完全comment out， call xcorr 1000次，耗时 <1s.
/ A/ X$ z  o1 U6 c& f' b8 ~" G

雷达

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

& y: \+ O7 j, u& _6 l  n9 X+ V3 T3 X不应该，看我上面的回复。
" g9 B8 D; ~( I
我更怀疑是 VS 社区版的问题

数值分析

  ^: ^( p+ ~: U, H

雷达 发表于 2022-9-24 23:54
9 E( Y1 `; l3 ivoid xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
6 x: s) \, x( O! {( E, U9 g5 y6 |# c{
        comp temp, xtimesy;

. N# |- s7 M, Y2 |/ c
这个不是这么比的吧。。。

' @* b3 l% ~* z3 s您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

* G% S7 _1 Y/ `9 M而加上内循环，光jmp和dec指令就至少多执行了6000个，慢个几十倍不是正常的么？

雷达

数值分析 发表于 2022-9-25 00:20
, E0 t8 E: O, A+ T4 o) ^这个不是这么比的吧。。。

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

有道理。
所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，记得 numeric 库里有算向量内积的，我回头试试。

我先尝试尽量用标准库，一个小程序，不想搞得太复杂。多谢了

沉宝

雷达 发表于 2022-9-25 00:46
; F  u) U1 E5 ~0 }! k1 \& f9 c有道理。
, L( g4 s2 c4 `# x: r所以存在内循环速度就上不去，把内循环取消，改成两个向量直接点乘再求和应该就会好得多，这大 ...

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

沉宝

数值分析 发表于 2022-9-25 00:20
这个不是这么比的吧。。。
, g6 G0 o7 f$ l$ }: f
, w  W2 z% M* m9 d( _8 l您这个函数，不带内循环的话，汇编完总共操作也没几个（不到100个）。

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

  [' F" V* i( X! q7 ^. q
现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果循环这样跑，花不了多少时间。

数值分析

+ J% s. x/ d4 \5 M5 U

沉宝 发表于 2022-9-25 01:48
+ U: T0 C9 ?: U现在的CPU，可以把判断、jmp和dec指令全部融合进一个µOp（微操作，CPU内部流水线上的执行单位）。如果 ...

是的，兄台说的对。
) k* o6 P/ T, @) _/ O
其实我想说的是 真正数值计算部分和代码中其他不直接计算的overhead的比值这个事儿。
0 F! V+ e/ @5 R( d2 S$ J
7 b( z, U: P+ Q# R; K, E+ @雷达兄构造测试用例的时候，屏蔽掉了所有计算的部分，使得剩下的都是overhead，这样run time比较的结果就显得好像不合理了。如果把计算加回去，计算部分的run time会dominate，结果就不那么离谱了。因为不好说，所以用指令数对比的方式试图直观地说明这一点。

比如说，如果有计算，那么跑六千个循环相对于计算应该用不了多少时间。但是如果一边是什么都不做，另一边是六千个循环，那六千个循环比什么都不做慢几十倍了，就不是那么不合理了。
4 M4 @/ [! i# D: L$ D( V- s0 r
当然也有可能像兄台说的，是优化参数的问题，但我觉得更多地是测试用例设计的不合理。

雷达

6 L$ ~9 `' H1 m7 ?) v

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

又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差一倍，我上面这个差的太多了。
! P! W/ T3 x4 a( h, U* h
我已经完全懵了。

沉宝

雷达 发表于 2022-9-25 04:47
5 R2 Z$ ]/ @# p- p7 {! c: J! o. H又写了个小实验，没有调用子函数，双层循环，外层6千次，内循环30万次空转，有或没有空转内循环，时间差 ...

- R/ ^1 D9 x1 v% h, a! X/ C6 P% a时间差一倍的结果可以接受。

你还是用profile工具看看吧。现在大家都主观瞎猜。

数值分析

: W( X8 {0 T( ^& e. V" v

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

4 b2 p* i: s+ O) ?

能不能把这个也贴上来，看看和上一个有什么不同？

雷达

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

$ {/ g) Y9 s: ^6 d理了理思路，重新做了一个测试。
做了两个 vector 和 两个 float *, 都长 100000
0 N, K, u' V6 v( D: ?' W外循环 6000，里面先做随机数生成，模拟真实环境，避免数据的 cache.

: V% ^6 [9 |6 l' C) Z$ A' [) u! h8 p9 T内循环试了4种方法，
, Q+ O) G& U- `- h2 ]1. 直接调用 vector inner_product 247s
2. vector 循环点乘累加 237s
  l* O3 `- y1 h* l- M6 o3. float * 循环点乘累加 204s
4. 空循环 100000 次 202s
( G. j* y  Z9 l, p0 R9 I# ?4 _
不做内循环 200s

! [0 N: u6 ^& n, x" ?5 I$ U你昨天说的对，内循环本身占比是很小的，大头在其他处理。
4 n; _8 B4 r7 z2 O: P8 q另外可以看到， float * 循环点乘累加 并不差，比用vector 还更快。
; M, J( ^& e, k
# }9 b( i( ?9 y$ U至于我那个原始程序，还有一些疑问，见5楼，其他都不变仅仅是有无空的内循环就有很大不同，这是不对的，也许有一些其他缺陷我没有看到。（也许可以改成 while 试试）

（为什么下面我贴的  b1 加 方括号里的 i , 显示出来却是 b1 ？方括号 i 消失了。 LOL . 改成  jj 好了，原来 方括号里的 i 是斜体标志  LOL）

        std::vector < float > vec1(N);
        std::vector < float > vec2(N);
3 x+ [, ^6 A  R, B1 z        float* b1 = new float[N];
  l; e7 l5 r, E  P6 N        float* b2 = new float[N];
6 g  i& v* P7 |: X- f1 q/ L
        for (int j = 0; j < 6000; j++)
' j1 L1 `. `3 Y( O1 r        {
7 T1 R* Z! t2 `6 e% @& h+ Y" [% C                std::generate(vec1.begin(), vec1.end(), []() {
                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 23.23));;
+ C8 X# Q1 Z: V$ ~8 m                        });
4 q+ `% U" _1 T! F* ?: h4 q
. \9 ^: y/ o1 O& f                std::generate(vec2.begin(), vec2.end(), []() {
                        return static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / 24.31));;
3 K/ q) g3 V' x( v                        });
6 N" t  z/ ~/ Q( D# \; o7 Q4 e* a$ R
- t7 n- y0 {1 E6 l" C" t  N                for (size_t jj = 0; jj < vec1.size(); jj++)
( Q: H$ j- P! k                {
0 J6 Q) s8 d% V, ~                        b1[jj] = vec1[jj];
8 Z6 D2 V9 [* i+ W                }

                for (size_t jj = 0; jj < vec2.size(); jj++)
, Z: L$ p9 ]/ p0 U- I2 u1 p- `                {
4 d; n+ a0 [# k! p( ^) l                        b2[jj] = vec2[jj];
0 d9 u! \) |, z7 v  R                }
! S5 R* d2 L+ h) z8 U
0 q8 n. \6 H& x1 n! s$ v                //Method - 1  N=100000 247s  
& e$ |# |; N* m# x                //fresult = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
                                
                //Method - 2  N=100000  237s
6 G, N- I' }+ D" h; y9 S/ `                /*
                for (int jj = 0; jj < N ; jj++)
                {
: X9 P* X- b" G1 k, s                        fresult += vec1[jj] * vec2[jj];
5 Y% {1 p8 d8 j' Z7 F                }
* a: H/ J  ~- x$ a& i2 f) @                */
                                
                //Method - 3  N=100000 204s
- W) s2 A, D( o5 m% C# E5 a1 V                /*
                for (int jj = 0; jj < N; jj++)
' L: v5 k* u1 A7 @( p3 n% u1 Q                {
1 V" p& x8 c  J* t7 P) ^# T                        fresult += b1[jj] * b2[jj];
9 e) y& d: R, s- l! F9 u5 b; U4 d& P                }
3 \4 B2 E2 T: G- ?) X                */
8 v  b% d( \" r' [/ T( G
                //Method - 4   202s
                /*
                for (int jj = 0; jj < N; jj++)
                {
& H9 P; @# J8 U; L                        
                }
* }0 y$ r1 e, a3 G2 A                */
                //comment out all methods, N=100000  202s               
        }

        delete []b1;
        delete []b2;

机器猫

瞎猜一下啊。把第一个的那个j定义成register变量会不会有不同？
4 d2 E6 P  J( c  |/ c
你第二个试验里面的j在循环里面又重新定义了啊，你确定真的跑了6000次？
  r9 h( K5 @) m+ F- v' q7 o/ N* U

雷达

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

4 m/ l) H1 k2 c& H+ x1 }) [1 W/ X你第二个试验里面的j在循环里面又重新定义 ...

内循环里面的 j 实际是 i, 为了规避爱坛显示的冲突帖子里临时改成了j, 现在是 jj 了。好累 、LOL

/ T* e) l& N9 M不和它较劲了，瞎耽误工夫，我已经转到 ubuntu, 也准备顺便试试 avx2 向量化。

机器猫

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

9 h% @8 G( C6 j! ^/ i  ~( `7 A不和它 ...

: ^% X( ?3 q- G; P) ]" I9 o) m
不过可以试试我说的register变量。前一个试验j是混在一堆其它变量里一起定义的，很有可能是在stack上，这样内存读写会更多，要是再碰上每次都需要加载cache就更慢了。
* O1 u6 K; {9 G  j! t后面一个是在循环那里定义的，说不定编译器就把它优化成register变量了

opensrc

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

雷声

雷达 发表于 2022-9-24 23:54
void xcorr(comp* outcomp, comp* A, int lenA, comp* B, int lenB)
{
        comp temp, xtimesy;

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