爱吱声

标题: C++ 比 Octave 慢好多，怎么破？ [打印本页]
作者: 雷达    时间: 2022-9-23 06:27
标题: C++ 比 Octave 慢好多，怎么破？
本帖最后由 雷达 于 2022-9-23 06:29 编辑 9 f0 X8 Y: J7 A

* e. a: e  z+ T; i: _7 i5 n' n8 ~$ I做一个数字信号处理的小算法，需要算互相关。
( `# }* g1 X8 I" N  s先用 Octave （兼容matlab 那个东东） 做了一下，感觉慢，走通后就用C++ 重写，结果比 Octave 还慢，目测能慢10倍，很不科学啊。6 g# X( n4 W& ?2 G6 l) ^
: W8 E) G$ m' R, E5 u- [5 ~+ ?: C
Octave的互相关有现成函数 xcorr,  C++ 需要自己写。互相关是一个一维矢量和一个二维数组里的矢量依次做。矢量里是复数数据，没有用 STL，自己做了个  Re/Im 的struct，其实就是两个四字节 float 。
  A# R* U1 n6 J+ R- U互相关的最基本运算是两个复数的乘法，就是四次 float 乘法再相加，所以本质上影响速度的应该就是 float 乘法和加法。
: E* x, Y0 \8 Z0 F
; h0 F9 y3 B0 }- t. U% I4 K* lC++ 用的是VS 社区版，估计编译器不给力，但也不至于差这么多啊。8 z: [5 H; ?0 H! [9 ^: G

2 v0 H# p6 s7 Z5 [' L7 I3 Q! E( P3 O高手们给分析分析,  多谢了。
* H& k  k* v- _# N9 a) k
作者: 雷声    时间: 2022-9-23 07:02
互相关这种是最适合矢量化的，Octave应该是用SIMD 或者CUDA写了核心的计算部分。所以比没有优化的快很多。我差不多20年前做过类似的二维相关处理，优化过的比老师自己写的快了三四十倍，实验室的小崽子们怨声载道。因为本来等处理完一次数据需要差不多六七个小时，正好打游戏。优化完了之后不到二十分钟就好了。啥也干不了。
: r1 D2 z. y, a6 Y+ F% s) n你想省事的话用Intel的IPP库，里面有现成的高度优化的互相关函数。或者用CUDA自己写一个。- S. t; |+ n* h7 z; h
你做信号处理很熟的话，这个还可以用FFT来做。应该会更快一些。九十年代很多人这么处理，主要是那时候CPU实在太慢。现在基本用不着了。而且FFT前后处理比较麻烦，加窗什么的。
作者: 雷达    时间: 2022-9-23 08:13
本帖最后由 雷达 于 2022-9-23 08:15 编辑 0 p, o5 A( H8 c7 z  u: v
雷声 发表于 2022-9-23 07:02
2 r! z3 C; V/ c7 c' F" i互相关这种是最适合矢量化的，Octave应该是用SIMD 或者CUDA写了核心的计算部分。所以比没有优化的快很多。 ...
# z1 J" K$ T" K5 W
/ X5 A5 M# n- s+ M: {2 u$ v
嗯， 我就是觉得 FFT 反而麻烦，互相关代码本身倒真没有几行。那看来就用 octave 就好了，没必要再用C++重写了。% d# i/ M/ X6 O  J
另外，我现在就是用指针数组，如果用 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 编辑 7 t9 }" Q8 H1 i0 U3 F

- B# N3 }1 \' M# o9 _- S# A研究了一下，似乎可以用预处理指令对浮点运算做一些优化。这个问题比我最初想象的要复杂得多
作者: 马鹿    时间: 2022-9-23 11:18
汇编快！
作者: 数值分析    时间: 2022-9-23 11:34
本帖最后由 数值分析 于 2022-9-23 11:48 编辑
- f6 a* z7 P7 _. m0 v
# J1 I1 H% H& {# O! TC++ code 用的是普通乘法？换成sse/avx向量乘法试试？" `& [% S' \) }  z1 z
并且是单线程的？加个openmp并行试试
$ y. [5 Z4 W! |+ |; c5 C! C' X% A或者调用mkl 库的互相关函数试试- h# H8 f" Z' B
作者: mark    时间: 2022-9-23 11:43
马鹿 发表于 2022-9-23 11:18
& K( W( W- Y/ T  O1 ^汇编快！
/ Z; g4 E: w8 k8 d
这种问题的优化, 在语言层面没太大意义, c++和汇编没什么本质区别.
% v4 j! R3 {9 O. q$ O$ M8 I! O" W; ?
最好还是用高性能的计算库, 比如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:13& C4 a6 n6 R; I$ m+ y
嗯， 我就是觉得 FFT 反而麻烦，互相关代码本身倒真没有几行。那看来就用 octave 就好了，没必要再用C++ ...
; B$ v4 g5 `" A4 s
STL对性能优化没什么帮助，只是写起来比较安全而已。% }8 ~3 s2 w  b5 r$ a
下面数值分析回答的是对的，要么用avx自己写，要么就凑合用octave得了。
# r% R' H% S& E! u; b/ H买个Ipp库虽然不贵，但是还是要几百刀的吧？
  ^& ]* k1 A8 A2 I
作者: 四处张望    时间: 2022-9-23 16:05
矩阵最简单用eigen，然后enable  avx2以上
作者: 马鹿    时间: 2022-9-23 20:24
mark 发表于 2022-9-22 22:431 h% `) }" y8 E& h7 m' _
这种问题的优化, 在语言层面没太大意义, c++和汇编没什么本质区别.
6 G$ ^* [% M' w# Q/ K: k
4 `  ~  f8 h, a; t最好还是用高性能的计算库, 比如inte ...
+ A* R& e( t: E
我不是it的，说汇编是起哄呢
作者: 沉宝    时间: 2022-9-23 20:53
雷声 发表于 2022-9-23 15:48* x1 d0 ?6 C' w% {! u4 X( [8 d
STL对性能优化没什么帮助，只是写起来比较安全而已。/ j6 V' ~# S1 \5 z/ l8 I
下面数值分析回答的是对的，要么用avx自己写，要么 ...

; q9 k  c$ Y, {你觉得在用AVX自己写与用GPU加速的Octave之间，谁有可能性能上超出？（基于中等价位的硬件水平）
作者: 数值分析    时间: 2022-9-23 21:37
本帖最后由 数值分析 于 2022-9-23 23:50 编辑 + U4 S& l9 U( _
沉宝 发表于 2022-9-23 20:533 h; [0 m8 r# A' f) a
你觉得在用AVX自己写与用GPU加速的Octave之间，谁有可能性能上超出？（基于中等价位的硬件水平） ...
5 j1 c" x  Q& D, c- g

& M$ l+ _4 v9 q8 q8 Y# u必然是GPU啊，10来个核心对上千个计算单元。。。
- M. |4 O2 k: p5 L: ?' `! R4 O
& C$ n1 m9 f  k9 \* T9 K5 M有道是 双拳难敌四手 一虎不如群狼
作者: ltpub    时间: 2022-9-26 18:34
先用性能探查器看下热点在哪里，用前面坛友们的方法针对性优化下，满足了应用需求就收手（心中牢记那句箴言：又不是不能用！）
, @: A4 E. H3 n+ v
; y. v+ j4 A! o, a  Z: W0 a1 S# N1 m不知道vs的社区版带不带性能探查器，不行的话用pro/ent试用几天应该是不违规的，实在不行把C++编译到Linux下，那perf工具可就多了去了
作者: 机器猫    时间: 2022-9-26 23:30
mark 发表于 2022-9-23 11:43
* G- d: C8 k3 F3 |+ E4 }, [) D这种问题的优化, 在语言层面没太大意义, c++和汇编没什么本质区别., x: K! @$ K6 q4 Y" r( }% F
% l) Q, B, A; R0 N7 U4 K1 k
最好还是用高性能的计算库, 比如inte ...
  O( |+ m" b# t, v2 f
区别还是很大的。编译器的优化还到不了那种程度。  j( `) ?- s5 h" m; ^  f+ D
你说的那些“高性能的计算库”很多估计都是专门的人用汇编手工优化出来的。那个得对要优化的系统非常熟悉的人来干，打个比方那条指令用在哪个地方会导致cache需要加载，这些都必须考虑到6 y/ Q+ Z) W6 f) u

# O$ n: H. `. j/ {: E当然对于调用这些库的代码来说，一般C和汇编区别不大
作者: 沉宝    时间: 2022-10-2 01:38
现在进展怎么样了？
  T0 `- X& X! v
& V2 H/ e. B0 y' [0 A想了解一下你问题的规模：3 w7 f  l  l; Q
1) 你说互相关是一个一维矢量和一个二维数组里的矢量依次做，那么这个二维数组有什么特殊意义吗？需要对所有维度按列操作并返回一个矩阵，还是就是简单的一对一算过去？换一句话，本质上要的是一个1-维互相关算法，还是N-维互相关算法。6 d$ \8 s* B$ l1 p9 _& d
2) 矢量和一个二维数组的长度大概是多少？
1 N* P% p- M( `: K3) Octave 大约跑了多长时间，你心里期望的速度大约是多少？
作者: 雷达    时间: 2022-10-2 03:04
本帖最后由 雷达 于 2022-10-2 03:06 编辑
/ e! B& \3 N: c
沉宝 发表于 2022-10-2 01:38
- t+ [- ]1 M7 F; }2 C8 ?现在进展怎么样了？$ n" g. o  B7 d6 ?0 i" Z, W
& X5 n% T4 f, y$ j
想了解一下你问题的规模：
1 A# v+ |7 t9 T% m4 s

% B5 _8 I' ?' d9 m6 u( n多谢关注。
  z7 I& ]  e  O1 t0 Z规模还比较大，一个至少3万*3万的二维浮点复数矩阵，用一个4000点复数矢量对矩阵的每一个3万点矢量做互相关，重复3万次这种互相关。
& H8 y3 T$ K/ s7 G+ h我已经试验成功了 AVX 算浮点内积和 VS 优化， 再加上多核并行，我希望能至少和 octave 打平。但现在手头有其他事，还没有时间改正式代码。
作者: 沉宝    时间: 2022-10-3 01:16
雷达 发表于 2022-10-2 03:047 p% l/ `1 D+ V/ t& M1 h
多谢关注。
/ g* V  ~- C$ q. W5 |9 \5 u# v( R" G规模还比较大，一个至少3万*3万的二维浮点复数矩阵，用一个4000点复数矢量对矩阵的每一个3万 ...

) [* P6 f- w% f你在 Octave 跑出来的速度是多少？没有具体数据的话能不能说一下数量级上大致在哪里？3 O/ L6 g# k7 p5 t1 N7 w
9 R" I: y; G" E
另外，你在 Octave 上的测试是按实际数据量跑的吗？我大概估计了一下，如果我没有算错，你那个二维浮点复数矩阵的数据量大约240TB（1 billion elements, each element has 30000x8 bytes）。这么大的数据量不可能全都放进内存中准备好，（事实上，它们已经不是一块硬盘可以装得下的了，放在磁盘阵列上吗？）有可能计算机的I/O吞吐性能也成为影响真正计算速度的一个重要因素。
作者: 雷达    时间: 2022-10-3 09:13
本帖最后由 雷达 于 2022-10-3 09:16 编辑
' j- ~7 J6 u7 u
沉宝 发表于 2022-10-3 01:16
7 d/ Y2 O7 a. c' ?: l4 S你在 Octave 跑出来的速度是多少？没有具体数据的话能不能说一下数量级上大致在哪里？5 v) N+ x6 s  {9 O

4 T2 k) j3 S$ X+ `& _8 c另外，你在 Octav ...

; B* I, @/ J) I
0 Q9 `: {* f; U! O9 p应该没有那么大。
% ?2 f% t& \& J# h) z1 v, y我算的：& s" v, c! [' f% E& k/ b! A
3万*3万的二维浮点复数矩阵, 30k*30k = 900M个点, 复数 *2， 浮点数 *4，总共 7.2G。7 N, N; ]  O/ z
做算法的时候，一行一行从文件读取，有个16G内存应该足够了



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