爱吱声

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

作者: 雷达    时间: 2022-9-23 06:27
标题: C++ 比 Octave 慢好多,怎么破?
本帖最后由 雷达 于 2022-9-23 06:29 编辑
! @* _+ @+ ]+ k: P% `" I; q  v4 r" n. x/ ]. ^- ~3 m( [2 v
做一个数字信号处理的小算法,需要算互相关。1 Q; ~3 H6 C$ |, U- Y
先用 Octave (兼容matlab 那个东东) 做了一下,感觉慢,走通后就用C++ 重写,结果比 Octave 还慢,目测能慢10倍,很不科学啊。5 C( T- X; \7 U0 H

3 \# [1 H; }  z8 Z. n. OOctave的互相关有现成函数 xcorr,  C++ 需要自己写。互相关是一个一维矢量和一个二维数组里的矢量依次做。矢量里是复数数据,没有用 STL,自己做了个  Re/Im 的struct,其实就是两个四字节 float 。. c( v9 ~' I$ _  x/ \7 }" W
互相关的最基本运算是两个复数的乘法,就是四次 float 乘法再相加,所以本质上影响速度的应该就是 float 乘法和加法。
2 ?: I- m, Q9 A: o& e# ]; B: r- K; m2 p4 J! q2 k2 i1 K
C++ 用的是VS 社区版,估计编译器不给力,但也不至于差这么多啊。
  O5 p: k; F$ u( n: Y' U! ?) P9 q9 h+ Y8 R7 O! i/ J
高手们给分析分析,  多谢了。
- i, l, t6 u; W7 J7 C- ^9 B( t4 l
作者: 雷声    时间: 2022-9-23 07:02
互相关这种是最适合矢量化的,Octave应该是用SIMD 或者CUDA写了核心的计算部分。所以比没有优化的快很多。我差不多20年前做过类似的二维相关处理,优化过的比老师自己写的快了三四十倍,实验室的小崽子们怨声载道。因为本来等处理完一次数据需要差不多六七个小时,正好打游戏。优化完了之后不到二十分钟就好了。啥也干不了。; g" U+ F  z6 z# V/ m( z: s
你想省事的话用Intel的IPP库,里面有现成的高度优化的互相关函数。或者用CUDA自己写一个。
1 J, F- N; s$ h$ x4 n你做信号处理很熟的话,这个还可以用FFT来做。应该会更快一些。九十年代很多人这么处理,主要是那时候CPU实在太慢。现在基本用不着了。而且FFT前后处理比较麻烦,加窗什么的。
作者: 雷达    时间: 2022-9-23 08:13
本帖最后由 雷达 于 2022-9-23 08:15 编辑 + d* D0 P! _5 |$ M/ O; D
雷声 发表于 2022-9-23 07:02  g3 w3 J& s7 Z6 q# p
互相关这种是最适合矢量化的,Octave应该是用SIMD 或者CUDA写了核心的计算部分。所以比没有优化的快很多。 ...

$ x6 f* S' H; s: i( N$ S( X- a# z, h! B4 ^  Y
嗯, 我就是觉得 FFT 反而麻烦,互相关代码本身倒真没有几行。那看来就用 octave 就好了,没必要再用C++重写了。$ B9 k, k, S3 z4 \2 |6 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 编辑
- u& q0 o6 d2 X6 ]
- i9 {4 }, z9 l/ P" V研究了一下,似乎可以用预处理指令对浮点运算做一些优化。这个问题比我最初想象的要复杂得多
作者: 马鹿    时间: 2022-9-23 11:18
汇编快!
作者: 数值分析    时间: 2022-9-23 11:34
本帖最后由 数值分析 于 2022-9-23 11:48 编辑
6 C1 b/ B+ T5 ?) c7 L) H9 ~  m! w$ V
$ ~* n! B' @, l, o$ B7 tC++ code 用的是普通乘法?换成sse/avx向量乘法试试?/ l, v4 s" l" \1 L; k
并且是单线程的?加个openmp并行试试
3 A2 q- F' n! f1 b& ^4 I  m7 F或者调用mkl 库的互相关函数试试& F5 A# o# R5 B% j/ E1 f0 T

作者: mark    时间: 2022-9-23 11:43
马鹿 发表于 2022-9-23 11:18) b2 q( Q# h7 E8 ]
汇编快!

3 L4 x5 T3 o% [& O7 M; ^这种问题的优化, 在语言层面没太大意义, c++和汇编没什么本质区别.
' R+ j: O: h8 V$ F! K4 L2 c; j" F) b: a+ ~0 b0 w4 a- ^, j
最好还是用高性能的计算库, 比如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
0 I3 J8 r6 H7 }7 N4 J* ~嗯, 我就是觉得 FFT 反而麻烦,互相关代码本身倒真没有几行。那看来就用 octave 就好了,没必要再用C++ ...
8 N/ W% x* G/ _+ L
STL对性能优化没什么帮助,只是写起来比较安全而已。
  i1 j8 h4 u5 ?. k% h下面数值分析回答的是对的,要么用avx自己写,要么就凑合用octave得了。
, q2 o( `* k' P0 w5 L# ]买个Ipp库虽然不贵,但是还是要几百刀的吧?
1 I( T% J; P$ Y
作者: 四处张望    时间: 2022-9-23 16:05
矩阵最简单用eigen,然后enable  avx2以上
作者: 马鹿    时间: 2022-9-23 20:24
mark 发表于 2022-9-22 22:43
8 t, L: o% T: \/ T) X6 B这种问题的优化, 在语言层面没太大意义, c++和汇编没什么本质区别.( X+ b: j  L) I, q9 b1 H1 q: p/ a
- }* r! r. c9 a  }5 H! D
最好还是用高性能的计算库, 比如inte ...

