魔改系列-8快速比较两个dwg全部图元差异

你有种再说一遍

上一篇我们用OpenGL实现了半个cad,大家肯定没想到原来协同办公这么复杂,其中还有巨量细节,例如鼠标同步/网络通讯/共享内存/RPC/消息队列/幂等,还得为了可能的出错调试实现链路追踪...那么复杂敲个屁啊...
没错,你可以不敲,但是你阻碍不了技术发展.
今天我们就实现一个能实现的吧.


JPEG/DWG文件数据储存通常涉及了数据压缩,通用算法是采取霍夫曼编码以及稀疏数组.为了不破坏它们,我们采取分布式dwg方案.当一个单线程数据库dwg无法完成,我们就新建多一个dwg数据库去操作,实际上就是把dwg当成一个黑盒不去处理它.
项目里面每个子dwg都是一个总dwg一小部分,联动修改就通过内部消息和外部网络控制,而不是进行局域网文件夹共享,而你的文件夹只是存有每个角色的一份副本,每次修改副本就自动新建版本号,然后发送给对方角色(实时发送/需要才发送),实现权限隔离.
没错这就git仓库,但是git仓库对于建筑类设计师来说是提高学习成本的,所以我们肯定要避免这个问题,如何不让建筑类设计师接触git,然后又让他们能在软件过程中自动触发备份和提升效率呢?
用过git的都知道,git最麻烦的地方是版本造成冲突,冲突的比较有版本自动迭代和人工介入,我们这里只用关心用户如何处理冲突部分,也正是本次主题:dwg无明文对比.


比较两个dwg全部图元差异的方法是什么?
而且要快速的,允许浮点数容差,这个问题其实是两个问题:
1,对比两个dwg.
2,对比两个图元集合,允许他们相对坐标.
第二种情况仅仅需要平移坐标(或许角度也需要呢),然后产生浮点数误差,很明显他们效率是不一样的,在九成都相同的数据里面判断不同和九成不同里面判断会造成大量分支预测失败,只是我们很喜欢通过并归方式来简化代码实现.


很多人抢着先回答:四叉树,四叉树!!
四叉树比较时间:四叉树构造时间+m*log4(n)
首先我们需要需要一个多线程四叉树,因为分裂节点时需要锁定父节点,而父节点此时可能被其他线程读取,因此需要引入读写锁来进行.还好它没有旋转节点,不然更难实现.
四叉树的分裂是不会引发上层分裂的,这和B+树不一样,因此我们在SMO阶段不会引起Latch蔓延到根节点.


重合的图元需要移除出四叉树,剩余的就是差异了,我们可以不移除,因为有四叉树缩容成本,只是标记它重复.
最后来一次并行搜索:
https://learn.microsoft.com/zh-c ... with-parallel-tasks
(我让AI产生多线程二叉树,它给出了CAS操作,但是没有读写锁,说明还是脑子转得更快才行...)
但是多线程成本是存在的...


第二波人抢着回答:SIMD,SIMD!!
那么怎么使用SIMD呢?
首先,有序的部分是什么?如果是两个相同的dwg,那么它们天然具备句柄序,所以比较速度更快.需要单独写这个部分.
但是没有这个句柄序,就需要两个dwg图元数组经过包围盒排序了.如果多了一个图元,表示存在错位,那么从错位开始一路都是比较失败的.
这个问题很像diff算法,对比两个txt差异并列出行号.
因为有序性,我们只需要找到差异行,再++跳过它.
图形上面通过包围盒来进行判断,把包围盒矩形构造数组实现SOA结构,两两比较,大量是相同的,少数不同,是不是就可以SIMD加速定位到差异部分.
对了SIMD是支持三角函数的.
{天宫大模型2.0问:
使用SIMD比较两个float数组,并且超出容差0.01的地方停止.给我c#例子.
但是它没有提供SIMD的,因为Math.Abs不支持SIMD,所以你得使用点积来完成这个任务.}


