爱吱声

标题: C++ 比 Octave 慢好多,怎么破? [打印本页]

作者: 雷达    时间: 2022-9-23 06:27
标题: C++ 比 Octave 慢好多,怎么破?
本帖最后由 雷达 于 2022-9-23 06:29 编辑 % n5 r1 I, a* {4 s
3 \6 B. s5 F% u  s/ B( E( J8 p9 O
做一个数字信号处理的小算法,需要算互相关。. }9 C' U1 {+ r& g$ a1 A
先用 Octave (兼容matlab 那个东东) 做了一下,感觉慢,走通后就用C++ 重写,结果比 Octave 还慢,目测能慢10倍,很不科学啊。
1 d9 ?5 s9 W' l9 I* d" K% n
& s# v; |% i2 [; j' bOctave的互相关有现成函数 xcorr,  C++ 需要自己写。互相关是一个一维矢量和一个二维数组里的矢量依次做。矢量里是复数数据,没有用 STL,自己做了个  Re/Im 的struct,其实就是两个四字节 float 。3 |  S7 \# H$ ?+ p1 f
互相关的最基本运算是两个复数的乘法,就是四次 float 乘法再相加,所以本质上影响速度的应该就是 float 乘法和加法。" h+ t0 a% t$ u

4 m. Y# U" \& ], X6 P) Z( qC++ 用的是VS 社区版,估计编译器不给力,但也不至于差这么多啊。  k; Q: N* u& x. D: \" k

+ W: s3 ?& z3 P$ U3 P3 L高手们给分析分析,  多谢了。. R  i2 |, b9 w6 a5 U: k

作者: 雷声    时间: 2022-9-23 07:02
互相关这种是最适合矢量化的,Octave应该是用SIMD 或者CUDA写了核心的计算部分。所以比没有优化的快很多。我差不多20年前做过类似的二维相关处理,优化过的比老师自己写的快了三四十倍,实验室的小崽子们怨声载道。因为本来等处理完一次数据需要差不多六七个小时,正好打游戏。优化完了之后不到二十分钟就好了。啥也干不了。
, Y: O7 l# c& ]  y你想省事的话用Intel的IPP库,里面有现成的高度优化的互相关函数。或者用CUDA自己写一个。% [& E/ e& X) W4 G. B& I4 i4 A& M
你做信号处理很熟的话,这个还可以用FFT来做。应该会更快一些。九十年代很多人这么处理,主要是那时候CPU实在太慢。现在基本用不着了。而且FFT前后处理比较麻烦,加窗什么的。
作者: 雷达    时间: 2022-9-23 08:13
本帖最后由 雷达 于 2022-9-23 08:15 编辑 2 n! y) u$ ^, Z% F# F2 q$ U- b
雷声 发表于 2022-9-23 07:02
. ?6 h. O9 X+ G  ^0 N- _互相关这种是最适合矢量化的,Octave应该是用SIMD 或者CUDA写了核心的计算部分。所以比没有优化的快很多。 ...
9 q) U6 @4 K# _) l+ _9 R

7 _, n/ @5 V  y嗯, 我就是觉得 FFT 反而麻烦,互相关代码本身倒真没有几行。那看来就用 octave 就好了,没必要再用C++重写了。
4 }4 n/ r: E. K另外,我现在就是用指针数组,如果用 STL 的Vector 会不会更快一些?
作者: 可梦之    时间: 2022-9-23 09:18
Octave/Matlab内部对数值计算做了很多并行和优化。内核甚至是用Fortran写的。你用C++重写,没有做并行优化,真未必比他们的性能好。
作者: 阿忙    时间: 2022-9-23 09:55
Matlab不是浪得虚名的,要打败它还是要下点功夫才行
作者: 雷达    时间: 2022-9-23 11:00
本帖最后由 雷达 于 2022-9-23 11:10 编辑
( c: J) w9 P3 S3 X2 p' X& j1 {  C, {9 |) F5 ~$ N
研究了一下,似乎可以用预处理指令对浮点运算做一些优化。这个问题比我最初想象的要复杂得多
作者: 马鹿    时间: 2022-9-23 11:18
汇编快!
作者: 数值分析    时间: 2022-9-23 11:34
本帖最后由 数值分析 于 2022-9-23 11:48 编辑
$ f% j( A( P: C, O
; Z7 d- y. J+ q  y. e) @* J7 FC++ code 用的是普通乘法?换成sse/avx向量乘法试试?
. r) n) q) L* [$ n并且是单线程的?加个openmp并行试试
4 R# I+ d* a% q, P或者调用mkl 库的互相关函数试试. N& o+ q. p, V! v

作者: mark    时间: 2022-9-23 11:43
马鹿 发表于 2022-9-23 11:18) `1 T( {3 W: N# Y
汇编快!

6 T$ t$ R, A' y# _! Y9 U这种问题的优化, 在语言层面没太大意义, c++和汇编没什么本质区别.# A: T$ ?* M6 ?8 n9 T: t
4 A6 t  X1 F+ A0 y
最好还是用高性能的计算库, 比如intel的ipp,或者看看gpu方面有没有类似的库.
作者: 走两步    时间: 2022-9-23 12:59
涉及矩阵的用blas
作者: 雨楼    时间: 2022-9-23 14:05
实际使用中要考虑综合成本/时间。比如用octave /Python 解决起来简单。自己另起炉灶麻烦些。
作者: 雷声    时间: 2022-9-23 15:48
雷达 发表于 2022-9-23 08:134 S" Y/ o5 D- I8 h) G
嗯, 我就是觉得 FFT 反而麻烦,互相关代码本身倒真没有几行。那看来就用 octave 就好了,没必要再用C++ ...
  ?* Y  |+ B* R/ `* I
