MapReduce并行化处理

你有种再说一遍

如何在10万个图元中获取全部首尾相连?
如何在10亿个点找到邻近的点?
获取100G txt内重复度前十的名字.
单机获取十亿行(约13G)天文台数据的最低温度,最高温度,平均温度.

这都是一些大数据编程问题,要保证短时间内获取,并且还必须要全部遍历一次,而解决起来就需要各种优化技术了.

首先我们要确定硬件的能力,
衡量CPU处理能力我们会使用每秒浮点运算次数FLOP/S(Floating Point Operations Per Secon),
1 TOP/S==1万亿FLOP/S.
因此,现在的CPU是非常快的,如果你的程序没有写到这个极限,那么说明还有优化空间.
在cad上面,我们不需要极度优化,我们要工作流级的优化就好了,但是降低到2秒内是必要的.

我们仍然需要知道要优化什么方向.
例如时间复杂度的计算是非常重要的,数数代码里面有几个for,每个for的复杂度是多少,这是基础技能.
因为第一次山人这么数给我,我就惊了,居然时间也是能数出来的,甚至都不需要测试就知道规模了,然后你就会发现代码越长反而运行越快.

10w图元链选:10%碰撞率
http://bbs.mjtd.com/thread-190866-1-1.html
链接里面展示了一个四叉树DFS算法.
会发现一次链选是2ms(自带的ssget60ms).
那么10w都链选一次,岂不是200秒!!
那100w个呢?时间上面太可怕了吧!!
而且我发现大家还是太迷信了,觉得四叉树能够完成这个任务,有的觉得数据库就快,殊不知数据库就是八叉树...
不要迷信数据结构好吗?

简单的处理:
剔除状态机:把foreach改为for.
减少栈帧:属性改字段/使用内联特性.
拒绝递归:四(八)叉树速度并没有特别快,不要迷恋它们了!!
一条线两个端点,都链选一次,那么时间复杂度为2n*log4(n),并且每次进入多叉树节点是递归进去的,会频繁开辟栈帧.
cad自带的ssget更甚,会进入屏幕缓冲区再进入八叉树更慢了,所以lisp遇到此问题举步维艰...

根据选择的时间复杂度分析,发现它其实不慢,只是遇到这个数量级问题上面还是太高了,会随着规模变大而亚线性增长,是线性对数时间复杂度,
如果能变成线性或者常数时间复杂度就更好了,
因此第一个优化方向需要降低这个2n*log4(n).
完成后的时间复杂度:
平均:O((n*log(n) +m) / parallel),
(快排+线性搜索)/并行.
最坏:O(n^2+n)
聪明的小子们看到这个快排就大概能明白个七七八八了,接下来听我娓娓道来.

首先明确一些优化方向:
1,链条必然出现在碰撞的地方,因此求碰撞是很快的,是粗过滤,不然还加速个毛线啊.
2,两点交错是细比较,是慢速,而且比较时候要容差判断.因为碰撞区内部也是有序的,所以两点交错比较其实可以前后向中间夹逼进行,因为CPU有分支流水线技术,所以这居然是加速的...这甚至不需要用到SIMD...
3,为什么用有序数组代替四叉树?因为不需要递归入栈,且少产生cache miss.
4,有序数组可以线性搜索.这意思就是构造有序数组(索引)无论如何都要遍历一次,然后加上线性搜索的1.x次,总体也就是2.x次,收益巨大.
5,并行化

具体步骤,SAP算法:
0x01,读取图元包围盒转为矩形.
矩形是4个值:左右上下,不是4个点,不是左下宽高.
*重点在于搜索速度,而不是构造速度.高频读取时候需要考虑内存瓶颈.
*矩形的数值类型通过计算db范围再自适应double,float,定点数,或者把超出范围的全部映射到定点数区域.
*其实也不用那么变态,double就算了,毕竟要极限一点还得改成SOA结构.
普通AOS就好了:调用时候List<CadEntity>
class CadEntity:Rect { //包围盒
  ObjectId Id;//当前图元
  List<ObjectId> Link;//碰撞链
}
SOA结构:(排序时注意联动移动,代码非常多)
class CadEntity {
  public List<double> Left
  public List<double> Right;
  public List<double> Top;
  public List<double> Bottom;
  public List<ObjectId> Id;//当前图元
  public List<List<ObjectId>> Link;//碰撞链
}

0x02,进行包围盒xyz排序(快排nlogn),成为只读数组.

0x03,因为已经排序,碰撞总是前面碰撞后面的,存在一个顺序窗口搜索区,此时就是线性速度求邻近碰撞.
线性有很多好处,大大贴合CPU预读数据的能力,到这步为止c#单线程74ms/c++估计能进入60ms.