在量少的情况下(10w图元),排序时间成本在单线程下比多线程还快...所以,SIMD效率更高,它只需要快排+构造SOA+搜索,对比两个dwg不光是图元重合,还有颜色,线型,图层等等,所以这个SOA更重要.
所以这需要大量测试才能进行渐进式机制,自适应数据量采取不同的决策.嘿嘿.
不过,四叉树方案不光可以用在这个单一功能,还可以用在其他功能上面,这个设计是优秀的,聪明的程序员大部分时间都是运用再如何构建索引和命中索引上面,因为选择总是多次的.我们并不在乎为了一个功能而从头制造SOA,而在乎多次少量代码复用索引命中.加之这种方法是可以和"选择相似"复用的.




我们又再次回到分布式上面...
你每画一个图元,组块,更改图层,这些命令都可以异步去构造索引,不需要同步等待它map扩容/分支节点分裂,这些SMO时间的.
有没有想过合并图层其实是异步的,然后当你触发下一次图层设定的时才需要"立马"完成上一次的合并图层任务.
这样的好处是用户可以立马交互,减少用户等待时间(获取鼠标键盘等操作).用户交互期间已经进行了"些许"任务,最后某个时刻把队列任务全部完成.
但是这样会造成回滚问题,不过还记得吗?我们只是分布式"显示图元参照",完全不需要回滚(当然也有其他批量操作不需要回滚的)


要如何实现派发任务呢?例如合并图层这个任务怎么派发到全部机子的图纸上面?
既然是派发任务,那就是一个生产消费模式.
这个模式上面,利用消息队列解耦是非常常用的手段,为什么存在git push/git pull呢?因为拉模式和推模式是解耦的.
而消息队列这里就不需要发送dwg了,只需要利用图元数据来发送修改信息,以及序列化队列作为恢复依据.


我们都知道,同步不解耦,异步解耦.
线程间通讯除了共享内存之外,还可以进行利用消息队列解耦.很多时候看上去是同步的任务其实是异步的,异步速度更快.跨网络其实也是可以同步的,例如RPC协议.


多线程任务上面,你可能了解过lock和读写锁,可能了解过concurrent开头的函数,甚至了解过CAS指令(比较并替换),但是无锁环形队列Disruptor估计你就没有了解过了.
因为很多消息队列都存在缓存行失效问题,这类问题叫伪共享.
伪共享问题的表现是:并发的修改在一个缓存行中的多个独立变量,看起来是并发执行的,但实际在CPU 处理的时候是串行执行的,并发的性能大打折扣.
在SMP(对称多处理器)系统中,每个处理器都有各自的本地cache.当不同处理器上的线程修改了位于同一个cache line上的数据时,就会发生伪共享.
这令cache line失效,强制内存更新来维护cache一致性.由于从代码中很难看出是否会出现伪共享,所以有人将其描述成无声的性能杀手.
说人话就是一旦某个线程修改了缓存行的某个成员,那么其他载入这行缓存的内核会被消息总线通知淘汰,再去主存获取.问题出现在共享同一行缓存,所以让他们隔开就好了,这就是填充剩余对齐的操作.
它里面有很多精彩的设计,例如交换类字段到局部变量避免竞态,读栅栏,单向递增+2次方容量位运算代替取余.填充64字节避免伪共享造成缓存行失效(128缓存就没办法了).
所以计算机有两大难题,一是命名,二是缓存失效.

tranque

就看懂了一句话
那么复杂敲个屁啊...

东升铮

在源头解决问题、画完用特定软件记录下文件内的数据、这是首次提交！
然后文件加密发出去、不用咱们这个特定的软件就打不开、这是指定Git!
甲方用了软件查看修改图纸、马上把日志记录下来、定期补充上传、这是代码审验！
啥？？甲方不给小钱钱？直接远程把锁死、这是移出项目。
开玩笑开玩笑、大惊好样的

你有种再说一遍

东升铮 发表于 2024-4-17 07:52
在源头解决问题、画完用特定软件记录下文件内的数据、这是首次提交！
然后文件加密发出去、不用咱们这个特 ...

好主意,下载后开启倒计时,不付款就销毁

yimiyangguang55

比较图源， CAD有协助比较功能，我是小白菜，大哥勿拍我

lijunfa12345

不懂。。。。。。。

你有种再说一遍

lijunfa12345 发表于 2024-9-26 10:50
不懂。。。。。。。

比较两个数组,那么就是arr[j]和brr[j]比较,这样就是最快的,而j成立的条件就是有序