https://github.com/heptagonhust/recruitment-2021-autumn

最终的加速比：26.123。

CPU: AMD Ryzen 7 5800HS Creator Edition (8C16T) @3.200GHz

RAM: 16GB LPDDR4 @4266MHz

最初，不进行任何优化，程序运行时长 20.4943s。

一眼就看到有两个可以合起来的循环，就嗯合并。

优化后程序运行时长 20.2776s，几乎什么都没有发生。

用 gprof 分析后发现 Distance 函数居然占了高达 42.7% 的运行时间。观察发现这个函数内容极度简单，疯狂调用函数开销很大，可以用 inline 优化一下。

优化后程序运行时长 6.87372s，相对于原代码，速度提升了 2.982 倍，效果拔群！

在划分点集的循环中 assignment 数组被不断的引用，但它只需要得到比较的最终值，可以用一个中间变量去当比较的替死鬼以减少内存的引用。

优化后程序运行时长 2.40719s，相对于原代码，速度提升了 8.514 倍，效果非常 nice。

划分点集的大循环计算量非常庞大，考虑用多线程优化它。

优化后程序运行时长 1.4886s，相对于原代码，速度提升了 13.732 倍，已经非常接近题面的 15.6 倍了！

如果我对后面两个维护点集的循环也套用多线程，程序运行时间反而会劣化到 25.2207s，这是为什么？

猜想：这两个循环耗时本来就不长，套上多线程产生线程的时间都比正常运行时间长。

经高人指点后，使用 AMDuProf 分析发现 gomp_barrier_wait_end 占比 68.28% ，同步的时间比计算还长。

于是尝试添加 dynamic 调度子句，结果程序运行时间劣化到 4.24155s，这次是 gomp_iter_dynamic_next 占了 57.17%，任务动态申请的开销太大。

多次修改 chunk，程序运行时间始终无法突破 1.7s，甚至还不如不用 dynamic 调度。遂放弃。

原代码对于收敛的判断是利用的 vector 的比较，然而 vector 比较是 O(n) 的，可以用一个记录是否修改过的标志变量代替。

这里还有个优化，就是我在后面的循环有个引用用的并不恰当，属于是负优化，我把它去掉了。

优化后程序运行时长 1.18603s，相对于原代码，速度提升了 17.280 倍。

m_centers[cluster_1].y += m_points[i].y; 这个语句不断的交叉引用 m_centers 和 m_points，可以先连续引用了 m_points[i]，把值存下来，之后之间用局部变量，提高了代码的空间局部性。这一步非常有效，将代码运行时间优化到了 1.1s。

这个循环里都是结构体，我不知道怎么用或者是能不能用 SIMD 优化。于是我用了循环展开，经测试展开 4 次的结果比较一颗赛艇。

优化后程序运行时长 0.921956s，相对于原代码，速度提升了 22.229 倍。

我宣布个事，我是个星际玩家。

p_cnt 数组下标是与 m_numCenters 相关的，原代码的 m_numPoints 甚至可以说是一个错误。

优化后程序运行时长 0.784543s，相对于原代码，速度提升了 26.123 倍。

• CS:APP Chapter 5 & 6

• Guide into OpenMP: Easy multithreading programming for C++