3.1,粗过滤
线性碰撞就是从左下角的第一个基准图元盒A开始和它x区间的每一个图元进行矩形碰撞.实现每个图元都比较过碰撞.
x区间怎么获取?都排序了啊,A+1,A+2...图元就是了啊,超出基盒A右边范围就直接break啊.

矩形碰撞比较:
基盒A和盒N的x左比较,
如果在基盒A的x左右区间,再判断y上下区间,也在之间则为碰撞:
基盒A新建碰撞链加入盒N,盒N的链指向此链.链指针加到全局链集合,用于后续流程.

如果盒N上下穿过基盒A(此时为碰撞),
但是盒N已经被前面基盒A-视为碰撞(链指针不是null),
将基盒A和其碰撞链全部成员加入对方碰撞链,并且指针指向对方碰撞链.(选择数量少的那方并归就好了)
因此会成为无序链堆,而不是有序链条.

3.2,细比较
两点交错比较示意:要容差
LineA.P1==LineB.P1 || LineA.P1==LineB.P2 ||
LineA.P2==LineB.P1 || LineA.P2==LineB.P2
并行每个链堆进行两点交错比较,生成多段线数据.
32A:如果碰撞了直接求两点交错,此时读取图元信息是首次访问,将产生cache miss,不过却减少了储存无用碰撞区.
32B:如果记录碰撞区后再并行,因为储存数据是存入主存而不是CPU缓存,也存在线程内cache miss.
需要测试上述,A写不如算,B更符合流程.

0x04,你会发现0x01,0x02这两步是没有并行的,并且包围盒数组也不需要全局排序,因为排序是非常慢的,快排也是O(n*log(n)),对于大规模也崩坏.
最终时间=构造索引(有序数组)+选择数据.
选择数据:10w图元碰撞是74ms+两点成链时间,但是我想做到10-20ms.

4.1,因此构造有序数组(索引)前,在外面套一层并发空间哈希网格,从源头上实现任务的划分,尽可能并行+并行+并行...
但是存在大图元跨越分区,要化解这个问题.
41A:包围盒上下左右都在,才属于这个网格.
41B:出现跨网格大包围盒,
每个子网格都要有一个跨网格容器(实际上是全局的map),
获取大包围盒左下角子网格的跨网格容器,
判断容器矩形范围:
相同就加入图元.
不同就通过大包围盒矩形新建大网格,大网格加入图元,并加入跨网格容器.
41C:简单的来说,大网格图元就是和全部子网格图元碰撞,而细比较时候,无可避免要遍历子网格全部图元,但是并行子网格排序的时间收益更高.
大网格利用已经排好序的子网格只读数组,进行线性求细比较.

*错误几点:
*把大包围盒id都加入面积区全部子网格?类似栅格化,可以减少子网格内容碰撞,但是网格细分出现多个网格重复添加id,储存到集合总是特别慢的.
*如果将排序后的包围盒数组/CPU核心数,对于每域并行化求碰撞,不过这种切割方式不合理,存在跨域碰撞,难以找到最后一组x的邻近碰撞.还是得是成碰撞区后并行碰撞区.

[扩展问题]
上面0x04 4.1可能大家没做之前难以感受,通过此例子也可以感受感受.
我们把上面的包围盒集想像成一个点集先,这样我们就扩展到了十亿点集求最近距离问题了.
var sortedPoints = points
.OrderBy(p => p.X).ThenBy(p => p.Y).ThenBy(p => p.Z);
排序之后的点集,同x就是一组(纵向),最近点必然出现在同组(上下)或者邻近组(左右),如果有Z还有前后.
排序前,需要一定的容差.可以向下取整(推荐),可以制作有序数组,二分法求邻近组值,接近则加入其组.

一次性十亿个点排序?你要疯了哦.
必须要先用空间哈希网格去切割点集.
如果那么刚好切割到某个邻近点到下一个分区,此时就尴尬了,边缘还得去邻近一圈网格搜索,
四周一圈邻近网格如果是空的,还得去下一圈网格,
这个就是读扩散问题.
但是,读扩散非常少,而排序总是极慢,那么多线程并行排序多个网格就显得更快.
网格越多,并行化越高,缓存命中越高,读扩散风险越高.

所以通篇下来,你会发现就是MapReduce思想:
先分区,并行分区的任务,最后合并.
(完)

i小小白i

虽然没看懂，但觉得很牛逼，很有用！

czb203

感谢大佬分享的精华

tigcat

谢谢惊惊大佬分享，虽然看不懂。