STL对性能优化没什么帮助,只是写起来比较安全而已。6 i% _1 n: d* ?" j) U$ `
下面数值分析回答的是对的,要么用avx自己写,要么就凑合用octave得了。
  d7 {7 e4 p% ]. v. f买个Ipp库虽然不贵,但是还是要几百刀的吧?
. s! O% l$ j" {" d; Q. d% ^
作者: 四处张望    时间: 2022-9-23 16:05
矩阵最简单用eigen,然后enable  avx2以上
作者: 马鹿    时间: 2022-9-23 20:24
mark 发表于 2022-9-22 22:43
  L* J  J1 P6 Q* v这种问题的优化, 在语言层面没太大意义, c++和汇编没什么本质区别.! j. l4 K) o9 ^: v

+ y6 S- n' r, c/ b0 W* |最好还是用高性能的计算库, 比如inte ...
( {2 g1 \! z: N- B8 X8 Q/ y; c9 ~
我不是it的,说汇编是起哄呢
作者: 沉宝    时间: 2022-9-23 20:53
雷声 发表于 2022-9-23 15:48
$ d8 M4 [/ U3 F( c" m( MSTL对性能优化没什么帮助,只是写起来比较安全而已。
# z/ o- T- G0 g& E* ^下面数值分析回答的是对的,要么用avx自己写,要么 ...
  f- B3 B- D, g8 I& c
你觉得在用AVX自己写与用GPU加速的Octave之间,谁有可能性能上超出?(基于中等价位的硬件水平)
作者: 数值分析    时间: 2022-9-23 21:37
本帖最后由 数值分析 于 2022-9-23 23:50 编辑 5 H6 i  S& v  Z" n
沉宝 发表于 2022-9-23 20:53
0 w( t% r" ?9 G$ |你觉得在用AVX自己写与用GPU加速的Octave之间,谁有可能性能上超出?(基于中等价位的硬件水平) ...

9 m) l( O1 J: p% a( T$ H
3 ?2 g4 |' E, M/ ?9 I+ h% D) s1 ]% b2 f" g必然是GPU啊,10来个核心对上千个计算单元。。。9 b  W2 n, w, R' A* F: A

& t: U  s- E; Q3 j4 u有道是 双拳难敌四手 一虎不如群狼
作者: ltpub    时间: 2022-9-26 18:34
先用性能探查器看下热点在哪里,用前面坛友们的方法针对性优化下,满足了应用需求就收手(心中牢记那句箴言:又不是不能用!& k, P  \. H* n( i8 J( L
1 J) I) v) c% b! w& j6 W+ }3 o
不知道vs的社区版带不带性能探查器,不行的话用pro/ent试用几天应该是不违规的,实在不行把C++编译到Linux下,那perf工具可就多了去了
作者: 机器猫    时间: 2022-9-26 23:30
mark 发表于 2022-9-23 11:431 _3 h: R3 ^" T+ G) R  G9 h* q
这种问题的优化, 在语言层面没太大意义, c++和汇编没什么本质区别.
  |, i/ [$ i4 |' A2 {7 x- d9 Y
- c% I. E/ j% \' r' z; [7 G6 r最好还是用高性能的计算库, 比如inte ...
: D' K* v3 y+ B3 j) M6 u9 ?
区别还是很大的。编译器的优化还到不了那种程度。3 r! i& K2 z7 y3 t
你说的那些“高性能的计算库”很多估计都是专门的人用汇编手工优化出来的。那个得对要优化的系统非常熟悉的人来干,打个比方那条指令用在哪个地方会导致cache需要加载,这些都必须考虑到
* g/ t% l# m$ a: e8 F+ _; p* \7 e( W6 V
当然对于调用这些库的代码来说,一般C和汇编区别不大
作者: 沉宝    时间: 2022-10-2 01:38
现在进展怎么样了?7 O; A7 ^2 @# U# O
/ B" ?5 E, T: q$ B# n
想了解一下你问题的规模:: b8 j" a' ~% q+ Z; N* K8 d
1) 你说互相关是一个一维矢量和一个二维数组里的矢量依次做,那么这个二维数组有什么特殊意义吗?需要对所有维度按列操作并返回一个矩阵,还是就是简单的一对一算过去?换一句话,本质上要的是一个1-维互相关算法,还是N-维互相关算法。& @4 D6 o$ [7 {% [
2) 矢量和一个二维数组的长度大概是多少?* t1 u" K2 c' E- e
3) Octave 大约跑了多长时间,你心里期望的速度大约是多少?
作者: 雷达    时间: 2022-10-2 03:04
本帖最后由 雷达 于 2022-10-2 03:06 编辑
9 Q4 U1 a# n( a" H2 H2 e
沉宝 发表于 2022-10-2 01:38
4 V# @! p. }% S8 G# y7 i2 E现在进展怎么样了?
+ a: I/ G2 m# \& z# |: q* n; j" M  h( K! ?. b. H# N; |
想了解一下你问题的规模:
8 @: \# `3 s$ v. H
% N) Q5 b9 C* i+ ]: Y; ]
多谢关注。
6 W' ?$ x8 m$ P$ O7 D7 F规模还比较大,一个至少3万*3万的二维浮点复数矩阵,用一个4000点复数矢量对矩阵的每一个3万点矢量做互相关,重复3万次这种互相关。 # k; L! y2 h( e
我已经试验成功了 AVX 算浮点内积和 VS 优化, 再加上多核并行,我希望能至少和 octave 打平。但现在手头有其他事,还没有时间改正式代码。
作者: 沉宝    时间: 2022-10-3 01:16
雷达 发表于 2022-10-2 03:04$ `$ F# L! \' i) i& W6 I% }! A3 Y
多谢关注。
9 A9 s" ~5 V( q8 I1 o* }0 ^规模还比较大,一个至少3万*3万的二维浮点复数矩阵,用一个4000点复数矢量对矩阵的每一个3万 ...
0 j8 P7 F& {& w
你在 Octave 跑出来的速度是多少?没有具体数据的话能不能说一下数量级上大致在哪里?
+ l# J) I& X$ O  U& t# g. z1 |1 i" `( K. y0 O; I1 u
另外,你在 Octave 上的测试是按实际数据量跑的吗?我大概估计了一下,如果我没有算错,你那个二维浮点复数矩阵的数据量大约240TB(1 billion elements, each element has 30000x8 bytes)。这么大的数据量不可能全都放进内存中准备好,(事实上,它们已经不是一块硬盘可以装得下的了,放在磁盘阵列上吗?)有可能计算机的I/O吞吐性能也成为影响真正计算速度的一个重要因素。
作者: 雷达    时间: 2022-10-3 09:13
本帖最后由 雷达 于 2022-10-3 09:16 编辑
8 ?8 J( {' ^! A: @0 M5 B- c0 a0 n+ B. z
沉宝 发表于 2022-10-3 01:16$ G, E2 h* I4 [3 U0 [6 X( }
你在 Octave 跑出来的速度是多少?没有具体数据的话能不能说一下数量级上大致在哪里?: C& m) k& m" Y% D
1 ~; r( D2 _' R2 V, h
另外,你在 Octav ...

+ u, Q) {+ D/ D$ N* w# n& `5 M- x& g' r( @; B5 x' K" B3 y* u) Z
应该没有那么大。
! \3 Y) v+ T+ x9 Q7 o我算的:
3 X. X" _$ y" _3 v! ~" W5 L+ \3万*3万的二维浮点复数矩阵, 30k*30k = 900M个点, 复数 *2, 浮点数 *4,总共 7.2G。2 E" [5 M) o0 N( |
做算法的时候,一行一行从文件读取,有个16G内存应该足够了




欢迎光临 爱吱声 (http://129.226.69.186/bbs/) Powered by Discuz! X3.2