: z, m* h7 }" i6 r! \" E我不是it的,说汇编是起哄呢
作者: 沉宝    时间: 2022-9-23 20:53
雷声 发表于 2022-9-23 15:48. y, x5 }5 @  {- |
STL对性能优化没什么帮助,只是写起来比较安全而已。6 P# ?" [8 w# r. x, l
下面数值分析回答的是对的,要么用avx自己写,要么 ...
, G4 h4 v1 V1 |- T" P) X# @: q
你觉得在用AVX自己写与用GPU加速的Octave之间,谁有可能性能上超出?(基于中等价位的硬件水平)
作者: 数值分析    时间: 2022-9-23 21:37
本帖最后由 数值分析 于 2022-9-23 23:50 编辑 $ P  C" E: p4 k) }/ e2 b
沉宝 发表于 2022-9-23 20:533 ]9 ~9 n9 ~4 f
你觉得在用AVX自己写与用GPU加速的Octave之间,谁有可能性能上超出?(基于中等价位的硬件水平) ...
) \, g3 {3 u$ Z1 d
1 `' ^5 _1 p' _% a3 t% e/ n
必然是GPU啊,10来个核心对上千个计算单元。。。
7 h6 W5 O7 i$ i/ D0 o0 W; f; |) w: z" p, h9 g3 w
有道是 双拳难敌四手 一虎不如群狼
作者: ltpub    时间: 2022-9-26 18:34
先用性能探查器看下热点在哪里,用前面坛友们的方法针对性优化下,满足了应用需求就收手(心中牢记那句箴言:又不是不能用!  w9 L+ A4 X( F' m: W
  s; i- R! K6 M  m$ Y5 l
不知道vs的社区版带不带性能探查器,不行的话用pro/ent试用几天应该是不违规的,实在不行把C++编译到Linux下,那perf工具可就多了去了
作者: 机器猫    时间: 2022-9-26 23:30
mark 发表于 2022-9-23 11:43. u. o$ s( W) S! [8 `
这种问题的优化, 在语言层面没太大意义, c++和汇编没什么本质区别.  S' j7 \& i/ @/ u" [) S( ^
- e2 l  d# A* D. L
最好还是用高性能的计算库, 比如inte ...

$ S& T$ B7 `" r& j2 P6 e+ m区别还是很大的。编译器的优化还到不了那种程度。, ~/ g9 W# S/ I1 b
你说的那些“高性能的计算库”很多估计都是专门的人用汇编手工优化出来的。那个得对要优化的系统非常熟悉的人来干,打个比方那条指令用在哪个地方会导致cache需要加载,这些都必须考虑到
) J, ~. b3 m3 t
; a0 Z+ B2 R7 H' \' x3 o6 g  ?8 T当然对于调用这些库的代码来说,一般C和汇编区别不大
作者: 沉宝    时间: 2022-10-2 01:38
现在进展怎么样了?6 m* k& Z$ V, t+ J2 r' \4 t

6 \" L$ k# a% w' Q8 k8 t想了解一下你问题的规模:3 }( l  [5 J( ~, W5 [
1) 你说互相关是一个一维矢量和一个二维数组里的矢量依次做,那么这个二维数组有什么特殊意义吗?需要对所有维度按列操作并返回一个矩阵,还是就是简单的一对一算过去?换一句话,本质上要的是一个1-维互相关算法,还是N-维互相关算法。) c4 H7 J% c3 z4 l& g+ K, ^
2) 矢量和一个二维数组的长度大概是多少?
! G8 j& m. x3 r3) Octave 大约跑了多长时间,你心里期望的速度大约是多少?
作者: 雷达    时间: 2022-10-2 03:04
本帖最后由 雷达 于 2022-10-2 03:06 编辑
( i; E1 K' Q9 a9 r3 }
沉宝 发表于 2022-10-2 01:387 A* @9 k& I# B$ K9 R  @! l! G; ]
现在进展怎么样了?
. V7 F/ M7 J) o$ v7 D* i
' z" j# P% i) P& b! X想了解一下你问题的规模:

2 _7 l. Y' U. n) X) {! y  H2 C/ Y; i& f
多谢关注。
8 Z) X' _* v& z9 X/ S规模还比较大,一个至少3万*3万的二维浮点复数矩阵,用一个4000点复数矢量对矩阵的每一个3万点矢量做互相关,重复3万次这种互相关。 & A$ e7 K; m% e0 ?, I* Q" ]5 h: _
我已经试验成功了 AVX 算浮点内积和 VS 优化, 再加上多核并行,我希望能至少和 octave 打平。但现在手头有其他事,还没有时间改正式代码。
作者: 沉宝    时间: 2022-10-3 01:16
雷达 发表于 2022-10-2 03:04; m) Y  r. X' u5 q9 [
多谢关注。
) V7 P8 O- s) m/ Y* c: c规模还比较大,一个至少3万*3万的二维浮点复数矩阵,用一个4000点复数矢量对矩阵的每一个3万 ...
8 T/ O0 j- H+ I
你在 Octave 跑出来的速度是多少?没有具体数据的话能不能说一下数量级上大致在哪里?9 z" @. {$ J0 `/ ~* L6 L9 t* }" t5 u

