- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
原文:blog.fanscore.cn/a/62/ 。
前一段时间公司上线了一套Go实现的推荐系统,上线后发现MMR层虽然只有纯计算但耗时十分离谱,通过pprof定位问题所在之后进行了优化,虽然降低了非常多但是我们认为其中还有优化空间.
可以看到日常平均耗时126ms,P95 360ms.
MMR层主要耗时集中在了余弦相似度的计算部分,这部分我们使用的gonum库进行计算,其底层在x86平台上利用了SSE指令集进行了加速.
SSE指令集已经非常古老了,xmm寄存器只能存储两个双精度浮点数,每次只能并行进行两个双精度浮点数的计算,而AVX2指令集可以并行计算四个,理论上可以获得两倍的性能提升,因此我们决定自己使用AVX2指令集手写汇编的方式替代掉gonum库.
余弦相似度的计算公式为 。
对应的代码为 。
import "gonum.org/v1/gonum/floats"
func CosineSimilarity(a, b []float64) float64 {
dotProduct := floats.Dot(a, b) // 计算a和b的点积
normA := floats.Norm(a, 2) // 计算向量a的L2范数
normB := floats.Norm(b, 2) // 计算向量b的L2范数
return dotProduct / (normA * normB)
}
gonum点积计算Dot的部分汇编代码如下:
TEXT ·DotUnitary(SB), NOSPLIT, $0
...
loop_uni:
// sum += x[i] * y[i] unrolled 4x.
MOVUPD 0(R8)(SI*8), X0
MOVUPD 0(R9)(SI*8), X1
MOVUPD 16(R8)(SI*8), X2
MOVUPD 16(R9)(SI*8), X3
MULPD X1, X0
MULPD X3, X2
ADDPD X0, X7
ADDPD X2, X8
ADDQ $4, SI // i += 4
SUBQ $4, DI // n -= 4
JGE loop_uni // if n >= 0 goto loop_uni
...
end_uni:
ADDPD X8, X7
MOVSD X7, X0
UNPCKHPD X7, X7
ADDSD X0, X7
MOVSD X7, sum+48(FP) // Return final sum.
RET
可以看到其中使用xmm寄存器并行计算两个双精度浮点数,并且还采用了循环展开的优化手段,一个循环中同时进行4个元素的计算.
我们利用AVX2指令集并行计算四个双精度浮点数进行加速 。
loop_uni:
// sum += x[i] * y[i] unrolled 8x.
VMOVUPD 0(R8)(SI*8), Y0 // Y0 = x[i:i+4]
VMOVUPD 0(R9)(SI*8), Y1 // Y1 = y[i:i+4]
VMOVUPD 32(R8)(SI*8), Y2 // Y2 = x[i+4:i+8]
VMOVUPD 32(R9)(SI*8), Y3 // Y3 = x[i+4:i+8]
VMOVUPD 64(R8)(SI*8), Y4 // Y4 = x[i+8:i+12]
VMOVUPD 64(R9)(SI*8), Y5 // Y5 = y[i+8:i+12]
VMOVUPD 96(R8)(SI*8), Y6 // Y6 = x[i+12:i+16]
VMOVUPD 96(R9)(SI*8), Y7 // Y7 = x[i+12:i+16]
VFMADD231PD Y0, Y1, Y8 // Y8 = Y0 * Y1 + Y8
VFMADD231PD Y2, Y3, Y9
VFMADD231PD Y4, Y5, Y10
VFMADD231PD Y6, Y7, Y11
ADDQ $16, SI // i += 16
CMPQ DI, SI
JG loop_uni // if len(x) > i goto loop_uni
可以看到我们每个循环中同时用到8个ymm寄存器即一次循环计算16个数,而且还用到了VFMADD231PD指令同时进行乘法累积的计算.
最终Benchmark结果:
BenchmarkDot 一个循环中计算8个数
BenchmarkDot-2 14994770 78.85 ns/op
BenchmarkDot16 一个循环中计算16个数
BenchmarkDot16-2 22867993 53.46 ns/op
BenchmarkGonumDot Gonum点积计算
BenchmarkGonumDot-2 8264486 144.4 ns/op
可以看到点积部分我们得到了大约2.7倍的性能提升 。
gonum库中进行L2范数计算的算法并不是常规的a1^2 + a2^2 ... + aN^2这种计算,而是采用了Netlib算法,减少了溢出和下溢,其Go源码如下:
func L2NormUnitary(x []float64) (norm float64) {
var scale float64
sumSquares := 1.0
for _, v := range x {
if v == 0 {
continue
}
absxi := math.Abs(v)
if math.IsNaN(absxi) {
return math.NaN()
}
if scale < absxi {
s := scale / absxi
sumSquares = 1 + sumSquares*s*s
scale = absxi
} else {
s := absxi / scale
sumSquares += s * s
}
}
if math.IsInf(scale, 1) {
return math.Inf(1)
}
return scale * math.Sqrt(sumSquares)
}
其汇编代码比较晦涩难懂,但管中窥豹再结合Go源码可以看出来没有用到并行能力,每次循环只计算一个数 。
TEXT ·L2NormUnitary(SB), NOSPLIT, $0
...
loop:
MOVSD (X_)(IDX*8), ABSX // absxi = x[i]
...
我们优化之后的核心代码如下:
loop:
VMOVUPD 0(R8)(SI*8), Y0 // Y0 = x[i:i+4]
VMOVUPD 32(R8)(SI*8), Y1 // Y1 = y[i+4:i+8]
VMOVUPD 64(R8)(SI*8), Y2 // Y2 = x[i+8:i+12]
VMOVUPD 96(R8)(SI*8), Y3 // Y3 = x[i+12:i+16]
VMOVUPD 128(R8)(SI*8), Y4 // Y4 = x[i+16:i+20]
VMOVUPD 160(R8)(SI*8), Y5 // Y5 = y[i+20:i+24]
VMOVUPD 192(R8)(SI*8), Y6 // Y6 = x[i+24:i+28]
VMOVUPD 224(R8)(SI*8), Y7 // Y7 = x[i+28:i+32]
VFMADD231PD Y0, Y0, Y8 // Y8 = Y0 * Y0 + Y8
VFMADD231PD Y1, Y1, Y9
VFMADD231PD Y2, Y2, Y10
VFMADD231PD Y3, Y3, Y11
VFMADD231PD Y4, Y4, Y12
VFMADD231PD Y5, Y5, Y13
VFMADD231PD Y6, Y6, Y14
VFMADD231PD Y7, Y7, Y15
ADDQ $32, SI // i += 32
CMPQ DI, SI
JG loop // if len(x) > i goto loop
我们采用原始的算法计算以利用到并行计算的能力,并且循环展开,一次循环中同时计算32个数,最终Benchmark结果:
BenchmarkAVX2L2Norm
BenchmarkAVX2L2Norm-2 29381442 40.99 ns/op
BenchmarkGonumL2Norm
BenchmarkGonumL2Norm-2 1822386 659.4 ns/op
可以看到得到了大约16倍的性能提升 。
通过这次优化我们在余弦相似度计算部分最终得到了(144.4 + 659.4 * 2) / (53.46 + 40.99 * 2) = 10.8倍的性能提升,效果还是非常显著的。相较于《记一次SIMD指令优化计算的失败经历》这次失败的初次尝试,本次还是非常成功的,切实感受到了SIMD的威力.
另外在本次优化过程中也涨了不少姿势 。
AVX-512指令因为并行度更高理论上性能也更高,但AVX-512指令会造成CPU降频,因此业界使用非常慎重,这一点可以参考字节的json解析库sonic的这个issue: https://github.com/bytedance/sonic/issues/319 。
在一次循环中做更多的工作,优点有很多:
但一次循环使用过多的寄存器从实际Benchmark看性能确实更好,但是否存在隐患我没有看到相关的资料,希望这方面的专家可以指教一下.
最后此篇关于使用AVX2指令集加速推荐系统MMR层余弦相似度计算的文章就讲到这里了,如果你想了解更多关于使用AVX2指令集加速推荐系统MMR层余弦相似度计算的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我想在我的 iPhone 应用程序中加入线性回归。经过一些搜索,我发现 Accelerate Framework 中的 LAPACK 和 BLAS 是正确的库。但是我很难将加速框架添加到我的 XCod
有什么方法可以加速 JS 脚本(我指的是一些复杂的 DOM 操作,比如游戏或动画)? 最佳答案 真的没有办法真正加快速度。您可以压缩它,但不会快很多。 关于Javascript 加速?,我们在Stac
有时,我必须为一个项目重新导入数据,从而将大约 360 万行读入 MySQL 表(目前是 InnoDB,但我实际上并不局限于这个引擎)。 “加载数据文件...”已被证明是最快的解决方案,但它有一个权衡
在尝试计算加速时,我被卡住了。所以给出的问题是: 问题 1 如果程序的 50% 增强了 2 倍,其余 50% 增强了 4 倍,那么由于增强而导致的整体加速是多少? Hints:考虑增强前(未增强)机器
目前我正在处理实时绘图,但可视化非常慢。我想知道你可以做些什么来加速 Matplotlib 中的事情: 后端如何影响性能?是否有后端 实时绘图比其他人更好吗? 我可以降低分辨率以提高 FPS 吗? 如
我有一个小型测试框架。它执行一个循环,执行以下操作: 生成一个小的 Haskell 源文件。 使用 runhaskell 执行此操作.该程序生成各种磁盘文件。 处理刚刚生成的磁盘文件。 这种情况发生了
这是我的网站:Instant-YouTube 如您所见,加载需要很长时间。在 IE8 及以下甚至有时会导致浏览器崩溃。我不确定是什么原因造成的。可能是 Clicksor 广告,但我认为是 swfobj
是否可以加速 SKSpriteNode? 我知道可以使用 node.physicsBody.velocity 轻松设置速度但是设置它的加速度有多难? 最佳答案 从牛顿第二定律倒推运动:F = m.a您
有没有人有加速 FCKEditor 的技术?是否有一些关键的 JavaScript 文件可以缩小或删除? 最佳答案 在最新版本 (3.0.1) 中,FCKEditor 已重命名为 CKEditor .
我有以下 MySQL 查询,需要一天多的时间才能执行: SELECT SN,NUMBER FROM a WHERE SN IN (SELECT LOWER_SN FROM b WHER
我现在正在开发一款使用加速来玩的游戏。我找到了如何让我的元素移动,但不改变它的“原点”,或者更准确地说,改变加速度计算的原点: 事实上,我的图像是移动的,它的中心是这样定义的: imageView.c
我有一个 mysql 表,其中存储有 4 列的成员消息: message_id(主键,自增) sender_id( key ) receiver_id( key ) 消息内容 我做了很多 SELECT
我在 cuda_computation.cu 中有以下代码 #include #include #include #include void checkCUDAError(const char
我正在使用 BeautifulSoup 在 for 循环中解析数千个网站。这是我的代码片段: def parse_decision(link): t1 = time.time() de
我正在使用 OpenCV 2.4 (C++) 在灰度图像上进行寻线。这涉及一些基本的图像处理步骤,如模糊、阈值、Canny 边缘检测器、梯度滤波器或霍夫变换。我必须在数千张图像上应用寻线算法。 考虑到
当我试图连续生成四次相同的报告时,我刚刚分析了我的报告应用程序。第一个用了 1859 毫秒,而后面的只用了 400 到 600 毫秒。对此的解释是什么?我能以某种方式使用它来使我的应用程序更快吗?报告
当我打开 Storyboard文件时,由于其中包含的 VC 数量,打开它需要 1-2 分钟。加快速度的最佳做法是什么?我们应该将一些 VC 移动到不同的 Storyboard文件中吗?我们是否应该使用
我有一个包含多个页面的 UIPageViewController。每个页面都是相同的 View Controller ,但会跟踪页码并显示 PDF 的正确页面。问题是每个 PDF 页面都需要在 cur
这实际上是两个问题,但它们非常相似,为了简单起见,我想将它们放在一起: 首先:给定一个已建立的 Java 项目,除了简单的代码内优化之外,还有哪些不错的方法可以加快它的速度? 其次:在用Java从头写
我有一个包含 1000 个条目的文档,其格式类似于:
我是一名优秀的程序员,十分优秀!