! s, V# ^4 q' A$ ~7 U8 v2 q另外,你在 Octave 上的测试是按实际数据量跑的吗?我大概估计了一下,如果我没有算错,你那个二维浮点复数矩阵的数据量大约240TB(1 billion elements, each element has 30000x8 bytes)。这么大的数据量不可能全都放进内存中准备好,(事实上,它们已经不是一块硬盘可以装得下的了,放在磁盘阵列上吗?)有可能计算机的I/O吞吐性能也成为影响真正计算速度的一个重要因素。
作者: 雷达    时间: 2022-10-3 09:13
本帖最后由 雷达 于 2022-10-3 09:16 编辑
- x4 Q1 Y4 a7 U4 S- g4 U
沉宝 发表于 2022-10-3 01:16) D! `% z/ @; T/ q
你在 Octave 跑出来的速度是多少?没有具体数据的话能不能说一下数量级上大致在哪里?- H1 E7 Q$ K( m( o, l, R5 O- ?: o

& M  |- }) G2 S7 z0 t% B2 P另外,你在 Octav ...

3 ?9 A7 s( c# o7 J  v7 K6 F% [* ~* z% L: U& u0 g! ^
应该没有那么大。
) m, ~- T1 U! [& _% M我算的:+ T9 j8 Y5 a% L. n7 P
3万*3万的二维浮点复数矩阵, 30k*30k = 900M个点, 复数 *2, 浮点数 *4,总共 7.2G。" J% O3 S+ e$ h
做算法的时候,一行一行从文件读取,有个16G内存应该足够了




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